joi2008yo_e

問題だけ読んでほったらかしてたら急に解法が降ってきた。

例のごとく000...000 ~ 111...111までのbitでR列目をひっくり返した場合にどうなるかをC行に試す全探索を行う。

C行目は独自にひっくり返せれるのでmax(1のbit数, 0のbit数)を考えればよい。

すぐに分かったけどRとCがごっちゃになってWA出しまくった。。。

#include<bits/stdc++.h>

using namespace std;

int r, c;

int a[11][11111];

int b[11111];

int cnt_bit(int bit){

    int cnt = 0;

    for(;bit;bit&=(bit-1)) cnt++;

    return cnt;

}

int main(){

    cin >> r >> c;

    for(int i=0;i<r;i++)

        for(int j=0;j<c;j++) cin >> a[i][j];

    for(int j=0;j<c;j++){

        for(int i=0;i<r;i++){

            b[j] = b[j] << 1;

            b[j] |= a[i][j];

        }

    }

    int ans = 0;

    for(int i=0;i<(1<<r);i++){

        int num = 0;

        for(int j=0;j<c;j++){

            int p = b[j] ^ i;

            int cnt = cnt_bit(p);

            num += max(cnt, r-cnt);

        }

        ans = max(ans, num);

    }

    cout << ans << endl;

}