Pagini recente » Cod sursa (job #3219980) | Cod sursa (job #2216931) | Cod sursa (job #485030) | Cod sursa (job #1690503) | Cod sursa (job #142589)
Cod sursa(job #142589)
#include<stdio.h>
long b[100000],a[100000];
//int partit(int b[ ],int st, int dr)
//{int i,j,m,piv,aa;
// m=(st+dr)/2;
// piv=b[m];
// i=st-1;
// j=dr+1;
// while(1)
// {do{++i;} while(b[i]<piv);
// do{--j;} while(b[j]>piv);
// if (i<j)
// {aa=a[i];a[i]=a[j];a[j]=aa;aa=b[i];b[i]=b[j];b[j]=aa;}
// else
// return j;
// }
//}
//void quicks(int b[ ],int st,int dr)
//{int p;
// if (st<dr)
// {p=partit(b,st,dr);
// quicks(b,st,p);
// quicks(b,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];}
best[0]=0;
for(i=1;i<=tm;++i)
{best[i]=best[i-1];
for(j=1;j<=n;++j)
if(b[j]==i)
if(best[a[j]]+(b[j]-a[j])>best[i])
best[i]=best[a[j]]+b[j]-a[j];
}
printf("%ld",best[tm]);
return 0;
}