Pagini recente » Cod sursa (job #1748726) | Cod sursa (job #1278913) | Cod sursa (job #2626947) | Cod sursa (job #2575706) | Cod sursa (job #602142)
Cod sursa(job #602142)
#include<stdio.h>
#include<stdlib.h>
struct TIP { long d,a;};
TIP oi[100010];
long num,h[100010];
int comp ( const void *a, const void *b)
{
TIP *pa,*pb ;
pa=(TIP *)a;
pb=(TIP *)b;
if(pa->d==pb->d)
return 0;
if(pa->d>pb->d)
return 1;
return -1;
}
void down ( long k )
{
long fiu=0,aux;
do
{
fiu=0;
if(2*k<=num)
fiu=2*k;
if(2*k+1<=num && h[2*k+1]>h[fiu])
fiu=2*k+1;
if(h[fiu]>h[k])
{
aux=h[k];
h[k]=h[fiu];
h[fiu]=aux;
k=fiu;
}
else
fiu=0;
}while(fiu);
}
void up (long k)
{
long aux;
while(k>1 && h[k]>h[k/2])
{
aux=h[k];
h[k]=h[k/2];
h[k/2]=aux;
k=k/2;
}
}
int main()
{
freopen("lupu.in","r",stdin);
freopen("lupu.out","w",stdout);
long i,max,lana,n,lim,x,l;
scanf("%ld%ld%ld",&n,&x,&l);
max=0;
for(i=1;i<=n;i++)
{
scanf("%ld%ld",&oi[i].d,&oi[i].a);
if(oi[i].d==0 && oi[i].a>max) max=oi[i].a;
}
qsort(oi+1,n,sizeof(oi[0]),comp);
num=i=lana=0;
lim=0;
lana=max;
do
{
i=i+1;
while(i<=n && oi[i].d<=lim+l)
{
h[++num]=oi[i].a;
up(num);
++i;
}
lana=lana+h[1];
h[1]=h[num];
num--;
down(1);
lim=lim+l;
}while(lim<=x && i<n);
printf("%ld\n",lana);
return 0;
}