Pagini recente » Cod sursa (job #1495514) | Cod sursa (job #142522) | Cod sursa (job #704171) | Cod sursa (job #2101788) | Cod sursa (job #3313314)
#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;
}