Cod sursa(job #3313313)

Utilizator LucaMirsolea14Luca Mirsolea LucaMirsolea14 Data 3 octombrie 2025 12:33:58
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.18 kb
//dif3 diamant  nrpuf abc acces text2

#include<bits/stdc++.h>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");

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){

        mij = (st+dr)/2;

        if(v[mij].second <= val){
            rez=mij;
            st=mij+1;
        }

        else
            dr=mij-1;

    }
    return rez;
}

int main(){

    int i;

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

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

   // for(i=1;i<=n;i++)
    //    fout<<"("<<v[i].first<<","<<v[i].second<<") ";
   // fout<<endl;

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

    fout << dp[n];
}