AOJ 0525: Osenbei

Rが小さいので、行単位でひっくり返すのは全て試します。
列は自由にひっくり返すことができるため、表になっているものの個数か裏になっているものの個数の内大きい方を使えば良いです。
数えるのにO(RC)かかるので、全体ではO(RC･2^R)になります。

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

int R,C;
bitset<10000> bs[10];

int main(){
	while(scanf("%d%d",&R,&C),R){
		for(int i = 0; i < R; i++){
			bs[i].reset();
		}
		for(int i = 0; i < R; i++){
			for(int j = 0; j < C; j++){
				int a;
				scanf("%d",&a);
				bs[i][j] = a;
			}
		}
		int ans = 0;
		for(int i = 0; i < (1<<R); i++){
			for(int j = 0; j < R; j++){
				if(i&(1<<j))bs[j].flip();
			}
			int tmp = 0;
			for(int j = 0; j < C; j++){
				int t = 0;
				for(int k = 0; k < R; k++){
					t += bs[k][j];
				}
				tmp += max(t,R-t);
			}
			ans = max(ans,tmp);
			
			for(int j = 0; j < R; j++){
				if(i&(1<<j))bs[j].flip();
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}