Cod sursa(job #1123184)

Utilizator gabrielvGabriel Vanca gabrielv Data 25 februarie 2014 23:14:42
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 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 start, int finish, int val)
{
    if(start == finish)
        return start-1;

    int mid = (start + finish) / 2;
    if(I[mid].first > val)
        return Suche(start, mid, val);
    return Suche(mid + 1, finish, val);
}

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;
}