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:
#coding:utf-8
import sys,os
from collections import defaultdict, deque
from fractions import gcd
from math import ceil, floor
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7
    H,W,K = LMIIS()
    from itertools import accumulate
    S = [list(accumulate(map(int,input()))) for _ in range(H)]
    


    def divide(pattern):
        lenP = len(pattern)
        divided = [0]*lenP
        count = lenP - 1
        for i in range(1,W):
            # print('divided=',divided)
            for j in range(lenP):
                if K < pattern[j][i] - divided[j]:
                    for l in range(lenP):
                        divided[l] = pattern[l][i-1]
                    count += 1
                    break
        # print('count=',count)
        return count
                    

            
        



    ans = H+W

    for i in range(2**H):
        pattern = []
        line = [0] * W
        for j in range(H):
            for k in range(W):
                line[k] += S[j][k]
            if 2**j & i:
                pattern.append(line)
                line = [0] * W
        pattern.append(line)
        # print(pattern)
        ans = min(divide(pattern),ans)
    print(ans)
    return
        
    

                

                
                

    

    

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

ans = 10**9+7

for i in range(1<<(h-1)):
    box = [[0] * w]
    bcnt = 0 #縦のindex

    box[bcnt] = [s + b for s, b in zip(S[0], box[bcnt])]

    #横に適当に線を入れる(=その分のboxを増やす)
    #線が入らなかったらその区画にそのまま値を入れる
    #区画ごとの畳み込み
    for j in range(1, h):
        if (i >> (j-1)) & 1:
            bcnt += 1
            box.append([0] * w)
        box[bcnt] = [s + b for s, b in zip(S[j], box[bcnt])]

    #
    # if not all([all([i<=k for i in b]) for b in box]):
    #     continue

    
    cutcnt = len(box) - 1 #すでに縦にに切っている分の個数
    cnt = [0] * len(box)    #区画ごとのcntのbox
    #縦ごとにグループに白チョコの個数を追加していく
    for m in range(w):
        for n in range(len(box)):
            cnt[n] += box[n][m] #n番目のグループにbox n番目m列目の個数を追加する
        if any([c > k for c in cnt]):  #グループ内白チョコの個数がkを超えているグループが1つでもあったら縦線を1つ追加する
            cutcnt += 1
            #個数がオーバーしたので改めて今の列を新しいグループの最初の列としてこれから白チョコを追加していく
            for n in range(len(box)):
                cnt[n] = box[n][m]
    ans = min(ans, cutcnt)

print(ans)

Submission status: Wrong Answer

Solution code:
h, w, kkk = map(int, input().split())
choco = [0]*h
for i in range(h):
  choco[i] = input()

answer = h+w-2
for i in range(max([2**(h-1), 1])):
  flag = True
  board = [0]*(h-1)
  for j in range(h-1):
    if (i >> j)&1:
      board[j] = 1
  count = sum(board)
  key = [0]*(count+1)
  ans = count
  for p in range(w):
    k = 0
    for q in range(h):
      if choco[q][p] == "1":
        key[k] += 1
      if q == h-1:
        break
      if board[q] == 1:
        k += 1
    for q in range(count+1):
      if key[q] <= kkk:
        continue
      ans += 1
      if p == w-1:
        flag = False
      key = [0]*(count+1)
      k = 0
      for q in range(h):
        if choco[q][p] == "1":
          key[k] += 1
        if q == h-1:
          break
        if board[q] == 1:
          k += 1
      break
  if ans < answer and flag:
    answer = ans
print(answer)

Submission status: Wrong Answer

Solution code:
h, w, kkk = map(int, input().split())
choco = [0]*h
for i in range(h):
  choco[i] = input()
answer = h+w-2
for i in range(max([2*(h-1), 1])):
  flag = True
  board = [0]*(h-1)
  for j in range(h-1):
    if (i >> j)&1:
      board[j] = 1
  count = sum(board)
  key = [0]*(count+1)
  ans = count
  for p in range(w):
    max_board = [0]*(count+1)
    k = 0
    for q in range(h):
      if choco[q][p] == "1":
        max_board[k] += 1
      if q == h-1:
        if max(max_board) > kkk:
          flag = False
        break
      if board[q] == 1:
        k += 1
  if not flag:
    continue
  for p in range(w):
    k = 0
    for q in range(h):
      if choco[q][p] == "1":
        key[k] += 1
      if q == h-1:
        break
      if board[q] == 1:
        k += 1
    for q in range(count+1):
      if key[q] <= kkk:
        continue
      ans += 1
      key = [0]*(count+1)
      k = 0
      for q in range(h):
        if choco[q][p] == "1":
          key[k] += 1
        if q == h-1:
          break
        if board[q] == 1:
          k += 1
      break
  if ans < answer and flag:
    answer = ans
print(answer)

Submission status: Wrong Answer

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

h, w, K = [int(x) for x in input().split()]
s = [input().rstrip() for _ in range(h)]
# print(s)
# print(len(s[1]))

# ans = h + w - 2
ans = h + w - 2
for i in range(2 ** (h - 1)):
    new_s = []
    cnt = 0
    i_bin = bin(i)[2:].zfill(h - 1)
    add = []
    for j in range(h - 1):
        if i_bin[j] == "1":
            cnt += 1
            add.append(s[j])
            new_s.append(add)
            add = []
        else:
            add.append(s[j])
        if j == h - 2:
            add.append(s[-1])
            new_s.append(add)
    if h == 1:
        new_s = [s]
    #print(len(new_s))
    total = [0] * len(new_s)
    #print(new_s)
    for k in range(w):
        # print(k)
        tmp_list = [0]*len(new_s)
        #print(total)
        flag = 0
        for l in range(len(new_s)):
            tmp = sum([int(new_s[l][x][k]) for x in range(len(new_s[l]))])
            # tmp_list[l] = tmp
            # print(tmp)
            if tmp > K:
                cnt = 10**18
                flag = 1
                break
            tmp_list[l] = tmp
            total[l] += tmp
        if sum(tmp_list) > K:
            flag = 1
        if flag:
            break
        for m in total:
            flag_2 = 1
            if m > K:
                cnt += 1
                total = tmp_list
                flag_2 = 0
                break
      
    if not flag:
        #print(cnt)
        ans = min(ans, cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
h, w, kkk = map(int, input().split())
choco = [0]*h
for i in range(h):
  choco[i] = input()
answer = h+w-2
for i in range(max([2*(h-1), 1])):
  flag = True
  board = [0]*(h-1)
  for j in range(h-1):
    if (i >> j)&1:
      board[j] = 1
  count = sum(board)
  key = [0]*(count+1)
  ans = count
  for p in range(w):
    max_board = [0]*(count+1)
    k = 0
    for q in range(h):
      if choco[q][p] == "1":
        max_board[k] += 1
      if q == h-1:
        if max(max_board) > kkk:
          flag = False
        break
      if board[q] == 1:
        k += 1
  for p in range(w):
    k = 0
    for q in range(h):
      if choco[q][p] == "1":
        key[k] += 1
      if q == h-1:
        break
      if board[q] == 1:
        k += 1
    for q in range(count+1):
      if key[q] <= kkk:
        continue
      ans += 1
      if p == w-1:
        flag = False
      key = [0]*(count+1)
      k = 0
      for q in range(h):
        if choco[q][p] == "1":
          key[k] += 1
        if q == h-1:
          break
        if board[q] == 1:
          k += 1
      break
  if ans < answer and flag:
    answer = ans
print(answer)

Submission status: Wrong Answer

Solution code:
H, W, K = map(int, input().split())

S = []
for _ in range(H):
    S.append(input())

ans = H * W

for c in range(2**(H-1)):
    num_lines = 0

    g = {}
    tmp = c
    g_index = 0
    for h in range(H):
        g[h] = g_index 
        num_groups = g_index 
        if tmp & 1 == 1:
            g_index += 1
        tmp <<= 1

    num_groups += 1
    num_lines = num_groups - 1 
    g_sum = [0] * num_groups

    for w in range(W):
        tmp = g_sum[:]

        ok = True
        ok2 = True
        for h in range(H):
            tmp[g[h]] += int(S[h][w])
        
            if tmp[g[h]] > K :
                # modoru
                ok = False
                if g_sum[g[h]] == 0:
                    ok2 = False

        if ok :
            g_sum = tmp
        else:
            if ok2:
                g_sum = [tmp[gi] - g_sum[gi] for gi in range(num_groups)]
                num_lines += 1
            else:
                break

    if not ok2:
        continue

    if ans > num_lines:
        ans = num_lines


print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import product
h, w, k = map(int, input().split())
CHOCO = [list(map(int, input())) for _ in range(h)]
INF = 10**5

it = ["01"]*(h-1)
ans = INF
for x in product(*it):
    cnt = sum(map(int, x))
    L = 0
    R = 0
    while R != w:
        R += 1
        tmp = 0
        pieces = []
        for idx, split in enumerate(map(int, x+("0",))):
            if split:
                pieces.append(tmp)
                tmp = 0
            tmp += sum(CHOCO[idx][L:R])
        else:
            pieces.append(tmp)

        if all(piece <= k for piece in pieces):
            continue
        R -= 1
        L = R
        cnt += 1

    ans = min(ans, cnt)
print(ans)

Submission status: Wrong Answer

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

h, w, K = [int(x) for x in input().split()]
s = [input().rstrip() for _ in range(h)]
# print(s)
# print(len(s[1]))

# ans = h + w - 2
ans = h + w - 2
for i in range(2 ** (h - 1)):
    new_s = []
    cnt = 0
    i_bin = bin(i)[2:].zfill(h - 1)
    add = []
    for j in range(h - 1):
        if i_bin[j] == "1":
            cnt += 1
            add.append(s[j])
            new_s.append(add)
            add = []
        else:
            add.append(s[j])
        if j == h - 2:
            add.append(s[-1])
            new_s.append(add)
    if h == 1:
        new_s = [s]
    #print(len(new_s))
    total = [0] * len(new_s)
    #print(new_s)
    for k in range(w):
        # print(k)
        tmp_list = [0]*len(new_s)
        #print(total)
        flag = 0
        for l in range(len(new_s)):
            tmp = sum([int(new_s[l][x][k]) for x in range(len(new_s[l]))])
            # tmp_list[l] = tmp
            # print(tmp)
            if tmp > K:
                cnt = 10**18
                flag = 1
                break
            tmp_list[l] = tmp
            total[l] += tmp
        if flag:
            break
        flag_2 = 1
        for m in total:
            if m > K:
                cnt += 1
                total = tmp_list
                flag_2 = 0
                break
        if flag_2:
            for m in total:
                if m == K and k != w - 1:
                  cnt += 1
                  total = [0]*len(new_s)
                  break
    if not flag:
        #print(cnt)
        ans = min(ans, cnt)
print(ans)

Submission status: Wrong Answer

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

h, w, K = [int(x) for x in input().split()]
s = [input().rstrip() for _ in range(h)]
# print(s)
# print(len(s[1]))

# ans = h + w - 2
ans = h + w - 2
for i in range(2 ** (h - 1)):
    new_s = []
    cnt = 0
    i_bin = bin(i)[2:].zfill(h - 1)
    add = []
    for j in range(h - 1):
        if i_bin[j] == "1":
            cnt += 1
            add.append(s[j])
            new_s.append(add)
            add = []
        else:
            add.append(s[j])
        if j == h - 2:
            add.append(s[-1])
            new_s.append(add)
    if h == 1:
        new_s = [s]
    #print(len(new_s))
    total = [0] * len(new_s)
    #print(new_s)
    for k in range(len(s[0])):
        # print(k)
        tmp_list = [0]*len(new_s)
        #print(total)
        flag = 0
        for l in range(len(new_s)):
            #print(l)
            #sprint(len(new_s))
            #print(len(new_s[l]))
            #print(k)
            #print(len(new_s[0][1]))
            #print(len(new_s[0][1]))
            #print(new_s[0][1])
            #print(new_s[0][1][k])
            tmp = sum([int(new_s[l][x][k]) for x in range(len(new_s[l]))])
            # tmp_list[l] = tmp
            # print(tmp)
            if tmp > K:
                cnt = 10**18
                flag = 1
                break
            tmp_list[l] = tmp
            total[l] += tmp
            # print(total)
        # print(total)
        if flag:
            break
        for m in total:
            if m > K:
                cnt += 1
                total = tmp_list
                break
            elif m == K and k != w - 1:
                cnt += 1
                total = [0]*len(new_s)
                break
    if not flag:
        #print(cnt)
        ans = min(ans, cnt)
print(ans)

Submission status: Wrong Answer

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

h, w, K = [int(x) for x in input().split()]
s = [input().rstrip() for _ in range(h)]

# ans = h + w - 2
ans = h + w - 2
for i in range(2 ** (h - 1)):
    new_s = []
    cnt = 0
    i_bin = bin(i)[2:].zfill(h - 1)
    add = []
    for j in range(h - 1):
        if i_bin[j] == "1":
            cnt += 1
            add.append(s[j])
            new_s.append(add)
            add = []
        else:
            add.append(s[j])
        if j == h - 2:
            add.append(s[-1])
            new_s.append(add)
    if h == 1:
        new_s = [s]
    # print(len(new_s))
    total = [0] * len(new_s)
    # print(new_s)
    for k in range(w):
        tmp_list = [0]*len(new_s)
        flag = 0
        for l in range(len(new_s)):
            tmp = sum([int(new_s[l][x][k]) for x in range(len(new_s[l]))])
            # tmp_list[l] = tmp
            # print(tmp)
            if tmp > K:
                cnt = 10**18
                flag = 1
                break
            tmp_list[l] = tmp
            total[l] += tmp
            # print(total)
        # print(total)
        if flag:
            break
        for m in total:
            if m > K:
                cnt += 1
                total = tmp_list
                break
            elif m == K and k != w - 1:
                cnt += 1
                total = [0]*len(new_s)
                break
    if not flag:
        #print(cnt)
        ans = min(ans, cnt)
print(ans)

Submission status: Wrong Answer

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

h, w, K = [int(x) for x in input().split()]
s = [input().rstrip() for _ in range(h)]

# ans = h + w - 2
ans = h + w - 2
for i in range(2 ** (h - 1)):
    new_s = []
    cnt = 0
    i_bin = bin(i)[2:].zfill(h - 1)
    add = []
    for j in range(h - 1):
        if i_bin[j] == "1":
            cnt += 1
            add.append(s[j])
            new_s.append(add)
            add = []
        else:
            add.append(s[j])
        if j == h - 2:
            add.append(s[-1])
            new_s.append(add)
    if h == 1:
        new_s = [s]
    # print(len(new_s))
    total = [0] * len(new_s)
    # print(new_s)
    for k in range(w):
        tmp_list = [0]*len(new_s)
        flag = 0
        for l in range(len(new_s)):
            tmp = sum([int(new_s[l][x][k]) for x in range(len(new_s[l]))])
            # tmp_list[l] = tmp
            # print(tmp)
            if tmp > K:
                flag = 1
                break
            tmp_list[l] = tmp
            total[l] += tmp
            # print(total)
        # print(total)
        if flag:
            break
        for m in total:
            if m > K:
                cnt += 1
                total = tmp_list
                break
            elif m == K and k != w - 1:
                cnt += 1
                total = [0]*len(new_s)
                break
    if not flag:
        ans = min(ans, cnt)
print(ans)

Submission status: Wrong Answer

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

h, w, K = [int(x) for x in input().split()]
s = [input().rstrip() for _ in range(h)]

# ans = h + w - 2
ans = h + w - 2
for i in range(2 ** (h - 1)):
    new_s = []
    cnt = 0
    i_bin = bin(i)[2:].zfill(h - 1)
    add = []
    for j in range(h - 1):
        if i_bin[j] == "1":
            cnt += 1
            add.append(s[j])
            new_s.append(add)
            add = []
        else:
            add.append(s[j])
        if j == h - 2:
            add.append(s[-1])
            new_s.append(add)
    if h == 1:
        new_s = [s]
    # print(len(new_s))
    total = [0] * len(new_s)
    # print(new_s)
    tmp_list = [0]*len(new_s)
    for k in range(w):
        flag = 0
        for l in range(len(new_s)):
            tmp = sum([int(new_s[l][x][k]) for x in range(len(new_s[l]))])
            # tmp_list[l] = tmp
            # print(tmp)
            if tmp > K:
                flag = 1
                break
            tmp_list[l] = tmp
            total[l] += tmp
            # print(total)
        # print(total)
        if flag:
            break
        for m in total:
            if m > K:
                cnt += 1
                total = tmp_list
                break
            elif m == K and k != w - 1:
                cnt += 1
                total = [0]*len(new_s)
                break
            else:
                pass
    if not flag:
        ans = min(ans, cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
from itertools import product

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

if sum(sum(s) for s in S)<=K:
    print(0)
else:
    answer = (H-1) * (W-1)
    for X in product([False,True], repeat=H-1):
        ans = np.sum(X)
        if ans >= answer:
            continue
        M = [[0]]
        for i, x in enumerate(X):
            if x:
                M.append([])
            M[-1].append(i+1)
        D = np.array([0]*len(M))
        for s in S:
            D[:] += [sum(s[i] for i in m) for m in M]
            if any(d > K  for d in D):
                ans += 1
                if ans >= answer:
                    break
                D[:] = [sum(s[i] for i in m) for m in M]
                if any(d > K for d in D):
                    break

        if answer > ans:
            answer = ans
        elif answer==1:
            break

    print(min(answer,ans))

Submission status: Wrong Answer

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

h, w, K = [int(x) for x in input().split()]
s = [input().rstrip() for _ in range(h)]

# ans = h + w - 2
ans = h + w - 2
for i in range(2 ** (h - 1)):
    new_s = []
    cnt = 0
    i_bin = bin(i)[2:].zfill(h - 1)
    add = []
    for j in range(h - 1):
        if i_bin[j] == "1":
            cnt += 1
            add.append(s[j])
            new_s.append(add)
            add = []
        else:
            add.append(s[j])
        if j == h - 2:
            add.append(s[-1])
            new_s.append(add)
    if h == 1:
        new_s = [s]
    # print(len(new_s))
    total = [0] * len(new_s)
    # print(new_s)
    for k in range(w):
        flag = 0
        tmp_list = [0]*len(new_s)
        for l in range(len(new_s)):
            tmp = sum([int(new_s[l][x][k]) for x in range(len(new_s[l]))])
            # tmp_list[l] = tmp
            # print(tmp)
            if tmp > K:
                flag = 1
                break
            tmp_list[l] = tmp
            total[l] += tmp
            # print(total)
        # print(total)
        if flag:
            break
        for m in total:
            if m > K:
                cnt += 1
                total = tmp_list
                break
            elif m == K and k != w - 1:
                cnt += 1
                total = [0]*len(new_s)
                break
            else:
                pass
    if not flag:
        ans = min(ans, cnt)
print(ans)

Submission status: Wrong Answer

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

h, w, K = [int(x) for x in input().split()]
s = [input().rstrip() for _ in range(h)]

# ans = h + w - 2
ans = h + w - 2
for i in range(2 ** (h - 1)):
    new_s = []
    cnt = 0
    i_bin = bin(i)[2:].zfill(h - 1)
    add = []
    for j in range(h - 1):
        if i_bin[j] == "1":
            cnt += 1
            add.append(s[j])
            new_s.append(add)
            add = []
        else:
            add.append(s[j])
        if j == h - 2:
            add.append(s[-1])
            new_s.append(add)
    # print(len(new_s))
    total = [0] * len(new_s)
    # print(new_s)
    for k in range(w):
        flag = 0
        tmp_list = [0]*len(new_s)
        for l in range(len(new_s)):
            tmp = sum([int(new_s[l][x][k]) for x in range(len(new_s[l]))])
            # tmp_list[l] = tmp
            # print(tmp)
            if tmp > K:
                flag = 1
                break
            tmp_list[l] = tmp
            total[l] += tmp
            # print(total)
        if flag:
            break
        for m in total:
            if m > K:
                cnt += 1
                total = tmp_list
                break
            elif m == K and k != w - 1:
                cnt += 1
                total = [0]*len(new_s)
                break
            else:
                pass
    if not flag:
        ans = min(ans, cnt)
print(ans)

Submission status: Wrong Answer

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

h, w, K = [int(x) for x in input().split()]
s = [input().rstrip() for _ in range(h)]

# ans = h + w - 2
ans = 10 ** 18
for i in range(2 ** (h - 1)):
    new_s = []
    cnt = 0
    i_bin = bin(i)[2:].zfill(h - 1)
    add = []
    for j in range(h - 1):
        if i_bin[j] == "1":
            cnt += 1
            add.append(s[j])
            new_s.append(add)
            add = []
        else:
            add.append(s[j])
        if j == h - 2:
            add.append(s[-1])
            new_s.append(add)
    # print(len(new_s))
    total = [0] * len(new_s)
    # print(new_s)
    for k in range(w):
        flag = 0
        tmp_list = [0]*len(new_s)
        for l in range(len(new_s)):
            tmp = sum([int(new_s[l][x][k]) for x in range(len(new_s[l]))])
            # tmp_list[l] = tmp
            # print(tmp)
            if tmp > K:
                flag = 1
                break
            tmp_list[l] = tmp
            total[l] += tmp
            # print(total)
        if flag:
            break
        for m in total:
            if m > K:
                cnt += 1
                total = tmp_list
                break
            elif m == K and k != w - 1:
                cnt += 1
                total = [0]*len(new_s)
                break
            else:
                pass
    if not flag:
        ans = min(ans, cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
from itertools import product

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

if np.sum(S)<=K:
    print(0)
else:
    answer = H * W
    for X in product([False,True], repeat=H-1):
        ans = np.sum(X)
        if ans >= answer:
            continue
        M = [[0]]
        for i, x in enumerate(X):
            if x:
                M.append([])
            M[-1].append(i+1)
        D = np.zeros(len(M))
        for s in S:
            D[:] += [sum(s[i] for i in m) for m in M]
            print(D)
            if any(d > K  for d in D):
                ans += 1
                if ans >= answer:
                    break
                D[:] = [sum(s[i] for i in m) for m in M]

    if answer > ans:
        answer = ans

    print(min(answer,ans))

Submission status: Wrong Answer

Solution code:
import numpy as np
from itertools import product

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

if np.sum(S)<=K:
    print(0)
else:
    answer = H * W
    D = []
    for X in product([False,True], repeat=H-1):
        ans = np.sum(X)
        if ans > answer:
            continue
        M = [[0]]
        for i, x in enumerate(X):
            if x:
                M.append([])
            M[-1].append(i+1)
        D = [0]*len(M)
        for s in S:
            D[:] += [sum(s[i] for i in m) for m in M]
            print(D)
            if any(d > K  for d in D):
                ans += 1
                D[:] = [sum(s[i] for i in m) for m in M]

    if answer > ans:
        answer = ans

    print(min(answer,ans))

Submission status: Wrong Answer

Solution code:
import numpy as np
from itertools import product

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

if np.sum(S)<=K:
    print(0)
else:
    answer = H * W
    for X in product([False,True], repeat=H-1):
        ans = np.sum(X)
        M = [[0]]
        for i, x in enumerate(X):
            if x:
                M.append([])
            M[-1].append(i+1)
        D = [0]*len(M)
        for s in S:
            D[:] += [sum(s[i] for i in m) for m in M]
            if any(d > K  for d in D):
                ans += 1
                D[:] = [sum(s[i] for i in m) for m in M]
                
        if answer > ans:
            answer = ans

    print(min(answer,ans))

Submission status: Wrong Answer

Solution code:
import numpy as np
from itertools import product

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

if np.sum(S)<=K:
    print(0)
else:
    answer = H * W
    for X in product([False,True], repeat=H-1):#分けるか分けないか
        ans = np.sum(X)
        M = [[0]]
        for i, x in enumerate(X):
            if x:
                M.append([])#切った回数箱を増やす
            M[-1].append(i+1)#後ろの箱に切る場所を入れていく
        #print(M)
        D = np.zeros(len(M))
        #print(D)
        for s in S:
            D[:] += [np.sum(s[i] for i in m) for m in M]
            if any(d > K  for d in D):
                ans += 1
                #print("ans",ans)
                D[:] = [np.sum(s[i] for i in m) for m in M]
                
        if answer > ans:
            answer = ans

    print(min(answer,ans))

Submission status: Wrong Answer

Solution code:
import numpy as np
from itertools import product

H,W,K = map(int, input().split())
S = np.array([list(map(int,list(input()))) for _ in range(H)]).T
"""
H,W,K = 3,5,2

S = [[1,1,1,0,0],
     [1,0,0,0,1],
     [0,0,1,1,1]]
"""


S = np.array(S).T

if np.sum(S)<=K:
    print(0)
else:
    answer = H * W
    for X in product([False,True], repeat=H-1):#分けるか分けないか
        ans = np.sum(X)#横に切った回数
        #print(ans)
        M = [[0]]
        for i, x in enumerate(X):
            if x:
                M.append([])#切った回数箱を増やす
            M[-1].append(i+1)#後ろの箱に切る場所を入れていく
        #print(M)
        D = [0]*len(M)
        #print(D)
        for s in S:
            for k, m in enumerate(M):
                D[k] += np.sum(s[i] for i in m)
                #print("D",D)
            if any(d > K  for d in D):
                ans += 1
                #print("ans",ans)
                D[:] = [np.sum(s[i] for i in m) for m in M]
                
        if answer > ans:
            answer = ans

    print(min(answer,ans))

Submission status: Wrong Answer

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

minimum = (h - 1) * (w - 1)
for div_h in range(1 << (h - 1)):
  h_index = [0] * h
  cur_index = 0
  mask = 1 << (h - 2)
  for i in range(1, h):
    if div_h & mask:
      cur_index += 1
    h_index[i] = cur_index
    mask >>= 1
  white_choco = [0] * (cur_index + 1)
  divide = 0
  j = 0
  while j < w:
    for i in range(h):
      if s[i][j] == '1':
        if white_choco[h_index[i]] < k:
          white_choco[h_index[i]] += 1
        else:
          break
    else:
      j += 1
      continue
    white_choco = [0] * (cur_index + 1)
    divide += 1
  print(h_index, divide)
  minimum = min(minimum, divide + cur_index)
print(minimum)

Submission status: Wrong Answer

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

minimum = (h - 1) * (w - 1)
for div_h in range(1 << (h - 1)):
  h_index = [0] * h
  cur_index = 0
  mask = 1 << (h - 2)
  for i in range(1, h):
    if div_h & mask:
      cur_index += 1
    h_index[i] = cur_index
    mask >>= 1
  white_choco = [0] * (cur_index + 1)
  divide = 0
  for j in range(w):
    for i in range(h):
      if s[i][j] == '1':
        if white_choco[h_index[i]] < k:
          white_choco[h_index[i]] += 1
        else:
          break
    else:
      continue
    white_choco = [0] * (cur_index + 1)
    divide += 1
  minimum = min(minimum, divide + cur_index)
print(minimum)

Submission status: Wrong Answer

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

def nl(a, b):
    return [[0]*b for _ in range(a)]

def add(j):
    for i in range(g):
        now[i] += group_sum[i][j]
        if now[i] > K:
            return False
    return True

ans = float('inf')
for bit in range(1<<(H-1)):
    id_of = [0]*H
    g = 0
    
    for i in range(H):
        id_of[i] = g
        if bit >> i & 1:
            g += 1
    
    g += 1
    count = g - 1

    # グループごとに統合
    group_sum = nl(H, W)
    flg = True
    for i in range(H):
        for j in range(W):
            group_sum[id_of[i]][j] += S[i][j]
            if group_sum[id_of[i]][j] > K:
                # 横方向の分割が不適
                bl = False
    if not flg:
        continue

    # 縦方向に分割
    now = [0]*g
    for j in range(W):
        if not add(j):
            count += 1
            now = [0]*g
            add(j)
    
    ans = min(ans, count)

print(ans)

Submission status: Wrong Answer

Solution code:
import collections
import math
import numpy as np
H, W, K = map(int, input().split(' '))
S = []

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

df = np.array(S)
df = df.astype('int64')
minimum = float('inf')
for i in range(2**(H-1)):
    temp = df.copy()
    count = 0
    for j in range(H-1):
        if((i >> j) & 1):
            count += 1
            temp[H-j-2] += temp[H-j-1]
            temp = np.delete(temp, H-j-1, 0)
    if (temp > K).any().any():
        continue

    count = H-1 - count
    wa = 0
    column = 0
    for k in range(1, W-1):
        temp[:, column] += temp[:, k]
        if (temp[:, column] > K).any():
            column = k
            count += 1
    if count < minimum:
        minimum = count
    count = 0

print(minimum)