Cod sursa(job #11942)

Utilizator raula_sanChis Raoul raula_san Data 2 februarie 2007 13:58:21
Problema Elimin Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.58 kb
#include<cstdio>
#define dim 7300

int N, M, R, C, inv_read, A[16][dim], x[16];
long s[dim], s1[16], s2[dim], S, Aux, Max;

void read();
void gen();
void swap( long&, long& );
void copy( long A[], long B[] );
void sort();
void heapup( int );
void restore( int, int );
void write();

int main()
{
	read();
	gen();
	write();

	return 0;
}

void read()
{
	 freopen("elimin.in", "r", stdin);

	 scanf("%d %d %d %d", &N, &M, &R, &C);

	 if(N > M)
		  inv_read = 1;

	 int i, j;

	 for(i=1; i<=N; ++i)
			  for(j=1; j<=M; ++j)
					   if(inv_read)
					   {
								   scanf("%d", &A[j][i]);
								   s1[j] += A[j][i];
								   s2[i] += A[j][i];
								   S += A[j][i];
					   }
					   else
					   {
						   scanf("%d", &A[i][j]);
						   s1[i] += A[i][j];
						   s2[j] += A[i][j];
						   S += A[i][j];
					   }

	 if(inv_read)
	 {
				 N ^= M ^= N ^= M;
				 R ^= C ^= R ^= C;
	 }

	 fclose(stdin);
}

void gen()
{
     int byte, k, value, n, j;
     
	 for(byte=0; byte<(1<<N); ++byte)
     {
                k = n = 0; value = byte; 
                
                for(k=1,n=0,value=byte; n<=R&&value; value>>=1, ++k)
                                      if(value&1)
                                                 x[++n] = k;
                /*
                while(value)
                {
                            ++ k;
                            if(value & 1) x[++n] = k;
                            value >>= 1;
                            
                            if(n > R)
                                 break;

                }
                */
                if(n == R)
                {
                     Aux = S;
                     copy(s, s2);
                     
                     for(k=1; k<=n; ++k)
                     {
                              S -= s1[x[k]];
                              
                              for(j=1; j<=M; ++j)
                                       s2[j] -= A[x[k]][j];
                     }
                     
                     sort();
                     
                     for(k=1; k<=C; ++k)
                              S -= s2[k];
                              
                     if(S > Max)
                          Max = S;
                     
                     copy(s2, s);
                     S = Aux;
                }
     }
}

void swap(long &x, long &y)
{ x^=y^=x^=y; }

void copy( long A[], long B[] )
{
     int i;
     for(i=1; i<=M; ++i)
              A[i] = B[i];
}

void sort()
{
     int i;
     for(i=2; i<=M; ++i)
              heapup(i);
              
     for(i=M; i>1;)
     {
              swap(s2[1], s2[i]);
              -- i;
              restore(1, i);
     }
}

void heapup(int k)
{
     if(k <= 1)
          return;
          
     int t = k/2;
     
     if(s2[t] < s2[k])
     {
              swap(s2[t], s2[k]);
              heapup(t);
     }
}

void restore(int r, int b)
{
     if(r << 1 <= b)
     {
          long st, dr, x; st = s2[r<<1];
          
          if( (r<<1) + 1 <= b )
              dr = s2[(r<<1)+1];
          else
              dr = st - 1;
              
          if(st > dr)
                x = r << 1;
          else
              x = (r<<1) + 1;
              
          if(s2[r] < s2[x])
          {
                   swap(s2[r], s2[x]);
                   restore(x, b);
          }
     }
}

void write()
{
     freopen("elimin.out", "w", stdout);
     printf("%ld", Max);
     fclose(stdout);
}