Pagini recente » Cod sursa (job #1258128) | 1235 | Cod sursa (job #1737053) | Cod sursa (job #2193956) | Cod sursa (job #142608)
Cod sursa(job #142608)
#include<stdio.h>
long c[100000],b[100000],a[100000];
long partit(long c[ ],long st, long dr)
{long i,j,m,piv,aa;
m=(st+dr)/2;
piv=c[m];
i=st-1;
j=dr+1;
while(1)
{do{++i;} while(c[i]<piv);
do{--j;} while(c[j]>piv);
if (i<j)
{aa=c[i];c[i]=c[j];c[j]=aa;}
else
return j;
}
}
void quicks(long c[ ],long st,long dr)
{long p;
if (st<dr)
{p=partit(c,st,dr);
quicks(c,st,p);
quicks(c,p+1,dr);
}
}
int main()
{long n,m,i,best[2000000],tm,j;
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
scanf("%ld",&n);
m=2000000000;
tm=0;
for(i=1;i<=n;++i){scanf("%ld%ld",&a[i],&b[i]);if(m>a[i])m=a[i];}
for(i=1;i<=n;++i){a[i]-=(m-1);b[i]-=(m-1);if(b[i]>tm)tm=b[i];}
for(i=1;i<=n;++i){c[i*2-1]=a[i];c[i*2]=b[i];}
quicks(c,1,n*2);
best[0]=0;
for(i=1;i<=n*2;++i)
{best[c[i]]=best[c[i-1]];
for(j=1;j<=n;++j)
if(b[j]==c[i])
if(best[a[j]]+(b[j]-a[j])>best[c[i]])
best[c[i]]=best[a[j]]+b[j]-a[j];
}
printf("%ld",best[tm]);
return 0;
}