Cod sursa(job #91144)

Utilizator undogSavu Victor Gabriel undog Data 11 octombrie 2007 19:04:33
Problema Jocul Flip Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <stdio.h>

#define FIN "flip.in"
#define FOUT "flip.out"

int A[20][20];
int S[20];
int i, j, N, M;
long long BEST = -300000;

int main ()
{
  freopen (FIN, "r", stdin);
  freopen (FOUT, "w", stdout);

  scanf ("%d %d", &N, &M);
  for (i = 1; i <= N; ++i)
   for (j = 1; j <= M; ++j)
     scanf ("%d", A[i] + j);

  int x;
  for (x = 0; x < (1 << N); ++x)
  {
     for (i = 1; i <= N; ++i)
       if (x & (1 << (i - 1)))
	for (j = 1; j <= M; ++j)
	  A[i][j] = - A[i][j];


     long long Sum = 0;
     for (j = 1; j <= M; ++j)
     {
       long long Sc = 0;
       for (i = 1; i <= N; ++i)
	   Sc+=A[i][j];
       if (Sc > 0) Sum +=Sc; else Sum -=Sc;
     }

     if (Sum > BEST) BEST = Sum;
     for (i = 1; i <= N; ++i)
       if (x & (1 << (j - 1)))
	for (j = 1; j <= M; ++j)
	  A[i][j] = - A[i][j];
  }

  printf ("%lld\n", (long long)(BEST));

  return 0;
}