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:
#!/usr/bin/env python3

import sys
# import math
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product                # product(iter, repeat=n)
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4


def main():
    mod = 1000000007                  # 10^9+7
    inf = float('inf')
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():  return int(input())
    def mi():  return map(int, input().split())
    def mi_0(): return map(lambda x: int(x)-1, input().split())
    def lmi(): return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():  return list(input())
    
    
    h, w, k = mi()
    L = []
    for _ in range(h):
        L.append(list(map(int, li())))
    L_trans = [[None] * h for _ in range(w)]
    # print(L)
    # print(L_trans)
    for i in range(h):
        for j in range(w):
            L_trans[j][i] = L[i][j]
    d = 2 ** (h-1)
    cost = [float('inf')] * d
    for state in range(d):
        bit_count = bin(state)[2:].count('1')
        separated = [[0] * (bit_count + 1) for _ in range(w)]
        for i in range(w):
            current = 0
            for j in range(h):
                if j >= 1 and 1 << (j-1) & state:
                    current += 1
                if L_trans[i][j]:
                    separated[i][current] += 1
        previous = [0] * (bit_count + 1)
        cnt = 0
        # print(separated)
        for i in range(w):
            if any(map(lambda x: x > k, separated[i])):
                break
            if all(map(lambda x: x <= k, [elm + previous[ind] for ind, elm in enumerate(separated[i])])):
                for ind, elm in enumerate(separated[i]):
                    previous[ind] += elm    # 追加
                # print('add')
                # print(previous)
            else:
                cnt += 1
                for ind, elm in enumerate(separated[ind]):
                    previous[ind] = elm    # 上書き
                # print(previous)
        else:
            # print(f"{state} {bit_count} {cnt}")
            cost[state] = bit_count + cnt
    # print(cost)
    print(min(cost))
                

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from itertools import product

H, W, K = map(int, input().split())
l = [[0]*W for _ in range(H)]
for i in range(H):
    for j, s in enumerate(input()):
        if s=="1":
            l[i][j] = 1

dp = [[0]*(W+1) for _ in range(H+1)]
for i in range(1, H+1):
    for j in range(1, W+1):
        dp[i][j] = l[i-1][j-1]+dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]

f=lambda lx,ly,rx,ry:dp[ry][rx]-dp[ly-1][rx]-dp[ry][lx-1]+dp[ly-1][lx-1]

ans = H*W
for i in product(range(2), repeat=H-1):
    candidate = []
    if any(i):
        start = 1
        for j, k in enumerate(i, start=1):
            if k:
                candidate.append((start, j))
                start = j+1
        candidate.append((start, H))
    else:
        candidate.append((1, H))
    
    q = [1]
    cutx = 0

    while q:
        s = q.pop()
        for t in range(s, W+1)[::-1]:
            if all(f(s, j, t, k)<=K for j, k in candidate):
                if t!=W:
                    q.append(t+1)
                    cutx += 1
                break
    v = cutx+sum(i)
    ans = min(ans, v)

print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import product

H, W, K = map(int, input().split())
l = [[0]*W for _ in range(H)]
for i in range(H):
    for j, s in enumerate(input()):
        if s=="1":
            l[i][j] = 1

dp = [[0]*(W+1) for _ in range(H+1)]
for i in range(1, H+1):
    for j in range(1, W+1):
        dp[i][j] = l[i-1][j-1]+dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]

f=lambda lx,ly,rx,ry:dp[ry][rx]-dp[ly-1][rx]-dp[ry][lx-1]+dp[ly-1][lx-1]

ans = H*W
for i in product(range(2), repeat=H-1):
    candidate = []
    if any(i):
        start = 1
        for j, k in enumerate(i, start=1):
            if k:
                candidate.append((start, j))
                start = j+1
        candidate.append((start, H))
    else:
        candidate.append((1, H))
    lx = 1
    q = [1]
    cutx = 0

    while q:
        s = q.pop()
        for t in range(s, W+1)[::-1]:
            if all(f(s, j, t, k)<=K for j, k in candidate):
                if t!=W:
                    q.append(t+1)
                    cutx += 1
                break
    v = cutx+sum(i)
    ans = min(ans, v)

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
import numpy as np

H, W, K = map(int, input().split())
grid = np.array([list(map(int, list(input()))) for _ in range(H)], dtype=np.int32)
min_cost = None


for H_div_pattern in itertools.product([0, 1], repeat=H-1):
    H_div_num = [i+1 for i, j in enumerate(H_div_pattern) if j == 1] + [H]
    
    sum_grid = np.zeros((len(H_div_num), W), dtype=np.int32)
    start_H = 0
    for idx, div_num in enumerate(H_div_num):
        for w in range(W):
            sum_grid[idx, w] = np.sum(grid[start_H:div_num, w])
        start_H = div_num
    
    cost = len(H_div_num) - 1
    if (sum_grid > K).any():
        break
    
    block_cost = sum_grid[:, 0]
    for w in range(1, W):
        tmp = sum_grid[:, w] + block_cost
        if (tmp <= K).all():
            block_cost = tmp
        else:
            block_cost = sum_grid[:, w]
            cost += 1
            
        if min_cost is not None and cost >= min_cost:
            break
    
    if min_cost is None or min_cost > cost:
        min_cost = cost

print(min_cost)

Submission status: Wrong Answer

Solution code:
import itertools
import numpy as np

H, W, K = map(int, input().split())
grid = np.array([list(map(int, list(input()))) for _ in range(H)], dtype=np.int32)
min_cost = None


for H_div_pattern in itertools.product([0, 1], repeat=H-1):
    H_div_num = [i+1 for i, j in enumerate(H_div_pattern) if j == 1] + [H]
    
    sum_grid = np.zeros((len(H_div_num), W), dtype=np.int32)
    start_H = 0
    for idx, div_num in enumerate(H_div_num):
        for w in range(W):
            sum_grid[idx, w] = np.sum(grid[start_H:div_num, w])
        start_H = div_num
    
    cost = len(H_div_num) - 1
    if (sum_grid > K).any():
        break
    
    block_cost = sum_grid[:, 0]
    for w in range(1, W):
        tmp = sum_grid[:, w] + block_cost
        if (tmp <= K).all():
            block_cost = tmp
        else:
            block_cost = sum_grid[:, w]
            cost += 1
            
        if min_cost is not None and cost >= min_cost:
            break
    
    if min_cost is None or min_cost > cost:
        min_cost = cost

if min_cost is None:
    print(0)
else:
    print(min_cost)

Submission status: Wrong Answer

Solution code:
import itertools
import numpy as np

H, W, K = map(int, input().split())
grid = np.array([list(map(int, list(input()))) for _ in range(H)], dtype=np.int32)
min_cost = None


for H_div_pattern in itertools.product([0, 1], repeat=H-1):
    H_div_num = [i+1 for i, j in enumerate(H_div_pattern) if j == 1] + [H]
    
    sum_grid = np.zeros((len(H_div_num), W), dtype=np.int32)
    start_H = 0
    for idx, div_num in enumerate(H_div_num):
        for w in range(W):
            sum_grid[idx, w] = np.sum(grid[start_H:div_num, w])
        start_H = div_num
    
    cost = len(H_div_num) - 1
    if (sum_grid > K).any():
        break
    
    block_cost = sum_grid[:, 0]
    for w in range(1, W):
        tmp = sum_grid[:, w] + block_cost
        if (tmp <= K).all():
            block_cost = tmp
        else:
            block_cost = sum_grid[:, w]
            cost += 1
            
        if min_cost is not None and cost >= min_cost:
            break
    
    if min_cost is None or min_cost > cost:
        min_cost = cost
    
print(min_cost)

Submission status: Wrong Answer

Solution code:
import itertools
import numpy as np

H, W, K = map(int, input().split())
grid = np.array([list(map(int, list(input()))) for _ in range(H)], dtype=np.int32)
min_cost = None


for H_div_pattern in itertools.product([0, 1], repeat=H-1):
    H_div_num = [i+1 for i, j in enumerate(H_div_pattern) if j == 1] + [H]
    sum_grid = np.zeros((len(H_div_num), W), dtype=np.int32)
    if len(H_div_num) != 0:
        start_H = 0
        for idx, div_num in enumerate(H_div_num):
            for w in range(W):
                sum_grid[idx, w] = np.sum(grid[start_H:div_num, w])
            start_H = div_num
    
    cost = len(H_div_num) - 1
    if (sum_grid > K).any():
        break
    
    block_cost = sum_grid[:, 0]
    for w in range(1, W):
        tmp = sum_grid[:, w] + block_cost
        if (tmp <= K).all():
            block_cost = tmp
        else:
            block_cost = sum_grid[:, w]
            cost += 1
        if min_cost is not None and cost >= min_cost:
            break
    
    if min_cost is None or min_cost > cost:
        min_cost = cost
    
print(min_cost)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
H, W, K = map(int, input().split())  # H行, W列, 1エリア内にK個以下のホワイトチョコレートにしたい
gridgraph = [list(input()) for _ in range(H)]
ans = 10**10
# Hに関するビット全探索を行うイメージ
for i in range(1 << (H-1)):
    bits = []
    for j in range(H-1):
        bits.append((i >> j) & 1)  # iのjビット目が立っているかどうかを調べる
    separate_row = True
    cnt = sum(bits)  # 横に切る場所, 最終的に ans = min(ans, cnt)をする
    all_accumulation = defaultdict(int)
    # その列を区切るか区切らないかを貪欲法で判断していく
    for j in range(W):
        now_area = 0
        now_accumulation = defaultdict(int)
        for i in range(H):
            # iが変動していく
            # 今見ている列のものだけも、数えておく必要がある
            now_accumulation[now_area] += int(gridgraph[i][j])
            if i != H-1:
                now_area += bits[i]
        # その列を見終わったら、cntをインクリメントすることでリセットできる
        if all([K >= v for v in now_accumulation.values()]):
            for key in now_accumulation.keys():
                all_accumulation[key] += now_accumulation[key]
            # 累積されていたものに足した
            if all([K >= v for v in all_accumulation.values()]):
                continue
            else:
                cnt += 1
                # 今見ていたところの左側を分割して、累積部分の値を現在のものに変更する
                all_accumulation = now_accumulation.copy()
        else:
            # その行だけを見てもKを超えるものがあるなら行の分割の仕方が論外
            separate_row = False
            break
    if not separate_row:
        break
    else:
        ans = min(ans, cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    H, W, K = map(int, input().split())
    S = [list(map(int,list(input()))) for _ in range(H)]
    
    ans = float('inf')
    for i in range(1<<H-1):
        cut = []
        for j in range(H):
            if (i >> j) & 1:
                cut.append(j+1)

        tmp_S = [[0] * W for _ in range(len(cut) + 1)]
        tmp_id = 0
        for i in range(H):
            if i in cut:
                tmp_id += 1
            for j in range(W):
                tmp_S[tmp_id][j] += S[i][j]
        
        cnt = len(cut)
        white = [0] * (len(cut)+1)

        flag = False
        for w in range(W):
            for i in range(len(cut) + 1):
                white[i] += tmp_S[i][w]
                if white[i] > K:
                    cnt += 1
                    flag = True
                    break
            if flag:
                for i in range(len(cut) + 1):
                    white[i] = tmp_S[i][w]
                flag = False
        ans = min(ans, cnt)

    print(ans)

                


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from itertools import product

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

ans = 10**9
count = 0
for h_div in product([0, 1], repeat=H-1):
    h_div = [idx+1 for idx in range(H-1) if h_div[idx]]
    h_div = [0] + h_div + [H]
    count = len(h_div) - 2  # 縦割りの回数

    flag = True
    for i in range(len(h_div) - 1):
        h1, h2 = h_div[i], h_div[i+1]
        if max([sum([s[h][w] for h in range(h1, h2)]) for w in range(W)]) > K:
            flag = False
    if not flag:
        continue

    tmp = [0] * (len(h_div) - 1)
    for w in range(W):
        for i in range(len(h_div) - 1):
            h1, h2 = h_div[i], h_div[i+1]
            tmp[i] += sum([s[h][w] for h in range(h1, h2)])
            if tmp[i] > K:
                count += 1
                tmp = [0] * (len(h_div) - 1)
        if sum(tmp) == 0:
            for i in range(len(h_div) - 1):
                h1, h2 = h_div[i], h_div[i+1]
                tmp[i] += sum([s[h][w] for h in range(h1, h2)])
    ans = min(ans, count)

print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import product

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

ans = 10**9
count = 0
for h_div in product([0, 1], repeat=H-1):
    h_div = [idx+1 for idx in range(H-1) if h_div[idx]]
    h_div = [0] + h_div + [H]
    count = len(h_div) - 2  # 縦割りの回数

    tmp = [0] * (len(h_div) - 1)
    w_prev = -1
    for w in range(W):
        for i in range(len(h_div) - 1):
            h1, h2 = h_div[i], h_div[i+1]
            tmp[i] += sum([s[h][w] for h in range(h1, h2)])
            if tmp[i] > K:
                if w - w_prev == 1:
                    count += 10**9
                    break
                else:
                    count += 1
                tmp = [0] * (len(h_div) - 1)
                w_prev = w
        else:
            if sum(tmp) == 0:
                for i in range(len(h_div) - 1):
                    h1, h2 = h_div[i], h_div[i+1]
                    tmp[i] += sum([s[h][w] for h in range(h1, h2)])
            continue
        break
    ans = min(ans, count)

print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import product

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

ans = 10**9
count = 0
for h_div in product([0, 1], repeat=H-1):
    h_div = [idx+1 for idx in range(H-1) if h_div[idx]]
    h_div = [0] + h_div + [H]
    count = len(h_div) - 2  # 縦割りの回数

    tmp = [0] * (len(h_div) - 1)
    w_prev = -1
    for w in range(W):
        for i in range(len(h_div) - 1):
            h1, h2 = h_div[i], h_div[i+1]
            tmp[i] += sum([item[w] for item in s[h1:h2]])
            if tmp[i] > K:
                if w - w_prev == 1:
                    count += 10**9
                else:
                    count += 1
                tmp = [0] * (len(h_div) - 1)
                w_prev = w
        
        if sum(tmp) == 0:
            for i in range(len(h_div) - 1):
                h1, h2 = h_div[i], h_div[i+1]
                tmp[i] += sum([item[w] for item in s[h1:h2]])
    ans = min(ans, count)

print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import product

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

ans = 10**9
count = 0
for h_div in product([0, 1], repeat=H-1):
    h_div = [idx+1 for idx in range(H-1) if h_div[idx]]
    h_div = [0] + h_div + [H]
    count = len(h_div) - 2  # 縦割りの回数

    tmp = [0] * (len(h_div) - 1)
    w_prev = -1
    for w in range(W):
        for i in range(len(h_div) - 1):
            h1, h2 = h_div[i], h_div[i+1]
            tmp[i] += sum([item[w] for item in s[h1:h2]])
            if tmp[i] > K:
                if w - w_prev == 1:
                    count += 10**9
                else:
                    count += 1
                tmp = [0] * (len(h_div) - 1)
        
        if sum(tmp) == 0:
            for i in range(len(h_div) - 1):
                h1, h2 = h_div[i], h_div[i+1]
                tmp[i] += sum([item[w] for item in s[h1:h2]])
    ans = min(ans, count)

print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import product

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

ans = 10**9
count = 0
for h_div in product([0, 1], repeat=H-1):
    h_div = [idx+1 for idx in range(H-1) if h_div[idx]]
    h_div = [0] + h_div + [H]
    count = len(h_div) - 2  # 縦割りの回数

    tmp = [0] * (len(h_div) - 1)
    for w in range(W):
        for i in range(len(h_div) - 1):
            h1, h2 = h_div[i], h_div[i+1]
            tmp[i] += sum([item[w] for item in s[h1:h2]])
            if tmp[i] > K:
                count += 1
                tmp = [0] * (len(h_div) - 1)
        
        if sum(tmp) == 0:
            for i in range(len(h_div) - 1):
                h1, h2 = h_div[i], h_div[i+1]
                tmp[i] += sum([item[w] for item in s[h1:h2]])
    ans = min(ans, count)

print(ans)

Submission status: Wrong Answer

Solution code:
h,w,k=map(int,input().split())
s=['' for _ in range(h)]
for i in range(h):
  s[i]=input()
b=2**(h-1)
ans=10000
for i in range(b):  #bit  1:割る 0:割らない
  bit=i
  #print(i)
  sep=0
  for ii in range(h-1):   #部分の数
    if bit%2==1:
      sep+=1
    bit=bit//2
  bit=i
  cnt=[0]*(sep+1)
  cntt=[0]*(sep+1)
  ref=False
  cntref=False
  ans1=0
  prt=[]
  for j in range(w):  #横に一個ずつ見ていく
    ind=0
    bit=i
    if ref==True and cntref==False:
      cnt=[0]*(sep+1)
      ans1+=1
      ref=False
    elif cntref==True:
      cnt=cntt[:]
      #ans1+=1
      cntref=False
    cntt=[0]*(sep+1)
    for l in range(h):   #縦
      if s[l][j]=='1':
        cntt[ind]+=1
        if cnt[ind]+cntt[ind]==k and cntref==False:
          #一度の更新でk+1以上になった時バグる
          ref=True
          prt.append(j+1)
        elif cnt[ind]+cntt[ind]>k:
          cntref=True
          ref=False
          ans1+=1
          prt.append(j)
      f=bit%2
      bit=bit//2
      if f==1:
        ind+=1
    if ref==False and cntref==False:
      for m in range(sep+1):
        cnt[m]+=cntt[m]
  ans1+=sep
  ans=min(ans,ans1)

print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    inf = 100100100
    ans = inf
    H, W, K = map(int, input().split())
    S = [0]*H
    for i in range(H):
        S[i] = [int(x) for x in sys.stdin.readline().strip()]
    for i in range(2**(H-1)):
        group = [0]
        g = 0
        for j in range(H-1):
            if (i >> j) & 1:
                g += 1
            group.append(g)
        g += 1
        c = [[0]*W]*g
        for j in range(H):
            for k in range(W):
                c[group[j]][k] += S[j][k]
        num = g-1
        now = [0]*g
        def large(now):
            for n in now:
                if n > K:
                    return True
            else:
                return False
        def v_vec(twodlis, k):
            ans = []
            for lis in twodlis:
                ans.append(lis[k])
            return ans
        for k in range(W):
            for n in range(g):
                now[n] += v_vec(c,k)[n]
            if large(now):
                now = v_vec(c,k)
                num += 1
                if large(now):
                    num = inf
                    break

        ans = min(ans, num)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import copy
H,W,K=map(int,input().split())
S=[]
for _ in range(H):
    S.append([int(x) for x in list(input())])

ans=(H-1)+(W-1)

for i in range(2**(H-1)):
    check=[0]*H
    for j in range(H-1):
        if ((i>>j)&1):
            check[j+1]=check[j]+1
        else:
            check[j+1]=check[j]
    
    g=check[H-1]+1
    A=[0]*g
    c=0
    f=0
    for j in range(W):
        B=[0]*g
        for k in range(H):
            if S[k][j]==1:
                B[check[k]]+=1
            if B[check[k]]>K:
                c=10**4
                f=1
                break
        #print("AB",A,B)
        for l in range(g):
            if A[l]+B[l]>K:
                c+=1
                A=copy.copy(B)
                break
            else:
                A[l]+=B[l]
    if f:
        break
    ans=min(ans,c+g-1)

print(ans)

Submission status: Wrong Answer

Solution code:
import copy
H,W,K=map(int,input().split())
S=[]
for _ in range(H):
    S.append([int(x) for x in list(input())])

ans=(H-1)+(W-1)

for i in range(2**(H-1)):
    check=[0]*H
    for j in range(H-1):
        if ((i>>j)&1):
            check[j+1]=check[j]+1
        else:
            check[j+1]=check[j]
    
    g=check[H-1]+1
    A=[0]*g
    c=0
    f=0
    for j in range(W):
        B=[0]*g
        for k in range(H):
            if S[k][j]==1:
                B[check[k]]+=1
        for k in B:
            if k>K:
                c=10**4
                f=1
                break
        #print("AB",A,B)
        for l in range(g):
            if A[l]+B[l]>K:
                c+=1
                A=copy.copy(B)
                break
            else:
                A[l]+=B[l]
    if f:
        break
    ans=min(ans,c+g-1)

print(ans)

Submission status: Wrong Answer

Solution code:
import copy
H,W,K=map(int,input().split())
S=[]
for _ in range(H):
    S.append([int(x) for x in list(input())])

ans=(H-1)+(W-1)

for i in range(2**(H-1)):
    check=[0]*H
    for j in range(H-1):
        if ((i>>j)&1):
            check[j+1]=check[j]+1
        else:
            check[j+1]=check[j]
    
    g=check[H-1]+1
    A=[0]*g
    c=0
    f=0
    for j in range(W):
        B=[0]*g
        for k in range(H):
            if S[k][j]==1:
                B[check[k]]+=1
        if B[check[k]]>K:
            f=1
            c=10**4
            break
        #print("AB",A,B)
        for l in range(g):
            if A[l]+B[l]>K:
                c+=1
                A=copy.copy(B)
                break
            else:
                A[l]+=B[l]
        if f==1:
            break
    #print(c,g)
    ans=min(ans,c+g-1)

print(ans)

Submission status: Wrong Answer

Solution code:
import copy
H,W,K=map(int,input().split())
S=[]
for _ in range(H):
    S.append([int(x) for x in list(input())])

ans=(H-1)+(W-1)

for i in range(2*(H-1)):
    check=[0]*H
    for j in range(H-1):
        if ((i>>j)&1):
            check[j+1]=check[j]+1
        else:
            check[j+1]=check[j]
    
    g=check[H-1]+1
    A=[0]*g
    c=0
    f=0
    for j in range(W):
        B=[0]*g
        for k in range(H):
            if S[k][j]==1:
                B[check[k]]+=1
        if B[check[k]]>K:
            f=1
            c=10**4
            break
        #print("AB",A,B)
        for l in range(g):
            if A[l]+B[l]>K:
                c+=1
                A=copy.deepcopy(B)
                break
            else:
                A[l]+=B[l]
        if f==1:
            break
    #print(c,g)
    ans=min(ans,c+g-1)

print(ans)

Submission status: Wrong Answer

Solution code:
import copy
H,W,K=map(int,input().split())
S=[]
for _ in range(H):
    S.append([int(x) for x in list(input())])

ans=(H-1)*(W-1)

for i in range(2*(H-1)):
    check=[0]*H
    for j in range(H-1):
        if ((i>>j)&1):
            check[j+1]=check[j]+1
        else:
            check[j+1]=check[j]
    
    g=check[H-1]+1
    A=[0]*g
    c=0
    f=0
    for j in range(W):
        B=[0]*g
        for k in range(H):
            if S[k][j]==1:
                B[check[k]]+=1
        if B[check[k]]>K:
            f=1
            c=10**4
            break
        #print("AB",A,B)
        for l in range(g):
            if A[l]+B[l]>K:
                c+=1
                A=copy.deepcopy(B)
                break
            else:
                A[l]+=B[l]
        if f==1:
            break
    #print(c,g)
    ans=min(ans,c+g-1)

print(ans)

Submission status: Wrong Answer

Solution code:
import copy
H,W,K=map(int,input().split())
S=[]
for _ in range(H):
    S.append([int(x) for x in list(input())])

ans=(H-1)*(W-1)

for i in range(2*(H-1)):
    check=[0]*H
    for j in range(H-1):
        if ((i>>j)&1):
            check[j+1]=check[j]+1
        else:
            check[j+1]=check[j]
    
    g=check[H-1]+1
    A=[0]*g
    c=0
    f=0
    for j in range(W):
        B=[0]*g
        for k in range(H):
            if S[k][j]==1:
                B[check[k]]+=1
        if B[check[k]]>K:
            f=1
            c=10**4
            break
        #print("AB",A,B)
        for l in range(g):
            if A[l]+B[l]>K:
                c+=1
                A=copy.copy(B)
                break
            else:
                A[l]+=B[l]
        if f==1:
            break
    #print(c,g)
    ans=min(ans,c+g-1)

print(ans)

Submission status: Wrong Answer

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

def get_switch(n):
    allswitch = []
    for i in range(0,2**n):
        bin_str = format(i,'0'+str(n)+'b')
        swt = list(map(int,list(bin_str)))
        allswitch.append(swt)
    return allswitch
    
def greedy(lines,w,k):
    h = len(lines)
    ans = 0
    cnt = [0 for i in range(h)]
    for i in range(w):
        tmp_cnt = [0 for i in range(h)]
        flag = False
        for j in range(h):
            if lines[j][i] > k:
                return 10 * w
            cnt[j] += lines[j][i]
            tmp_cnt[j] += lines[j][i]
            if cnt[j] > k:
                ans += 1
                flag = True
        if flag:
            cnt = tmp_cnt
    return ans
                
            

h,w,k = map(int,input().split())
field = [list(input().replace("\n","")) for _ in range(h)]

ans = h*w

for swh in get_switch(2**(h-1)):
    line_num = sum(swh) + 1
    tmp_field = [[0 for i in range(w)] for j in range(line_num)]
    for i in range(w):
        flag = 0
        for j in range(h):
            if field[j][i] == '1':
                tmp_field[flag][i] += 1
            if swh[j] == 1:
                flag += 1
    ans = min(ans, greedy(tmp_field,w,k) + line_num - 1)

print(ans)

Submission status: Wrong Answer

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

def get_switch(n):
    allswitch = []
    for i in range(0,2**n):
        bin_str = format(i,'0'+str(n)+'b')
        swt = list(map(int,list(bin_str)))
        allswitch.append(swt)
    return allswitch

h,w,k = map(int,input().split())
field = [list(input().replace("\n","")) for _ in range(h)]

ans = h*w

for swh in get_switch(2**(h-1)):
    line_num = sum(swh) + 1
    cnt = [0 for i in range(line_num)]
    ans_i = 0
    for i in range(w):
        flag = 0
        for j in range(h):
            if field[j][i] == '1':
                cnt[flag] += 1
                if cnt[flag] > k:
                    cnt = [0 for i in range(line_num)]
                    ans_i += 1
                    break
            if swh[j] == 1:
                flag += 1
    ans = min(ans, ans_i)
print(ans)

Submission status: Wrong Answer

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

ans = H*W

def countWhite(ytop, ybottom, xleft, xright):
    ret = sum([sum(s[xleft:xright]) for s in S[ytop:ybottom]])
    return ret
    

for h_div in range(1 << H-1):
    count = 0
    cut = [0]
    for i in range(H):
        if h_div >> i & 1:
            cut.append(i+1)
            count += 1
    cut.append(H)
    if count > ans:
        continue
    
    left = 0
    for right in range(1, W+1):
        white = 0
        for i in range(len(cut)-1):
            white = max(white, countWhite(cut[i], cut[i+1], left, right))
        
        if white > K:
            left = right-1
            count += 1
            if count > ans:
                break
    else:
        if count < ans:
            ans = count

print(ans)

Submission status: Wrong Answer

Solution code:
import functools
def main():
    H, W, K = map(int, input().split())
    S = tuple(tuple(map(int, tuple(input()))) for _ in range(H))
    
    ans = 10**9
    
    for i in range(1 << H-1): # 横の割り方について全探索 O(2^H-1)
        cut_count = 0
        cuts_h = [0]
        for c in range(1, H):
            if i & 1:
                cuts_h.append(c)
                cut_count += 1
            i = i >> 1
        cuts_h.append(H)
        if cut_count > ans:
            continue
        
        # 縦の最適な割り方を貪欲に求める
        cut_v_bef = 0
        for cut_x in range(1,W+1):
            max_w = 0
            for ci in range(1,len(cuts_h)):
                choco = S[cuts_h[ci-1]:cuts_h[ci]]
                w = sum(list(map(lambda x: sum(x[cut_v_bef:cut_x]), choco)))
                if w > max_w:
                    max_w = w
            if max_w > K:
                cut_v_bef = cut_x-1
                cut_count += 1
        
        if cut_count < ans:
            ans = cut_count
    
    print(ans)
        

if __name__ == "__main__":
    main()