Cod sursa(job #3200430)

Utilizator TrifoitaBejenescu-Babusanu Stefan Trifoita Data 4 februarie 2024 17:48:54
Problema Jocul Flip Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <fstream>
#include <cmath>
#define maxim 17
using namespace std;

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

int mat[maxim][maxim], stack[maxim], level, n, m, smax=0;

void citire() {
  fin >> n >> m;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
      fin >> mat[i][j];
}

int valid() {
  return (level <= n);
}

int solutie() {
  return (level == n);
}

void flip() {
  for (int i = 1; i <= n; i++)
    if (stack[i]) {
      for (int j = 1; j <= m; j++)
        mat[i][j] = mat[i][j] * (-1);
    }
  int smat = 0, s;
  for (int j = 1; j <= m; j++) {
    s = 0;
    for (int i = 1; i <= n; i++)
      s += mat[i][j];
      s = max(s, s*(-1));
    smat += s;
  }
  if (smat > smax)
    smax = smat;
  for (int i = 1; i <= n; i++)
    if (stack[i]) {
      for (int j = 1; j<= m; j++)
        mat[i][j] = mat[i][j] * (-1);
    }
}

void bkt() {
  if (valid()) {
    for (int i = 0; i <= 1; i++) {
      stack[level] = i;
      if (solutie())
        flip();
      level++;
      bkt();
      level--;
    }
  }
}

int main() {
  citire();
  bkt();
  fout << smax;
  return 0;
}