Cod sursa(job #142608)

Utilizator taloibogdanTaloi Bogdan Cristian taloibogdan Data 24 februarie 2008 20:02:36
Problema Heavy metal Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include<stdio.h>
long c[100000],b[100000],a[100000];
long partit(long c[ ],long st, long dr)
{long i,j,m,piv,aa;
 m=(st+dr)/2;
 piv=c[m];
 i=st-1;
 j=dr+1;
 while(1)
  {do{++i;} while(c[i]<piv);
   do{--j;} while(c[j]>piv);
   if (i<j)
     {aa=c[i];c[i]=c[j];c[j]=aa;}
       else
     return j;
  }
}
void quicks(long c[ ],long st,long dr)
{long p;
 if (st<dr)
   {p=partit(c,st,dr);
    quicks(c,st,p);
    quicks(c,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];}
 for(i=1;i<=n;++i){c[i*2-1]=a[i];c[i*2]=b[i];}
 quicks(c,1,n*2);
 best[0]=0;
 for(i=1;i<=n*2;++i)
    {best[c[i]]=best[c[i-1]];
     for(j=1;j<=n;++j)
	if(b[j]==c[i])
	  if(best[a[j]]+(b[j]-a[j])>best[c[i]])
	    best[c[i]]=best[a[j]]+b[j]-a[j];
    }
 printf("%ld",best[tm]);
 return 0;
}