Cod sursa(job #142589)

Utilizator taloibogdanTaloi Bogdan Cristian taloibogdan Data 24 februarie 2008 19:40:21
Problema Heavy metal Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include<stdio.h>
long b[100000],a[100000];
//int partit(int b[ ],int st, int dr)
//{int i,j,m,piv,aa;
// m=(st+dr)/2;
// piv=b[m];
// i=st-1;
// j=dr+1;
// while(1)
//  {do{++i;} while(b[i]<piv);
//   do{--j;} while(b[j]>piv);
//   if (i<j)
//     {aa=a[i];a[i]=a[j];a[j]=aa;aa=b[i];b[i]=b[j];b[j]=aa;}
//       else
//     return j;
//  }
//}
//void quicks(int b[ ],int st,int dr)
//{int p;
// if (st<dr)
//   {p=partit(b,st,dr);
//    quicks(b,st,p);
//    quicks(b,p+1,dr);
//   }
//}
int main()
{long n,m,i,best[2000000],tm,j;
 freopen("heavymetal.in","r",stdin);
 freopen("heavymetal.out","w",stdout);
 scanf("%ld",&n);
 m=2000000000;
 tm=0;
 for(i=1;i<=n;++i){scanf("%ld%ld",&a[i],&b[i]);if(m>a[i])m=a[i];}
 for(i=1;i<=n;++i){a[i]-=(m-1);b[i]-=(m-1);if(b[i]>tm)tm=b[i];}
 best[0]=0;
 for(i=1;i<=tm;++i)
    {best[i]=best[i-1];
     for(j=1;j<=n;++j)
	if(b[j]==i)
	  if(best[a[j]]+(b[j]-a[j])>best[i])
	    best[i]=best[a[j]]+b[j]-a[j];
    }
 printf("%ld",best[tm]);
 return 0;
}