Cod sursa(job #1972094)

Utilizator stefan_creastaStefan Creasta stefan_creasta Data 21 aprilie 2017 21:00:12
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.68 kb
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int NMAX = 100005;
vector <int> v[NMAX];
vector <int> sol;

int main()
{
    int n, a, b, i, j, maxb = 0;
    freopen("heavymetal.in","r",stdin);
    freopen("heavymetal.out","w",stdout);
    scanf("%d", &n);
    for(i = 1;i <= n; ++i) {
        scanf("%d%d", &a, &b);
        maxb = max(maxb, b);
        v[b].push_back(a);
    }
    sol.push_back(0);
    for(i = 1;i <= maxb; ++i) {
       sol.push_back(sol[i - 1]);
       for(j = 0;j < v[i].size(); ++j) {
            sol[i] = max(sol[i], sol[v[i][j]] + i - v[i][j]);
       }
    }
    printf("%d\n", sol[maxb]);
    return 0;
}