Pagini recente » Cod sursa (job #970939) | Cod sursa (job #572235) | Cod sursa (job #2914741) | Cod sursa (job #2294815) | Cod sursa (job #602053)
Cod sursa(job #602053)
#include<stdio.h>
#include<stdlib.h>
struct oi { int d, a,t; };
oi oaie[100010];
struct TIP {int c1,c2; };
TIP aux[100010];
bool f[100010];
int comp (const void *x, const void *y)
{
oi *pa,*pb;
pa=(oi *)x;
pb=(oi *)y;
if(pa->a==pb->a) return 0;
if(pa->a>pb->a) return -1;
return 1;
}
int comp2 (const void *x, const void *y)
{
TIP *pa,*pb;
pa=(TIP *)x;
pb=(TIP *)y;
if(pa->c2==pb->c2) return 0;
if(pa->c2>pb->c2) return -1;
return 1;
}
int bs ( int val, int n)
{
int st,dr,med;
st=1; dr=n;
while(st<dr)
{
med=(st+dr)/2;
if(aux[med].c2==val) return med;
if(aux[med].c2>val) dr=med-1;
if(aux[med].c2<val) st=med+1;
}
return -1;
}
int main()
{
freopen("lupu.in","r",stdin);
freopen("lupu.out","w",stdout);
int i,rez,j,n,k,x,l;
scanf("%d%d%d",&n,&x,&l);
for(i=1;i<=n;i++)
{
scanf("%d%d",&oaie[i].d,&oaie[i].a);
oaie[i].t=(x-oaie[i].d)/2;
}
qsort(oaie+1,n,sizeof(oaie[0]),comp);
for(i=1;i<=n;i++)
{
aux[i].c1=i;
aux[i].c2=oaie[i].t;
}
qsort(aux+1,n,sizeof(aux[0]),comp2);
rez=0;
for(i=1;i<=n;i++)
{
if(f[oaie[i].t]==0)
{
rez=rez+oaie[i].a;
f[oaie[i].t]=1;
}
else
{
k=bs(oaie[i].t,n);
if(k==-1) continue;
for(j=k;j>=1;j--)
if(f[oaie[aux[j].c1].t]==0)
{
rez=rez+oaie[aux[j].c1].a;
f[oaie[aux[j].c1].t]=1;
}
}
}
printf("%d\n",rez);
return 0;
}