Cod sursa(job #873991)

Utilizator cahemanCasian Patrascanu caheman Data 7 februarie 2013 20:12:45
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#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;}