Cod sursa(job #327521)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 29 iunie 2009 12:12:56
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#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;
}