Pagini recente » Cod sursa (job #2402372) | Cod sursa (job #951303) | Cod sursa (job #1775428) | Cod sursa (job #1962483) | Cod sursa (job #2498021)
#include <iostream>
#include <fstream>
#include <algorithm>
#define Nmax 100001
using namespace std;
ifstream f("heavymetal.in");
ofstream o("heavymetal.out");
struct form{
int a,b;
}fo[Nmax];
bool cmp(form &f1,form &f2){
return f1.b < f2.b;
}
int i,j,n,dp[Nmax],d,v;
int bin(int v,int n){
int s=1,d=n,g=0,m;
while(s<=d){
m=(s+d)>>1;
if(fo[m].b<=v){
s=m+1;
g=max(g,m);
}
else
d=m-1;
}
return g;
}
int main()
{
f >> n;
for(i=1;i<=n;++i)
f >> fo[i].a >> fo[i].b;
sort(fo+1,fo+n+1,cmp);
dp[1]=fo[1].b-fo[1].a;
for(i=2;i<=n;++i){
v=fo[i].a;
d=fo[i].b-v;
dp[i]=dp[i-1];
dp[i]=max(dp[i],dp[bin(v,i-1)]+d);
}
o << dp[n];
return 0;
}