問題概要

$H \times W$ のマス目がある。各マスの値は 0 または 1 である。次の操作を好きな順序で好きな回数だけ行うことができる。

ある行を選択して、その行の数値をすべてひっくり返す (0 を 1 にして、1 を 0 にする)
ある列を選択して、その列の数値をすべてひっくり返す (0 を 1 にして、1 を 0 にする)

操作後の 0 の個数を最大にせよ。

制約

$1 \le H \le 10$
$1 \le W \le 10000$

考えたこと

「どの行をひっくり返すか」を固定してしまうことを考える。行の選択方法は $2^{H}$ 通りある。これらの行をあらかじめひっくり返してしまうことにする。

このとき、各列については次のように考えればよい。

その列の 0 の個数を $a$ とする
その行の 1 の個数を $b$ とする

このとき、 $a \ge b$ ならば何もしなくてよく、 $a \lt b$ ならば列をひっくり返すことで 0 の個数を $b$ 個にすることができる。すなわち、各列について

$\max(a, b)$

を合計した値となる。

全体として計算量は $O(2^{H}HW)$ となる。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int H, W;
    cin >> H >> W;
    vector fi(H, vector(W, 0));
    for (int i = 0; i < H; ++i) for (int j = 0; j < W; ++j) cin >> fi[i][j];
    int res = 0;
    for (int bit = 0; bit < (1<<H); ++bit) {
        auto fi2 = fi;
        for (int i = 0; i < H; ++i) {
            if (!(bit & (1<<i))) continue;
            for (int j = 0; j < W; ++j) fi2[i][j] = 1 - fi2[i][j];
        }
        int tmp = 0;
        for (int j = 0; j < W; ++j) {
            int num = 0;
            for (int i = 0; i < H; ++i) if (fi2[i][j] == 0) ++num;
            tmp += max(num, H-num);
        }
        res = max(res, tmp);
    }
    cout << res << endl;
}