Pagini recente » Cod sursa (job #471725) | Cod sursa (job #490075) | Cod sursa (job #1133789) | Cod sursa (job #1628957) | Cod sursa (job #2603804)
#include <bits/stdc++.h>
using namespace std;
ifstream ci("heavymetal.in");
ofstream cou("heavymetal.out");
struct date{
int a,b;
};
int n,dp[100005];
date v[100005];
bool cmp(date a,date b){
if(a.b!=b.b){
return a.b<b.b;
}else{
return a.a<b.a;
}
}
void citire(){
ci>>n;
for(int i=1;i<=n;i++){
ci>>v[i].a>>v[i].b;
}
sort(v+1,v+n+1,cmp);
}
int cautare(int st,int dr,int x){
int sol=st,mij;
while(st<=dr){
mij=(st+dr)/2;
if(v[mij].b>x){
dr=mij-1;
}else{
sol=mij;
st=mij+1;
}
}
return sol;
}
void rez(){
int p;
/*
for(int i=1;i<=n;i++){
cout<<v[i].a<<" "<<v[i].b<<"\n";
}
cout<<"\n";
*/
dp[1]=v[1].b-v[1].a;
for(int i=2;i<=n;i++){
p=cautare(1,n,v[i].a);
if(v[p].b<=v[i].a){
dp[i]=max(dp[i-1],dp[p]+v[i].b-v[i].a);
}else{
dp[i]=max(dp[i-1],v[i].b-v[i].a);
}
//cout<<i<<" "<<dp[i]<<" "<<dp[i-1]<<" "<<p<<"\n";
}
cou<<dp[n];
}
int main()
{
citire();
rez();
return 0;
}