Cod sursa(job #2278050)

Utilizator JigsawKillerPetrescu Alexandru JigsawKiller Data 7 noiembrie 2018 10:48:37
Problema Jocul Flip Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <fstream>
#include <algorithm>
#define MAX 17
#define MIN -1000000000

using namespace std;

int a[MAX][MAX], sumeC[MAX], linii[MAX], Max = MIN;

void backtracking(int n, int m, int k)
{
  if(k <= n)
  {
    linii[k] = 0;
    backtracking(n, m, k + 1);
    linii[k] = 1;
    backtracking(n, m, k + 1);
  }
  else
  {
    int i, j;

    for(i = 1; i <= n; i++)
      for(j = 1; j <= m; j++)
        if(linii[i] == 1)sumeC[j] = sumeC[j] - 2 * a[i][j];

    //sort(sume2C + 1, sume2C + 1 + m);
int    suma = 0;

    for(j = 1; j <= m; j++)
      if(sumeC[j] < 0)suma += -sumeC[j];
      else suma += sumeC[j];

    if(suma > Max)Max = suma;

    for(i = 1; i <= n; i++)
      for(j = 1; j <= m; j++)
        if(linii[i] == 1)sumeC[j] = sumeC[j] + 2 * a[i][j];
  }
}
int main()
{
  int n, m, i, j;

  ifstream fin("flip.in");
  ofstream fout("flip.out");

  fin >> n >> m;

  for(i = 1; i <= n; i++)
    for(j = 1; j <= m; j++)
    {
      fin >> a[i][j];
      sumeC[j] += a[i][j];
    }

  if(n > m)
  {
    swap(n, m);
  }

  backtracking(n, m, 1);

  fout << Max;

  fin.close();
  fout.close();

  return 0;
}