Pagini recente » Cod sursa (job #2246944) | Cod sursa (job #252002) | Cod sursa (job #1116637) | Cod sursa (job #1853119) | Cod sursa (job #1336997)
#include <fstream>
#include <algorithm>
#define DIM 100005
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
int N,best[DIM];
pair <int,int> v[DIM];
int cautbin(int x,int lim){
int p,u,mid,sol=0;
p=1;
u=lim;
while(p<=u){
mid=(p+u)>>1;
if(v[mid].second<=x){
p=mid+1;
sol=mid;
}
else
u=mid-1;
}
return sol;
}
int main(){
fin>>N;
for(int i=1;i<=N;i++)
fin>>v[i].first>>v[i].second;
sort(v+1,v+N+1);
best[1]=v[1].second-v[1].first;
for(int i=2;i<=N;i++){
best[i]=max(best[i-1],v[i].second-v[i].first);
int x=cautbin(v[i].first,i-1);
best[i]=max(best[i],best[x]+v[i].second-v[i].first);
}
fout<<best[N];
fin.close();fout.close();
return 0;
}