Problem:


 おせんべい 

問題

IOI製菓では，創業以来の伝統の製法で煎餅（せんべい）を焼いている．この伝統の製法は，炭火で一定時間表側を焼き，表側が焼けると裏返して，炭火で一定時間裏側を焼くというものである．この伝統を守りつつ，煎餅を機械で焼いている．この機械は縦 R (1 ≤ R ≤ 10) 行, 横 C (1 ≤ C ≤ 10000) 列の長方形状に煎餅を並べて焼く．通常は自動運転で，表側が焼けたら一斉に煎餅を裏返し裏側を焼く．

ある日，煎餅を焼いていると，煎餅を裏返す直前に地震が起こり何枚かの煎餅が裏返ってしまった．幸いなことに炭火の状態は適切なままであったが，これ以上表側を焼くと創業以来の伝統で定められている焼き時間を超えてしまい，煎餅の表側が焼けすぎて商品として出荷できなくなる．そこで，急いで機械をマニュアル操作に変更し，まだ裏返っていない煎餅だけを裏返そうとした．この機械は，横の行を何行か同時に裏返したり縦の列を何列か同時に裏返したりすることはできるが，残念なことに，煎餅を１枚ごと裏返すことはできない．

裏返すのに時間がかかると，地震で裏返らなかった煎餅の表側が焼けすぎて商品として出荷できなくなるので，横の何行かを同時に１回裏返し，引き続き，縦の何列かを同時に１回裏返して，表側を焼きすぎずに両面を焼くことのできる煎餅，つまり，「出荷できる煎餅」の枚数をなるべく多くすることにした．横の行を１行も裏返さない，あるいは，縦の列を１列も裏返さない場合も考えることにする．出荷できる煎餅の枚数の最大値を出力するプログラムを書きなさい．

地震の直後に，煎餅が次の図のような状態になったとする．黒い丸が表側が焼ける状態を，白い丸が裏側が焼ける状態を表している． 

1行目を裏返すと次の図のような状態になる． 

さらに， 1列目と5列目を裏返すと次の図のような状態になる．この状態では，出荷できる煎餅は9枚である． 

ヒント

R の上限 10 は C の上限 10000 に比べて小さいことに注意せよ．

入力

入力は複数のデータセットからなる．各データセットは以下の形式で与えられる．

入力の1行目には2つの整数 R, C (1 ≤ R ≤ 10, 1 ≤ C ≤ 10 000) が空白を区切りとして書かれている．続く R 行は地震直後の煎餅の状態を表す． (i+1) 行目 (1 ≤ i ≤ R) には， C 個の整数 ai,1, ai,2, ……, ai,C が空白を区切りとして書かれており， ai,j は i 行 j 列 の煎餅の状態を表している. ai,j が 1 なら表側が焼けることを， 0 なら裏側が焼けることを表す．

C, R がともに 0 のとき入力の終了を示す.　データセットの数は 5 を超えない．

出力

データセットごとに，出荷できる煎餅の最大枚数を1行に出力する．

入出力例

入力例

2 5
0 1 0 1 0
1 0 0 0 1
3 6
1 0 0 0 1 0
1 1 1 0 1 0
1 0 1 1 0 1  
0 0

出力例

9
15

上記問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。



Sample input:
2 5
0 1 0 1 0
1 0 0 0 1
3 6
1 0 0 0 1 0
1 1 1 0 1 0
1 0 1 1 0 1
0 0


Sample output:
9
15

Submission status: Wrong Answer

Solution code:
import copy

def culc(k):
    cnt_0=0
    cnt_1=0
    for i in xrange(r):
        if osenbei1[i][k]==1:
            cnt_1+=1
        else:
            cnt_0+=1
    return max(cnt_0,cnt_1)

def rev(j):
    for i in xrange(c):
        if osenbei1[j][i]==1:
            osenbei1[j][i]=0
        else:
            osenbei1[j][i]=1

r,c=map(int,raw_input().split())
osenbei=[map(int,raw_input().split()) for _ in xrange(r)]
r_cnt=[[0]*2 for _  in xrange(r)]
c_cnt=[[0]*2 for _  in xrange(c)]
dp=[[0]*(c+1) for _ in xrange(1<<r)]
for i in xrange(1<<r):
    osenbei1=copy.deepcopy(osenbei)
    for j in xrange(r):
        if i&(1<<j):
            rev(j)
    for k in xrange(c):
        dp[i][k+1]=dp[i][k]+culc(k)
ans=-1
for i in xrange(1<<r):
    ans=max(ans,max(dp[i]))
print(ans)

Submission status: Wrong Answer

Solution code:
for e in iter(input,'0 0'):
 r,_=map(int,e.split())
 d=[int(''.join(x),2)for x in zip(*[input().split()for _ in[0]*r])]
 a=0
 for i in range(1<<r):
  b=0
  for j in d:
   c=bin(i^j).count('1')
   b+=min(c,r-c)
  a=max(a,b)
 print(a)

Submission status: Wrong Answer

Solution code:
for e in iter(input,'0 0'):
 r=int(e.split()[0])
 d=[int(''.join(x))for x in zip(*[input().split()for _ in[0]*r])]
 a=[]
 for i in range(1<<r):
  b=0
  for j in d:
   c=bin(i^j).count('1')
   b+=c if c>r//2 else r-c
  a+=[b]
 print(max(a))

Submission status: Wrong Answer

Solution code:
R, C = map(int, raw_input().split(" "))

matrix = []
for i in range(R):
    matrix.append(map(int, raw_input().split(" ")))

ans = 0
for i in xrange(1<<R):
    tmatrix = []
    tans = 0
    for j in range(R):
        turn =  i>>j & 1
        tmatrix.append([turn^v for v in matrix[j]])
    for j in range(C):
        cnt = 0
        for k in range(R):
            cnt += tmatrix[k][j]
        tans += max(cnt, R-cnt)
    ans = max(ans, tans)

print ans

Submission status: Time Limit Exceeded

Solution code:
def solve(A,flip):
	res = 0
	if len(flip) != H:
		res = max(res,solve(A,flip+[1]),solve(A,flip+[0]))
	else:
		B = [A[i][:] for i in range(H)]
		for h in range(H):
			if flip[h]:
				B[h] = [1-val for val in B[h]]
		for w in range(W):
			good = sum(1-B[h][w] for h in range(H))
			res += max(good,H-good)
	return res
	
while 1:
	H,W = map(int,raw_input().split())
	if H == W == 0:
		break
	A = [map(int,raw_input().split()) for h in range(H)]
	print solve(A,[])

Submission status: Time Limit Exceeded

Solution code:
def solve(A,flip):
	res = 0
	if len(flip) != H:
		res = max(res,solve(A,flip+[1]),solve(A,flip+[0]))
	else:
		B = [A[i][:] for i in range(H)]
		for w in range(W):
			good = sum(1-B[h][w] if flip[h] else B[h][w] for h in range(H))
			res += max(good,H-good)
	return res
	
while 1:
	H,W = map(int,raw_input().split())
	if H == W == 0:
		break
	A = [map(int,raw_input().split()) for h in range(H)]
	print solve(A,[])

Submission status: Time Limit Exceeded

Solution code:
import copy
def solve(A,flip):
	res = 0
	if len(flip) != H:
		res = max(res,solve(A,flip+[1]),solve(A,flip+[0]))
	else:
		B = copy.deepcopy(A)
		for w in range(W):
			good = sum(1-B[h][w] if flip[h] else B[h][w] for h in range(H))
			res += max(good,H-good)
	return res
	
while 1:
	H,W = map(int,raw_input().split())
	if H == W == 0:
		break
	A = [map(int,raw_input().split()) for h in range(H)]
	print solve(A,[])

Submission status: Time Limit Exceeded

Solution code:
import copy
def solve(A,flip):
	res = 0
	if len(flip) != H:
		res = max(res,solve(A,flip+[1]),solve(A,flip+[0]))
	else:
		for w in range(W):
			good = sum(1-A[h][w] if flip[h] else A[h][w] for h in range(H))
			res += max(good,H-good)
	return res
	
while 1:
	H,W = map(int,raw_input().split())
	if H == W == 0: break
	A = [map(int,raw_input().split()) for h in range(H)]
	print solve(A,[])

Submission status: Time Limit Exceeded

Solution code:
import itertools
while 1:
	H,W = map(int,raw_input().split())
	if H == W == 0: break
	A = [map(int,raw_input().split()) for h in range(H)]
	ans = 0
	for flip in itertools.product([0,1],repeat=H):
		tmp = 0
		for w in range(W):
			good = sum(1-A[h][w] if flip[h] else A[h][w] for h in range(H))
			tmp += max(good,H-good)
		ans = max(ans,tmp)
	print ans

Submission status: Time Limit Exceeded

Solution code:
import itertools
while 1:
	H,W = map(int,raw_input().split())
	if H == W == 0: break
	A = [map(int,raw_input().split()) for h in range(H)]
	ans = 0
	ls = []
	for flip in itertools.product([0,1],repeat=H):
		if flip in ls: continue
		ls += [flip] + [[1-i for i in flip]]
		tmp = 0
		for w in range(W):
			good = sum(1-A[h][w] if flip[h] else A[h][w] for h in range(H))
			tmp += max(good,H-good)
		ans = max(ans,tmp)
	print ans

Submission status: Time Limit Exceeded

Solution code:
def hantei(field,r,c):
    count=0
    for i in range(c):
        countc=0
        for j in range(r):
            countc=countc+field[j][i]
        count=max(countc,r-countc)+count
    return count
    
def turnr(field,rn,r,c):
    if rn==r:
        return hantei(field,r,c)
    field1=field
    field2=field
    field2[rn]=[not x for x in field[rn]]
    return max(turnr(field1,rn+1,r,c),turnr(field2,rn+1,r,c))

while(1):
    [r,c]=[int(x) for x in raw_input().split()]
    if r==0:
        break
    else:
        field=[]
        for i in range(r):
            field.append([int(x) for x in raw_input().split()])
        print turnr(field,0,r,c)

Submission status: Time Limit Exceeded

Solution code:
while 1:
    r, c = map(int, raw_input().split())
    if r == 0: break
    old = [None for i in range(r)]
    new = [[True]*c for i in range(r)]
    for i in range(r):
        old[i] = "".join(map(str, raw_input().split()))
    ans = 0
    n = 1<<r
    for i in range(n):
        for j in range(r):
            if i & (1<<j):
                for k in range(c):
                    new[j][k] = bool(int(old[j][k])) ^ True
            else:
                for k in range(c):
                    new[j][k] = bool(int(old[j][k]))
        ret = 0
        for j in range(c):
            cnt = 0
            for k in range(r):
                if not new[k][j]: cnt+=1
            ret += cnt if cnt > r/2 else r-cnt
        ans = max(ans, ret)
    print ans

Submission status: Time Limit Exceeded

Solution code:
import copy

def culc(k):
    cnt_0=0
    cnt_1=0
    for i in xrange(r):
        if osenbei1[i][k]==1:
            cnt_1+=1
        else:
            cnt_0+=1
    return max(cnt_0,cnt_1)

def rev(j):
    for i in xrange(c):
        if osenbei1[j][i]==1:
            osenbei1[j][i]=0
        else:
            osenbei1[j][i]=1
while 1:
    r,c=map(int,raw_input().split())
    if r==c==0:break
    osenbei=[map(int,raw_input().split()) for _ in xrange(r)]
    r_cnt=[[0]*2 for _  in xrange(r)]
    c_cnt=[[0]*2 for _  in xrange(c)]
    dp=[[0]*(c+1) for _ in xrange(1<<r)]
    for i in xrange(1<<r):
        osenbei1=copy.deepcopy(osenbei)
        for j in xrange(r):
            if i&(1<<j):
                rev(j)
        for k in xrange(c):
            dp[i][k+1]=dp[i][k]+culc(k)
    ans=-1
    for i in xrange(1<<r):
        ans=max(ans,max(dp[i]))
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
while True:
    r,c = map(int, input().split())
    if (r|c)==0: break

    array = []
    for i in range(r):
        array.append(list(map(int, input().split())))
    num = [0]*c
    for i in range(r):
        for j in range(c):
            num[j] = num[j]*2+array[i][j]

    maxx = -1
    for i in range(1 << r):
        answer = 0
        for j in range(c):
            oksenbei = bin(num[j]^i).count("1")
            answer += max(oksenbei, r-oksenbei)
        maxx = max(maxx, answer)

    print(maxx)

Submission status: Time Limit Exceeded

Solution code:
while True:
    r,c = map(int, input().split())
    if (r|c)==0: break

    array = []
    for i in range(r):
        array.append(input())
    num = [0]*c
    for i in range(r):
        for j in range(c):
            num[j] = num[j]*2+int(array[i][2*j])

    maxx = -1
    for i in range(1 << r):
        answer = 0
        for j in range(c):
            oksenbei = bin(num[j]^i).count("1")
            answer += max(oksenbei, r-oksenbei)
        maxx = max(maxx, answer)

    print(maxx)

Submission status: Time Limit Exceeded

Solution code:
def hantei(mask, pos):
    if mask & (1 << pos):
        return True
    else:
        return False


if __name__ == '__main__':
    while True:
        R, C = list(map(int, input().split()))
        if R == 0 and C == 0: break
        mesh = [list(map(int, input().split())) for i in range(R)]
        ans = 0
        for mask in range(0, (1 << R)):
            tmp_sum = [0 for i in range(C)]
            for pos in range(0, R):
                if hantei(mask, pos):
                    for i in range(0, C):
                        if mesh[pos][i] == 1:
                            tmp_sum[i] += 1
                else:
                    for i in range(0, C):
                        if mesh[pos][i] == 0:
                            tmp_sum[i] += 1
            tmp_ans = 0
            for i in range(0, C):
                if tmp_sum[i] < R / 2:
                    tmp_ans += R - tmp_sum[i]
                else:
                    tmp_ans += tmp_sum[i]
            ans = max([ans, tmp_ans])
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
import itertools
def solve():
    max = 0
    for i in range(H):
        for rs in itertools.combinations(range(H),i+1):
            for j in range(W):
                for cs in itertools.combinations(range(W),j+1):
                    tmp = countReverse(rs,cs)
                    if tmp>max: max = tmp
                    
    for i in range(H):
        cs = []
        for rs in itertools.combinations(range(H),i+1):
            tmp = countReverse(rs,cs)
            if tmp>max: max = tmp

    for j in range(W):
        rs = []
        for cs in itertools.combinations(range(W),j+1):
            tmp = countReverse(rs,cs)
            if tmp>max: max = tmp
            
    return max

def countZero(tmpO):
    c = 0
    for i in range(H):
        c += tmpO[i].count('0')
    return c

def countReverse(rs,cs):
    tmpO = copy.deepcopy(osenbei)
    tmpO = reverseR(tmpO, rs)
    tmpO = reverseC(tmpO, cs)
    return countZero(tmpO)

def reverseR(tmpO, rs):
    for r in rs:
        for i in range(W):
            if tmpO[r][i] == '0': tmpO[r][i] = '1'
            elif tmpO[r][i] == '1': tmpO[r][i] = '0'
    return tmpO

def reverseC(tmpO, cs):
    for c in cs:
        for i in range(H):
            if tmpO[i][c] == '0': tmpO[i][c] = '1'
            elif tmpO[i][c] == '1': tmpO[i][c] = '0'
    return tmpO

H = -1
W = -1
osenbei = []
counter = -1

line = input()
while line!='0 0':
    if H == -1:
        H,W = map(int,line.split(' '))
        osenbei = [[-1 for i in range(W)] for j in range(H)]
        counter = 0
    else:
        osenbei[counter] = line.split(' ')
        counter += 1
    if counter == H:
        print(solve())
        H = -1
        W = -1
        
    line = input()

Submission status: Time Limit Exceeded

Solution code:
import sys


def solve(A, R, C):
    res = 0
    for i in range(2 ** R):
        s = 0
        for j in range(C):
            s2 = 0
            for k in range(R):
                a = A[k][j]
                if a ^ ((i >> k) & 1):
                    s2 += 1
            s += max(s2, R-s2)
        res = max(res, s)
    print(res)


while True:
    R, C = map(int, sys.stdin.readline().split())
    if R == 0 and C == 0:
        break

    A = []
    for _ in range(R):
        A.append(list(map(int, sys.stdin.readline().split())))
    solve(A, R, C)

Submission status: Time Limit Exceeded

Solution code:
import copy
import itertools
def solve():
    max = 0
    for i in range(-1,H):
        for rs in itertools.combinations(range(H),i+1):
            tmpMap = copy.deepcopy(osenbei)
            tmpMap = reverseR(tmpMap, rs)
            cs = []
            for j in range(W):
                if needReverse(tmpMap,j):
                    cs.append(j)
            tmpMap = reverseC(tmpMap, cs)
            tmp = countZero(tmpMap)
            if max < tmp:
                max = tmp
    return max

def needReverse(tmpMap,j):
    #?????£???????????????????????????????????????
    sum = 0
    for a in range(H):
        sum += int(tmpMap[a][j])
    return sum>(H/2)

def countZero(tmpO):
    c = 0
    for i in range(H):
        c += tmpO[i].count('0')
    return c

def countReverse(rs,cs):
    tmpO = copy.deepcopy(osenbei)
    tmpO = reverseR(tmpO, rs)
    tmpO = reverseC(tmpO, cs)
    return countZero(tmpO)

def reverseR(tmpO, rs):
    for r in rs:
        for i in range(W):
            if tmpO[r][i] == '0': tmpO[r][i] = '1'
            elif tmpO[r][i] == '1': tmpO[r][i] = '0'
    return tmpO

def reverseC(tmpO, cs):
    for c in cs:
        for i in range(H):
            if tmpO[i][c] == '0': tmpO[i][c] = '1'
            elif tmpO[i][c] == '1': tmpO[i][c] = '0'
    return tmpO

H = -1
W = -1
osenbei = []
counter = -1

line = input()
while line!='0 0':
    if H == -1:
        H,W = map(int,line.split())
        osenbei = [[-1 for i in range(W)] for j in range(H)]
        counter = 0
    else:
        osenbei[counter] = line.split()
        counter += 1
    if counter == H:
        print(solve())
        H = -1
        W = -1
        
    line = input()

Submission status: Time Limit Exceeded

Solution code:
import sys


def solve(A, R, C):
    res = 0
    for i in range(2 ** (R-1)):
        s = 0
        for j in range(C):
            number_of_0s = 0
            for k in range(R):
                a = A[k][j]
                flip_kth_row = (i >> k) & 1
                if a and flip_kth_row or ((not a) and (not flip_kth_row)):
                    number_of_0s += 1
            number_of_1s = R - number_of_0s
            s += max(number_of_1s, number_of_0s)
        res = max(res, s)
    print(res)


while True:
    R, C = map(int, sys.stdin.readline().split())
    if R == 0 and C == 0:
        break

    A = []
    for _ in range(R):
        A.append(list(map(int, sys.stdin.readline().split())))
    solve(A, R, C)

Submission status: Time Limit Exceeded

Solution code:
while True:
  r,c = map(int,input().split())
  if not r and not c:
    break
  lst = []
  for i in range(r):
    lst.append(list(map(int,input().split())))
  def dfs(l,n):
    if n == r:
      ans = 0
      for i in range(c):
        count = 0
        for j in range(r):
          if l[j][i]:
            count += 1
        ans += max(count, r - count)
      return ans
    else:
      return max(dfs(l + [[0 if i else 1 for i in lst[n]]],n + 1),
                 dfs(l + [[1 if i else 0 for i in lst[n]]],n + 1))
  print(dfs([],0))

Submission status: Time Limit Exceeded

Solution code:
def main():
  while True:
    r,c = map(int,input().split())
    if not r and not c:
      break
    lst = []
    for i in range(r):
      lst.append(list(map(int,input().split())))
    def dfs(l,n):
      if n == r:
        ans = 0
        for i in range(c):
          count = 0
          for j in range(r):
            if l[j][i]:
              count += 1
          ans += max(count, r - count)
        return ans
      else:
        return max(dfs(l + [[0 if i else 1 for i in lst[n]]],n + 1),
                   dfs(l + [[1 if i else 0 for i in lst[n]]],n + 1))
    print(dfs([],0))

main()

Submission status: Time Limit Exceeded

Solution code:
for e in iter(input,'0 0'):
 H,W=map(int,e.split())
 s=[[*map(int,input().split())]for _ in[0]*H]
 a=0
 for x in range(2**H):
     t=[[c^int(b)for c in r]for r,b in zip(s,bin(x)[2:].zfill(H))]
     a=max(a,sum(max(sum(c),H-sum(c))for c in zip(*t)))
 print(a)

Submission status: Time Limit Exceeded

Solution code:
for e in iter(input,'0 0'):
 H,W=map(int,e.split())
 s=[[*map(int,input().split())]for _ in[0]*H]
 a=0
 for x in range(2**H):
     t=[[c^(1>>b&x)for c in r]for r,b in zip(s,range(H))]
     a=max(a,sum(max(sum(c),H-sum(c))for c in zip(*t)))
 print(a)

Submission status: Time Limit Exceeded

Solution code:
import sys
e=sys.stdin.readlines()
while 1:
 H,W=map(int,e[0].split())
 if H<1:break
 s=[[*map(int,r.split())]for r in e[1:H+1]]
 a=0
 for x in range(2**H):
  t=[[c^1>>b&x for c in map(int,r)]for r,b in zip(s,range(H))]
  a=max(a,sum(max(sum(c),H-sum(c))for c in zip(*t)))
 print(a)
 del e[:H+1]

Submission status: Time Limit Exceeded

Solution code:
def v():
 for e in iter(input,'0 0'):
  r=int(e.split()[0])
  d=[int(''.join(x),2)for x in zip(*[input().split()for _ in[0]*r])]
  a=0
  for m in range(1<<~-r):
   t=0
   for s in d:
    c=sum(map(int,bin(m^s)[2:]))
    t+=c if c>r//2 else r-c
   if a<t:a=t
  print(a)
if'__main__'==__name__:v()

Submission status: Time Limit Exceeded

Solution code:
import sys

#fp = open("input.txt", "r")
fp = sys.stdin

r = 0
c = 0

def pow2(n):
    ret = 1
    for i in xrange(n):
        ret *= 2
    return ret

def turnRow(senbei, op):
    ret = senbei[:]
    li = [not(op & (1 << i)) for i in xrange(r)]
    for i in xrange(r):
        if li[i]:
            for j in xrange(i*c, (i+1)*c):
                ret[j] = not ret[j]
    return ret

def turnColumn(senbei):
    ret = senbei[:]
    for i in xrange(c):
        li = [ret[i+c*j] for j in xrange(r)]
        if li.count(False) * 2 > r:
            for j in xrange(r):
                ret[i+c*j] = not ret[i+c*j]
    return ret
        
while True:
    r, c = map(int, fp.readline()[:-1].split(" "))
    if r == 0 and c == 0:
        break

    senbei = []
    for i in xrange(r):
        senbei.extend(map(lambda x: x != "1", fp.readline()[:-1].split(" ")))

    max_count = 0
    for i in xrange(pow2(r)):
        turned = turnRow(senbei, i)
        res = turnColumn(turned)
        count = res.count(True)
        if count > max_count:
            max_count = count
    print max_count

Submission status: Time Limit Exceeded

Solution code:
import sys

#fp = open("input.txt", "r")
fp = sys.stdin

r = 0
c = 0

def countBit(n):
    ret = 0
    for i in xrange(r):
        if n & (1 << i):
            ret += 1
    return ret

def turnRow(senbei, op):
    for i in xrange(c):
        senbei[i] ^= op

def countWelldone(senbei):
    ret = 0
    for i in senbei:
        count = countBit(i)
        ret += max(count, r - count)
    return ret

while True:
    r, c = map(int, fp.readline()[:-1].split(" "))
    if r == 0 and c == 0:
        break

    senbei = [0 for i in xrange(c)]
    for i in xrange(r):
        buf = map(int, fp.readline()[:-1].split(" "))
        for j in xrange(c):
            senbei[j] <<= 1
            senbei[j] |= buf[j]

    max_count = 0
    for i in xrange(2**r):
        cloned = senbei[:]
        turnRow(cloned, i)
        count = countWelldone(cloned)
        if count > max_count:
            max_count = count

    print max_count

Submission status: Time Limit Exceeded

Solution code:
import itertools
from copy import deepcopy

def turnOverRow(now_state,combs,c):
    for i in combs:
        for j in range(c):
            now_state[i][j]=0 if now_state[i][j]==1 else 1

def turnOverCol(now_state,r,c):
    h=r/2
    for i in range(c):
        cnt=0
        for j in range(r):
            if now_state[j][i]==1:
                cnt+=1
        if cnt>h:
            for j in range(r):
                now_state[j][i]=1 if now_state[j][i]==0 else 0

def countMax(now_state,r):
    return sum(sum(now_state[i]) for i in range(r))

while True:
    r,c=map(int,raw_input().split())
    if r==c==0:break
    init_state=[map(int,raw_input().split()) for i in range(r)]
    now_state=deepcopy(init_state)
    ans=10000000000
    for i in range(r+1):
        for combs in itertools.combinations(range(r),i):
            turnOverRow(now_state,combs,c)
            turnOverCol(now_state,r,c)
            ans=min(ans,countMax(now_state,r))
            now_state=deepcopy(init_state) #initialization
    print r*c-ans

Submission status: Time Limit Exceeded

Solution code:
while True:
    r,c=map(int,raw_input().split())
    if r==c==0:break
    state=[raw_input().split() for i in range(r)]
    state=map(list,zip(*state))
    new_state=[int("".join(ls),2) for ls in state]
    ans=0
    h=r/2
    for i in range(pow(2,r)):
        cnt=0
        for j in new_state:
            b=format(i^j,"b")
            n=b.count("1")
            cnt+=n if n>h else r-n
        ans=max(ans,cnt)
    print ans

Submission status: Time Limit Exceeded

Solution code:
def inv(row):
    return map(lambda x: 1 if x == 0 else 0, row)

def count(col):
    tmp = sum(col)
    return max(len(col) - tmp, tmp)

def solve(field, bs):
    for i, b in enumerate(bs):
        if b == 1:
            field[i] = inv(field[i])
    return sum(count(col) for col in zip(*field))

while True:
    R, C = map(int, raw_input().split())
    if R | C == 0:
        break
    field = [map(int, raw_input().split()) for _ in xrange(R)]
    print max(solve([f[:] for f in field], bs) 
              for bs in map(lambda n: map(int, list(format(n, "b").zfill(R))),
                            xrange(1 << R)))

Submission status: Time Limit Exceeded

Solution code:
while 1:    
    R, C = map(int, raw_input().split(" "))
    if R==0 and C==0:
        break

    matrix = []
    for i in range(R):
        matrix.append(map(int, raw_input().split(" ")))
    
    ans = 0
    for i in xrange(1<<R):
        tmatrix = []
        tans = 0
        for j in range(R):
            turn =  i>>j & 1
            tmatrix.append([turn^v for v in matrix[j]])
        for j in range(C):
            cnt = 0
            for k in range(R):
                cnt += tmatrix[k][j]
            tans += max(cnt, R-cnt)
        ans = max(ans, tans)
    print ans

Submission status: Time Limit Exceeded

Solution code:
import itertools
while 1:
	R,C = map(int,raw_input().split())
	if R == 0: break
	A = [map(int,raw_input().split()) for i in range(R)]
	ans = 0
	for n in range(1,R+1):
		for flip in itertools.combinations(range(R),n):
			cur = 0
			for ci in range(C):
				s = 0
				for ri in range(R):
					s += A[ri][ci] if ri not in flip else 1 - A[ri][ci]
				cur += max(s,R-s)
			ans = max(ans,cur)
	print ans

Submission status: Time Limit Exceeded

Solution code:
import itertools
while 1:
	R,C = map(int,raw_input().split())
	if R == 0: break
	A = [map(int,raw_input().split()) for i in range(R)]
	ans = 0
	for n in range(1,R+1):
		for flip in itertools.combinations(range(R),n):
			cur = 0
			for ci in range(C):
				s = sum((A[ri][ci] if ri not in flip else 1 - A[ri][ci]) for ri in range(R))
				cur += max(s,R-s)
			ans = max(ans,cur)
	print ans

Submission status: Accepted

Solution code:

def hanteib(bfield,r,c):
    count=0
    for b in bfield:
        ccount=bin(b).count("1")
        count=count+max(ccount,r-ccount)
    return count

def turnrb(bfield,rn,r,c):
    if rn==r:
        return hanteib(bfield,r,c)
    bfield1=bfield
    bfield2=[b ^ 2**rn for b in bfield]
    return max(turnrb(bfield1,rn+1,r,c),turnrb(bfield2,rn+1,r,c))

while(1):
    [r,c]=[int(x) for x in raw_input().split()]
    if r==0:
        break
    else:
        field=[]
        bfield=[]
        for i in range(r):
            field.append([int(x) for x in raw_input().split()])
        for j in range(c):
            bb=0
            for i in range(r):
                bb=bb+2**i*field[i][j]
            bfield.append(bb)
        print turnrb(bfield,0,r,c)

Submission status: Accepted

Solution code:
while 1:
    r, c = map(int, raw_input().split())
    if r == 0: break
    old = [raw_input().split() for i in range(r)]
    old = map(list, zip(*old))
    new = [int("".join(lst),2) for lst in old]
    ans = 0
    for i in range(1<<r):
        ret = 0
        for j in new:
            cnt = bin(i^j).count('1')
            ret += cnt if cnt > r/2 else r-cnt
        ans = max(ans, ret)
    print ans

Submission status: Accepted

Solution code:
while 1:
    r,c=map(int,raw_input().split())
    if r==c==0:break
    osenbei=[map(int,raw_input().split()) for _ in xrange(r)]
    r_osenbei=[0]*c
    for i in xrange(c):
        st=""
        for j in xrange(r):
            st+=str(osenbei[j][i])
        r_osenbei[i]=int(st,2)
    ans=-1
    for i in xrange(1<<r):
        cnt=0
        for j in xrange(c):
            n=bin(i^r_osenbei[j]).count('1')
            cnt+=max(n,r-n)
        ans=max(ans,cnt)
    print(ans)

Submission status: Accepted

Solution code:
while 1:
    r,c=map(int,raw_input().split())
    if r==c==0:break
    osenbei=[map(int,raw_input().split()) for _ in xrange(r)]
    r_osenbei=[None]*c
    for i in xrange(c):
        st=""
        for j in xrange(r):
            st+=str(osenbei[j][i])
        r_osenbei[i]=int(st,2)
    ans=-1
    for i in xrange(1<<r):
        cnt=0
        for j in xrange(c):
            n=bin(i^r_osenbei[j]).count('1')
            cnt+=max(n,r-n)
        ans=max(ans,cnt)
    print(ans)

Submission status: Accepted

Solution code:
while 1:
    r,_=map(int,input().split())
    if r==0:break
    prv=[input().split() for _ in[0]*r]
    prv=map(list,zip(*prv))
    now=[int(''.join(x),2)for x in prv];a=0
    for i in range(1<<r):
        b=0
        for j in now:
            c=bin(i^j).count('1')
            b+=c if c>r//2else r-c
        a=max(a,b)
    print(a)

Submission status: Accepted

Solution code:
while True:
    r,c = map(int, input().split())
    if (r|c)==0: break

    num = [0]*c
    for i in range(r):
        instr = input()
        for j in range(c):
            num[j] = num[j]*2+int(instr[2*j])

    maxx = -1
    for i in range(1 << r):
        answer = 0
        for j in range(c):
            oksenbei = bin(num[j]^i).count("1")
            answer += oksenbei if oksenbei*2//r >= 1 else r-oksenbei
        if maxx < answer:
            maxx = answer

    print(maxx)

Submission status: Accepted

Solution code:
while True:
    r,c = map(int, input().split())
    if (r|c)==0: break

    num = [0]*c
    for i in range(r):
        instr = input()
        for j in range(c):
            num[j] = (num[j]<<1) + (instr[2*j]=="1")

    maxx = -1
    for i in range(1 << r):
        answer = 0
        for j in range(c):
            oksenbei = bin(num[j]^i).count("1")
            answer += oksenbei if oksenbei*2//r >= 1 else r-oksenbei
        if maxx < answer:
            maxx = answer

    print(maxx)

Submission status: Accepted

Solution code:
while 1:
    r, c = map(int, raw_input().split())
    if r == 0: break
    old = [raw_input().split() for i in range(r)]
    old = map(list, zip(*old))
    new = [int("".join(lst),2) for lst in old]
    ans = 0
    for i in range(1<<(r-1)):
        ret = 0
        for j in new:
            cnt = bin(i^j).count('1')
            ret += cnt if cnt > r/2 else r-cnt
        ans = max(ans, ret)
    print ans

Submission status: Accepted

Solution code:
def solve():
    import sys
    input_lines = sys.stdin.readlines()
    
    while True:
        R, C = map(int, input_lines[0].split())
        if R == 0:
            break
        
        rows = map(lambda x: x.rstrip().replace(' ', ''), input_lines[1:R+1])
        cols = [int(''.join(t_c), base=2) for t_c in zip(*rows)]
        
        ans = []
        b = 2 ** R
        flip_check = [True] * (b)
        
        for m in range(b):
            if flip_check[m]:
                flip_check[~m] = False
                shipment = 0
                for s in cols:
                    bit_cnt = bin(m ^ s).count('1')
                    shipment += max(bit_cnt, R - bit_cnt)
                ans.append(shipment)
        
        print(max(ans))
        
        del input_lines[:R+1]

solve()

Submission status: Accepted

Solution code:
def solve():
    import sys
    input_lines = sys.stdin.readlines()
    
    while True:
        R, C = map(int, input_lines[0].split())
        if R == 0:
            break
        
        rows = map(lambda x: x.rstrip().replace(' ', ''), input_lines[1:R+1])
        cols = [int(''.join(t_c), base=2) for t_c in zip(*rows)]
        
        ans = []
        
        for m in range(2 ** (R - 1)):
            shipment = 0
            for s in cols:
                bit_cnt = bin(m ^ s).count('1')
                shipment += max(bit_cnt, R - bit_cnt)
            ans.append(shipment)
        
        print(max(ans))
        
        del input_lines[:R+1]

solve()

Submission status: Accepted

Solution code:
for e in iter(input,'0 0'):
 r,_=map(int,e.split())
 d=[int(''.join(x),2)for x in zip(*[input().split()for _ in[0]*r])]
 a=0
 for i in range(1<<r):
  b=0
  for j in d:
   c=bin(i^j).count('1')
   b+=c if c>r//2else r-c
  a=max(a,b)
 print(a)

Submission status: Accepted

Solution code:
for e in iter(input,'0 0'):
 r,_=map(int,e.split())
 d=[int(''.join(x),2)for x in zip(*[input().split()for _ in[0]*r])]
 a=0
 for i in range(1<<r):
  b=0
  for j in d:
   c=bin(i^j).count('1')
   b+=max(c,r-c)
  a=max(a,b)
 print(a)

Submission status: Accepted

Solution code:
for e in iter(input,'0 0'):
 r,_=map(int,e.split())
 d=[int(''.join(x),2)for x in zip(*[input().split()for _ in[0]*r])]
 a=0
 for i in range(1<<r):
  b=0
  for j in d:
   c=bin(i^j).count('1')
   b+=[r-c,c][c>r//2]
  if b>a:a=b
 print(a)

Submission status: Accepted

Solution code:
for e in iter(input,'0 0'):
 r,_=map(int,e.split())
 d=[int(''.join(x),2)for x in zip(*[input().split()for _ in[0]*r])]
 a=0
 for i in range(1<<r):
  b=0
  for j in d:
   c=bin(i^j).count('1')
   b+=c if c>r//2 else r-c
  a=max(a,b)
 print(a)

Submission status: Accepted

Solution code:
for e in iter(input,'0 0'):
 r=int(e.split()[0])
 d=[int(''.join(x),2)for x in zip(*[input().split()for _ in[0]*r])]
 a=0
 for i in range(1<<r):
  b=0
  for j in d:
   c=bin(i^j).count('1')
   b+=c if c>r//2 else r-c
  a=max(a,b)
 print(a)

Submission status: Accepted

Solution code:
for e in iter(input,'0 0'):
 r=int(e.split()[0])
 d=[int(''.join(x),2)for x in zip(*[input().split()for _ in[0]*r])]
 a=0
 for i in range(1<<r):
  b=0
  for j in d:
   c=bin(i^j).count('1')
   b+=c if c>r//2 else r-c
  if a<b:a=b
 print(a)

Submission status: Accepted

Solution code:
for e in iter(input,'0 0'):
 r=int(e.split()[0])
 d=[int(''.join(x),2)for x in zip(*[input().split()for _ in[0]*r])]
 a=[]
 for i in range(1<<r):
  b=0
  for j in d:
   c=bin(i^j).count('1')
   b+=c if c>r//2 else r-c
  a+=[b]
 print(max(a))