Problem p02733 (python)

Fixed submission:
import sys


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


def get_sum(x1, x2, y1, y2):
    return acc[x2][y2] - acc[x1][y2] - acc[x2][y1] + acc[x1][y1]


h, w, k = map(int, input().split())
s = [[int(c) for c in input()] for i in range(h)]

acc = [[0 for j in range(w + 1)] for i in range(h + 1)]
for i in range(h):
    for j in range(w):
        acc[i + 1][j + 1] = acc[i][j + 1] + acc[i + 1][j] - acc[i][j] + s[i][j]

ans = h + w

for h_div in range(1 << (h - 1)):
    h_ranges = []
    h_begin = 0
    for i in range(h - 1):
        if h_div >> i & 1:
            h_ranges.append([h_begin, i + 1])
            h_begin = i + 1
    h_ranges.append([h_begin, h])
    div_cnt = len(h_ranges) - 1

    def is_addable():
        for h_range in h_ranges:
            if get_sum(h_range[1], h_range[0], j + 1, w_begin) > k:
                return False
        return True

    w_begin = 0
    for j in range(w):
        if not is_addable():
            w_begin = j
            div_cnt += 1
            if not is_addable():
                div_cnt = h + w
                break
    ans = min(ans, div_cnt)

print(ans)

Buggy submission (verdict: Runtime Error):
def get_sum(x1, x2, y1, y2):
    return acc[x2][y2] - acc[x1][y2] - acc[x2][y1] + acc[x1][y1]


h, w, k = map(int, input().split())
s = [[int(c) for c in input()] for i in range(h)]

acc = [[0 for j in range(w + 1)] for i in range(h + 1)]
for i in range(h):
    for j in range(w):
        acc[i + 1][j + 1] = acc[i][j + 1] + acc[i + 1][j] - acc[i][j] + s[i][j]

min_div_cnt = 10 ** 18

for h_div in range(1 << (h - 1)):
    h_ranges = []
    cur_begin = 0
    for i in range(h - 1):
        if (h_div >> i) & 1:
            h_ranges.append([cur_begin, i + 1])
            cur_begin = i + 1
    h_ranges.append([cur_begin, h])
    h_div_cnt = len(h_ranges) - 1

    max_hchoco_cnt = 0
    tgt_h_range = []
    for h_range in h_ranges:
        hchoco_cnt = get_sum(h_range[1], h_range[0], w, 0)
        if hchoco_cnt > max_hchoco_cnt:
            max_hchoco_cnt = hchoco_cnt
            tgt_h_range = h_range

    cur_begin = 0
    v_div_cnt = 0
    is_valid = True
    for i in range(0, w):
        cur_cnt = get_sum(tgt_h_range[1], tgt_h_range[0], i, cur_begin)
        next_cnt = get_sum(tgt_h_range[1], tgt_h_range[0], i + 1, cur_begin)
        if next_cnt - cur_cnt > k:
            is_valid = False
            break
        if cur_cnt <= k and next_cnt > k:
            cur_begin = i
            v_div_cnt += 1

    if is_valid:
        min_div_cnt = min(min_div_cnt, h_div_cnt + v_div_cnt)

print(min_div_cnt)

Buggy submission (verdict: Runtime Error):
import sys


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


def get_sum(x1, x2, y1, y2):
    return acc[x2][y2] - acc[x1][y2] - acc[x2][y1] + acc[x1][y1]


h, w, k = map(int, input().split())
s = [[int(c) for c in input()] for i in range(h)]

acc = [[0 for j in range(w + 1)] for i in range(h + 1)]
for i in range(h):
    for j in range(w):
        acc[i + 1][j + 1] = acc[i][j + 1] + acc[i + 1][j] - acc[i][j] + s[i][j]

min_div_cnt = 10 ** 18

for h_div in range(1 << (h - 1)):
    h_ranges = []
    cur_begin = 0
    for i in range(h - 1):
        if (h_div >> i) & 1:
            h_ranges.append([cur_begin, i + 1])
            cur_begin = i + 1
    h_ranges.append([cur_begin, h])
    h_div_cnt = len(h_ranges) - 1

    max_hchoco_cnt = 0
    tgt_h_range = []
    for h_range in h_ranges:
        hchoco_cnt = get_sum(h_range[1], h_range[0], w, 0)
        if hchoco_cnt > max_hchoco_cnt:
            max_hchoco_cnt = hchoco_cnt
            tgt_h_range = h_range

    cur_begin = 0
    v_div_cnt = 0
    is_valid = True
    for i in range(0, w):
        cur_cnt = get_sum(tgt_h_range[1], tgt_h_range[0], i, cur_begin)
        next_cnt = get_sum(tgt_h_range[1], tgt_h_range[0], i + 1, cur_begin)
        if next_cnt - cur_cnt > k:
            is_valid = False
            break
        if cur_cnt <= k and next_cnt > k:
            cur_begin = i
            v_div_cnt += 1

    if is_valid:
        min_div_cnt = min(min_div_cnt, h_div_cnt + v_div_cnt)

print(min_div_cnt)