Pagini recente » Cod sursa (job #214837) | Cod sursa (job #65894) | Cod sursa (job #294007) | Cod sursa (job #1941166) | Cod sursa (job #873994)
Cod sursa(job #873994)
#include<stdio.h>
#include<algorithm>
using namespace std;
inline long max(long c,long b)
{ if(b>=c)
return b;
return c;}
struct casy{long x,y;};
casy a[100011];
long cost[100011];
long cb(long dr,long c)
{
long last=0,st,m; st=1;
while(st<=dr)
{m=(st+dr)>>1;
if(a[m].y<=c)
{ last=m; st=m+1;
}
else dr=m-1;
}
return last;
}
int comp(const void *c,const void *b)
{
casy *pc,*pb; pc=(casy*)c; pb=(casy*)b;
if(pc->y>pb->y)
return 1;
if(pc->y==pb->y)
return 0;
return -1;
}
bool comp2(casy a,casy b)
{
return a.y<b.y;
}
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); //qsort(a+1,n,sizeof(a[0]),comp); sort(a+1,a+n+1,comp2); cost[1]=a[1].y-a[1].x; for(i=2;i<=n;i++) cost[i]=max(cost[i-1],a[i].y-a[i].x+cost[cb(i-1,a[i].x)]); printf("%ld\n",cost[n]); return 0;
}