Pagini recente » Cod sursa (job #1509175) | Cod sursa (job #2913768) | Cod sursa (job #1599488) | Cod sursa (job #1886963) | Cod sursa (job #274263)
Cod sursa(job #274263)
#include<stdio.h>
#define nmax 100010
struct timp
{
unsigned long t,ti;}a[nmax],c[nmax];
unsigned long h[nmax], d[nmax], ln[nmax], n, x, l, nh, tmax, nr, nt;
FILE *f, *g;
void ins(unsigned long lana)
{ unsigned 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(unsigned long k)
{ unsigned 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(unsigned long p,unsigned long mj,unsigned long u)
{
unsigned 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 (unsigned long p,unsigned long u)
{
if(p<u)
{
unsigned long mj=(p+u)/2;
sort(p,mj);
sort(mj+1,u);
intercls(p,mj,u);
}
}
int main()
{ unsigned long i, j,nt=0;;
f=fopen("lupu.in", "r");
g=fopen("lupu.out", "w");
fscanf(f, "%ld%ld%ld", &n, &x, &l);
for(i=1; i<=n; i++)
{ fscanf(f, "%ld%ld", &d[i], &ln[i]);
if(x>=d[i]){
a[++nt].t=(x-d[i])/l+1;a[nt].ti=i;
if((x-d[i])/l+1>tmax)
tmax=(x-d[i])/l+1;
}
}
n=nt;
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;
}