Cod sursa(job #2864893)

Utilizator mihaistamatescuMihai Stamatescu mihaistamatescu Data 8 martie 2022 12:13:56
Problema Heavy metal Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.65 kb
#include <fstream>
#include <algorithm>
using namespace std;
pair<int, int> s[100010];
int d[100010];
int n, maxim;
int main () {
    ifstream fin ("heavymetal.in");
    ofstream fout("heavymetal.out");
    fin>>n;
    for (int i=1;i<=n;i++){
        fin>>s[i].second>>s[i].first;
    }
    sort(s+1, s+n+1);
    for (int i=1;i<=n;i++){
        d[i]=s[i].first-s[i].second;
        for (int j=i-1;j>=1;j--){
            if (s[i].second>=s[j].first){
                d[i]=max(d[i], d[j]+s[i].first-s[i].second);
            }
        }
        if (d[i]>maxim){
            maxim=d[i];
        }
    }
    fout<<maxim;
    return 0;
}