Cod sursa(job #2650877)

Utilizator cristi_macoveiMacovei Cristian cristi_macovei Data 20 septembrie 2020 17:25:50
Problema Jocul Flip Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <fstream>
#include <vector>
#include <climits>

std::ifstream in ("flip.in");
std::ofstream out ("flip.out");
void quit () {
  in.close();
  out.close();
  exit(0);
}

const int nmax = 16;

int n, m;
int64_t ans = LLONG_MIN;
std::vector<std::vector<int>> a;
std::vector<int> sol;

void read () {
  in >> n >> m;
  a = std::vector<std::vector<int>>(n);
  for (int i=0; i<n; ++i) {
    a[i] = std::vector<int>(m);
    for (int j=0; j<m; ++j)
      in >> a[i][j];
  }
  sol = std::vector<int> (n + m);
}

void calc() {
  /*
  for (int i: sol)
    out << i << ' ';
  */

  // index 0 .. n - 1 => lines
  // index n .. m + n - 1 => cols
  int64_t s = 0;
  for (int i=0; i<n; ++i) {
    for (int j=0; j<m; ++j)
      s += ((sol[i] + sol[n+j] == 1) ? -a[i][j] : a[i][j]);
  }

  //out << "   :   " << s << '\n';

  ans = std::max(ans, s);
}

void backtrack (int k) {
  for (int i=0; i<=1; ++i) {
    sol[k] = i;
    if (k == n + m)
      calc();
    else
      backtrack(k + 1);
  }
}

int main () {
  read();
  backtrack(0);
  out << ans;
  quit();
}