Cod sursa(job #2027403)

Utilizator workwork work work Data 26 septembrie 2017 01:42:34
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.58 kb
#include <bits/stdc++.h>

#define a first
#define b second

using namespace std;

ifstream F("heavymetal.in");
ofstream G("heavymetal.out");

int n, st, dr, mij, Tm, x, y;
long long dp[1<<18];
vector<int> w[1<<18];

int main()
{
    F >> n;
    for(int i = 1; i <= n; ++ i) {F >> x >> y, w[y].push_back(x); Tm=max(Tm, y);}
    vector<int>::iterator it;
    for(int i = 1; i <= Tm; ++ i)
    {
        dp[i]=dp[i-1];
        for(it=w[i].begin(); it!=w[i].end();++it)
            if(dp[i]<dp[*it]+i-(*it)) dp[i]=dp[*it]+i-(*it);
    }
    G<<dp[Tm];
    return 0;
}