Pagini recente » Istoria paginii runda/proba123451/clasament | Istoria paginii runda/asem-etapa1/clasament | Istoria paginii runda/1000101-1 | Istoria paginii runda/ojikk/clasament | Cod sursa (job #2004558)
#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;
if(dr==0)
return 0;
for(step=1;step<dr;step<<=1);
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;
for(i=1;i<=n;++i)
{
lng=v[i].y-v[i].x;
poz=bsearch(i-1,v[i].x);
dp[i]=dp[poz]+lng;
}
int maxim=0;
for(i=1;i<=n;++i)
if(maxim<dp[i])
maxim=dp[i];
printf("%d",maxim);
}