Pagini recente » Cod sursa (job #336213) | Cod sursa (job #3270982) | Cod sursa (job #2625182) | Cod sursa (job #3204050) | Cod sursa (job #2603802)
#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;
dp[1]=v[1].b-v[1].a;
for(int i=2;i<=n;i++){
p=cautare(1,n,v[i].a);
dp[i]=max(dp[i-1],dp[p]+v[i].b-v[i].a);
}
cou<<dp[n];
}
int main()
{
citire();
rez();
return 0;
}