Pagini recente » Cod sursa (job #2948806) | Cod sursa (job #837148) | Cod sursa (job #3138446) | Cod sursa (job #1094602) | Cod sursa (job #521382)
Cod sursa(job #521382)
#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 max=0,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)
{
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;
}
c[i]=v[i].b-v[i].a+c[last];
if(c[i]>max)
max=c[i];
}
printf("%ld\n",max);
return 0;
}