Cod sursa(job #7905)

Utilizator crawlerPuni Andrei Paul crawler Data 22 ianuarie 2007 22:25:55
Problema Elimin Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <stdio.h>

long  a[16][7300];
long  s[7300];

void qsort(long st, long dr)
{
  register long i, j, aux, sc;
  i=st;j=dr;
  sc=s[(st+dr)>>1];
  do{
      while(s[i]<sc)
       ++i;
      while(s[j]>sc)
       --j;
      if(i<=j)
       {
         aux=s[i];
         s[i]=s[j];
         s[j]=aux;

         ++i;--j;
       }
     }while((i<=j));
     
if(i<dr)qsort(i,dr);
if(j>st)qsort(st,j);

}


int main()
{
  register long i, j,  k, v[16], n, m, nr1,R,C;
  register long long suma, max=0;

  
  max=-2000000000;

  freopen("elimin.in","r",stdin);
  freopen("elimin.out","w",stdout);
  
  scanf("%ld%ld%ld%ld", &m, &n,&R,&C);

  if(m>n)
   {
    m^=n^=m^=n;
    R^=C^=R^=C;
   }

  for(i=1;i<=n;++i)
   v[i]=0;

  for(i=1;i<=n;++i)
   for(j=1;j<=m;++j)
    scanf("%ld",&a[i][j]);


  v[1]=-1;
  k=1;
  nr1=0;
  
  while(k)
   {
    if(++v[k]==1)
     ++nr1;
    
    if(v[k]==2 || nr1>R)
     {
      --k;
      nr1-=v[k]&1;
     }
      else
       if(k==n && nr1==R)
        {
         for(i=1;i<=n;++i)
          s[i]=0;
          
         for(i=1;i<=n;++i)
          if(!v[i])
           for(j=1;j<=m;++j)
            s[j]+=a[i][j];

         qsort(1,n);

         suma=0;
         for(i=C+1;i<=n;++i)
          suma+=s[i];

         if(suma>max)
          max=suma;
        }
         else
        v[++k]=-1;
     if(k>n)
      k=n;
   }

  printf("%lld\n",max);

  return 0;
}