Pagini recente » Cod sursa (job #2270176) | Cod sursa (job #1486772) | Cod sursa (job #2466743) | Cod sursa (job #2854691) | Cod sursa (job #270556)
Cod sursa(job #270556)
#include<stdio.h>
#define nmax 100010
long h[nmax], ln[nmax], vz[nmax], n, x, l, nh;
FILE *f, *g;
void ins(long dist, long lana)
{ long k, z;
h[++nh]=dist; ln[nh]=lana;
k=nh;
while(h[k/2]>h[k] && k>1)
{ z=h[k]; h[k]=h[k/2]; h[k/2]=z;
z=ln[k]; ln[k]=ln[k/2]; ln[k/2]=z;
k=k/2;
}
}
void del(long k)
{ long z, m;
z=h[k]; h[k]=h[nh]; h[nh]=z;
z=ln[k]; ln[k]=ln[nh]; ln[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;
z=ln[m]; ln[m]=ln[k]; ln[k]=z;
k=m;
}
}
int main()
{ long i, j, dist, lana, max, pmax, lg, nr;
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", &dist, &lana);
ins(dist, lana);
}
while(nh)
del(1);
i=1; lg=l; nr=0;
while(i<=n)
{ max=-1; pmax=-1;
if(h[i]+lg-l<=x)
if(h[i]+lg>x)
while(h[i]+lg-l<=x && h[i]+lg>x && i<=n)
{ if(ln[i]>max && vz[i]==0)
{ if(pmax!=-1)
vz[pmax]=0;
max=ln[i];
pmax=i;
vz[pmax]=1;
}
i++;
}
else
{ max=-1; pmax=-1;
for(j=i; j<=n; j++)
if(ln[j]>max && vz[j]==0)
{ if(pmax!=-1)
vz[pmax]=0;
max=ln[j];
pmax=j;
vz[pmax]=1;
}
}
if(max!=-1)
{ nr+=max;
lg+=l;
}
else
i++;
}
fprintf(g, "%ld\n", nr);
fclose(g);
return 0;
}