Cod sursa(job #8688)

Utilizator raula_sanChis Raoul raula_san Data 25 ianuarie 2007 12:40:38
Problema Elimin Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.38 kb
#include<stdio.h>
#define dim 1 << 13

int N, M, R, C, A[1<<4][dim], Sol[1<<4];
long r[1<<4], c[1<<13], S_tot, MAX;

void swap(long &a, long &b)
{
     a ^= b ^= a ^= b;
     }

void read()
{
     freopen("elimin.in", "r", stdin);
     scanf("%d %d %d %d", &N, &M, &R, &C);

	 int i, j;
	 for(i=1; i<=N; ++i)
			  for(j=1; j<=M; ++j)
                       if(N < M)
                       {
                            scanf("%d", &A[i][j]);
							S_tot += A[i][j];
					   }
					   else
					   {
						   scanf("%d", &A[j][i]);
						   S_tot += A[j][i];
					   }
	if(M < N)
	{
		N ^= M ^= N ^= M;
		R ^= C ^= R ^= C;
	}
}

void heapup(long a[], int k)
{
	 if(k <= 1)
		  return;
	 int t = k / 2;

	 if(a[t] < a[k])
	 {
			 swap(a[t], a[k]);
			 heapup(a, t);
     }
}

void restore(long a[], int r, int b)
{
	 if(r << 1 <= b)
	 {
		  long st, dr; int x;
          
		  st = a[r << 1];

		  if((r << 1) + 1 <= b)
				dr = (r << 1) + 1;
		  else dr = st - 1;

		  if(st > dr) x = r << 1;
		  else x = (r << 1) + 1;

		  if(a[r] < a[x])
		  {
				  swap(a[r], a[x]);
				  restore(a, x, b);
          }
     }
}

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

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

void get_solution()
{
	int i, j;

	long S = S_tot, ra[1<<4], co[1<<13];

	for(i=1; i<=N; ++i) ra[i] = r[i];
	for(i=1; i<=M; ++i) co[i] = c[i];

    for(i=1; i<=R; ++i)
    {
             S -= ra[Sol[i]];
			 for(j=1; j<=M; ++j)
				co[j] -= A[Sol[i]][j];
    }
    sort(co, M);

    for(i=1; i<=C; ++i)
             S -= co[i];

	if(S > MAX)
		MAX = S;
}

void gen()
{
     long i, j, k; int bytes = 0;
     for(i=1; i<=(1<<N); ++i)
     {
			  k = i; j = bytes = 0;
			  while(k)
              {
                      ++ j;
                      if(k & 1)
                           Sol[++bytes] = j;
                      k >>= 1;
              }
              if(bytes == R)
                       get_solution();
           }
}

int main()
{
	read();

	int i, j;
	for(i=1; i<=N; ++i)
		for(j=1; j<=M; ++j)
        	r[i] += A[i][j], c[j] += A[i][j];

    gen();
	write();

    fclose(stdin); fclose(stdout);
    return 0;
}