Cod sursa(job #2203663)

Utilizator VladTZYVlad Tiganila VladTZY Data 12 mai 2018 20:46:04
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.58 kb
#include <fstream>
#include <algorithm>

using namespace std;

ifstream f("heavymetal.in");
ofstream g("heavymetal.out");

struct hh{
    int i,s;
};

int i,j=1,dp[100005],n;
hh v[100005];

int cmp(hh a,hh b)
{
    if(a.i>b.i)
        return 0;
    else
        return 1;
}
int main()
{
    f>>n;
    for(i=1;i<=n;i++)
        f>>v[i].i>>v[i].s;
    sort(v+1,v+1+n,cmp);
    for(i=1;i<=v[n].s;i++)
    {
        dp[i]=dp[i-1];
        while(v[j].s==i)
        {
            dp[i]=max(dp[i],dp[v[j].i]+v[j].s-v[j++].i);
        }
    }
    g<<dp[v[n].s];
}