Cod sursa(job #2919260)

Utilizator diana_dd03Dorneanu Diana diana_dd03 Data 16 august 2022 16:23:55
Problema Heavy metal Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.82 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin ("heavymetal.in");
ofstream fout ("heavymetal.out");

struct show{
    int s, f;
};
int n, dmax;
int dp[100000];
show v[100001];

bool comp( show A, show B){
    return A.f<B.f;
}

int main(){
    fin>>n;
    for(int i=1;i<=n;i++){
        fin>>v[i].s;
        fin>>v[i].f;
    }
    sort(v+1, v+n+1, comp);

    for(int i=1;i<=n;i++){
        int st=1, dr=i, mij, p=0;
        int x=v[i].s;
        while(st<=dr){
            mij=(st+dr)/2;
            if(v[mij].f<=x){
                if(mij>p)
                    p=mij;
                st=mij+1;
            }
            else dr=mij-1;
        }

        dp[i]=dp[p]+(v[i].f-v[i].s);
    }
    for(int i=1;i<=n;i++)
        dmax=max(dmax, dp[i]);

    fout<<dmax;
    return 0;
}