Cod sursa(job #1012547)

Utilizator razvan9310FMI - Razvan Damachi razvan9310 Data 19 octombrie 2013 12:29:31
Problema Jocul Flip Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <fstream>
#include <bitset>
using namespace std;

int mat[16][16];
int N, M, MAX;
bitset<16> sol;

void input() {
  ifstream in("flip.in");
  in>>N>>M;
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < M; ++j) {
      in>>mat[i][j];
      MAX += mat[i][j];
    }
  }
  in.close();
}

void coloane() {
  int i, j, total = 0;
  for (i = 0; i < N; ++i) {
    for (j = 0; j < M; ++j) {
      total += (sol[i] == 0 ? mat[i][j] : -mat[i][j]);
    }
  }
  for (j = 0; j < M; ++j) {
    int sum = 0;
    for (i = 0; i < N; ++i) {
      sum += (sol[i] == 0 ? mat[i][j] : -mat[i][j]);
    }
    if (total - 2*sum > MAX) {
      MAX = total = total - 2*sum;
    }
  }
}

void back(const int &line) {
  if (line == N) {
    return;
  }
  coloane();
  back(line + 1);
  sol[line] = 1;
  coloane();
  back(line + 1);
  sol[line] = 0;
}

void solve() {
  back(0);
}

void output() {
  ofstream out("flip.out");
  out<<MAX;
  out.close();
}

int main() {
  input();
  solve();
  output();
  return 0;
}