Pagini recente » Cod sursa (job #2304964) | Cod sursa (job #1002389) | Cod sursa (job #2010971) | Cod sursa (job #2005748) | Cod sursa (job #2004560)
#include<cstdio>
#include<algorithm>
using namespace std;
const int nmax=1e5+5;
struct al
{
int x,y;
}v[nmax];
int dp[nmax];
inline bool cmp(al a,al b)
{
return a.y<b.y;
}
inline int bsearch(int dr,int x)
{
int i,step=1<<20;
for(i=1;step;step>>=1)
if(i+step<dr && v[i+step].y<=x)
i+=step;
return i;
}
int main()
{
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
int n,i,j;
scanf("%d",&n);
for(i=1;i<=n;++i)
scanf("%d%d",&v[i].x,&v[i].y);
sort(v+1,v+n+1,cmp);
int lng,poz;
dp[1]=v[1].y-v[1].x;
for(i=2;i<=n;++i)
{
lng=v[i].y-v[i].x;
poz=bsearch(i,v[i].x);
dp[i]=dp[poz]+lng;
if(dp[i-1]>dp[i])
dp[i]=dp[i-1];
}
int maxim=0;
for(i=1;i<=n;++i)
if(maxim<dp[i])
maxim=dp[i];
printf("%d",maxim);
}