Cod sursa(job #1010816)

Utilizator razvan9310FMI - Razvan Damachi razvan9310 Data 15 octombrie 2013 19:05:12
Problema Jocul Flip Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 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) {
  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 (total - 2*sum > MAX) {
      MAX = total = total - 2*sum;
    }
  }
}

void back(int k, int total) {
  if (k == N) {
    return;
  }
  //sol[k] = 0:
  coloane(total);
  back(k + 1, total);
  //sol[k] = 1:
  sol[k] = 1;
  int suma = 0;
  for (int i = 0; i < M; ++i) {
    suma += mat[k][i];
  }
  coloane(total - 2*suma);
  back(k + 1, total - 2*suma);
  sol[k] = 0;
}

void solve() {
  back(0, MAX);
}

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

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