Cod sursa(job #137511)

Utilizator SmarandaMaria Pandele Smaranda Data 17 februarie 2008 12:30:51
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda preONI 2008, Runda 4, Clasele 5-8 Marime 0.94 kb
#include<stdio.h>
long d[100001],sol[100001];
int partitie(int st , int dr)
{
long piv,aux;
int i,j,m;
m=(st+dr)/2;
piv=d[m];
i=st-1;j=dr+1;
while(1)
   {
     do{++i;}while(d[i]<piv);
     do{--j;}while(d[j]>piv);
     if(i<j)
	{
	  aux=d[i];
	  d[i]=d[j];
	  d[j]=aux;
	}
     else
	return j;
   }
}

void quick(int st , int dr)
{
int sep;
if(st<dr)
  {
    sep=partitie(st,dr);
    quick(st,sep);
    quick(sep+1,dr);
  }
}

int main()
{
int n,i,u=0;
long a,b,s=0;

freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);

scanf("%d",&n);
for(i=1;i<=n;i++)
    {
      scanf("%ld %ld",&a,&b);
      d[i]=b-a;
    }
quick(1,n);
s=d[n];
sol[++u]=d[n];
int ok=1,j;
for(i=n-1;i>=1;i--)
    {
      ok=1;
      for(j=1;j<=u;j++)
	  if(sol[j]==d[i])
	     {ok=0;
	      break;}
      if(ok)
	 {
	   sol[++u]=d[i];
	   s=(long)s+d[i];
	 }
    }
printf("%ld",s);
return 0;
}