Cod sursa(job #3240527)

Utilizator EricRaiaEricRaia EricRaia Data 16 august 2024 10:13:12
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <fstream>
#include <algorithm>

using namespace std;

ifstream cin ("heavymetal.in");
ofstream cout ("heavymetal.out");

int main() {

    int N,i,j,ma,l,r,bun,md;
    cin>>N;
    pair<int, int> ore[N];
    int m[N];
    for(i=0; i<N; ++i)
        cin >> ore[i].first >> ore[i].second;
    sort(ore, ore+N, [](const std::pair<int, int> &left, const std::pair<int, int> &right) {
        return left.second < right.second;
    });
    m[0]=ore[0].second-ore[0].first;
    for(i=1;i<N;i++){
        ma=ore[i].second-ore[i].first;
        l=0;
        r=i-1;
        bun=-1;
        while(l<=r){
            md=l+(r-l)/2;
            if(ore[md].second<=ore[i].first){
                bun=md;
                l=md+1;
            }
            else
                r=md-1;
        }

        if(bun!=-1) {
            ma+=m[bun];
        }
        m[i]=max(ma, m[i-1]);
    }
    cout<<m[N-1];

    return 0;
}