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

import numpy as np

input = sys.stdin.readline


def main():
    H, W, K = map(int, input().split())
    S = np.zeros(shape=(H, W), dtype=np.uint16)
    for i in range(H):
        S[i] = list(map(int, input().rstrip()))

    ans = float("inf")
    for comb in product(range(2), repeat=H-1):
        n_cut = sum(comb)
        if n_cut >= ans:
            continue
        M = 1 + n_cut

        # horizontal chocolates
        h_chocos = np.zeros(shape=(M, W), dtype=np.uint16)
        h = 0  # upper index
        m = 0
        for i, c in enumerate(comb):
            if c == 1:
                h_chocos[m] = np.sum(S[h:i+1, :], axis=0)
                h = i + 1
                m += 1
        h_chocos[m] = np.sum(S[h:, :], axis=0)

        total = np.zeros(shape=M, dtype=np.uint16)
        width = 0
        for w in range(W):
            total += h_chocos[:, w]
            width += 1
            if not np.all(total <= K):
                if width == 1:
                    n_cut = float("inf")
                    break
                n_cut += 1
                width += 1
                if n_cut >= ans:
                    break
                total = h_chocos[:, w]
        if n_cut < ans:
            ans = n_cut

    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
"""
References: <https://www.hamayanhamayan.com/entry/2020/03/22/231629>
"""
import sys
from itertools import product

input = sys.stdin.readline


def main():
    H, W, K = map(int, input().split())
    S = [None] * H
    for i in range(H):
        S[i] = input().rstrip()

    ans = float("inf")
    for comb in product(range(2), repeat=(H - 1)):
        n_cut = sum(comb)
        if n_cut >= ans:
            continue

        group = []
        g_id = 0
        for c in comb:
            group.append(g_id)
            if c == 1:
                g_id += 1
        group.append(g_id)

        w = 0
        while w < W:
            count = [0] * (g_id + 1)
            next_w = w
            for x in range(w, W):
                over_K = False
                for y in range(H):
                    if S[y][x] == "1":
                        count[group[y]] += 1
                        if count[group[y]] > K:
                            over_K = True
                            break
                if over_K:
                    break
                next_w += 1

            # Impossible: over K in one column
            if next_w == w:
                n_cut = float("inf")
                break
            w = next_w

            if over_K:
                n_cut += 1
            if n_cut >= ans:
                break

        if n_cut < ans:
            ans = n_cut

    print(ans)


if __name__ == "__main__":
    main()

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

import numpy as np

input = sys.stdin.readline


def main():
    H, W, K = map(int, input().split())
    S = np.zeros(shape=(H, W), dtype=np.uint16)
    for i in range(H):
        S[i] = list(map(int, input().rstrip()))

    ans = float("inf")
    for comb in product(range(2), repeat=H-1):
        n_cut = sum(comb)
        if n_cut >= ans:
            continue
        M = 1 + n_cut

        # horizontal chocolates
        h_chocos = np.zeros(shape=(M, W), dtype=np.uint16)
        h = 0  # upper index
        m = 0
        for i, c in enumerate(comb):
            if c == 1:
                h_chocos[m] = np.sum(S[h:i+1, :], axis=0)
                h = i + 1
                m += 1
        h_chocos[m] = np.sum(S[h:, :], axis=0)

        total = np.zeros(shape=M, dtype=np.uint16)
        for w in range(W):
            total += h_chocos[:, w]
            if not np.all(total <= K):
                n_cut += 1
                if n_cut >= ans:
                    break
                total = h_chocos[:, w]
        if n_cut < ans:
            ans = n_cut

    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
"""
References: <https://www.hamayanhamayan.com/entry/2020/03/22/231629>
"""
import sys
from itertools import product

input = sys.stdin.readline


def main():
    H, W, K = map(int, input().split())
    S = [None] * H
    for i in range(H):
        S[i] = input().rstrip()

    ans = float("inf")
    for comb in product(range(2), repeat=(H - 1)):
        n_cut = sum(comb)
        if n_cut >= ans:
            continue

        group = []
        g_id = 0
        for c in comb:
            group.append(g_id)
            if c == 1:
                g_id += 1
        group.append(g_id)

        w = 0
        while w < W:
            count = [0] * (g_id + 1)
            next_w = w
            for x in range(w, W):
                over_K = False
                for y in range(H):
                    if S[y][x] == "1":
                        count[group[y]] += 1
                        if count[group[y]] > K:
                            over_K = True
                            break
                if over_K:
                    break
                next_w += 1

            # Impossible: over K in one column
            if next_w == w:
                n_cut = float("inf")
                break
            w = next_w

            if over_K:
                n_cut += 1
            if n_cut >= ans:
                break

        if n_cut < ans:
            ans = n_cut

    print(ans)


if __name__ == "__main__":
    main()

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

import numpy as np

input = sys.stdin.readline


def main():
    H, W, K = map(int, input().split())
    S = np.zeros(shape=(H, W), dtype=np.uint8)
    for i in range(H):
        S[i] = list(map(int, input().rstrip()))

    ans = float("inf")
    for comb in product(range(2), repeat=H-1):
        n_cut = sum(comb)
        M = 1 + n_cut

        # horizontal chocolates
        h_chocos = np.zeros(shape=(M, W), dtype=np.uint16)
        h = 0  # upper index
        m = 0
        for i, c in enumerate(comb):
            if c == 1:
                h_chocos[m] = np.sum(S[h:i+1, :], axis=0)
                h = i + 1
                m += 1
        h_chocos[m] = np.sum(S[h:, :], axis=0)

        total = np.zeros(shape=M, dtype=np.uint16)
        for w in range(W):
            total += h_chocos[:, w]
            if not np.all(total <= K):
                n_cut += 1
                total = h_chocos[:, w]
        if n_cut < ans:
            ans = n_cut

    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
"""
References: <https://www.hamayanhamayan.com/entry/2020/03/22/231629>
"""
import sys
from itertools import product

input = sys.stdin.readline


def main():
    H, W, K = map(int, input().split())
    S = [None] * H
    for i in range(H):
        S[i] = input().rstrip()

    ans = float("inf")
    for comb in product(range(2), repeat=(H - 1)):
        n_cut = sum(comb)
        if n_cut >= ans:
            continue

        group = []
        g_id = 0
        for c in comb:
            group.append(g_id)
            if c == 1:
                g_id += 1
        group.append(g_id)

        w = 0
        while w < W:
            count = [0] * (g_id + 1)
            next_w = w
            for x in range(w, W):
                over_K = False
                for y in range(H):
                    if S[y][x] == "1":
                        count[group[y]] += 1
                        if count[group[y]] > K:
                            over_K = True
                            break
                if over_K:
                    break
                next_w += 1

            # Impossible: over K in one column
            if next_w == w:
                n_cut = float("inf")
                break
            w = next_w

            if over_K:
                n_cut += 1
            if n_cut >= ans:
                break

        if n_cut < ans:
            ans = n_cut

    print(ans)


if __name__ == "__main__":
    main()

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

import numpy as np

input = sys.stdin.readline


def main():
    H, W, K = map(int, input().split())
    S = np.zeros(shape=(H, W), dtype=np.uint8)
    for i in range(H):
        S[i] = list(map(int, input().rstrip()))

    ans = float("inf")
    for comb in product(range(2), repeat=H-1):
        n_cut = sum(comb)
        M = 1 + n_cut

        # horizontal chocolates
        h_chocos = np.zeros(shape=(M, W), dtype=np.uint16)
        h = 0  # upper index
        m = 0
        for i, c in enumerate(comb):
            if c == 1:
                h_chocos[m] = np.sum(S[h:i+1, :], axis=0)
                h = i + 1
                m += 1
        h_chocos[m] = np.sum(S[h:, :], axis=0)

        total = np.zeros(shape=M, dtype=np.uint16)
        for w in range(W):
            total += h_chocos[:, w]
            if not np.all(total <= K):
                n_cut += 1
                total = h_chocos[:, w]
        if n_cut < ans:
            ans = n_cut

    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
"""
References: <https://www.hamayanhamayan.com/entry/2020/03/22/231629>
"""
import sys
from itertools import product

input = sys.stdin.readline


def main():
    H, W, K = map(int, input().split())
    S = [None] * H
    for i in range(H):
        S[i] = input().rstrip()

    ans = float("inf")
    for comb in product(range(2), repeat=(H - 1)):
        n_cut = sum(comb)
        if n_cut >= ans:
            continue

        group = []
        g_id = 0
        for c in comb:
            group.append(g_id)
            if c == 1:
                g_id += 1
        group.append(g_id)

        w = 0
        while w < W:
            count = [0] * (g_id + 1)
            next_w = w
            for x in range(w, W):
                over_K = False
                for y in range(H):
                    if S[y][x] == "1":
                        count[group[y]] += 1
                        if count[group[y]] > K:
                            over_K = True
                            break
                if over_K:
                    break
                next_w += 1

            # Impossible: over K in one column
            if next_w == w:
                n_cut = float("inf")
                break
            w = next_w

            if over_K:
                n_cut += 1
            if n_cut >= ans:
                break

        if n_cut < ans:
            ans = n_cut

    print(ans)


if __name__ == "__main__":
    main()

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

import numpy as np

input = sys.stdin.readline


def main():
    H, W, K = map(int, input().split())
    S = np.zeros(shape=(H, W), dtype=np.uint8)
    for i in range(H):
        S[i] = list(map(int, input().rstrip()))

    ans = float("inf")
    for comb in product(range(2), repeat=H-1):
        h_chocos = []  # horizontal chocolates
        h = 0  # upper index
        for i, c in enumerate(comb):
            if c == 1:
                h_chocos.append(np.sum(S[h:i+1, :], axis=0))
                h = i + 1
        h_chocos.append(np.sum(S[h:, :], axis=0))

        n_cut = sum(comb)
        M = len(h_chocos)
        total = [0] * M
        for w in range(W):
            for i in range(M):
                total[i] += h_chocos[i][w]
            if not all(t <= K for t in total):
                n_cut += 1
                total = [0] * M
                for i in range(M):
                    total[i] += h_chocos[i][w]
        if n_cut < ans:
            ans = n_cut

    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
"""
References: <https://www.hamayanhamayan.com/entry/2020/03/22/231629>
"""
import sys
from itertools import product

input = sys.stdin.readline


def main():
    H, W, K = map(int, input().split())
    S = [None] * H
    for i in range(H):
        S[i] = input().rstrip()

    ans = float("inf")
    for comb in product(range(2), repeat=(H - 1)):
        n_cut = sum(comb)
        if n_cut >= ans:
            continue

        group = []
        g_id = 0
        for c in comb:
            group.append(g_id)
            if c == 1:
                g_id += 1
        group.append(g_id)

        w = 0
        while w < W:
            count = [0] * (g_id + 1)
            next_w = w
            for x in range(w, W):
                over_K = False
                for y in range(H):
                    if S[y][x] == "1":
                        count[group[y]] += 1
                        if count[group[y]] > K:
                            over_K = True
                            break
                if over_K:
                    break
                next_w += 1

            # Impossible: over K in one column
            if next_w == w:
                n_cut = float("inf")
                break
            w = next_w

            if over_K:
                n_cut += 1
            if n_cut >= ans:
                break

        if n_cut < ans:
            ans = n_cut

    print(ans)


if __name__ == "__main__":
    main()