Buggy python submission (verdict: Time Limit Exceeded):
import itertools
import numpy as np
from sys import stdin

H, W, K = map(int, stdin.readline().split())
A = np.int32([[int(x) for x in stdin.readline().strip()] for _ in range(H)])

ans = H * W
for mask in itertools.product([0, 1], repeat=H - 1):
    pivots = [r + 1 for r in range(H - 1) if mask[r]]
    if len(pivots) > ans:
        continue

    blocks = np.concatenate([block.sum(axis=0) for block in np.split(A, pivots)])
    blocks = blocks.reshape(len(pivots) + 1, W)
    if blocks.max() > K:
        continue

    n_block = blocks.shape[0]
    n_cut = n_block - 1
    sums = np.zeros(n_block, dtype=int)

    for c in range(W):
        adds = blocks[:, c]
        sums = sums + adds
        if np.any(sums > K):
            n_cut += 1
            sums = adds
            if n_cut >= ans:
                break

    ans = min(ans, n_cut)

print(ans)


Fixed submission:
import itertools

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


def solve(blocks):
    n_vert_cut = 0
    n_block = len(blocks)
    vals = [0 for _ in range(n_block)]

    for c in range(W):
        adds = [block[c] for block in blocks]
        if any(add > K for add in adds):
            return H * W

        sums = [val + add for val, add in zip(vals, adds)]
        if any(x > K for x in sums):
            n_vert_cut += 1
            vals = adds
        else:
            vals = sums

    return n_vert_cut + n_block - 1


ans = H * W
for mask in itertools.product([0, 1], repeat=H - 1):
    mask = [1] + list(mask) + [1]
    pivots = [r for r in range(H + 1) if mask[r]]
    blocks = [A[p1:p2] for p1, p2 in zip(pivots[:-1], pivots[1:])]
    blocks = [[sum(row[c] for row in block) for c in range(W)] for block in blocks]
    # print(blocks, '->', solve(blocks))
    ans = min(ans, solve(blocks))
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import itertools
import numpy as np

H, W, K = map(int, input().split())
A = np.int32([[int(x) for x in input()] for _ in range(H)])

ans = H * W
for mask in itertools.product([0, 1], repeat=H - 1):
    pivots = [r + 1 for r in range(H - 1) if mask[r]]
    if len(pivots) > ans:
        continue

    blocks = np.concatenate([block.sum(axis=0) for block in np.split(A, pivots)])
    blocks = blocks.reshape(len(pivots) + 1, W)
    if blocks.max() > K:
        continue

    n_block = blocks.shape[0]
    n_cut = n_block - 1
    sums = np.zeros(n_block, dtype=int)

    for c in range(W):
        adds = blocks[:, c]
        sums = sums + adds
        if np.any(sums > K):
            n_cut += 1
            sums = adds
            if n_cut >= ans:
                break

    ans = min(ans, n_cut)

print(ans)


Fixed submission:
import itertools

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


def solve(blocks):
    n_vert_cut = 0
    n_block = len(blocks)
    vals = [0 for _ in range(n_block)]

    for c in range(W):
        adds = [block[c] for block in blocks]
        if any(add > K for add in adds):
            return H * W

        sums = [val + add for val, add in zip(vals, adds)]
        if any(x > K for x in sums):
            n_vert_cut += 1
            vals = adds
        else:
            vals = sums

    return n_vert_cut + n_block - 1


ans = H * W
for mask in itertools.product([0, 1], repeat=H - 1):
    mask = [1] + list(mask) + [1]
    pivots = [r for r in range(H + 1) if mask[r]]
    blocks = [A[p1:p2] for p1, p2 in zip(pivots[:-1], pivots[1:])]
    blocks = [[sum(row[c] for row in block) for c in range(W)] for block in blocks]
    # print(blocks, '->', solve(blocks))
    ans = min(ans, solve(blocks))
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import itertools
import numpy as np

H, W, K = map(int, input().split())
A = np.int32([[int(x) for x in input()] for _ in range(H)])

ans = H * W
for mask in itertools.product([0, 1], repeat=H - 1):
    pivots = [r + 1 for r in range(H - 1) if mask[r]]
    if len(pivots) > ans:
        continue

    blocks = np.concatenate([block.sum(axis=0) for block in np.split(A, pivots)])
    blocks = blocks.reshape(len(pivots) + 1, W)
    if blocks.max() > K:
        continue

    n_vert_cut = 0
    n_block = blocks.shape[0]
    sums = np.zeros(n_block, dtype=int)

    for c in range(W):
        adds = blocks[:, c]
        sums = sums + adds
        if np.any(sums > K):
            n_vert_cut += 1
            sums = adds

    ans = min(ans, n_vert_cut + n_block - 1)

print(ans)


Fixed submission:
import itertools

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


def solve(blocks):
    n_vert_cut = 0
    n_block = len(blocks)
    vals = [0 for _ in range(n_block)]

    for c in range(W):
        adds = [block[c] for block in blocks]
        if any(add > K for add in adds):
            return H * W

        sums = [val + add for val, add in zip(vals, adds)]
        if any(x > K for x in sums):
            n_vert_cut += 1
            vals = adds
        else:
            vals = sums

    return n_vert_cut + n_block - 1


ans = H * W
for mask in itertools.product([0, 1], repeat=H - 1):
    mask = [1] + list(mask) + [1]
    pivots = [r for r in range(H + 1) if mask[r]]
    blocks = [A[p1:p2] for p1, p2 in zip(pivots[:-1], pivots[1:])]
    blocks = [[sum(row[c] for row in block) for c in range(W)] for block in blocks]
    # print(blocks, '->', solve(blocks))
    ans = min(ans, solve(blocks))
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import itertools
import numpy as np

H, W, K = map(int, input().split())
A = np.int32([[int(x) for x in input()] for _ in range(H)])

ans = H * W
for mask in itertools.product([0, 1], repeat=H - 1):
    # pivots = [r + 1 for r in range(H - 1) if mask[r]]
    # blocks = np.concatenate([block.sum(axis=0) for block in np.split(A, pivots)])
    # blocks = blocks.reshape(len(pivots) + 1, W)
    blocks = np.zeros((sum(mask) + 1, W), dtype=int)
    block_id = 0
    for r in range(H - 1):
        blocks[block_id] += A[r]
        if mask[r]:
            block_id += 1
    blocks[block_id] += A[-1]

    if blocks.max() > K:
        continue

    n_vert_cut = 0
    n_block = blocks.shape[0]
    sums = np.zeros(n_block, dtype=int)

    for c in range(W):
        adds = blocks[:, c]
        sums = sums + adds
        if np.any(sums > K):
            n_vert_cut += 1
            sums = adds

    ans = min(ans, n_vert_cut + n_block - 1)

print(ans)


Fixed submission:
import itertools

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


def solve(blocks):
    n_vert_cut = 0
    n_block = len(blocks)
    vals = [0 for _ in range(n_block)]

    for c in range(W):
        adds = [block[c] for block in blocks]
        if any(add > K for add in adds):
            return H * W

        sums = [val + add for val, add in zip(vals, adds)]
        if any(x > K for x in sums):
            n_vert_cut += 1
            vals = adds
        else:
            vals = sums

    return n_vert_cut + n_block - 1


ans = H * W
for mask in itertools.product([0, 1], repeat=H - 1):
    mask = [1] + list(mask) + [1]
    pivots = [r for r in range(H + 1) if mask[r]]
    blocks = [A[p1:p2] for p1, p2 in zip(pivots[:-1], pivots[1:])]
    blocks = [[sum(row[c] for row in block) for c in range(W)] for block in blocks]
    # print(blocks, '->', solve(blocks))
    ans = min(ans, solve(blocks))
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import itertools
import numpy as np

H, W, K = map(int, input().split())
A = np.int32([[int(x) for x in input()] for _ in range(H)])

ans = H * W
for mask in itertools.product([0, 1], repeat=H - 1):
    pivots = [r + 1 for r in range(H - 1) if mask[r]]
    blocks = np.concatenate([block.sum(axis=0) for block in np.split(A, pivots)])
    blocks = blocks.reshape(len(pivots) + 1, W)
    if blocks.max() > K:
        continue

    n_vert_cut = 0
    n_block = blocks.shape[0]
    sums = np.zeros(n_block, dtype=int)

    for c in range(W):
        adds = blocks[:, c]
        sums = sums + adds
        if np.any(sums > K):
            n_vert_cut += 1
            sums = adds

    ans = min(ans, n_vert_cut + n_block - 1)

print(ans)


Fixed submission:
import itertools

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


def solve(blocks):
    n_vert_cut = 0
    n_block = len(blocks)
    vals = [0 for _ in range(n_block)]

    for c in range(W):
        adds = [block[c] for block in blocks]
        if any(add > K for add in adds):
            return H * W

        sums = [val + add for val, add in zip(vals, adds)]
        if any(x > K for x in sums):
            n_vert_cut += 1
            vals = adds
        else:
            vals = sums

    return n_vert_cut + n_block - 1


ans = H * W
for mask in itertools.product([0, 1], repeat=H - 1):
    mask = [1] + list(mask) + [1]
    pivots = [r for r in range(H + 1) if mask[r]]
    blocks = [A[p1:p2] for p1, p2 in zip(pivots[:-1], pivots[1:])]
    blocks = [[sum(row[c] for row in block) for c in range(W)] for block in blocks]
    # print(blocks, '->', solve(blocks))
    ans = min(ans, solve(blocks))
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import itertools
import numpy as np

H, W, K = map(int, input().split())
A = np.int32([[int(x) for x in input()] for _ in range(H)])

def solve(blocks):
    n_vert_cut = 0
    n_block = blocks.shape[0]
    sums = np.zeros(n_block, dtype=int)

    for c in range(W):
        adds = blocks[:, c]
        sums = sums + adds
        if np.any(sums > K):
            n_vert_cut += 1
            sums = adds

    return n_vert_cut + n_block - 1

ans = H * W
for mask in itertools.product([0, 1], repeat=H - 1):
    pivots = [r + 1 for r in range(H - 1) if mask[r]]
    blocks = np.concatenate([block.sum(axis=0) for block in np.split(A, pivots)])
    blocks = blocks.reshape(len(pivots) + 1, W)
    if blocks.max() > K:
        continue
    ans = min(ans, solve(blocks))
print(ans)


Fixed submission:
import itertools

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


def solve(blocks):
    n_vert_cut = 0
    n_block = len(blocks)
    vals = [0 for _ in range(n_block)]

    for c in range(W):
        adds = [block[c] for block in blocks]
        if any(add > K for add in adds):
            return H * W

        sums = [val + add for val, add in zip(vals, adds)]
        if any(x > K for x in sums):
            n_vert_cut += 1
            vals = adds
        else:
            vals = sums

    return n_vert_cut + n_block - 1


ans = H * W
for mask in itertools.product([0, 1], repeat=H - 1):
    mask = [1] + list(mask) + [1]
    pivots = [r for r in range(H + 1) if mask[r]]
    blocks = [A[p1:p2] for p1, p2 in zip(pivots[:-1], pivots[1:])]
    blocks = [[sum(row[c] for row in block) for c in range(W)] for block in blocks]
    # print(blocks, '->', solve(blocks))
    ans = min(ans, solve(blocks))
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import itertools
import numpy as np

H, W, K = map(int, input().split())
A = np.int32([[int(x) for x in input()] for _ in range(H)])

def solve(blocks):
    n_vert_cut = 0
    n_block = blocks.shape[0]
    vals = np.zeros(n_block)

    for c in range(W):
        adds = blocks[:, c]
        if np.any(adds > K):
            return H * W
        
        sums = vals + adds
        if np.any(sums > K):
            n_vert_cut += 1
            vals = adds
        else:
            vals = sums

    return n_vert_cut + n_block - 1

ans = H * W
for mask in itertools.product([0, 1], repeat=H - 1):
    pivots = [r + 1 for r in range(H - 1) if mask[r]]
    blocks = np.concatenate([block.sum(axis=0) for block in np.split(A, pivots)])
    blocks = blocks.reshape(len(pivots) + 1, W)
    ans = min(ans, solve(blocks))
print(ans)


Fixed submission:
import itertools

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


def solve(blocks):
    n_vert_cut = 0
    n_block = len(blocks)
    vals = [0 for _ in range(n_block)]

    for c in range(W):
        adds = [block[c] for block in blocks]
        if any(add > K for add in adds):
            return H * W

        sums = [val + add for val, add in zip(vals, adds)]
        if any(x > K for x in sums):
            n_vert_cut += 1
            vals = adds
        else:
            vals = sums

    return n_vert_cut + n_block - 1


ans = H * W
for mask in itertools.product([0, 1], repeat=H - 1):
    mask = [1] + list(mask) + [1]
    pivots = [r for r in range(H + 1) if mask[r]]
    blocks = [A[p1:p2] for p1, p2 in zip(pivots[:-1], pivots[1:])]
    blocks = [[sum(row[c] for row in block) for c in range(W)] for block in blocks]
    # print(blocks, '->', solve(blocks))
    ans = min(ans, solve(blocks))
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import itertools

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


def solve(blocks):
    n_vert_cut = 0
    n_block = len(blocks)
    vals = [0 for _ in range(n_block)]

    for c in range(W):
        adds = [block[c] for block in blocks]
        if any(add > K for add in adds):
            return H * W

        sums = [val + add for val, add in zip(vals, adds)]
        if any(x > K for x in sums):
            n_vert_cut += 1
            vals = adds
        else:
            vals = sums

    return n_vert_cut + n_block - 1


ans = H * W
for mask in itertools.product([0, 1], repeat=H - 1):
    mask = [1] + list(mask) + [1]
    pivots = [r for r in range(H + 1) if mask[r]]
    blocks = [A[p1:p2] for p1, p2 in zip(pivots[:-1], pivots[1:])]
    blocks = [[sum(row[c] for row in block) for c in range(W)] for block in blocks]
    # print(blocks, '->', solve(blocks))
    ans = min(ans, solve(blocks))
print(ans)


Fixed submission:
import itertools

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


def solve(blocks):
    n_vert_cut = 0
    n_block = len(blocks)
    vals = [0 for _ in range(n_block)]

    for c in range(W):
        adds = [block[c] for block in blocks]
        if any(add > K for add in adds):
            return H * W

        sums = [val + add for val, add in zip(vals, adds)]
        if any(x > K for x in sums):
            n_vert_cut += 1
            vals = adds
        else:
            vals = sums

    return n_vert_cut + n_block - 1


ans = H * W
for mask in itertools.product([0, 1], repeat=H - 1):
    mask = [1] + list(mask) + [1]
    pivots = [r for r in range(H + 1) if mask[r]]
    blocks = [A[p1:p2] for p1, p2 in zip(pivots[:-1], pivots[1:])]
    blocks = [[sum(row[c] for row in block) for c in range(W)] for block in blocks]
    # print(blocks, '->', solve(blocks))
    ans = min(ans, solve(blocks))
print(ans)