Pagini recente » Cod sursa (job #1337669) | Cod sursa (job #792933) | Cod sursa (job #425061) | Cod sursa (job #240766) | Cod sursa (job #274192)
Cod sursa(job #274192)
#include<stdio.h>
#define nmax 100010
struct timp
{
long long t,ti;}a[nmax],c[nmax];
long long h[nmax], d[nmax], ln[nmax], n, x, l, nh, tmax, nr, nt;
FILE *f, *g;
void ins(long long lana)
{ long long k, z;
h[++nh]=lana;
k=nh;
while(h[k/2]<h[k] && k>1)
{ z=h[k]; h[k]=h[k/2]; h[k/2]=z;
k=k/2;
}
}
void del(long long k)
{ long long z, m;
z=h[k]; h[k]=h[nh]; h[nh]=z;
nh--;
while(( (h[2*k]>h[k] && 2*k<=nh) ||
(h[2*k+1]>h[k] && 2*k+1<=nh) ) && k<nh)
{ if(2*k==nh) m=2*k;
else if(h[2*k]>h[2*k+1]) m=2*k;
else m=2*k+1;
z=h[m]; h[m]=h[k]; h[k]=z;
k=m;
}
}
void intercls(long long p,long long mj,long long u)
{
long long i=p,j=mj+1,k=0;
while(i<=mj && j<=u)
if(a[i].t>a[j].t)c[++k]=a[i++];
else c[++k]=a[j++];
while(i<=mj)c[++k]=a[i++];
while(j<=u)c[++k]=a[j++];
for(i=1;i<=k;i++)a[i+p-1]=c[i];
}
void sort (long long p,long long u)
{
if(p<u)
{
long long mj=(p+u)/2;
sort(p,mj);
sort(mj+1,u);
intercls(p,mj,u);
}
}
int main()
{ long long i, j;
f=fopen("lupu.in", "r");
g=fopen("lupu.out", "w");
fscanf(f, "%ll%ll%ll", &n, &x, &l);
for(i=1; i<=n; i++)
{ fscanf(f, "%ll%ll", &d[i], &ln[i]);
if(l!=0)
{a[i].t=(x-d[i])/l+1;a[i].ti=i;
if((x-d[i])/l+1>tmax)
tmax=(x-d[i])/l+1;
}
else
if(d[i]<=x)
{a[i].t=1;a[i].ti=i;tmax=1;}
}
sort(1,n);
i=1;
for(j=tmax; j>=1; j--)
{ while(a[i].t==j && i<=n)
{ ins(ln[a[i].ti]);
i++;
}
if(nh>0)
{ nr+=h[1];
del(1);
}
}
fprintf(g, "%ld\n", nr);
fclose(g);
return 0;
}