Cod sursa(job #405702)

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