Cod sursa(job #2059697)

Utilizator vladdy47Bucur Vlad Andrei vladdy47 Data 7 noiembrie 2017 14:19:13
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.62 kb
# include <bits/stdc++.h>

using namespace std;

const int Nmax = 1e5 + 5;

int n, i, x, y, Max;
int dp[Nmax];

vector <int> v[Nmax];

int main ()
{
    freopen("heavymetal.in", "r", stdin);
    freopen("heavymetal.out", "w", stdout);

    scanf("%d\n", &n);

    for (i = 1; i <= n; ++i) {
        scanf("%d %d\n", &x, &y);
        v[y].push_back(x);
        Max = max(Max, y);
    }

    dp[0] = 0;

    for (i = 1; i <= Max; ++i) {
        dp[i] = dp[i - 1];
        for (auto &it: v[i])
            dp[i] = max(dp[i], dp[it] + (i - it));
    }

    printf("%d\n", dp[Max]);

    return 0;
}