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:
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    H,W,K=MI()
    S=[]
    for _ in range(H):
        s=input()
        S.append(s)
        
    # Hに関してbit全探索
    import itertools
    
    inf=10**10
    ans=inf
    
    import bisect
    for ite in itertools.product([0,1], repeat=H-1):
        temp=sum(ite)
        g=[-1]#グループに分ける，区切り(末尾)の数字をいれる
        for i in ite:
            if i==1:
                g.append(i)
        
        g.append(H-1)
        M=len(g)
        cnt=[0]*M#グループ毎
        
        flag=1#無理かどうか
        for j in range(W):
            if flag==0:
                break
            cnt2=[0]*M#各列用
            
            #数える
            for i in range(H):
                if S[i][j]=="1":
                    num=bisect.bisect_left(g,i)-1
                    cnt[num]+=1
                    cnt2[num]+=1
            
            #無理
            for i in range(M):
                if cnt2[i]>K:
                    temp=inf
                    flag=0
                    break
                
            #わるか確認
            flag2=0
            for i in range(M):
                if cnt[i]>K:
                    flag2=1
                    break
            #わる
            if flag2:
                for i in range(M):
                    cnt[i]=cnt2[i]
                temp+=1
                    
        ans=min(ans,temp)
        
    print(ans)
                  
                
                

main()

Submission status: Wrong Answer

Solution code:
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    H,W,K=MI()
    S=[]
    for _ in range(H):
        s=input()
        S.append(s)
        
    # Hに関してbit全探索
    import itertools
    
    inf=10**10
    ans=inf
    
    import bisect
    for ite in itertools.product([0,1], repeat=H):
        temp=sum(ite)
        g=[-1]#グループに分ける，区切り(末尾)の数字をいれる
        for i in ite:
            if i==1:
                g.append(i)
        
        g.append(H-1)
        M=len(g)
        cnt=[0]*M#グループ毎
        
        flag=1#無理かどうか
        for j in range(W):
            if flag==0:
                break
            cnt2=[0]*M#各列用
            
            #数える
            for i in range(H):
                if S[i][j]=="1":
                    num=bisect.bisect_left(g,i)-1
                    cnt[num]+=1
                    cnt2[num]+=1
            
            #無理
            for i in range(M):
                if cnt2[i]>K:
                    temp=inf
                    flag=0
                    break
                
            #わるか確認
            flag2=0
            for i in range(M):
                if cnt[i]>K:
                    flag2=1
                    break
            #わる
            if flag2:
                cnt=[*cnt2]
                temp+=1
                    
        ans=min(ans,temp)
        
    print(ans)
                  
                
                

main()

Submission status: Wrong Answer

Solution code:
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    H,W,K=MI()
    S=[]
    for _ in range(H):
        s=input()
        S.append(s)
        
    # Hに関してbit全探索
    import itertools
    
    inf=10**10
    ans=inf
    
    import bisect
    for ite in itertools.product([0,1], repeat=H-1):
        temp=sum(ite)
        g=[-1]#グループに分ける，区切り(末尾)の数字をいれる
        for i in ite:
            if i==1:
                g.append(i)
        
        g.append(H-1)
        M=len(g)
        cnt=[0]*M#グループ毎
        
        flag=1#無理かどうか
        for j in range(W):
            if flag==0:
                break
            cnt2=[0]*M#各列用
            
            #数える
            for i in range(H):
                if S[i][j]=="1":
                    num=bisect.bisect_left(g,i)-1
                    cnt[num]+=1
                    cnt2[num]+=1
            
            #無理
            for i in range(M):
                if cnt2[i]>K:
                    temp=inf
                    flag=0
                    break
                
            #わるか確認
            flag2=0
            for i in range(M):
                if cnt[i]>K:
                    flag2=1
                    break
            #わる
            if flag2:
                cnt=[*cnt2]
                temp+=1
                    
        ans=min(ans,temp)
        
    print(ans)
                  
                
                

main()

Submission status: Wrong Answer

Solution code:
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    H,W,K=MI()
    S=[]
    for _ in range(H):
        s=input()
        S.append(s)
        
    # Hに関してbit全探索
    import itertools
    
    inf=10**10
    ans=inf
    
    import bisect
    for ite in itertools.product([0,1], repeat=H-1):
        temp=sum(ite)
        g=[-1]#グループに分ける，区切り(末尾)の数字をいれる
        for i in ite:
            if i==1:
                g.append(i)
        
        M=len(g)
        cnt=[0]*M#グループ毎
        
        flag=1
        for j in range(W):
            if flag==0:
                break
            cnt2=[0]*M#各列用
            
            #数える
            for i in range(H):
                if S[i][j]=="1":
                    num=bisect.bisect_left(g,i)-1
                    cnt[num]+=1
                    cnt2[num]+=1
            
            #無理
            for i in range(M):
                if cnt2[i]>K:
                    temp=inf
                    flag=0
                    break
                
            #わるか確認
            flag2=0
            for i in range(M):
                if cnt[i]>K:
                    flag2=1
                    break
            #わる
            if flag2:
                cnt=[*cnt2]
                temp+=1
                    
        ans=min(ans,temp)
        
    print(ans)
                  
                
                

main()

Submission status: Wrong Answer

Solution code:
h,w,k=map(int,input().split())
cho=[]
for _ in range(h):
    a=list(input())
    for f in range(w):
      a[f]=int(a[f])
    cho.append(a)

ans=1000000000009

for i in range(2**(h-1)):
    cut=0
    cut_n=[]
    b=[]
    for j in range(h-1):
        if (i>>j)&1:
            cut_n.append(j+1)
            cut+=1
    if len(cut_n)==0:
        ok=1
        dp=0
        for i in range(w):
            wa=0
            for j in range(h):
                wa+=cho[j][i]

            if dp+wa>k:
                cut+=1
                dp=wa
            else:
              dp+=wa

            if wa>k:
                ok+=1
                break
            
        if ok:
          ans=min(ans,cut)

    else:
        st=0
        for t in range(len(cut_n)):
            if t==len(cut_n)-1:
                b.append(cut_n[t]-st)
                b.append(h-cut_n[t])
            else:
              b.append(cut_n[t]-st)
              st=cut_n[t]
        
        dp=[0 for _ in range(len(b))]
        ok=1
        for y in range(w):
            for g in dp:
                if g>k:
                    ok+=1
                    break
            st=0
            ch=0
            c=[]
            for e in range(len(b)):
              p=b[e]
              temp=0
              for q in range(p):
                  temp+=cho[st+q][y]
                    
                  dp[e]+=cho[st+q][y]

              c.append(temp)
                
              st+=p

            for g in dp:
                if g>k:
                    ch+=1

            if ch!=0:
                cut+=1
                dp=c

            
            for last in c:
                  if last>k:
                      ok+=1

        
        if ok:
            ans=min(ans,cut)

print(ans)

Submission status: Wrong Answer

Solution code:
h,w,k=map(int,input().split())
cho=[]
for _ in range(h):
    a=list(input())
    for f in range(w):
      a[f]=int(a[f])
    cho.append(a)
    

ans=1000000000009

for i in range(2**(h-1)):
    cut=0
    cut_n=[]
    b=[]
    for j in range(h-1):
        if (i>>j)&1:
            cut_n.append(j+1)
            cut+=1
    if len(cut_n)==0:
        ok=1
        dp=0
        for i in range(w):
            wa=0
            for j in range(h):
                wa+=cho[j][i]

            if dp+wa>k:
                cut+=1
                dp=wa
            else:
              dp+=wa

            if wa>k:
                ok+=1
                break
            
        if ok:
          ans=min(ans,cut)

    else:
        st=0
        for t in range(len(cut_n)):
            if t==len(cut_n)-1:
                b.append(cut_n[t]-st)
                b.append(h-cut_n[t])
            else:
              b.append(cut_n[t]-st)
              st=cut_n[t]
        
        dp=[0 for _ in range(len(b))]
        ok=1
        for i in range(w):
            for g in dp:
                if g>k:
                    ok+=1
                    break
            st=0
            ch=0
            c=[]
            for e in range(len(b)):
              p=b[e]
              temp=0
              for q in range(p):
                  temp+=cho[st+q][i]
                    
                  dp[e]+=cho[st+q][i]

              c.append(temp)
                
              st+=p

            for g in dp:
                if g>k:
                    ch+=1

            if ch!=0:
                cut+=1
                dp=c

            if i==w-1:
                for last in c:
                    if last>k:
                        ok+=1

        
        if ok:
            ans=min(ans,cut)

print(ans)

Submission status: Wrong Answer

Solution code:
H, W, K = map(int, input().split())
HW = [[0] * W for i in range(H)]
S = [0] * H
for i in range(H):
  x = str(input())
  for j in range(len(x)):
    HW[i][j] = int(x[j])
#print(HW) 

for i in range(H):
  S[i] = sum(HW[i])
#print(S)  

ans = H + W
for i in range(2 ** (H - 1)):#521 * 9
  time = 0
  now = 0
  cut = []
  for j in range(H - 1):
    if (i >> j) & 1:#j番目とj+1番目の間で割る
      cut.append(j)
  #print(cut)
  cut2 = [[] for _ in range(len(cut) + 1)]
  for j in range(len(cut)):
    for p in range(now, cut[j] + 1):
      cut2[j].append(p)
      now = cut[j] + 1
  for p in range(now, H):
    cut2[-1].append(p)
  #print(cut2)    
    
  time = len(cut2) - 1  
  choco = [0] * len(cut2)
  for l in range(W):
    for k in range(len(cut2)):
      for p in cut2[k]:
        choco[k] += HW[p][l]
    if max(choco) > K:
      time += 1
      for k in range(len(cut2)):
        choco[k] = 0
      for k in range(len(cut2)):
        for p in cut2[k]:
          choco[k] += HW[p][l]
        
        
  ans = min(ans, time)
  #print(i, time)
  
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
from itertools import permutations
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
H, W, K = map(int, input().split())
S = [input() for _ in range(H)]
acc = [[0] * (W + 1) for _ in range(H)]
for i in range(H):
    for j in range(1, W + 1):
        acc[i][j] = acc[i][j - 1] + int(S[i][j - 1])


ans = INF
for bit in range(1 << (H - 1)):
    base = 0
    vertical = []
    for i in range(H - 1):
        if bit & 1 << i > 0:
            vertical.append((base, i))
            base = i + 1
    vertical.append((base, H - 1))

    tmp_ans = len(vertical) - 1
    prev = 0
    j = 1
    valid = False
    while j <= W:
        ok = True
        for v in vertical:
            now = 0
            for i in range(v[0], v[1] + 1):
                now += acc[i][j] - acc[i][prev]
            if now > K:
                ok = False
        if ok:
            valid = True
        else:
            if valid:
                prev = j
                tmp_ans += 1
                valid = False
            else:
                break
        j += 1
    if valid:
        ans = min(tmp_ans, ans)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
from itertools import permutations
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
H, W, K = map(int, input().split())
S = [input() for _ in range(H)]
acc = [[0] * (W + 1) for _ in range(H)]
for i in range(H):
    for j in range(1, W + 1):
        acc[i][j] = acc[i][j - 1] + int(S[i][j - 1])


ans = INF
for bit in range(1 << (H - 1)):
    base = 0
    vertical = []
    for i in range(H - 1):
        if bit & 1 << i > 0:
            vertical.append((base, i))
            base = i + 1
    vertical.append((base, H - 1))

    tmp_ans = len(vertical) - 1
    prev = 0
    j = 1
    valid = False
    while j <= W:
        ok = True
        for v in vertical:
            now = 0
            for i in range(v[0], v[1] + 1):
                now += acc[i][j] - acc[i][prev]
            if now > K:
                ok = False
        if ok:
            valid = True
        else:
            if valid:
                prev = j - 1
                tmp_ans += 1
                valid = False
            else:
                break
        j += 1
    if valid:
        ans = min(tmp_ans, ans)
print(ans)

Submission status: Wrong Answer

Solution code:
H,W,K=map(int,input().split())
S=[[int(s) for s in input()] for i in range(H)]

ans=1000000
for i in range(2**(H-2)):
    tmp=0
    L=[]
    for j in range(H-2):
        if i>>j&1:
            L.append(j)
    tmp+=len(L)
    L.append(H-1)
    c=[0]*len(L)
    for k in range(W):
        h=0
        c1=[0]*len(L)
        for l in range(len(L)):
            for m in range(h,L[l]+1):
                c1[l]+=S[m][k]
            h=L[l]+1
        p=0
        for l in range(len(L)):
            if c1[l]>K:
                p=2
                break
            elif c[l]+c1[l]>K:
                p=1
            else:
                c[l]+=c1[l]
        if p==2:
            break
        elif p==1:
            c=[i for i in c1]
            tmp+=1
    else:
        ans=min(ans,tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
# import math
# import bisect
# import numpy as np
# from decimal import Decimal
# from numba import njit, i8, u1, b1 #JIT compiler
# from itertools import combinations, product
# from collections import Counter, deque, defaultdict

# sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_ints2(x):   return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def GCD(a: int, b: int) -> int: return b if a%b==0 else GCD(b, a%b)
def LCM(a: int, b: int) -> int: return (a * b) // GCD(a, b)

def search(topx, topy, botx, boty, grid):
    ret = grid[boty][botx]
    if topx > 0: ret -= grid[boty][topx - 1]
    if topy > 0: ret -= grid[topy - 1][botx]
    if topx > 0 and topy > 0: ret += grid[topy - 1][topx - 1]
    return ret

def Main():
    H, W, K = read_ints()
    chocolate = [list(read_str()) for _ in range(H)]
    
    grid = [[0] * W for _ in range(H)]
    for h in range(H):
        for w in range(W):
            if chocolate[h][w] == '1': grid[h][w] += 1
            if w > 0: grid[h][w] += grid[h][w - 1]
            if h > 0: grid[h][w] += grid[h - 1][w]
            if h > 0 and w > 0: grid[h][w] -= grid[h - 1][w - 1]

    ans = INF
    for bit in range(1 << ~-H):
        cnt = 0
        cut = []
        for h in range(~-H):
            if bit >> h & 1:
                cnt += 1
                cut.append(h)
        cut.append(~-H)

        white = [0] * len(cut)
        topx = 0
        for w in range(~-W):
            topy = 0
            for i in range(len(cut)):
                white[i] = search(topx, topy, w + 1, cut[i], grid)
                topy = cut[i]+1
            for x in white:
                if x <= K:
                    continue
                topx = w + 1
                cnt += 1
                break
        ans = min(ans, cnt)
    print(ans)
    

if __name__ == '__main__':
    Main()

Submission status: Wrong Answer

Solution code:
h,w,kk = map(int,input().split())
s = [list(map(int, input())) for i in range(h)]

ans = h+w-2
for i in range(1 << (h-1)):
    tate = 0
    index = [0] * h
    # しきりはh-1個なので2個目から考える
    for j in range(h-1):
        if i & (1 << j):
            tate += 1
        index[j+1] = tate # チョコ軍の番号
    chocos = [0]*(tate + 1) # チョコ軍
    yoko = 0
    ok = True
    for j in range(w):
        for k in range(h):
            chocos[index[k]] += s[k][j]
            # kkを超えるたびにその直前に仕切りをいれて新しいチョコ軍について考える
            if max(chocos) > kk:
                yoko += 1
                chocos = [0]*(tate+1)
                for l in range(h):
                    chocos[index[l]] += s[l][j]
                if max(chocos) > kk:# その列だけで超える
                    ok = False
            if not ok:
                break
    if ok:
        ans = min(ans, tate + yoko)

print(ans)

Submission status: Wrong Answer

Solution code:
h,w,kk = map(int,input().split())
s = [list(map(int, input())) for i in range(h)]

ans = h+w-2
for i in range(2**(h-1)):
    tate = 0
    index = [0] * h
    # しきりはh-1個なので2個目から考える
    for j in range(h-1):
        if i & (1 << j):
            tate += 1
        index[j+1] = tate # チョコ軍の番号
    chocos = [0]*(tate + 1) # チョコ軍
    yoko = 0
    ok = True
    for j in range(w):
        for k in range(h):
            chocos[index[k]] += s[k][j]
            # kkを超えるたびにその直前に仕切りをいれて新しいチョコ軍について考える
            if max(chocos) > kk:
                yoko += 1
                chocos = [0]*(tate+1)
                for l in range(h):
                    chocos[index[l]] += s[l][j]
                    if max(chocos) > kk:# その列だけで超える
                        ok = False
            if not ok:
                break
    if ok:
        ans = min(ans, tate + yoko)

print(ans)

Submission status: Wrong Answer

Solution code:
h,w,kk = map(int,input().split())
s = [list(map(int, input())) for i in range(h)]

ans = h+w-2
for i in range(1 << (h-1)):
    tate = 0
    index = [0] * h
    # しきりはh-1個なので2個目から考える
    for j in range(h-1):
        if i & (1 << j):
            tate += 1
        index[j+1] = tate # チョコ軍の番号
    chocos = [0]*(tate + 1) # チョコ軍
    yoko = 0
    ok = True
    for j in range(w):
        for k in range(h):
            chocos[index[k]] += s[k][j]
            # kkを超えるたびにその直前に仕切りをいれて新しいチョコ軍について考える
            if max(chocos) > kk:
                yoko += 1
                chocos = [0]*(tate+1)
                for l in range(h):
                    chocos[index[l]] += s[l][j]
                    if max(chocos) > kk:# その列だけで超える
                        ok = False
            if not ok:
                break
    if ok:
        ans = min(ans, tate + yoko)

print(ans)

Submission status: Wrong Answer

Solution code:
h,w,kk = map(int,input().split())
s = [list(map(int, input())) for i in range(h)]

ans = h+w-2
for i in range(1 << (h-1)):
    tate = 0
    index = [0] * h
    # しきりはh-1個なので2個目から考える
    for j in range(h-1):
        if i & (1 << j):
            tate += 1
        index[j+1] = tate # チョコ軍の番号
    chocos = [0]*(tate + 1) # チョコ軍
    yoko = 0
    ok = True
    for j in range(w):
        for k in range(h):
            chocos[index[k]] += s[k][j]
            # kkを超えるたびにその直前に仕切りをいれて新しいチョコ軍について考える
            if max(chocos) > kk:
                yoko += 1
                chocos = [0]*(tate+1)
                for l in range(h):
                    chocos[index[l]] += s[l][j]
                    if max(chocos) > kk:# その列だけで超える
                        ok = False
            if not ok:
                break
    ans = min(ans, tate + yoko)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline

H, W, K = map(int, input().split())
S = [list(input()) for _ in range(H)]

res = float('inf')
for i in range(2**(H-1)):
    c = bin(i).count('1')
    cnt = c
    sum_l = [0] * (c+1)
    j = 0
    flag = True
    while j < W:
        tmp = sum_l.copy()
        pos = 0
        for k in range(H):
            if S[k][j] == '1':
                tmp[pos] += 1
            if (i >> k) & 1:
                pos += 1
        if max(tmp) <= K:
            sum_l = tmp.copy()
            j += 1
            flag = False
        else:
            if flag:
                break
            cnt += 1
            flag = True
            sum_l = [0] * (c+1)

    res = min(res, cnt)

print(res)

Submission status: Wrong Answer

Solution code:
from itertools import product

H, W, K = map(int, input().split())
grid = ""

for _ in range(H):
  grid += input()

ans = 10000

for Hcut in product((0, 1), repeat = H-1):
  Gr_num = sum(Hcut) + 1
  old_Gr, new_Gr = [0]*Gr_num, [0]*Gr_num
  cnt = 0
  for i in range(W):
    choco = grid[i::W]
    gr = 0
    #縦にchoco見る
    for j in range(H):
      new_Gr[gr] += int(choco[j])
      if j < H-1:
        if Hcut[j] == 1:
          gr += 1
    #そもそも一列でオーバーしてたら詰み。
    if max(new_Gr) > K:
      break
    #追加しても大丈夫か確認
    check = [old_Gr[g] + new_Gr[g] for g in range(Gr_num)]
    if max(check) > K:
      old_Gr = new_Gr[:]
      new_Gr = [0]*Gr_num
      cnt += 1
    else:
      old_Gr = check[:]
      new_Gr = [0]*Gr_num
  ans = min(ans, cnt+sum(Hcut))

print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import product

H, W, K = map(int, input().split())
grid = ""

for _ in range(H):
  grid += input()

ans = 10000
Flag = True

for cut in product((0, 1), repeat = H-1):
  in_cnt = sum(cut)
  temp = [0]*(in_cnt+1)
  cnt = in_cnt
  for i in range(W):
    check = [0]*(in_cnt+1)
    j = 0
    temp[j] += int(grid[i])
    check[j] += int(grid[i])
    for x, c in enumerate(cut):
      if c == 1:
        j += 1
      temp[j] += int(grid[i+W*(x+1)])
      check[j] += int(grid[i+W*(x+1)])
    if max(check) > K:
      Flag = False
      break
    if max(temp) == K:
      if i != W-1:
        cnt += 1
        temp = [0]*(in_cnt+1)
    if max(temp) > K:
      cnt += 1
      j = 0
      temp[j] = int(grid[i])
      for x, c in enumerate(cut):
        if c == 1:
          j += 1
        temp[j] += int(grid[i+W*(x+1)])
  if Flag:
    ans = min(ans, cnt)
  else:
    Flag = True

print(ans)

Submission status: Wrong Answer

Solution code:
#! /usr/bin/env python3
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def bit_search(n):
    res = []
    for i in range(2**n):
        st = set()
        for j in range(n): 
            if ((i >> j) & 1):
                st.add(j)
        res.append(st)
    return res

def main():
    H,W,K=mi()
    
    G = []
    for i in range(H):
        G.append(list(input()))
    
    v = [[0] * W for _ in range(H+1)]
    for w in range(W):
        for h in range(H):
            white_choc = G[h][w] == "1"
            v[h+1][w] = v[h][w] + white_choc
    
    ans = INF
    for borders in bit_search(H):
        counts = [[0] for _ in range(20)]
        k_fact = 1
        W_borders = []

        failed = False
        from_zero = True
        for w in range(W):
            pre = 0
            over_K = False

            max_pure_count = 0
            for i,border in enumerate(borders):
                if border == 0: continue
                count = v[border][w] - v[pre][w]

                max_pure_count = max(max_pure_count,count)
                if not from_zero:
                    count += counts[i][-1]
                
                if count > K:
                    over_K = True
                

                counts[i].append(count)
                pre = border

            
            count = v[H][w] - v[pre][w]
            if not from_zero:
                count += counts[i+1][-1]

    
            if count > K:
                over_K = True


            counts[i+1].append(count)
            max_pure_count = max(max_pure_count,count)


            if over_K:
                W_borders.append(w-1)
                from_zero = True

                if max_pure_count > K:
                    failed = True
                    break
                elif max_pure_count == K:
                    W_borders.append(w)

            else:
                from_zero = False

            if failed:
                break

        # print(counts)
        if not failed:
            # print(borders)
            # print(W_borders)
            # print(counts)
            # # # print(v[2])
            # # exit()
            count_of_ope = len(borders) + len(W_borders)
            ans = min(count_of_ope,ans)


    print(ans)




if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#! /usr/bin/env python3
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def bit_search(n):
    res = []
    for i in range(2**n):
        st = set()
        for j in range(n): 
            if ((i >> j) & 1):
                st.add(j)
        res.append(st)
    return res

def main():
    H,W,K=mi()
    
    G = []
    for i in range(H):
        G.append(list(input()))
    
    v = [[0] * W for _ in range(H+1)]
    for w in range(W):
        for h in range(H):
            white_choc = G[h][w] == "1"
            v[h+1][w] = v[h][w] + white_choc
    
    ans = INF
    for borders in bit_search(H):
        counts = [[0] for _ in range(20)]
        k_fact = 1
        W_borders = []

        failed = False
        from_zero = True
        for w in range(W):
            pre = 0
            over_K = False

            max_diff = 0
            for i,border in enumerate(borders):
                if border == 0: continue
                count = v[border][w] - v[pre][w]
                if not from_zero:
                    count += counts[i][-1]
                
                if count > K:
                    over_K = True
                

                counts[i].append(count)
                pre = border

                max_diff = max(max_diff,count - counts[i][-1])
            
            count = v[H][w] - v[pre][w]
            if not from_zero:
                count += counts[i+1][-1]

    
            if count > K:
                over_K = True


            counts[i+1].append(count)
            max_diff = max(max_diff,count - counts[i][-1])


            if over_K:
                W_borders.append(w-1)
                from_zero = True

                if max_diff > K:
                    failed = True
                    break
                
            else:
                from_zero = False

            if failed:
                break

        # print(counts)
        if not failed:
            # print(borders)
            # print(W_borders)
            # print(counts)
            # # # print(v[2])
            # # exit()
            count_of_ope = len(borders) + len(W_borders)
            ans = min(count_of_ope,ans)


    print(ans)




if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from itertools import product
import copy
H,W,K = list(map(int, input().split()))
A = []
for i in range(H):
  A.append(list(map(int, input())))

#SM = [np.cumsum(A[i]) for i in range(H)]

ANS = []
for pat in product(['0','1'], repeat = H-1):
  res = []
  cnt = 0
  now = copy.copy(A[0])
  for i in range(1,H):
    p = pat[i-1]
    if p == '1':
      res.append(now)
      now = copy.copy(A[i])
      cnt += 1
    else:
      for j in range(W):
        now[j] += A[i][j]
  res.append(now)
  
  """
  print("---")
  print(pat)
  print(res)
  print(cnt)
  """
  wk2 = [0] * len(res)
  cnt2 = 0
  for x in range(W):
    for j in range(len(res)):
      if wk2[j] + res[j][x] > K:
        cnt2 += 1
        wk2 = [0] * len(res)
        break
    for j in range(len(res)):
      wk2[j] += res[j][x]
  
  ANS.append(cnt + cnt2)
  
print(min(ANS))