Pagini recente » Cod sursa (job #3238359) | Cod sursa (job #1452083) | Cod sursa (job #1908720) | Cod sursa (job #1099602) | Cod sursa (job #873991)
Cod sursa(job #873991)
#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;}