Pagini recente » Cod sursa (job #661903) | Cod sursa (job #3209582) | Cod sursa (job #1338609) | Cod sursa (job #2097710) | Cod sursa (job #405885)
Cod sursa(job #405885)
#include <stdio.h>
#define MAX 100002
typedef long long tipus;
tipus n, a[MAX],b[MAX],best[MAX];
void quick(int lo,int hi){
int i=lo,j=hi;
tipus x=b[lo+(hi-lo)/2],h;
do{
while(b[i]<x){i++;}
while(b[j]>x){j--;}
if(i<=j){
h=a[i];
a[i]=a[j];
a[j]=h;
h=b[i];
b[i]=b[j];
b[j]=h;
i++;
j--;
}
}while(i<j);
if(i<hi)quick(i,hi);
if(lo<j)quick(lo,j);
}
int main(){
int i,j;
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
scanf("%lld",&n);
for(i=1;i<=n;i++){
scanf("%lld %lld",&a[i],&b[i]);
}
quick(1,n);
best[1]=b[1]-a[1];
for(i=2;i<=n;i++){
best[i]=best[i-1];
j=i;
while((b[j]>a[i])&&(j>=1)){j--;}
if((j>=1)&&(best[j]+(b[i]-a[i])>best[i])){best[i]=best[j]+(b[i]-a[i]);}
}
printf("%lld",best[n]);
return 0;
}