Pagini recente » Cod sursa (job #2969276) | Cod sursa (job #1105303) | Cod sursa (job #207995) | Cod sursa (job #14535) | Cod sursa (job #405893)
Cod sursa(job #405893)
#include <stdio.h>
#define MAX 10000000
typedef long long tipus;
tipus n, a[MAX],b[MAX],best[MAX],Tmax=0;
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(){
tipus i,j=1;
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]);
if(b[i]>Tmax)Tmax=b[i];
}
quick(1,n);
for(i=2;i<=Tmax;i++){
best[i]=best[i-1];
while((b[j]==i)&&(j<=n)){
if(best[a[j]]+(b[j]-a[j])>best[i]){best[i]=best[a[j]]+(b[j]-a[j]);}
j++;}
}
printf("%lld",best[Tmax]);
return 0;
}