Cod sursa(job #405892)

Utilizator SzabiVajda Szabolcs Szabi Data 28 februarie 2010 21:21:49
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <stdio.h>
#define MAX 100000000
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;
}