Cod sursa(job #759990)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 19 iunie 2012 22:24:24
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <cstdio>
#include <algorithm>

#define NMax 1000005
#define r first
#define l second
#define LL long long

using namespace std;

pair <int, int> I[NMax];
int N;
LL 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 ()
{
    freopen ("heavymetal.in", "r", stdin);
    scanf ("%d", &N);
    for (int i=1; i<=N; ++i)
    {
        scanf ("%d %d", &I[i].l, &I[i].r);
    }
}

void Print ()
{
    freopen ("heavymetal.out", "w", stdout);
    printf ("%lld\n", DP[N]);
}

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