Cod sursa(job #247392)

Utilizator ConsstantinTabacu Raul Consstantin Data 22 ianuarie 2009 23:17:03
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
struct concert{unsigned long long int a,b;}v[100000];
unsigned long long int i,max,j,k,l,m,n,best[100000];
int caut(int val)
{int p=0,u=i-1;
int mij;
while(p!=u)
                {mij=(p+u)>>1;
        if(v[mij].b>=val)
                u=mij;
        else
                {p=mij+1;
                if(v[mij].b<val&&v[mij+1].b>val)
                        return mij;}

       }
 return p;}

int cmp(concert a,concert b)
        {return a.b<b.b;}
int main(){
FILE *f=fopen("heavymetal.in","r");
fscanf(f,"%lld",&n);
for(i=1;i<=n;i++)
        fscanf(f,"%lld %lld",&v[i].a,&v[i].b);
fclose(f);

best[0]--;
sort(v,v+n+1,cmp);
best[1]=v[1].b-v[1].a;
for(i=2;i<=n;i++)
        {best[i]=best[i-1];
        j=caut(v[i].a);
        if(best[i]<(best[j]+v[i].b-v[i].a))
                best[i]=best[j]+v[i].b-v[i].a;
        }
FILE *g=fopen("heavymetal.out","w");
fprintf(g,"%lld",best[n]);
fclose(g);
return 0;}