Cod sursa(job #1093726)

Utilizator ShaDoWsiD100Rzv Rzv ShaDoWsiD100 Data 28 ianuarie 2014 15:27:01
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include<fstream>
#include<algorithm>
using namespace std;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
int n,i,j,Max=-1,timp[100001],p,u,mij;
struct str{
    int inc,sf;
}v[100001];
int cmp(str x,str y){
    return x.sf<y.sf;
}
int main(){
    f>>n;
    for(i=1;i<=n;i++)
        f>>v[i].inc>>v[i].sf;
    sort(v+1,v+n+1,cmp);
    timp[1]=v[1].sf-v[1].inc;
    Max=timp[1];
    for(i=2;i<=n;i++)
    {
        p=1;
        u=i;
        timp[i]=max(timp[i-1],v[i].sf-v[i].inc);
        while(p<=u)
        {
            mij=(p+u)/2;
            if(v[i].inc>=v[mij].sf){
                timp[i]=max(timp[i],v[i].sf-v[i].inc+timp[mij]);
                p=mij+1;
            }
            else
                u=mij-1;
        }
        if(Max<timp[i])
            Max=timp[i];
    }
    g<<Max;
    return 0;
}