Cod sursa(job #1123100)

Utilizator gabrielvGabriel Vanca gabrielv Data 25 februarie 2014 22:37:27
Problema Heavy metal Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

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

int N;
int Tmax;

vector < int > DP;

vector < pair < int , int > > I;

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.push_back(make_pair(y,x));
    }
}

void Losen()
{
    sort(I.begin(),I.end());

    Tmax = I[N-1].first;

    DP.resize(Tmax + 1);

    for(int i=1; i<=Tmax; i++)
    {
        DP[i] = DP[i-1];

        vector < pair < int , int > > :: iterator it = I.begin();

        for(;(*it).first  < i; ++it);
        for(;(*it).first == i; ++it)
            DP[i] = maxim(DP[i], DP[(*it).second] + (*it).first - (*it).second);

    }
}

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

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

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