Cod sursa(job #1208228)

Utilizator mihaimusatMihai Musat mihaimusat Data 15 iulie 2014 10:24:30
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <fstream>
#include <algorithm>
#define NMax 1000005
#define r first
#define l second

using namespace std;

pair <int, int> I[NMax];
int N;
long long DP[NMax];

inline int BSearch (int X, int R)
{
    int L=0, P=0;
    while (L<=R)
    {
        int Mid=(L+R)/2;
        if (I[Mid].r<=X) P=Mid, L=Mid+1;
        else R=Mid-1;
    }
    return P;
}

void Solve ()
{
    sort (I+1, I+N+1);
    for (int i=1; i<=N; ++i)
    {
        int j=BSearch (I[i].l, i-1);
        DP[i]=max (DP[i-1], DP[j]+I[i].r-I[i].l);
    }
}

void Read ()
{
    ifstream f("heavymetal.in");
    f>>N;
    for (int i=1; i<=N; ++i)
    {
        f>>I[i].l>>I[i].r;
    }
}

void Print ()
{
   ofstream g("heavymetal.out");
    g<<DP[N];
}

int main ()
{
    Read ();
    Solve ();
    Print ();
    return 0;
}