Cod sursa(job #2864905)

Utilizator mihaistamatescuMihai Stamatescu mihaistamatescu Data 8 martie 2022 12:18:44
Problema Heavy metal Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.79 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;
        int st=1;
        int dr=i-1;
        while (st<=dr){
            int mid = (st+dr)/2;
            if (s[i].second>=s[mid].first){
                st=mid+1;
            }
            else{
                dr=mid-1;
            }
        }
        d[i]=max(d[i], d[dr]+s[i].first-s[i].second);
        if (d[i]>maxim){
            maxim=d[i];
        }
    }
    fout<<maxim;
    return 0;
}