Cod sursa(job #137521)

Utilizator bacerandreiBacer Andrei bacerandrei Data 17 februarie 2008 12:33:03
Problema Stalpi Scor 0
Compilator cpp Status done
Runda preONI 2008, Runda 4, Clasa a 10-a Marime 1.08 kb
#include<fstream.h>
long long n,x[100000],c[100000],s[100000],d[100000],uz[100000],i,j,cost,gasit,a,b,k;



void quik(long long p,long long q)
{
  long long aux,i,j,t1;
   if(p<q)
    {
     i=p;
     j=q;
     t1=1;
      do
       {
	if(c[i]>c[j])
	 {
	  aux=c[i];
	  c[i]=c[j];
	  c[j]=aux;
	  aux=x[i];
	  x[i]=x[j];
	  x[j]=aux;
	  aux=s[i];
	  s[i]=s[j];
	  s[j]=aux;
	  aux=d[i];
	  d[i]=d[j];
	  d[j]=aux;
	  t1=!t1;
	 }
       if(t1)
	j--;
       else
	i++;
      }while(i!=j);
   quik(p,i-1);
   quik(i+1,q);
  }
}


int main()
{
  ifstream f("stalpi.in");
  ofstream g("stalpi.out");
   f>>n;
    for(i=1;i<=n;i++)
     f>>x[i]>>c[i]>>s[i]>>d[i];
    quik(1,n);
   i=0;
   while(!gasit)
    {
     i++;
     gasit=1;
      cost+=c[i];
      for(k=1;k<=i;k++)
      {
	a=x[k]-s[k];
	b=x[k]+d[k];
       for(j=i+1;j<=n;j++)
	if(x[j]>=a&&x[j]<=b)
	  uz[j]=1;
       }
	for(j=i+1;j<=n;j++)
	 if(uz[j]==0)
	  gasit=0;
      if(i==n)
       gasit=1;
      for(j=i+1;j<=n;j++)
       uz[j]=0;
    }
   g<<cost;
  return 0;
}