Cod sursa(job #1012601)

Utilizator razvan9310FMI - Razvan Damachi razvan9310 Data 19 octombrie 2013 13:20:23
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 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 total = 0;
  for (int j = 0; j < M; ++j) {
    int sum = 0;
    for (int i = 0; i < N; ++i) {
      sum += sol[i] == 0 ? mat[i][j] : -mat[i][j];
    }
    if (sum > -sum) {
      total += sum;
    } else {
      total -= sum;
    }
  }
  if (total > MAX) {
    MAX = total;
  }
}

void back(int k) {
  coloane();
  if (k == N) {
    return;
  }
  //sol[k] = 0:
  back(k + 1);
  //sol[k] = 1:
  sol[k] = 1;
  back(k + 1);
  sol[k] = 0;
}

void solve() {
  back(0);
}

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

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