Cod sursa(job #2551202)

Utilizator alexilasiAlex Ilasi alexilasi Data 19 februarie 2020 17:36:08
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.54 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin ("heavymetal.in");
ofstream fout ("heavymetal.out");

const int nMax = 100001;

vector <int> v[nMax], dp(nMax);

int main()
{
    int n, t=0; fin >> n;
    for(int i=0; i<=n; i++)
    {
        int x, y; fin >> x >> y;
        v[y].push_back(x);
        t = max(t, y);
    }
    for(int i=1; i<=t; i++)
    {
        dp[i] = dp[i-1];
        for(auto it : v[i])
            dp[i] = max(dp[i], dp[it] + i - it);
    }
    fout << dp[t] << '\n';
    return 0;
}