Pagini recente » Cod sursa (job #1940658) | Cod sursa (job #1994244) | Cod sursa (job #3190915) | Cod sursa (job #1347867) | Cod sursa (job #96630)
Cod sursa(job #96630)
#include<stdio.h>
#include<stdlib.h>
#define infinit -2000000000
#define lg 100005
int n, x, l, *dist[lg], oi, timp, gs[lg], r, ds, i, nr[lg];
long long raspuns;
struct citire{
int v, d;
};
citire v[lg];
struct heap{
int v, in;
};
heap hp[lg];
int gsnod(int i){
if (2*i < n){
if (hp[2*i].v <= hp[2*i+1].v)
return 2*i+1;
return 2*i;
}
return 2*i;
}
void arj(int i){
int nxt = gsnod(i), aux;
if (2*i <= n)
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[nxt].in] = nxt;
gs[hp[i].in] = i;
arj(nxt);
}
}
int main()
{
freopen("lupu.in", "rt", stdin);
freopen("lupu.out", "wt", stdout);
scanf("%d%d%d", &n, &x, &l);
// x - distanta maxima
// l - cu cat se mareste
for (i=1; i<=n; i++){
scanf("%d%d", &v[i].d, &v[i].v);
if (v[i].d <= x)
oi ++;
}
for (i=1; i<=n; i++)
if (v[i].d <= x){
hp[i].v = v[i].v;
hp[i].in = i;
ds = (x-v[i].d) / l + 1;
nr[ds] ++;
dist[ds] = (int *)realloc(dist[ds], (nr[ds]+1)*sizeof(int));
dist[ds][nr[ds]] = i;
}
for (i=oi/2; i; i--)
arj(i);
timp = 1;
while (oi){
raspuns += hp[1].v;
hp[1].v = infinit;
arj(1);
for (i=1; i<=nr[timp]; i++){
r = gs[dist[timp][i]];
hp[r].v = infinit;
arj(r);
}
oi -= nr[timp];
timp ++;
}
printf("%lld\n", raspuns);
return 0;
}