Cod sursa(job #2479573)

Utilizator TeddyDinutaDinuta Eduard Stefan TeddyDinuta Data 23 octombrie 2019 22:40:11
Problema Heavy metal Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.57 kb
#include <bits/stdc++.h>

using namespace std;
ifstream in("heavymetal.in");
ofstream out("heavymetal.out");
int n,t,dp[100100];
struct hm
{
    int l,r;
}v[100100];
bool cmp(hm a,hm b)
{
    return a.l<b.l||(a.l==b.l&&a.r<b.r);
}
int main()
{
    in>>n;
    for(int i=1;i<=n;i++)
        in>>v[i].l>>v[i].r;
    sort(v+1,v+n+1,cmp);
    dp[1]=v[1].r-v[1].l;
    for(int i=2;i<=n;i++)
    {
        dp[i]=v[i].r-v[i].l;
        for(int j=1;j<i;j++)
            if(v[i].l>=v[j].r) dp[i]=max(dp[i],v[i].r-v[i].l+dp[j]);
    }
    out<<dp[n];
    return 0;
}