Cod sursa(job #247683)

Utilizator ConsstantinTabacu Raul Consstantin Data 23 ianuarie 2009 18:59:24
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 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;
int mij;
while(p+1<u)
        {mij=(p+u)>>1;
        if(v[mij].b>val)
                u=mij;
        else
        if(v[mij]< val)
                p=mij+1;
       else
       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(v[j].b<=v[i].a)
        for(j=1;j<=i;j++)
        if(v[i].a>=v[j].b)
        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;}