Pagini recente » Borderou de evaluare (job #3332240) | Cod sursa (job #336287) | Cod sursa (job #3326398) | Cod sursa (job #3310402) | Cod sursa (job #3313313)
//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];
}