Cod sursa(job #1123201)

Utilizator gabrielvGabriel Vanca gabrielv Data 25 februarie 2014 23:25:31
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <cstdio>
#include <algorithm>

using namespace std;

#define NMAX 100005
#define maxim(a,b) ((a>b)?(a):(b))

int N;
int DP[NMAX];

pair < int , int > I[NMAX];

void Scannen()
{
    freopen("heavymetal.in","r",stdin);

    scanf("%d",&N);

    for(int i=1,x,y;i<=N;i++)
    {
        scanf("%d%d",&x,&y);

        I[i].first = y;
        I[i].second = x;
    }
}

int Suche(int Links, int Recht, int Wert)
{

    while(Links<=Recht)
    {
        int Mitte = (Links+Recht)/2;

        if(I[Mitte].first > Wert)
            Recht = Mitte - 1;
        else
            Links = Mitte + 1;
    }

    return (Links+Recht)/2;
}

void Losen()
{
    sort(I+1,I+N+1);

    for(int i=1;i<=N;i++)
        DP[i] = maxim(DP[i - 1], DP[Suche(0,i,I[i].second)] + I[i].first - I[i].second);
}

void Druken()
{
    freopen("heavymetal.out", "w", stdout);

    printf("%d\n", DP[N]);
}

int main()
{
    Scannen();
    Losen();
    Druken();
    return 0;
}