0525 Osenbei

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0525

方針

行数が最大10行までと小さいので、行のひっくり返し方を決めて全探索する。
行のひっくり返し方が決まれば、列の最適なひっくり返し方は一意に決まる。

ソース

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define REP(i,a,b) for(i=a; i<b; ++i)
#define rep(i,n) REP(i,0,n)

int board[10001];

int pop(int x) {
  int n = 0;
  while(x != 0) {
    n = n + 1;
    x &= (x-1);
  }
  return n;
}

int main() {
  int n,i,j,k,r,c;
  while(scanf("%d %d", &r, &c), r|c) {
    memset(board, 0, sizeof(board));
    rep(i,r) {
      rep(j,c) {
	scanf("%d", &k);
	if(k) board[j] |= (1<<i);
      }
    }

    int ans = 0,tt,t;
    rep(i,(1<<r)) {
      t = 0;
      rep(j,c) {
	tt = pop(board[j] ^ i);
	t += max(tt, r-tt);
      }
      ans = max(ans, t);
    }
    printf("%d\n", ans);
  }
}