Cod sursa(job #1971962)

Utilizator andrei20003Ionescu Andrei andrei20003 Data 21 aprilie 2017 13:14:51
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.53 kb
#include <bits/stdc++.h>

using namespace std;

int v1[100010];

vector <int>v[100010];

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