Cod sursa(job #1751506)

Utilizator c0mradec0mrade c0mrade Data 1 septembrie 2016 15:09:07
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.51 kb
#include<bits/stdc++.h>
using namespace std;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");

vector<int>v[111111];
int n,Time,dp[111111];

int main()
{
    int i;
    for(i=1,f>>n;i<=n;++i)
    {
        int x,y;
        f>>x>>y;
        v[y].push_back(x);
        Time=max(Time, y);
    }
    for(int i=1;i<=Time;++i)
    {
        dp[i]=dp[i-1];
        for(int j=0;j<v[i].size();++j)
            dp[i]=max(dp[i], dp[v[i][j]]+i-v[i][j]);
    }
    g<<dp[Time];
    return 0;
}