Pagini recente » Cod sursa (job #3583) | Cod sursa (job #817484) | Cod sursa (job #1164939) | Cod sursa (job #754303) | Cod sursa (job #748567)
Cod sursa(job #748567)
#include<stdio.h>
#include<algorithm>
using namespace std;
inline long max(long d,long b)
{
if(b>=d)
return b;
return d;
}
struct pozdy
{
long x,y;
};
pozdy a[100011];
long c[100011];
long cb(long dr,long curent)
{
long l=0,st,med;
st=1;
while(st<=dr)
{
med=(st+dr)>>1;
if(c[med].y<=curent)
{
l=med;
st=med+1;
}
else
dr=med-1;
}
return l;
}
int comp(pozdy d,pozdy e)
{
if(d.y>e.y)
return 0;
return 1;
}
int main()
{
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
long n,i;
scanf("%ld",&n);
for(i=1;i<=n;i++)
scanf("%ld%ld",&a[i].x,&a[i].y);
sort(a+1,a+n+1,comp);
c[1]=a[1].y-a[1].x;
for(i=2;i<=n;i++)
c[i]=max(c[i-1],a[i].y-a[i].x+c[cb(i-1,a[i].x)]);
printf("%ld\n",c[n]);
return 0;
}