Pagini recente » Cod sursa (job #1153099) | Cod sursa (job #1962673) | Cod sursa (job #722278) | Cod sursa (job #1369626) | Cod sursa (job #327521)
Cod sursa(job #327521)
#include <stdio.h>
#define Nmax 100005
long a[Nmax],b[Nmax],best[Nmax];
long n;
void citire(){
long i;
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
scanf("%ld",&n);
for(i=1;i<=n;++i) scanf("%ld%ld",&a[i],&b[i]);
}
void sort(long l,long r){
long i,j,x,y;
i=l; j=r; x=b[l+(r-l)/2]; // ordonez cresc dupa timp b de term
do{
while(b[i]<x) ++i;
while(x<b[j]) --j;
if(i<=j){
y=a[i]; a[i]=a[j]; a[j]=y;
y=b[i]; b[i]=b[j]; b[j]=y;
i++; --j;
}
} while(i<=j);
if(i<r)sort(i,r);
if(l<j)sort(l,j);
}
long MAX(long x,long y){
return x>y ? x : y;
}
long caut_bin(long l,long r,long x){
long m,ret=0;
while(l<=r){
m=l+(r-l)/2;
if(b[m]<=x){ ret=m; l=m+1; }
else r=m-1;
}
return ret;
}
void work(){
long i,poz;
best[1]=b[1]-a[1]; best[0]=0;
for(i=2;i<=n;++i){
poz=caut_bin(1,n,a[i]);
best[i]= MAX(best[i-1], best[poz]+b[i]-a[i]);
}
}
int main(){
citire();
sort(1,n);
work();
printf("%ld\n",best[n]);
fclose(stdin); fclose(stdout);
return 0;
}