Pagini recente » Rating Coroian David (Coroian_David) | Cod sursa (job #1410238)
#include <fstream>
#include <algorithm>
#define DIM 120000
#define f first
#define s second
#define LL long long
using namespace std;
ifstream fin ("lupu.in" );
ofstream fout("lupu.out");
LL N, M, i, j, K, ok, maxim, sum;
LL L, Heap[DIM], X, a, b, k, aux;
pair <LL, LL> V[DIM];
void SetUp(){
fin >> N >> L >> X;
for(i = 1; i <= N; i ++){
fin >> a >> b;
if(a <= L){
a = L - a;
a /= X;
if(maxim < a)
maxim = a;
}
else{
a = -a;
}
V[i].f = a;
V[i].s = b;
}
sort(V + 1, V + N + 1);
for(i = 1; i <= N / 2; i ++){
aux = V[i].f;
V[i].f = V[N-i+1].f;
V[N-i+1].f = aux;
aux = V[i].s;
V[i].s = V[N-i+1].s;
V[N-i+1].s = aux;
}
return;
}
void Swap(int a, int b){
LL aux;
aux = Heap[a];
Heap[a] = Heap[b];
Heap[b] = aux;
return;
}
void Shift(int c){
int p = c / 2;
while(p != 0){
if(Heap[p] < Heap[c]){
Swap(p, c);
c = p;
p /= 2;
}
else
break;
}
return;
}
void Percolate(int p){
int c = p * 2;
while(c <= M){
if(c + 1 <= M && Heap[c] < Heap[c+1])
c ++;
if(Heap[p] < Heap[c]){
Swap(p, c);
p = c;
c *= 2;
}
else
break;
}
return;
}
void HeapExpert(){
i = 1;
for(k = maxim; k >= 0; k --){
while(V[i].f == k){
M ++;
Heap[M] = V[i].s;
Shift(M);
i ++;
}
sum += Heap[1];
Heap[1] = Heap[M];
Heap[M--] = 0;
Percolate(1);
}
fout << sum;
return;
}
int main(){
SetUp();
HeapExpert();
return 0;
}