Problem p02733 (python)

Fixed submission:
from itertools import product
H, W, K = map(int, input().split())
G = [list(map(int, list(input()))) for _ in range(H)]

ans = float("inf")

for pattern in product([0, 1], repeat = H - 1):
    div = [0] + [i for i, p in enumerate(pattern, 1) if p == 1] + [H]
    rows = []
    for i in range(len(div) - 1):
        row = []
        for j in range(W):
            tmp = 0
            for k in range(div[i], div[i + 1]):
                tmp += G[k][j]
            row.append(tmp)
        rows.append(row)
        
    flag = True
    for row in rows:
        if [r for r in row if r > K]:
            flag = False
            break
    if not flag:
        continue

    tmp_ans = 0
    cnt = [0] * len(rows)
    w = 0

    while w < W:
        for r in range(len(rows)):
            cnt[r] += rows[r][w]
        if [c for c in cnt if c > K]:
            cnt = [0] * len(rows)
            tmp_ans += 1
            w -= 1
        w += 1
    
    tmp_ans += pattern.count(1)
    ans = min(ans, tmp_ans)

print(ans)

Buggy submission (verdict: Runtime Error):
import numpy as np
from itertools import product
H, W, K = map(int, input().split())
G = np.array([list(map(int, list(input()))) for _ in range(H)])

ans = float("inf")

for pattern in product([0, 1], repeat = H - 1):
    div = [0] + [i for i, p in enumerate(pattern, 1) if p == 1] + [20]
    rows = []
    for i in range(len(div) - 1):
        rows.append(np.count_nonzero(G[div[i]: div[i + 1]], axis=0)) # 列方向

    tmp_ans = 0
    cnt = [0] * len(rows)
    w = 0
    flag = False

    while w < W:
        for r in range(len(rows)):
            cnt[r] += rows[r][w]
        if np.any(np.array(cnt) > K):
            if w == 0:
                flag = True
                break
            cnt = [0] * len(rows)
            tmp_ans += 1
            w -= 1
        w += 1
    
    if not flag:
        tmp_ans += pattern.count(1)
        ans = min(ans, tmp_ans)

print(ans)

Buggy submission (verdict: Runtime Error):
import numpy as np

def divide(s):
    global ans
    left = 0
    top = 0
    right = s.shape[1] + 100
    btm = s.shape[0] + 100
    while left + 1 < right:
        if np.count_nonzero(s[:, :(left + right) // 2].ravel()) < np.count_nonzero(s[:, (left + right) // 2:].ravel()):
            left = (left + right) // 2
        else:
            right = (left + right) // 2
    
    while top + 1 < btm:
        if np.count_nonzero(s[: (top + btm) // 2].ravel()) < np.count_nonzero(s[(top + btm) // 2:].ravel()):
            top = (top + btm) // 2
        else:
            btm = (top + btm) // 2
            
    diff_1 = abs(np.count_nonzero(s[:, :left]) - np.count_nonzero(s[:, left:]))
    diff_2 = abs(np.count_nonzero(s[:top]) - np.count_nonzero(s[top:]))
   
    if diff_1 <= diff_2:
        ans += 1
        if np.count_nonzero(s[:, :left]) > K:
            divide(s[:, :left])
        if np.count_nonzero(s[:, left:]) > K:
            divide(s[:, left:])
    else:
        ans += 1
        if np.count_nonzero(s[:top]) > K:
            divide(s[:top])
        if np.count_nonzero(s[top:]) > K:
            divide(s[top:])
    
    return 0

if __name__ == "__main__":
    H, W, K = map(int, input().split())
    S = []
    for _ in range(H):
        S.append([int(s) for s in input()])
    S = np.array(S)
    ans = 0
    if np.count_nonzero(S.ravel()) <= K:
        print(ans)
        exit()
    divide(S)
    print(ans)