Cod sursa(job #669006)

Utilizator tzipleatudTudor Tiplea tzipleatud Data 25 ianuarie 2012 22:36:04
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <fstream>
#include <algorithm>
#define NMAX 100001
using namespace std;

ifstream f("heavymetal.in");
ofstream g("heavymetal.out");

long long n,i,p=0;
struct inter {long long s,f;};
bool comp(inter a,inter b) {return a.f<b.f;}
inter a[NMAX];
long long ANS[NMAX];
long long caut(long long v) {
    long long p=1,u=n,m,s=0;
    while (p<=u) {
        m=p+(u-p)/2;
        if (a[m].f<=v) p=m+1,s=ANS[m];
            else u=m-1;
    }
    return s;
}
int main () {
    f >> n;
    for (i=1;i<=n;i++) f >> a[i].s >> a[i].f;
    sort(a+1,a+n+1,comp);
    ANS[1]=a[1].f-a[1].s;
    for (i=2;i<=n;i++)
        ANS[i]=max(ANS[i-1],caut(a[i].s)+a[i].f-a[i].s);
    g << ANS[n] << '\n';
    f.close();g.close();
    return 0;
}