Problem:


Score : 500 points

Problem Statement

We have a chocolate bar partitioned into H horizontal rows and W vertical columns of squares.

The square (i, j) at the i-th row from the top and the j-th column from the left is dark if S_{i,j} is 0, and white if S_{i,j} is 1.

We will cut the bar some number of times to divide it into some number of blocks. In each cut, we cut the whole bar by a line running along some boundaries of squares from end to end of the bar.

How many times do we need to cut the bar so that every block after the cuts has K or less white squares?

Constraints

1 \leq H \leq 10

1 \leq W \leq 1000

1 \leq K \leq H \times W

S_{i,j} is 0 or 1.

Input

Input is given from Standard Input in the following format:

H W K
S_{1,1}S_{1,2}...S_{1,W}
:
S_{H,1}S_{H,2}...S_{H,W}

Output

Print the number of minimum times the bar needs to be cut so that every block after the cuts has K or less white squares.

Sample Input 1

3 5 4
11100
10001
00111

Sample Output 1

2

For example, cutting between the 1-st and 2-nd rows and between the 3-rd and 4-th columns - as shown in the figure to the left - works.

Note that we cannot cut the bar in the ways shown in the two figures to the right.

Sample Input 2

3 5 8
11100
10001
00111

Sample Output 2

0

No cut is needed.

Sample Input 3

4 10 4
1110010010
1000101110
0011101001
1101000111

Sample Output 3

3



Sample input:
3 5 4
11100
10001
00111


Sample output:
2

Submission status: Wrong Answer

Solution code:
import re

H,W,K = map(int,input().split())
grid = [[0 for i in range(W+1)]]
for i in range(H):
  S = input()
  grid.append([0]+[ int(S[i]) for i in range(W) ])

#累積和gridの作成
#行について
for i in range(H+1):
  for j in range(W):
    grid[i][j+1] += grid[i][j]
#列について
for j in range(W+1):
  for i in range(H):
    grid[i+1][j] += grid[i][j]   

min_cnt = 10011
#横の区切りを作る
for h in range(2**(H-1)):
  cnt = 0
  #二進数の文字列を取得
  bin_str = format(h,"0{}b".format(H-1)) 
  #区切りのインデックスリスト
  l_p =[1]+[ x.start()+2 for x in re.finditer("1",bin_str) ] +[H+1]

  #cntに区切りの分だけ付け加える
  cnt = cnt + len(l_p) - 2
  
  ws = 0
  for w in range(1,W+1):
    for k in range(len(l_p)-1):
      if grid[l_p[k+1]-1][w]- (grid[l_p[k]-1][w]+grid[l_p[k+1]-1][ws]-grid[l_p[k]-1][ws]) > K:
        cnt = cnt + 1
        ws = w-1
        break    
  min_cnt = min(min_cnt,cnt)

###
print(min_cnt)

Submission status: Wrong Answer

Solution code:
h,w,k = map(int,input().split())
s = [list(map(int,input())) for _ in range(h)]
    
ans = h*w
for div in range(1<<(h-1)):
    row = 0
    S = [[0]*w]
    S[row] = [s[0][i] for i in range(w)]
    for i in range(1,h):
        if 1&(div>>i-1):
            row += 1
            S.append([s[i][j] for j in range(w)])
        else:
            S[row] = [S[row][j]+s[i][j] for j in range(w)]
            
    count = [0]*(row+1)
    ans_ = row
    for i in range(w):
        for j in range(row+1):
            count[j] += S[j][i]
            if count[j] > k:
                ans_+=1
                count = [0]*(row+1)
                for l in range(row+1):
                    count[l] += S[l][i]
                break
        if ans_ >= ans:
            break
            
    ans = min(ans,ans_)

print(ans)

Submission status: Wrong Answer

Solution code:
import re
import numpy as np

H,W,K = map(int,input().split())
grid = [[0 for i in range(W+1)]]
for i in range(H):
  S = input()
  grid.append([0]+[ int(S[i]) for i in range(W) ])

#累積和gridの作成
#行について
for i in range(H+1):
  for j in range(W):
    grid[i][j+1] += grid[i][j]
#列について
for j in range(W+1):
  for i in range(H):
    grid[i+1][j] += grid[i][j]   

min_cnt = 10011
#横の区切りを作る
for h in range(2**(H-1)):
  cnt = 0
  #二進数の文字列を取得
  bin_str = format(h,"0{}b".format(H-1)) 
  #区切りのインデックスリスト
  l_p =[1]+[ x.start()+2 for x in re.finditer("1",bin_str) ] +[H+1]

  #cntに区切りの分だけ付け加える
  cnt = cnt + len(l_p) - 2
  
  ws = 0
  for w in range(1,W+1):
    for k in range(len(l_p)-1):
      if grid[l_p[k+1]-1][w]- (grid[l_p[k]-1][w]+grid[l_p[k+1]-1][ws]-grid[l_p[k]-1][ws]) > K:
        cnt = cnt + 1
        ws = w-1
        break    
  min_cnt = min(min_cnt,cnt)

###
print(min_cnt)

Submission status: Wrong Answer

Solution code:
    #端から端まで割る
#h<=10に対しては全探索
#wについては極力割らない

h,w,k = map(int, input().split( ))

s= [list(map(int,list(input()))) for i in range(h)]

bit = 1<<h
ans = 10000
for b in range(bit):
    cut = [0]+[j for j in range(1,h) if (b>>j)&1]+[h]
    tmp = len(cut)-2
    white = [0]*h
    for j in range(w):
        for i in range(h): 
            white[i] += (s[i][j])&1
        for u in range(1,len(cut)):
            tmp2 = 0
            for t in range(cut[u-1],cut[u]):
                tmp2 += white[t]
            if tmp2>k and j:##
                tmp += 1
                white = [s[x][j] for x in range(h)]##
            tmp2 = 0
        for u in range(1,len(cut)):###1列でもアウトな場合
            for t in range(cut[u-1],cut[u]):
                tmp2 += white[t]
            if tmp2>k and j:
                tmp = 100000
                break
    if ans > tmp:
        ans = tmp
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from itertools import product
 
H, W, K = map(int, input().split())
S = [input() for _ in range(H)]
 
i = 0
while i < len(S):
  if '1' in S[i]:
    i += 1
  else:
    del S[i]
H = len(S)
 
C = [[int(s[i]) for s in S] for i in range(W)]#列を一括りにする
print(C)
total = sum(sum(c) for c in C)#すべての値の合計を算出
 
if total <= K:
  answer = 0
else:
  answer = H * W
  for X in product([False, True], repeat=H-1):#Hは行数
    #あるXについて一回目のfor文が回る
    ans = sum(X)#Trueの数を換算
    if ans > answer:
      continue
    M = [[0]]
    for i, x in enumerate(X):
      if x:#Trueなら実行
        M.append([])#Trueの数の配列が作成される
      M[-1].append(i+1)#一番最後にその番目をappendする
    D = [0] * len(M)#初期値を設定
    for c in C:
      for k, m in enumerate(M):
        D[k] += sum(c[i] for i in m)#k番目の要素に足していく
        #Dにどんどん代入することによってどの列まで足すことができるか算出することができる
      if any(d > K for d in D):#一つでもKを超えていたら
        ans += 1
        if ans > answer:
          break
        D = [sum(c[i] for i in m) for m in M]#Dの更新(1番最初のDに戻る)
        if any(d > K for d in D):#一つでもKを超えていたら
          ans = answer + 1#ansの更新
          break
    answer = min(answer, ans)

print(answer)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from itertools import product
 
H, W, K = map(int, input().split())
S = [input() for _ in range(H)]
 
i = 0
while i < len(S):
  if '1' in S[i]:
    i += 1
  else:
    del S[i]
H = len(S)
 
C = [[int(s[i]) for s in S] for i in range(W)]#列を一括りにする
 
total = sum(sum(c) for c in C)#すべての値の合計を算出
 
if total <= K:
  answer = 0
else:
  answer = H * W
  for X in product([False, True], repeat=H-1):#Hは行数
    #あるXについて一回目のfor文が回る
    ans = sum(X)#Trueの数を換算
    if ans > answer:
      continue
    M = [[0]]
    for i, x in enumerate(X):
      if x:#Trueなら実行
        M.append([])#Trueの数の配列が作成される
      M[-1].append(i+1)#一番最後にその番目をappendする
    print('M{}'.format(M))
    D = [0] * len(M)#初期値を設定
    for c in C:
      print('c{}'.format(c))
      for k, m in enumerate(M):
        print('m{}'.format(m))
        D[k] += sum(c[i] for i in m)#k番目の要素に足していく
        #Dにどんどん代入することによってどの列まで足すことができるか算出することができる
      print('D1{}'.format(D))
      if any(d > K for d in D):#一つでもKを超えていたら
        ans += 1
        if ans > answer:
          break
        D = [sum(c[i] for i in m) for m in M]#Dの更新(1番最初のDに戻る)
        print('D2{}'.format(D))
        if any(d > K for d in D):#一つでもKを超えていたら
          ans = answer + 1#ansの更新
          break
    answer = min(answer, ans)

print(answer)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from itertools import product
 
H, W, K = map(int, input().split())
S = [input() for _ in range(H)]
 
C = [[int(s[i]) for s in S] for i in range(W)]#列を一括りにする
 
total = sum(sum(c) for c in C)#すべての値の合計を算出
 
if total <= K:
  answer = 0
else:
  answer = H * W
  for X in product([False, True], repeat=H-1):#Hは行数
    #あるXについて一回目のfor文が回る
    ans = sum(X)#Trueの数を換算
    if ans > answer:
      continue
    M = [[0]]
    for i, x in enumerate(X):
      if x:#Trueなら実行
        M.append([])#Trueの数の配列が作成される
      M[-1].append(i+1)#一番最後にその番目をappendする
    print('M{}'.format(M))
    D = [0] * len(M)#初期値を設定
    for c in C:
      print('c{}'.format(c))
      for k, m in enumerate(M):
        print('m{}'.format(m))
        D[k] += sum(c[i] for i in m)#k番目の要素に足していく
        #Dにどんどん代入することによってどの列まで足すことができるか算出することができる
      print('D1{}'.format(D))
      if any(d > K for d in D):#一つでもKを超えていたら
        ans += 1
        if ans > answer:
          break
        D = [sum(c[i] for i in m) for m in M]#Dの更新(1番最初のDに戻る)
        print('D2{}'.format(D))
        if any(d > K for d in D):#一つでもKを超えていたら
          ans = answer + 1#ansの更新
          break
    answer = min(answer, ans)

print(answer)

Submission status: Wrong Answer

Solution code:
import itertools

H, W, K = map(int, input().split())
S = [input() for _ in range(H)]
ans = 1e4
for t in itertools.product([0, 1], repeat=H-1):
    cnt = t.count(1)
    SW = []
    tmp = [int(s) for s in S[0]]
    for i, c in enumerate(t):
        if c:
            SW.append(tmp)
            tmp = [int(s) for s in S[i+1]]
        else:
            tmp = [tmp[j] + int(S[i+1][j]) for j in range(W)]
    SW.append(tmp)
    H_ = len(SW)
    sums = [0] * H_
    for w in range(W):
        sumtmp = [sums[i] + SW[i][w] for i in range(H_)]
        if max(sumtmp) > K:
            cnt += 1
            sums = [SW[i][w] for i in range(H_)]
        else:
            sums = sumtmp
    ans = min(ans, cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import time
import numpy as np
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
H, W, K = [int(x) for x in input().strip().split()]
G = np.zeros((H, W), dtype=int)

for h in range(H):
    G[h, :] = np.array([int(x) for x in list(input().strip())])

ans = float('inf')
for i in range(1 << H-1):
    l = []
    for j in range(H-1):
        if i >> j & 1:
            l.append(j+1)
    # print(l)
    if len(l):
        l = [0] + l + [H]
        G2 = []
        for j in range(1, len(l)):
            G2.append(G[l[j-1]:l[j], :].sum(axis=0))
    else:
        G2 = [G.sum(axis=0)]
    t_ans = len(l)
    col = 0
    # print(G2)
    offset = 0
    f = True
    for g2 in G2:
        if g2.max() > K:
            f = False
            break
    if not f:
        continue
    while len(G2[0]):
        ind = len(G2[0])+1
        for g2 in G2:
            e2 = g2.cumsum()
            # print('e2 = {}'.format(e2))
            l = 0
            r = len(g2)
            while l + 1 < r:
                m = (l+r)//2
                if e2[m] <= K:
                    l = m
                else:
                    r = m
            ind = min(ind, l)
        t_ans += 1
        for i in range(len(G2)):
            G2[i] = G2[i][ind+1:]
    ans = min(ans, t_ans)
    # print(ans)
print(ans-1)

Submission status: Wrong Answer

Solution code:
import sys
import time
import numpy as np
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
H, W, K = [int(x) for x in input().strip().split()]
G = np.zeros((H, W), dtype=int)

for h in range(H):
    G[h, :] = np.array([int(x) for x in list(input().strip())])

ans = float('inf')
for i in range(1 << H-1):
    l = []
    for j in range(H-1):
        if i >> j & 1:
            l.append(j+1)
    print(l)
    if len(l):
        l = [0] + l + [H]
        G2 = []
        for j in range(1, len(l)):
            G2.append(G[l[j-1]:l[j], :].sum(axis=0))
    else:
        G2 = [G.sum(axis=0)]
    t_ans = len(l)
    col = 0
    print(G2)
    offset = 0
    f = True
    for g2 in G2:
        if g2.max() > K:
            f = False
            break
    if not f:
        continue
    while len(G2[0]):
        ind = len(G2[0])+1
        for g2 in G2:
            e2 = g2.cumsum()
            print('e2 = {}'.format(e2))
            l = 0
            r = len(g2)
            while l + 1 < r:
                m = (l+r)//2
                if e2[m] <= K:
                    l = m
                else:
                    r = m
            ind = min(ind, l)
        t_ans += 1
        for i in range(len(G2)):
            G2[i] = G2[i][ind+1:]
    ans = min(ans, t_ans)
    print(ans)
print(ans-1)

Submission status: Wrong Answer

Solution code:
import numpy as np
H,W,K=map(int,input().split())
CO=np.array([[0]*W]*H)
DO=np.array([[0]*W]*H)
for i in range(H):
 C=input()
 for j in range(W):
  DO[i][j]=int(C[j])
F=1000000
for s in range(2**(H-1)):
 D=0
 E=0
 Sui=[0]*(H-1)
 for t in range(H-1):
  if ((s >> t) & 1):
   Sui[t]+=1
 for m in range(H-1):
  E+=Sui[m]
 CO[H-1]=DO[H-1]
 for k in range(H-1):
  if Sui[k]==0:
   CO[H-k-2]=DO[H-k-2]+CO[H-k-1]
   CO[H-k-1]=[0]*W
  else:
   CO[H-k-2]=DO[H-k-2]
 G=0
 for h in range(W-1):
  if np.amax(CO[:,h])>K:
   E=1000000
   break
  elif np.amax(np.sum(CO[:,G:(h-G+1)],axis=1))<=K and np.amax(np.sum(CO[:,G:(h-G+2)],axis=1))>K:
   D+=1
   G=h+1
 if np.amax(CO[:,W-1])>K:
  E=1000000
 if D==0 and E==0:
  F=0
 elif E==0:
  continue
 else:
  F=min(F,D+E)
print(F)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from itertools import product
 
H, W, K = map(int, input().split())
S = [input() for _ in range(H)]
 
i = 0
while i < len(S):
  if '1' in S[i]:
    i += 1
  else:
    del S[i]
H = len(S)
 
C = [[int(s[i]) for s in S] for i in range(W)]
 
total = sum(sum(c) for c in C)
 
if total <= K:
  answer = 0
else:
  answer = H * W
  for X in product([False, True], repeat=H-1):
    ans = sum(X)
    M = [[0]]
    for i, x in enumerate(X):
      if x:
        M.append([])
      M[-1].append(i+1)
      print(M)
    D = [0] * len(M)
    print(M)
    for c in C:
      for k, m in enumerate(M):
        D[k] += sum(c[i] for i in m)
      if any(d > K for d in D):
        ans += 1
        if ans > answer:
          break
        D = [sum(c[i] for i in m) for m in M]
        if any(d > K for d in D):
          ans = answer + 1
          break
    answer = min(answer, ans)

print(answer)

Submission status: Wrong Answer

Solution code:
import numpy as np
H,W,K=map(int,input().split())
CO=np.array([[0]*W]*H)
DO=np.array([[0]*W]*H)
for i in range(H):
 C=input()
 for j in range(W):
  DO[i][j]=int(C[j])
F=1000000
for s in range(2**(H-1)):
 D=0
 E=0
 Sui=[0]*(H-1)
 for t in range(H-1):
  if ((s >> t) & 1):
   Sui[t]+=1
 for m in range(H-1):
  E+=Sui[m]
 CO[H-1]=DO[H-1]
 for k in range(H-1):
  if Sui[k]==0:
   CO[H-k-2]=DO[H-k-2]+CO[H-k-1]
   CO[H-k-1]=[0]*W
  else:
   CO[H-k-2]=DO[H-k-2]
print(0)

Submission status: Wrong Answer

Solution code:
import sys
#input = sys.stdin.readline

def main():
    h,w,k=map(int,input().split())
    s=[list(input()) for _ in range(h)]
    cnt=[[0]*(w+1) for _ in range(h+1)]#計算しやすくするために0の一に余剰なマスを入れてある

    for i in range(1,h+1):
        for j in range(1,w+1):
            flg=int(s[i-1][j-1])
            if i==0 and j==0:
                cnt[i][j]=flg
            elif i==0:
                cnt[i][j]=cnt[i][j-1]+flg
            elif j==0:
                cnt[i][j]=cnt[i-1][j]+flg
            else:
                cnt[i][j]=cnt[i-1][j]+cnt[i][j-1]-cnt[i-1][j-1]+flg
    ans=h+w+1
    for p in range(1<<(h-1)):
        g=[0]*(h+1)
        gnum,gcnt=0,0
        for i in range(h-1):
            if p>>i&1:
                gnum+=1
                g[gnum]=i+1
        gcnt+=gnum
        gnum+=1
        g[gnum]=h
        sw,j=1,2
        while j<=w:
            for i in range(1,gnum+1):
                if cnt[g[i]][j-1]-cnt[g[i]][sw-1]-cnt[g[i-1]][j-1]+cnt[g[i-1]][sw-1]>k:
                    gcnt=h+w+1
                    j=w
                    break
                if cnt[g[i]][j]-cnt[g[i]][sw-1]-cnt[g[i-1]][j]+cnt[g[i-1]][sw-1]>k:
                    sw=j
                    gcnt+=1
                    break
            j+=1
        ans=min(ans,gcnt)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
H,W,K = map(int,input().split())
A = [0]*H
for i in range(H):
    A[i] = input()
s = 10000
for i in range(2**(H-1)):
    count = 0
    B = [0]*H
    B[H-1] = 1
    for j in range(H-2):
        if (i >> j & 1):
            B[j] = 1
            count += 1
    C = [0]*(count + 1)
    for j in range(W):
        a = [0]*(count + 1)
        n = 0
        max = C[0]
        for k in range(H):
            a[n] += int(A[k][j])
            C[n] += int(A[k][j])
            if B[k] == 1:
                if max < C[n]:
                    max = C[n]
                n += 1
        if max > K:
            count += 1
            C[:] = a[:]
    if s > count:
        s = count
print(s)

Submission status: Wrong Answer

Solution code:
H,W,K = map(int,input().split())
A = [0]*H
for i in range(H):
    A[i] = input()
s = 10000
for i in range(2**(H-1)):
    count = 0
    B = [0]*H
    B[H-1] = 1
    for j in range(H-1):
        if (i >> j & 1):
            B[j] = 1
            count += 1
    C = [0]*(count + 1)
    for j in range(W):
        a = [0]*(count + 1)
        n = 0
        max = C[0]
        for k in range(H):
            a[n] += int(A[k][j])
            C[n] += int(A[k][j])
            if B[k] == 1:
                if max < C[n]:
                    max = C[n]
                n += 1
        if max > K:
            count += 1
            C[:] = a[:]
    if s > count:
        s = count
print(s)

Submission status: Wrong Answer

Solution code:
import sys
#input = sys.stdin.readline

def main():
    h,w,k=map(int,input().split())
    s=[list(input()) for _ in range(h)]
    cnt=[[0]*(w+1) for _ in range(h+1)]#計算しやすくするために0の一に余剰なマスを入れてある

    for i in range(1,h+1):
        for j in range(1,w+1):
            flg=int(s[i-1][j-1])
            if i==0 and j==0:
                cnt[i][j]=flg
            elif i==0:
                cnt[i][j]=cnt[i][j-1]+flg
            elif j==0:
                cnt[i][j]=cnt[i-1][j]+flg
            else:
                cnt[i][j]=cnt[i-1][j]+cnt[i][j-1]-cnt[i-1][j-1]+flg
    ans=h+w+1
    for p in range(1<<(h-1)):
        g=[0]*(h+1)
        gnum,gcnt=0,0
        for i in range(h-1):
            if p>>i&1:
                gnum+=1
                g[gnum]=i+1
        gcnt+=gnum
        gnum+=1
        g[gnum]=h
        sw,j=1,2
        while j<=w:
            for i in range(1,gnum+1):
                if cnt[g[i]][j]-cnt[g[i]][sw-1]-cnt[g[i-1]][j]+cnt[g[i-1]][sw-1]>k:
                    sw=j
                    gcnt+=1
                    break
            j+=1
        ans=min(ans,gcnt)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np
H,W,K=map(int,input().split())
CO=np.array([[0]*W]*H)
DO=np.array([[0]*W]*H)
for i in range(H):
 C=input()
 for j in range(W):
  DO[i][j]=int(C[j])
F=1000000
for s in range(2**(H-1)):
 D=0
 E=0
 Sui=[0]*(H-1)
 for t in range(H-1):
  if ((s >> t) & 1):
   Sui[t]+=1
 for m in range(H-1):
  E+=Sui[m]
 CO[H-1]=DO[H-1]
 for k in range(H-1):
  if Sui[k]==0:
   CO[H-k-2]=DO[H-k-2]+CO[H-k-1]
   CO[H-k-1]=[0]*W
  else:
   CO[H-k-2]=DO[H-k-2]
 print(Sui)
 print(CO)
 for h in range(W-1):
  if np.amax(CO[:,h])>K:
   E=1000000
   break
  elif np.amax(CO[:,h])<=K and np.amax(CO[:,h]+CO[:,h+1])>K:
   D+=1
  else:
   CO[:,h+1]=CO[:,h]+CO[:,h+1]
 if np.amax(CO[:,W-1])>K:
  E=1000000
 if D==0 and E==0:
  F=0
 elif E==0:
  continue
 else:
  F=min(F,D+E)
print(F)

Submission status: Wrong Answer

Solution code:
H, W, K = map(int, input().split())
S = [0] * H

for h in range(H):
    S[h] = list(input())


def check(divH):
    MAP = [0] * H
    BitDivH = "".join(["{:0", str(H - 1), "b}"]).format(divH)
    cnt = 0
    for i, bit in enumerate(BitDivH):
        if bit == "1":
            cnt += 1
            MAP[i + 1] = cnt
        else:
            MAP[i + 1] = cnt
    after_tmp = [0] * (MAP[-1] + 1)
    cnt = 0
    for w in range(W):
        for h in range(H):
            after_tmp[MAP[h]] += int(S[h][w])
        for af in after_tmp:
            if af > K:
                cnt += 1
                after_tmp = [0] * (MAP[-1] + 1)
                for h2 in range(H):
                    after_tmp[MAP[h2]] += int(S[h2][w])
                break
    return cnt + MAP[-1]

MIN = 1000000
for i in range(2**(H - 1)):
    MIN = min(MIN, check(i))

print(MIN)

Submission status: Wrong Answer

Solution code:
"""
3 5 2
11100
10001
00111
"""

import copy
H, W, K = map(int, input().split())
S = [0] * H

for h in range(H):
    S[h] = list(input())


def check(divH):
    MAP = [0] * H
    BitDivH = "".join(["{:0", str(H - 1), "b}"]).format(divH)
    cnt = 0
    for i, bit in enumerate(BitDivH):
        if bit == "1":
            cnt += 1
            MAP[i + 1] = cnt
        else:
            MAP[i + 1] = cnt
    after_tmp = [0] * (MAP[-1] + 1)
    cnt = 0
    for w in range(W):
        for h in range(H):
            after_tmp[MAP[h]] += int(S[h][w])
        for af in after_tmp:
            if af > K:
                cnt += 1
                after_tmp = [0] * (MAP[-1] + 1)
                for h2 in range(H):
                    after_tmp[MAP[h2]] += int(S[h2][w])
                break
    return cnt + MAP[-1]

MIN = 1000000
for i in range(2**(H - 1) - 1):
    MIN = min(MIN, check(i))

print(MIN)

Submission status: Wrong Answer

Solution code:
import numpy as np
H,W,K=map(int,input().split())
CO=np.array([[0]*W]*H)
DO=np.array([[0]*W]*H)
for i in range(H):
 C=input()
 for j in range(W):
  DO[i][j]=int(C[j])
F=1000000
for s in range(2**(H-1)):
 D=0
 E=0
 Sui=[0]*(H-1)
 for t in range(H-1):
  if ((s >> t) & 1):
   Sui[t]+=1
 for m in range(H-1):
  E+=Sui[m]
 for k in range(H-1):
  if k==0:
   CO[H-k-1]=DO[H-k-1]
  elif Sui[k]==0:
   CO[H-k-1]=DO[H-k-1]+CO[H-k]
   CO[H-k]=[0]*W
  else:
   CO[H-k-1]=DO[H-k-1]   
 for h in range(W-1):
  CO[:,h+1]=CO[:,h]+CO[:,h+1]
  if np.amax(CO[:,h])>K:
   E=1000000   
   break
  elif np.amax(CO[:,h])<=K and np.amax(CO[:,h+1])>K:
   CO[:,h+1]=CO[:,h+1]-CO[:,h]
   D+=1
 if np.amax(CO[:,W-1])>K:
  E=1000000
 if D==0 and E==0:
  F=0
 elif E==0:
  continue
 else:
  F=min(F,D+E)
print(F)

Submission status: Wrong Answer

Solution code:
import copy
H, W, K = map(int, input().split())
S = [0] * H

for h in range(H):
    S[h] = list(input())


def check(divH):
    MAP = [0] * H
    BitDivH = "".join(["{:0", str(H - 1), "b}"]).format(divH)
    cnt = 0
    for i, bit in enumerate(BitDivH):
        if bit == "1":
            cnt += 1
            MAP[i + 1] = cnt
        else:
            MAP[i + 1] = cnt
    befor_tmp = [0] * (MAP[-1] + 1)
    after_tmp = [0] * (MAP[-1] + 1)
    cnt = 0
    for w in range(W):
        for h in range(H):
            after_tmp[MAP[h]] += int(S[h][w])
        for af in after_tmp:
            if af > K:
                cnt += 1
                after_tmp = [0] * (MAP[-1] + 1)
                for h2 in range(H):
                    after_tmp[MAP[h2]] += int(S[h2][w])
                break
        else:
            befor_tmp = copy.copy(after_tmp)
    return cnt + MAP[-1]

MIN = H * W
for i in range(2**(H - 1) - 1):
    MIN = min(MIN, check(i))

print(MIN)

Submission status: Wrong Answer

Solution code:
import sys
#input = sys.stdin.readline

def main():
    h,w,k=map(int,input().split())
    s=[list(input()) for _ in range(h)]
    cnt=[[0]*(w+1) for _ in range(h+1)]#計算しやすくするために0の一に余剰なマスを入れてある

    for i in range(1,h+1):
        for j in range(1,w+1):
            flg=int(s[i-1][j-1])
            if i==0 and j==0:
                cnt[i][j]=flg
            elif i==0:
                cnt[i][j]=cnt[i][j-1]+flg
            elif j==0:
                cnt[i][j]=cnt[i-1][j]+flg
            else:
                cnt[i][j]=cnt[i-1][j]+cnt[i][j-1]-cnt[i-1][j-1]+flg
    ans=h+w+1
    for p in range(1<<(h-1)):
        g=[0]*(h+1)
        gnum,gcnt=0,0
        for i in range(h-1):
            if p>>i&1:
                gnum+=1
                g[gnum]=i+1
        gcnt+=gnum
        g[gnum+1]=h
        sw,j=1,1
        while j<=h:
            for i in range(1,gnum+2):
                if cnt[g[i]][j]-cnt[g[i]][sw-1]-cnt[g[i-1]][j]+cnt[g[i-1]][sw-1]>k:
                    sw=j
                    gnum+=1
                    break
            j+=1
        ans=min(ans,gnum)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np
H,W,K=map(int,input().split())
CO=np.array([[0]*W]*H)
DO=np.array([[0]*W]*H)
for i in range(H):
 C=input()
 for j in range(W):
  DO[i][j]=int(C[j])
F=1000000
for s in range(2**(H-1)):
 print(CO[0])
 D=0
 E=0
 for i in range(H):
  for j in range(W):
   CO[i][j]=DO[i][j]
 Sui=[0]*(H-1)
 for t in range(H-1):
  if ((s >> t) & 1):
   Sui[t]+=1
 for m in range(H-1):
  E+=Sui[m]
 for k in range(H-1):
  if Sui[k]==0:
   CO[H-k-2]=CO[H-k-2]+CO[H-k-1]
   CO[H-k-1]=[0]*W
 for h in range(W-1):
  CO[:,h+1]=CO[:,h]+CO[:,h+1]
  if np.amax(CO[:,h])>K:
   E=1000000   
   break
  elif np.amax(CO[:,h])<=K and np.amax(CO[:,h+1])>K:
   CO[:,h+1]=CO[:,h+1]-CO[:,h]
   D+=1
 if np.amax(CO[:,W-1])>K:
  E=1000000
 if D==0 and E==0:
  F=0
 elif E==0:
  continue
 else:
  F=min(F,D+E)
print(F)

Submission status: Wrong Answer

Solution code:
import sys
#input = sys.stdin.readline

def main():
    h,w,k=map(int,input().split())
    s=[list(input()) for _ in range(h)]
    cnt=[[0]*(w+1) for _ in range(h+1)]#計算しやすくするために0の一に余剰なマスを入れてある

    for i in range(1,h+1):
        for j in range(1,w+1):
            flg=int(s[i-1][j-1])
            if i==0 and j==0:
                cnt[i][j]=flg
            elif i==0:
                cnt[i][j]=cnt[i][j-1]+flg
            elif j==0:
                cnt[i][j]=cnt[i-1][j]+flg
            else:
                cnt[i][j]=cnt[i-1][j]+cnt[i][j-1]-cnt[i-1][j-1]+flg
    ans=h+w+1
    for p in range(1<<(h-1)):
        g=[0]*(h+1)
        gnum,gcnt=0,0
        for i in range(h-1):
            if p>>i&1:
                gnum+=1
                g[gnum]=i+1
        gcnt+=gnum
        gnum+=1
        g[gnum]=h
        sw,j=1,0
        while j<=h:
            for i in range(1,gnum+1):
                if cnt[g[i]][j]-cnt[g[i]][sw-1]-cnt[g[i-1]][j]+cnt[g[i-1]][sw-1]>k:
                    sw=j
                    gnum+=1
                    break
            j+=1
        ans=min(ans,gnum)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np

def main():
    H, W, K = map(int, raw_input().split())
    S = []

    for i in range(H):
        S.append(list(raw_input()))

    for i in range(H):
        for j in range(W):
            S[i][j] = int(S[i][j])

    ans = 10**9

    for divide in range(2**(H-1)):
        regions = []
        for l in range(H):
            if divide & 1 << l:
                regions.append(l+1)
        S_subs = []
        prev = 0
        for region in regions:
            new = region
            S_subs.append(S[prev:new])
            prev = new
        S_subs.append(S[prev:H])
        N = len(S_subs)

        count = [0]*N

        bin_num = bin(divide)[2:]

        ans_temp = 0
        for i in bin_num:
            ans_temp += int(i)

#        print "--"                                                                                                    
#        print ans_temp                                                                                                
        for j in range(W):
            for l in range(N):
                for item in S_subs[l]:
                    count[l] += item[j]
            if max(count) > K:
                ans_temp = ans_temp + 1
                count = [0]*N
                for l in range(N):
                    for item in S_subs[l]:
                        count[l] += item[j]

        if ans_temp < ans:
            ans = ans_temp

#        print ans_temp                                                                                                
    print ans


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np

def main():
    H, W, K = map(int, raw_input().split())
    S = []

    for i in range(H):
        S.append(list(raw_input()))

    for i in range(H):
        for j in range(W):
            S[i][j] = int(S[i][j])

    ans = 10**9

    for divide in range(2**(H-1)):
        regions = []
        for l in range(H):
            if divide & 1 << l:
                regions.append(l+1)
        S_subs = []
        prev = 0
        for region in regions:
            new = region
            S_subs.append(S[prev:new])
            prev = new
        S_subs.append(S[prev:H])
        N = len(S_subs)

        count = [0]*N

        bin_num = bin(divide)[2:]

        ans_temp = 0
        for i in bin_num:
            ans_temp += int(i)

#        print "--"                                                                                                    
#        print ans_temp                                                                                                
        for j in range(W):
            for l in range(N):
                for item in S_subs[l]:
                    count[l] += item[j]
            if max(count) > K:
                ans_temp = ans_temp + 1
                count = [0]*N
        if ans_temp < ans:
            ans = ans_temp

#        print ans_temp                                                                                                
    print ans

if __name__ == "__main__":
    main()