Cod sursa(job #521383)
#include<stdio.h>
#include<stdlib.h>
struct bob
{long a,b;};
bob v[100010];
long c[100010];
int comp(const void *a,const void *b)
{
bob *x,*y;
x=(bob*)a;
y=(bob*)b;
if(x->b-y->b==0)
return 0;
if(x->b-y->b>0)
return 1;
return -1;
}
int main()
{
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
long n,i,st,dr,last,med;
scanf("%ld",&n);
for(i=1;i<=n;++i)
scanf("%ld%ld",&v[i].a,&v[i].b);
qsort(v+1,n,sizeof(v[0]),comp);
for(i=1;i<=n;++i)
{
c[i]=c[i-1];
last=0;
st=1;
dr=i-1;
while(st<=dr)
{
med=(st+dr)>>1;
if(v[med].b<=v[i].a)
{
last=med;
st=med+1;
}
else
dr=med-1;
}
if(v[i].b-v[i].a+c[last]>c[i])
c[i]=v[i].b-v[i].a+c[last];
}
printf("%ld\n",c[n]);
return 0;
}