Cod sursa(job #2650883)

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

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

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> (m);
}

void calc() {
  int64_t s = 0;
  for (int i=0; i<n; ++i) {
    int64_t line = 0;
    for (int j=0; j<m; ++j)
      line += (sol[j] == 1 ? -a[i][j] : a[i][j]);
    s += abs(line);
  }
  ans = std::max(ans, s);
}

void backtrack (int k) {
  if (k == m) {
    calc();
    return;
  }
  sol[k] = 0;
  backtrack(k + 1);
  sol[k] = 1;
  backtrack(k + 1);
}

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