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: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

if True:
    h,w,k= map(int, input().split())
    sn = [[-1 for i in range(h)] for i in range(w)]
    for y in range(0,h):
        tmp = input()
        for x in range(0,w):
            sn[x][y] = int(tmp[x:x+1])
    pr(sn)
else:
    # h = 3
    # w = 5
    # k = 4
    # sn = [[1, 1, 0], [1, 0, 0], [1, 0, 1], [0, 0, 1], [0, 1, 1]]
    # h = 3
    # w = 5
    # k = 8
    # sn = [[1, 1, 0], [1, 0, 0], [1, 0, 1], [0, 0, 1], [0, 1, 1]]
    h = 4
    w = 10
    k = 4
    sn = [[1, 1, 0, 1], [1, 0, 0, 1], [1, 0, 1, 0], [0, 0, 1, 1], [0, 1, 1, 0], [1, 0, 0, 0], [0, 1, 1, 0], [0, 1, 0, 1], [1, 1, 0, 1], [0, 0, 1, 1]]


debug=False
def pr(data1,data2="",data3="",data4=""):
    global debug
    if debug:
        print("{},{},{},{}".format(str(data1),str(data2),str(data3),str(data4)))


def countWhite(lineh, linew):
    global w,h,k

    x_to=0
    y_to=0
    for areaw in range(0, len(linew) + 1):
        x_from = x_to
        if  areaw < len(linew):
            x_to = linew[areaw]-1
        else:
            x_to = w
        for areah in range(0, len(lineh) + 1):
            y_from = y_to
            if  areah < len(lineh):
                y_to = lineh[areah]-1
            else:
                y_to = h
            pr(x_from,y_from,x_to,y_to)

            # 数え上げる
            count = 0
            for x in range (x_from,x_to):
                for y in range (y_from,y_to):
                    count += sn[x][y]
                    pr("x,y",x,y,sn[x][y])
                    if count > k:
                        pr("count:" + str(count))
                        return False
                pr("count2:" + str(count))
        # 上からに戻す
        y_to=0


    return True

if False:
    # 横方向のライン 1だったら0と1の間
    lineh = [2]
    # 縦方向のライン
    linew = [3]

    if countWhite(lineh,linew):
        pr("OK")
    else:
        pr("NG")

not_find_flg = True
line_count = 0
linew_count = 0
lineh_count = 0
# while not_find_flg:


def getLines(count,line_max,range_from=1):
    ret = []
    if count == 0:
        return [[]]
    for i in range(range_from,line_max+1):
        datas = []
        datas.append(i)
        while len(datas) != count:
            lines = getLines(count-1,line_max,i+1)
            if len(lines) > 0:
                # pr("lenelne")
                # pr(datas)
                # pr(lines)
                #
                # pr(datas)
                for line in lines:
                    tmp = datas[:]
                    tmp.extend(line)
                    if(len(tmp) == count):
                        ret.append(tmp)
                # pr(ret)
                break
            else:
                #
                break
        # pr(datas)
        if len(datas) == count:
            ret.append(datas)

    return ret

# print(getTmp(2,5))

# print(getLines(1, 4))
# exit()
if countWhite([],[]):
    pr("OK")
    print(0)
    exit()
else:
    pr("NG")


not_find_flg = True

line_count = lineh_count = 1
linew_count = 0
break2_flg = False
while not_find_flg:
    linehs = getLines(lineh_count,h-1)
    linews = getLines(linew_count,w-1)
    pr("lines h,w",linehs,linews)
    # pr(linehs)
    # exit()
    for lineh in linehs:
        for linew in linews:
            pr("line h,w",lineh,linew)
            if countWhite(lineh,linew):
                pr("OK")
                pr(linew)
                pr(lineh)
                not_find_flg = False
                break2_flg = True
            else:
                pr("NG")
        if break2_flg:
            break

    if not_find_flg:
        # ラインの数の調整
        pr(linew_count,lineh_count,line_count)
        linew_count += 1
        lineh_count -= 1
        if lineh_count < 0:
            line_count += 1
            lineh_count = line_count
            linew_count = 0

pr("line:::",linew,lineh)
print(line_count)

Submission status: Runtime Error

Solution code:
import numpy as np
import itertools

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

ans = 2000
for t in itertools.product([0, 1], repeat=H - 1):
    cut = sum(t)
    lst = np.zeros((cut + 1, W), dtype=np.int)
    lst[0] += S[0]
    c = 0
    for h in range(H - 1):
        if t[h]:
            c += 1
        lst[c] += S[h + 1]
    L = len(lst)
    sum_lst = np.zeros(L)
    for w in range(W):
        lst_w = np.max(lst, axis=0)
        if lst_w[w] > K:
            break

        lst_s = sum_lst + lst_w
        if lst_s.max() > K:
            cut += 1
            sum_lst = lst_w
        else:
            sum_lst = lst_s
    else:
        ans = min(ans, cut)
print(ans)

Submission status: Runtime Error

Solution code:
    import numpy as np
     
    H, W, K = list(map(int, input().split()))
    S = [list(map(int, list(input()))) for _ in range(H)]
    S_orig = np.array(S)
     
     
    min_cnt = H * W
    for row_choice in range(2**(H-1)):
        S = np.copy(S_orig)
        row_splits = []
        for r in range(H-1):
            if (row_choice >> r) & 1:
                row_splits.append(r+1)
        if len(row_splits) > min_cnt:
            continue
        splitted_rows = np.vsplit(S, row_splits)
        splitted_rows = np.array([np.sum(row, axis=0) for row in splitted_rows])
        splitted_rows_cum = np.hstack([np.zeros((splitted_rows.shape[0], 1), dtype=np.uint32), np.cumsum(splitted_rows, 1)])
        
        cnt = len(row_splits)
        start = 0
        for i in range(W+1):
            if (splitted_rows_cum[:, i] - splitted_rows_cum[:, start] > K).any():
            #if (splitted_rows[:, start: i].sum(axis=1) > K).any():
                start = i - 1
                cnt += 1
                if cnt > min_cnt:
                    continue
        min_cnt = min([cnt, min_cnt])
        
    print(min_cnt)

Submission status: Runtime Error

Solution code:
def main():
    H,W,K = map(int,input().split())
    S = [[int(s) for s in input()]for _ in range(H)]
    ans = 2**60
    for i in range(2**(H-1)):
        aa = 0
        for j in range(H-1):
            if (i>>j)&1 == 1:
                aa+=1
        c = aa
        b = [0]*(c+1)
        OK = True
        for j in range(W):
            k = 0
            for h in range(H):
                if S[h][j] == 1:b[k] += 1
                if (i>>j)&1==1:k+=1
            
            ok = True
            for p in b:
                if p > K:ok = False
            if not ok:
                aa += 1
                b = [0]*(c+1)
                k = 0
                for h in range(H):
                    if S[h][j]==1:b[k] += 1
                    if (i>>j)&1==1:k+=1
                ok = True
                for p in b:
                    if p > K:ok = False
                if not ok:OK = False;break                
        if OK:ans = min(ans,aa)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def main():
    H,W,K = map(int,input().split())
    S = [[int(s) for s in input()]for _ in range(H)]
    ans = 10**9
    for i in range(2**(H-1)):
        aa = 0
        for j in range(H-1):
            if (i>>j)&1 == 1:
                aa+=1
        c = aa
        b = [0 for _ in range(c+1)]
        OK = True
        for j in range(W):
            k = 0
            for h in range(H):
                if S[h][j] == 1:b[k] += 1
                if (i>>j)&1==1:k+=1
            
            ok = True
            for p in b:
                if p > K:ok = False
            if not ok:
                aa += 1
                b = [0]*(c+1)
                k = 0
                for h in range(H):
                    if S[h][j]==1:b[k] += 1
                    if (i>>j)&1==1:k+=1
            ok = True
            for p in b:
                if p > K:ok = False
            if not ok:OK = False;break                
        if OK:ans = min(ans,aa)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def main():
    H,W,K = map(int,input().split())
    S = [[int(s) for s in input()]for _ in range(H)]
    ans = 2**60
    for i in range(2**(H-1)):
        aa = 0
        for j in range(H-1):
            if (i>>j)&1 == 1:
                aa+=1
        c = aa
        b = [0 for _ in range(c+1)]
        OK = True
        for j in range(W):
            k = 0
            for h in range(H):
                if S[h][j] == 1:b[k] += 1
                if (i>>j)&1==1:k+=1
            
            ok = True
            for p in b:
                if p > K:ok = False
            if not ok:
                aa += 1
                b = [0]*(c+1)
                k = 0
                for h in range(H):
                    if S[h][j]==1:b[k] += 1
                    if (i>>j)&1==1:k+=1
            ok = True
            for p in b:
                if p > K:ok = False
            if not ok:OK = False;break                
        if OK:ans = min(ans,aa)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from collections import deque
def main():
    H,W,K = map(int,input().split())
    S = [[int(s) for s in input()]for _ in range(H)]
    ans = 2**60
    for i in range(2**(H-1)):
        aa = 0
        for j in range(H-1):
            if (i>>j)&1 == 1:
                aa+=1
        c = aa
        b = [0 for _ in range(c+1)]
        OK = True
        for j in range(W):
            k = 0
            for h in range(H):
                if S[h][j]:b[k] += 1
                if (i>>j)&1==1:k+=1
            
            ok = True
            for p in b:
                if p > K:ok = False
            if not ok:
                aa += 1
                b = [0]*(c+1)
                k = 0
                for h in range(H):
                    if S[h][j]:b[k] += 1
                    if (i>>j)&1==1:k+=1
            ok = True
            for p in b:
                if p > K:ok = False
            if not ok:OK = False;break                
    if OK:ans = min(ans,aa)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:

def main():
    from itertools import product

    H,W,K = map(int, input().split())
    S = [list(input()) for _ in range(H)]
    
    i = 0
    while i < len(S):
        if '1' in S[i]:
            i += 1
        else:
            del S[i]
    H = len(S)
 
    S = [[int(s[i]) for s in S] for i in range(W)]

    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 = [0]*len(M)
            for s in S:
                for k, m in enumerate(M):
                    D[k] += sum(s[i] for i in m)
                if any(d > K  for d in D):
                    ans += 1
                    if ans >= answer:
                        break
                    for k, m in enumerate(M):
                        D[k] = sum(s[i] for i in m)
                    
                    if any(d > K for d in D):
                        ans = answer + 1
                        break

            answer = min(answer,ans)

        print(answer)

main()

Submission status: Runtime Error

Solution code:

def main():
    from itertools import product

    H,W,K = map(int, input().split())
    S = [list(input()) for _ in range(H)]
    
    i = 0
    while i < len(S):
        if '1' in S[i]:
            i += 1
        else:
            del S[i]
    H = len(S)
 
    S = [[int(s[i]) for s in S] for i in range(W)]

    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):
                        ans = answer + 1
                        break

            answer = min(answer,ans)

        print(answer)

main()

Submission status: Runtime Error

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):
                    ans = answer + 1
                    break

        answer = min(answer,ans)

    print(answer

Submission status: Runtime Error

Solution code:
import numpy as np

h, w, k = map(int, input().split())
s = np.array(
  [[s for s in map(int, input().split())] for _ in range(h)],
  dtype=np.int)

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

Submission status: Runtime Error

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
  bin_h = format(div_h, f'0{h-1}b')
  for i in range(1, h):
    if bin_h[-i] == '1':
      cur_index += 1
    h_index[i] = cur_index
  white_choco = [0] * (cur_index + 1)
  divide = 0
  j = 0
  while j < w:
    for i in range(h):
      if s[i][j] == '1':
        h_i = h_index[i]
        if white_choco[h_i] < k:
          white_choco[h_i] += 1
        else:
          break
    else:
      j += 1
      continue
    white_choco = [0] * (cur_index + 1)
    divide += 1
  minimum = min(minimum, divide + cur_index)
print(minimum)

Submission status: Runtime Error

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

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

# df = pd.DataFrame(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.iloc[H-j-2] += temp.iloc[H-j-1]
#             temp.drop(index=df.index[H-j-1], inplace=True)
#     count = H-1 - count
#     wa = 0
#     column = 0
#     for k in range(1, W-1):
#         temp.iloc[:, column] += temp.iloc[:, k]
#         if (temp.iloc[:, column] > K).any():
#             column = k
#             count += 1
#     if count < minimum:
#         minimum = count
#     count = 0

# print(minimum)

Submission status: Runtime Error

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

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

# df = pd.DataFrame(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.iloc[H-j-2] += temp.iloc[H-j-1]
#             temp.drop(index=df.index[H-j-1], inplace=True)
#     count = H-1 - count
#     wa = 0
#     column = 0
#     for k in range(1, W-1):
#         temp.iloc[:, column] += temp.iloc[:, k]
#         if (temp.iloc[:, column] > K).any():
#             column = k
#             count += 1
#     if count < minimum:
#         minimum = count
#     count = 0

# print(minimum)

Submission status: Runtime Error

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

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

df = pd.DataFrame(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.iloc[H-j-2] += temp.iloc[H-j-1]
            temp.drop(index=df.index[H-j-1], inplace=True)
    count = H-1 - count
    # print(temp)
    wa = 0
    column = 0
    for k in range(1, W-1):
        temp.iloc[:, column] += temp.iloc[:, k]
        if (temp.iloc[:, column] > K).any():
            column = k
            count += 1
    # print(count)
    if count < minimum:
        minimum = count
    count = 0

    # print()

print(minimum)

Submission status: Runtime Error

Solution code:

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

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


df = pd.DataFrame(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.iloc[H-j-2] += temp.iloc[H-j-1]
            temp.drop(index=df.index[H-j-1], inplace=True)
    count = H-1 - count
    # print(temp)
    wa = 0
    column = 0
    for k in range(1, W-1):
        temp.iloc[:, column] += temp.iloc[:, k]
        if (temp.iloc[:, column] > K).any():
            column = k
            count += 1
    # print(count)
    if count < minimum:
        minimum = count
    count = 0

    # print()

print(minimum)

Submission status: Runtime Error

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

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


# def finddivide(df):
#     #総和
#     s=df.sum().sum()
#     # 行和
#     print(df.sum(axis=1))
#     c = df.sum(axis=1).cumsum()

#     print(type(df[0][0]))


df = pd.DataFrame(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.iloc[H-j-2] += temp.iloc[H-j-1]
            temp.drop(index=df.index[H-j-1], inplace=True)
    count = H-1 - count
    # print(temp)
    wa = 0
    column = 0
    for k in range(1, W-1):
        temp.iloc[:, column] += temp.iloc[:, k]
        if (temp.iloc[:, column] > K).any():
            column = k
            count += 1
    # print(count)
    if count < minimum:
        minimum = count
    count = 0

    # print()

print(minimum)

Submission status: Runtime Error

Solution code:
import numpy as np


def solve(*args: str) -> str:
    h, w, k = map(int, args[0].split())
    white = np.array([[n for n in map(int, S)] for S in args[1:]])

    ret = h*w
    for b in range(2**(h-1)):
        h_cuts = set(i+1 for i in range(h-1) if (b >> i) & 1 == 1)
        count = len(h_cuts)
        if ret < count:
            continue

        A = np.array(tuple(x.sum(axis=0) for x in np.vsplit(white, h_cuts)))
        if (k < A).any():
            continue

        S = np.zeros((1, len(A)), dtype=int)
        for x in range(w):
            S += A[:, x]
            if (k < S).any():
                S = A[:, x]
                count += 1
                if ret < count:
                    break

        ret = min(ret, count)

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Runtime Error

Solution code:
import numpy as np


def solve(*args: str) -> str:
    h, w, k = map(int, args[0].split())
    white = np.array([[n for n in map(int, S)] for S in args[1:]])

    ret = h*w
    for b in range(2**(h-1)):
        h_cuts = set(i+1 for i in range(h-1) if (b >> i) & 1 == 1)
        count = len(h_cuts)
        if ret < count:
            continue

        A = np.array(tuple(x.sum(axis=0) for x in np.vsplit(white, h_cuts)))
        if k < np.max(A):
            continue

        S = np.zeros((1, len(A)), dtype=int)
        for x in range(w):
            S += A[:, x]
            if (k < S).any():
                S = A[:, x]
                count += 1
                if ret < count:
                    break

        ret = min(ret, count)

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Runtime Error

Solution code:
def main()
  H,W,K = map(int,input().split())
  from collections import deque
  ans = 10000
  S = [list(map(int,list(input()))) for _ in range(H)]
  cum = [[0]*W for _ in range(H+1)]
  for j in range(W):
    for i in range(1,H+1):
      cum[i][j] = cum[i-1][j]+S[i-1][j]

  for i in range(2**(H-1)):
    q = deque([0])
    for h in range(H):
      if (i>>h)&1:
        q.append(h+1)
    q.append(H)
    q = list(q)
    p = deque()
    judge = False
    for a in range(len(q)-1):
      x = [x-y for x in cum[q[a+1]] for y in cum[q[a]]]
      for j in x:
        if j>K:
          judge = True
          break
      if judge:
        break
      else:
        p.append(list(x))

    if judge:
      continue
    p = list(p)
    t_a = len(q)-2
    n = len(p)
    l = [0]*n
    for w in range(W):
      for x,a in enumerate(p):
        y = l[x]+a[w]
        if y>K:
          t_a+=1
          l = [0]*n
          for z,b in enumerate(p):
            l[z] = b[w]
          break
        else:
          l[x]=y
    ans = min(ans,t_a)

  print(ans)
  
main()

Submission status: Runtime Error

Solution code:
import sys
import math
import string
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
from bisect import bisect, bisect_left, bisect_right
import numpy as np

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)

H, W, K = map(int, input().split())
S = [list(map(int, list(input()))) for _ in range(H)]
ans = INF
for i in range(2 ** (H - 1)):
    p = deque()
    for j in range(H - 1):
        if (i >> j) & 1:
            p.append(j + 1)
    num = len(p)
    if len(p) == 0:
        check = 0
        for j in range(W):
            temp_sum = sum([S[l][j] for l in range(H)])
            if check + temp_sum > K:
                check = temp_sum
                num += 1
            else:
                check += temp_sum
    else:
        p.appendleft(0)
        p.append(H)
        check = [0] * (len(p) - 1)
        for j in range(W):
            for l in range(len(p)-1):
                if p[l+1] - p[l] == 1:
                    check[l] += S[l][j]
                else:
                    check[l] += sum([S[t][j] for t in range(p[l], p[l+1])])
            for l in check:
                if l > K:
                    num += 1
                    for l in range(len(p) - 1):
                        if p[l + 1] - p[l] == 1:
                            check[l] = S[l][j]
                        else:
                            check[l] = sum([S[t][j] for t in range(p[l], p[l + 1])])
                    break
    if num < ans:
        ans = num
print(ans)

Submission status: Runtime Error

Solution code:
H,W,K = map(int,input().split())
import numpy as np
from collections import deque
ans = 10000
S = np.array([list(map(int,list(input()))) for _ in range(H)])
cum = [[0]*W for _ in range(H+1)]
for j in range(W):
  for i in range(1,H+1):
    cum[i][j] = cum[i-1][j]+S[i-1][j]
    
cum = np.array(cum)
for i in range(2**(H-1)):
  q = deque([0])
  for h in range(H):
    if (i>>h)&1:
      q.append(h+1)
  q.append(H)
  q = list(q)
  p = deque()
  judge = False
  for a in range(len(q)-1):
    x = list(cum[q[a+1]]-cum[q[a]])
    if (x>K).any():
      judge = True
      break
    else:
      p.append(x)

  if judge:
    continue
  p = list(p)
  t_a = len(q)-2
  n = len(p)
  l = [0]*n
  for w in range(W):
    for x,a in enumerate(p):
      y = l[x]+a[w]
      if y>K:
        t_a+=1
        l = [0]*n
        for z,b in enumerate(p):
          l[z] = b[w]
        break
      else:
        l[x]=y
  ans = min(ans,t_a)
    
print(ans)

Submission status: Runtime Error

Solution code:
h,w,k=map(int,input().split())
S=[]
for i in range(h):
    s=int(input(),2)
    S.append(s)
ans=100000
for i in range(2**(h-1)):
    now=0 #区切った数
    cnt=0 #1の数
    y=0
    for j in range(h-1):
        if (i>>j)&1:
            y+=1
    C=[0]*(y+1) #1の数保存配列
    for x in range(w):
        T=[]　#現在の列での1の数保存配列
        for j in range(h):      
            cnt+=(S[j]>>x)&1
            if (i>>j)&1: #横の区切り判定
                T.append(cnt)
                cnt=0
            if j==h-1: #最後の列
                T.append(cnt)
                cnt=0
        for j in range(len(C)):
            if C[j]+T[j]>k:
                now+=1
                C=T
                break
            else:
                C[j]+=T[j]
    ans=min(ans,now+y)
print(ans)

Submission status: Runtime Error

Solution code:
import itertools
 
H, W, K = map(int, input().split())
S = []
for _ in range(H):
    S.append(list(map(int, input().split())))
 
ans = 2000
for t in itertools.product([0, 1], repeat=H - 1):
    cnt = t.count(1)
    lst = [[s for s in S[0]]]
    for h in range(H - 1):
        if t[h]:
            lst.append(S[h + 1])
        else:
            lst[-1] = [lst[-1][i] + S[h + 1][i] for i in range(W)]
    L = len(lst)
    sum_lst = [0] * L
    for w in range(W):
        if max(lst[i][w] for i in range(L)) > K:
            break
        tmp = [sum_lst[i] + lst[i][w] for i in range(L)]
        if max(tmp) > K:
            cnt += 1
            sum_lst = [lst[i][w] for i in range(L)]
        else:
            sum_lst = tmp
    else:
        ans = min(ans, cnt)
print(ans)

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time
import numpy
from statistics import mean, median,variance,stdev


def I(): return int(input())


def S(): return input()


def MI(): return map(int, input().split())


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


def print_matrix(mat):
    for i in range(len(mat)):
        print(*mat[i])


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False
# show_flg = True

WHITE = '1'
BLACK = '0'

# def count(graph):


def main():
    H, W, K = MI()
    graph = [None] * H

    for i in range(H):
        graph[i] = [int(v) for v in list(S())]

    ans = 10**9
    for i in range(2 ** (H-1)):
        groups = [0]
        for j in range((H-1)):
            if ((i >> j) & 1):
                groups.append(j+1)
        groups.append(H)

        divide_count = 0
        counter = defaultdict(int)
        for w in range(W):
            current_counter = defaultdict(int)
            for g in range(1, len(groups)):
                prev_div = groups[g-1]
                div = groups[g]
                total = 0
                for h in range(prev_div, div):
                    total += graph[h][w]
                current_counter[g] += total

            for k, v in current_counter.items():
                counter[k] += v
                if counter[k] > K:
                    divide_count += 1
                    counter = current_counter
                    break

        ans = min(ans, divide_count + len(groups) - 2)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
H,W,K = map(int,input().split())
import numpy as np
from collections import deque
ans = 10000
S = np.array([list(map(int,list(input()))) for _ in range(H)])
cum = [[0]*W for _ in range(H+1)]
for j in range(W):
  for i in range(1,H+1):
    cum[i][j] = cum[i-1][j]+S[i-1][j]
    
cum = np.array(cum)
for i in range(2**(H-1)):
  q = deque([0])
  for h in range(H):
    if (i>>h)&1:
      q.append(h+1)
  q.append(H)
  p = deque()
  for a in range(len(q)-1):
    x = cum[q[a+1]]-cum[q[a]]
    if (x>K).any():
      judge = True
      break
    else:
      p.append(x)

  if judge:
    continue
  
  t_a = len(q)-2
  l = [0]*len(p)
  judge = False
  for w in range(W):
    for x,a in enumerate(p):
      l[x]+=a[w]
      if l[x]>K:
        t_a+=1
        l = [0]*len(p)
        for z,b in enumerate(p):
          l[z] = b[w]
        break
  ans = min(ans,t_a)
    
print(ans)