Pagini recente » Cod sursa (job #2756263) | Cod sursa (job #1937272) | Cod sursa (job #2639721) | Cod sursa (job #1381908) | Cod sursa (job #95995)
Cod sursa(job #95995)
#include<stdio.h>
#include<stdlib.h>
#define infinit 2000000000
#define lg 10005
int n, ll, x, di, p, a, i, j, s, * d[lg], * ind[lg], max, l, nr[lg], gs[lg], viz[lg];
long long rezultat;
struct heap{
int v, in;
};
heap hp[100005];
int gsnod(int i){
if (2*i < n){
if (hp[2*i].v < hp[2*i+1].v)
return 2*i;
return 2*i+1;
}
return 2*i;
}
void arj(int i){
int nxt = gsnod(i), aux;
if (i <= n/2)
if (hp[i].v < hp[nxt].v){
aux = hp[i].v;
hp[i].v = hp[nxt].v;
hp[nxt].v = aux;
aux = hp[i].in;
hp[i].in = hp[nxt].in;
hp[nxt].in = aux;
gs[hp[i].in] = i;
gs[hp[nxt].in] = nxt;
arj(nxt);
}
}
int main()
{
freopen("lupu.in", "rt", stdin);
freopen("lupu.out", "wt", stdout);
scanf("%d%d%d", &n, &x, &ll);
// x - distanta maxima
for (i=1; i<=n; i++){
scanf("%d%d", &di, &a);
// di - distanta
l = (x-di) / ll +1;
if (l){
nr[l] ++;
d[l] = (int *)realloc(d[l], (nr[l]+1)*sizeof(int));
d[l][nr[l]] = a;
ind[l] = (int *)realloc(ind[l], (nr[l]+1)*sizeof(int));
ind[l][nr[l]] = i;
if (l > max)
max = l;
}
hp[i].v = a;
hp[i].in = i;
}
for (i=n/2; i; i--)
arj(i);
for (i=1; i<=max; i++){
if (nr[i]){
s = 0;
for (j=1; j<=nr[i]; j++){
if (d[i][j] > s && !viz[ind[i][j]])
s = d[i][j];
p = gs[ind[i][j]];
hp[p].v = infinit;
arj(p);
}
rezultat += s;
}
else{
rezultat += hp[1].v;
hp[1].v = infinit;
viz[hp[1].in] = 1;
arj(1);
}
}
printf("%lld\n", rezultat);
fclose(stdin);
fclose(stdout);
return 0;
}