Cod sursa(job #3313314)

Utilizator Raul_ADRPlutu Raul Raul_ADR Data 3 octombrie 2025 12:34:48
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <bits/stdc++.h>

using namespace std;

pair <int,int > v[100002];
int n;
int dp[100002];

bool comp( pair<int, int > x, pair<int, int > y ){
    return x.second<y.second;
}
int CB(int val){
    int st,dr,mij,rez=0;
    st=1;
    dr=n;
    while(st<=dr){

        int mij=(st+dr)/2;
        if(v[mij].second<=val)
            rez=mij,st=mij+1;
        else
            dr=mij-1;

    }
    return rez;
}

int main(){

    ifstream cin("heavymetal.in");
    ofstream cout("heavymetal.out");
    int i=1;

    cin>>n;
    for(i=1;i<=n;++i)
        cin>> v[i].first>>v[i].second;

    sort(v+1,v+n+1,comp);

    for(i=1;i<=n;++i){
        int lg=v[i].second-v[i].first;
        int poz = CB(v[i].first);///cea mai din dreapta pozitie care se termina inainte de concertul i
        dp[i]= max(dp[i-1],lg+dp[poz]);

    }
    cout<<dp[n];

    return 0;
}