Pagini recente » Cod sursa (job #1503943) | Cod sursa (job #2863598) | Cod sursa (job #1222324) | Cod sursa (job #1357798) | Cod sursa (job #602130)
Cod sursa(job #602130)
#include<stdio.h>
#include<stdlib.h>
struct TIP { int d,a;};
TIP oi[100010];
int 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 ( int k )
{
int 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 ( int k)
{
int 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);
int i,max,lana,n,lim,x,l;
scanf("%d%d%d",&n,&x,&l);
max=0;
for(i=1;i<=n;i++)
{
scanf("%d%d",&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("%d\n",lana);
return 0;
}