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: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def s(): return input()

def cuts(H):
    for i in range(1<<H):
        yield bin(i)[2:].zfill(H)

def main():
    H, W, K = LI()
    S = []
    for _ in range(H):
        S.append(s())
    ans = inf
    for cut in cuts(H-1):
        p = sum([1 for x in cut if x == '1'])
        cnt = p
        lines = [[0 for _ in range(W)] for __ in range(p+1)]
        cumr = 0
        for c in range(W):
            n_line = 0
            for r in range(H):
                if S[r][c] == '1':
                    cumr += 1
                if r >= H-1:
                    continue
                if cut[r] == '1':
                    lines[n_line][c] += cumr
                    n_line += 1
                    cumr = 0
            lines[-1][c] = cumr
            cumr = 0

        ng = False
        cumsum = [[0 for _ in range(W+1)] for __ in range(p+1)]

        for i in range(p+1):
            line = lines[i]
            for j in range(W):
                cumsum[i][j+1] = line[j] + cumsum[i][j]

        before = 0
        for j in range(1, W+1):
            # import pdb
            # pdb.set_trace()
            for i in range(p+1):
                if ng:
                    break
                if cumsum[i][j] - cumsum[i][before] > K:
                    if j - before == 1:
                        ng = True
                    cnt += 1
                    before = j - 1
                    break
        if ng:
            continue
        ans = min(ans, cnt)
    print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
import numpy as np
H, W, K = map(int, input().split())
choko = np.array([list(input()) for _ in range(H)], dtype=int)

np.cumsum(choko, axis=1, out=choko)

ans = 10**18
for p in product(range(2), repeat=H - 1):
    Hcut = sum(p)

    ch = np.zeros((Hcut + 1, W), dtype=int)
    cnt = choko[0]
    h = 0
    for i, b in enumerate(p):
        if b:
            ch[h] = cnt
            cnt = choko[i + 1]
            h += 1
        else:
            cnt = cnt + choko[i + 1]
    ch[h] = cnt

    if (ch[:, 0] > K).any():
        continue

    Vcut = 0
    left = np.zeros(Hcut + 1, dtype=int)
    for i in range(W):
        right = ch[:, i]
        if (right - left > K).any():
            Vcut += 1
            left = ch[:, i - 1]
    ans = min(ans, Hcut + Vcut)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

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

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

ans = h + w - 2
for i in range(1<<(h-1)):
    l = []
    tmp = s[0]
    for j in range(h-1):
        if i >> j & 1:
            tmp = [tmp[m] + s[j+1][m] for m in range(w)]
        else:
            l.append(tmp)
            tmp = s[j+1]
    l.append(tmp)
    c = [0] * len(l)
    cnt = 0
    flag = False
    j = 0
    while j < w:
        for m in range(len(l)):
            c[m] += l[m][j]
            if c[m] > k:
                flag = True
        if flag:
            c = [0] * len(l)
            cnt += 1
            flag = False
            j -= 1
        j += 1
    ans = min(ans, len(l) + cnt - 1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

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

if h == 1:
    j = 0
    c = 0
    cnt = 0
    while j < w:
        c += s[j]
        if c > k:
            flag = True
        if flag:
            c = 0
            cnt += 1
            flag = False
            j -= 1
        j += 1
    print(w + cnt - 1)
    sys.exit()

ans = h + w - 2
for i in range(2**(h-1)):
    l = []
    tmp = s[0]
    for j in range(h-1):
        if i >> j & 1:
            tmp = [tmp[m] + s[j+1][m] for m in range(w)]
        else:
            l.append(tmp)
            tmp = s[j+1]
    l.append(tmp)
    c = [0] * len(l)
    cnt = 0
    flag = False
    j = 0
    while j < w:
        for m in range(len(l)):
            c[m] += l[m][j]
            if c[m] > k:
                flag = True
        if flag:
            c = [0] * len(l)
            cnt += 1
            flag = False
            j -= 1
        j += 1
    ans = min(ans, len(l) + cnt - 1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
h, w, k = map(int, input().split())
s = []
for i in range(h):
    tmp = list(map(int, input()))
    s.append(tmp)

ans = h + w - 2
for i in range(2**(h-1)):
    l = []
    tmp = s[0]
    for j in range(h-1):
        if i >> j & 1:
            tmp = [tmp[m] + s[j+1][m] for m in range(w)]
        else:
            l.append(tmp)
            tmp = s[j+1]
    l.append(tmp)
    c = [0] * len(l)
    cnt = 0
    flag = False
    j = 0
    while j < w:
        for m in range(len(l)):
            c[m] += l[m][j]
            if c[m] > k:
                flag = True
        if flag:
            c = [0] * len(l)
            cnt += 1
            flag = False
            j -= 1
        j += 1
    ans = min(ans, len(l) + cnt - 1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
import itertools

h, w, k = map(int, input().split())
#s= list(input())

s = []
min = 100000
for i in range(h):
    s.append( [int(s) for s in list(input())])

l = list(range(h-1))
for i in range(h):
    p = list(itertools.combinations(l, i))
    for j in p:
        tmp = list(j)
        tmps = []
        q = 0
        tmps.append([])
        for r in range(h):
            tmps[q].append(copy.copy(s[r]))
            if(q < len(tmp) and r==tmp[q]):
                tmps.append([])
                q += 1
        #print(tmps)
        count = i
        sums = [0] * len(tmps)
        precut = 1
        exitflg = 0
        for r in range(w):
            for q in range(len(tmps)):
                for t in tmps[q]:
                    sums[q] += t[r]
            cutflg = 0
            for q in range(len(tmps)):
                if sums[q] > k :
                    cutflg = 1
            if cutflg == 1:
                #print('cut')
                count += 1
                sums = [0] * len(tmps)
                for q in range(len(tmps)):
                    for t in tmps[q]:
                        sums[q] += t[r]
            for q in range(len(tmps)):
                if sums[q] > k :
                    exitflg = 1
                    #print('exit')
        #print(exitflg)
        if exitflg == 0:
            if min > count:
                min = count
print(min)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

H, W, K = map(int, input().split())
S = list(input().split() for _ in range(H))
for i in range(len(S)):
    s = list(S[i][0])
    for j in range(len(s)):
        s[j] = int(s[j])
    S[i] = s    
    
def makes(k):
    k = np.array(k)
    s = np.array(S)
    x = np.sum(k == 1)
    z = np.array([])
    for j in range(len(k)):
        if k[j] == 0:
            s[j+1] += s[j]
        elif k[j] == 1:
            z = np.append(z,s[j])
    z = np.append(z,s[H-1])
    y = H-(len(k)-x)
    z = z.reshape(y,W)
    return z, y
    
def slc(z, h):
    cnt = 0
    head = 0
    tail = 1
    while True:
        for i in range(h):
            if np.sum(z[i][head:tail]) > K:
                head = tail-1
                tail = head
                cnt += 1
                break
        tail += 1
        if tail == W+1:
            break
    return cnt


best = 99999999
for i in range(pow(2, H-1)):
    cnt = 0
    a = pow(2, H-2)
    b = i
    k = []
    while a >= 1:
        cnt += b//a
        k += [b//a]
        b %= a
        a //= 2
    z, h = makes(k)
    p = slc(z, h)
    best = min(p+cnt, best)
    
print(best)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import numpy as np
import itertools

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    # Failed to predict input format
    H, W, K = list(map(int, input().split()))
    S = np.ndarray([H, W])
    answer = np.inf

    for h in range(H):
        row = list(map(int, list(input())))
        S[h, :] = row

    for n in range(H):
        for comb in itertools.combinations([h for h in range(1, H)], n):
            num_horizontal_cut = len(comb)
            if num_horizontal_cut == 0:
                sub_S = S.sum(axis=0)
            else:
                sub_S = np.zeros([num_horizontal_cut+1, W])
                head = 0

                c_prev = 0
                for i, c in enumerate(comb):
                    sub_S[i] = S[c_prev: c].sum(axis=0)
                    c_prev = c
                sub_S[num_horizontal_cut] = S[c_prev:].sum(axis=0)

            current_sum = np.zeros(num_horizontal_cut+1)
            num_cut = 0
            if np.any(sub_S > K):
                num_cut = np.inf
                continue
            for line in sub_S.T:
                if np.any(current_sum + line > K):
                    current_sum[:] = 0#np.zeros(num_horizontal_cut+1)
                    num_cut += 1
                current_sum += line

            if num_cut + num_horizontal_cut < answer:
                answer = num_cut + num_horizontal_cut
    print(answer)
    pass

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import numpy as np
import itertools

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    # Failed to predict input format
    H, W, K = list(map(int, input().split()))
    S = np.ndarray([H, W])
    answer = np.inf

    for h in range(H):
        row = list(map(int, list(input())))
        S[h, :] = row

    for n in range(H):
        for comb in itertools.combinations([h for h in range(1, H)], n):
            num_horizontal_cut = len(comb)
            if num_horizontal_cut == 0:
                sub_S = S.sum(axis=0)
            else:
                sub_S = np.zeros([num_horizontal_cut+1, W])
                head = 0

                c_prev = 0
                for i, c in enumerate(comb):
                    sub_S[i] = S[c_prev: c].sum(axis=0)
                    c_prev = c
                sub_S[num_horizontal_cut] = S[c_prev:].sum(axis=0)
                """
                for h in range(H):
                    if h in comb:
                        head += 1
                    sub_S[head, :] += S[h, :]
                """

            current_sum = np.zeros(num_horizontal_cut+1)
            num_cut = 0
            if np.any(sub_S > K):
                num_cut = np.inf
                continue
            for line in sub_S.T:
                if np.any(current_sum + line > K):
                    current_sum = np.zeros(num_horizontal_cut+1)
                    num_cut += 1
                current_sum += line

            if num_cut + num_horizontal_cut < answer:
                answer = num_cut + num_horizontal_cut
    print(answer)
    pass

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import numpy as np
import itertools

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    # Failed to predict input format
    H, W, K = list(map(int, input().split()))
    S = np.ndarray([H, W])
    answer = np.inf

    for h in range(H):
        row = input()
        for w in range(W):
            S[h, w] = int(row[w])
    for n in range(H+1):
        for comb in itertools.combinations([h for h in range(1, H)], n):
            if len(comb) == 0:
                sub_S = S.sum(axis=0)
            else:
                sub_S = np.zeros([len(comb)+1, W])

                head = 0
                for h in range(H):
                    if h in comb:
                        head += 1
                    sub_S[head, :] += S[h, :]
            current_sum = np.zeros(len(comb)+1)
            num_cut = 0
            for line in sub_S.T:
                if np.any(line > K):
                    num_cut = np.inf
                    break
                if np.any(current_sum + line > K):
                    current_sum = np.zeros(len(comb)+1)
                    num_cut += 1
                current_sum += line
            if num_cut + len(comb) < answer:
                answer = num_cut + len(comb)
    print(answer)
    pass

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def main():
    H, W, K = map(int, input().split())
    S = []
    for _ in range(H):
        S.append(list(map(int, list(input()))))
    S = np.array(S)
    if S.sum() <= K:
        print(0)
        exit(0)
    answer = (H - 1) * (W - 1)
    for i in range(0, 2 ** (H - 1)):
        horizons = list(map(int, list(bin(i)[2:].zfill(H - 1))))
        result = greedy(W, S, K, horizons)
        if result > 0 and result < answer:
            answer = result
    print(answer)

# ex. horizons = [0, 0, 1, 0, 0, 1]
def greedy(W, S, K, horizons):
    answer = sum(horizons)
    # ex.
    # S  = [[1, 1, 1, 0, 0],
    #       [1, 0, 0, 0, 1],
    #       [0, 0, 1, 1, 1]]
    # horizons = [0, 1]のとき,
    # S2 = [[2, 1, 1, 0, 0],
    #       [0, 0, 1, 1, 1]]
    # となる
    top = 0
    bottom = 0
    S2 = []
    for h in horizons:
        if h == 1:
            S2.append(S[:][top:(bottom + 1)].sum(axis=0))
            top = bottom + 1
        bottom += 1
    S2.append(S[:][top:].sum(axis=0))
    # ブロック毎の累積和を計算する
    left = 0
    right = 0
    partial_sums = [0] * len(S2)
    while right <= W - 1:
        satisfied = True
        for idx, row in enumerate(S2):
            partial_sums[idx] += row[right]
            # 無理(ブロックの中のホワイトチョコの数をk以下にできない)な場合
            if partial_sums[idx] > K:
                satisfied = False
                if left == right:
                    return -1
                left = right
                answer += 1
                partial_sums = [0] * len(S2)
                break
        if satisfied:
            right += 1
        # if satisfied:
        #     right += 1
        # else:
        #     # 無理(ブロックの中のホワイトチョコの数をk以下にできない)だったら-1を返す
        #     if left == right:
        #         return -1
        #     left = right
        #     answer += 1
        #     partial_sums = [0] * len(S2)
    return answer

main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def main():
    H, W, K = map(int, input().split())
    S = []
    for _ in range(H):
        S.append(list(map(int, list(input()))))
    S = np.array(S)
    if S.sum() <= K:
        print(0)
        exit(0)
    answer = (H - 1) * (W - 1)
    for i in range(0, 2 ** (H - 1)):
        horizons = list(map(int, list(bin(i)[2:].zfill(H - 1))))
        result = greedy(W, S, K, horizons)
        if result > 0 and result < answer:
            answer = result
    print(answer)

# ex. horizons = [0, 0, 1, 0, 0, 1]
def greedy(W, S, K, horizons):
    answer = sum(horizons)
    # greedyに縦線を引いていく
    # ex.
    # S  = [[1, 1, 1, 0, 0],
    #       [1, 0, 0, 0, 1],
    #       [0, 0, 1, 1, 1]]
    # horizons = [0, 1]のとき,
    # S2 = [[2, 1, 1, 0, 0],
    #       [0, 0, 1, 1, 1]]
    # となる
    top = 0
    bottom = 0
    S2 = []
    for h in horizons:
        if h == 1:
            S2.append(S[:][top:(bottom + 1)].sum(axis=0))
            top = bottom + 1
        bottom += 1
    S2.append(S[:][top:].sum(axis=0))
    left = 0
    right = 0
    partial_sums = [0] * len(S2)
    while right <= W - 1:
        if satisfy(K, S2, right, partial_sums):
            right += 1
        else:
            # 無理(ブロックの中のホワイトチョコの数をk以下にできない)だったら-1を返す
            if left == right:
                return -1
            left = right
            answer += 1
            partial_sums = [0] * len(S2)
    return answer

def satisfy(K, S2, right, partial_sums):
    result = True
    for idx, row in enumerate(S2):
        partial_sums[idx] += row[right]
        if partial_sums[idx] > K:
            result = False
    return result

main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

if S.sum() <= K:
    print(0)
    exit(0)

def satisfy(left, right, S2):
    global K
    for row in S2:
        if row[left:(right + 1)].sum() > K:
            return False
    return True

# ex. horizons = [0, 0, 1, 0, 0, 1]
def greedy(horizons):
    global W, S
    answer = sum(horizons)
    left = 0
    right = 0
    # greedyに縦線を引いていく
    # TODO: 横線で分けた後のそれぞれのブロックで集計
    # ex.
    # S  = [[1, 1, 1, 0, 0],
    #       [1, 0, 0, 0, 1],
    #       [0, 0, 1, 1, 1]]
    # horizons = [0, 1]のとき,
    # S2 = [[2, 1, 1, 0, 0],
    #       [0, 0, 1, 1, 1]]
    # となる
    top = 0
    bottom = 0
    S2 = []
    for h in horizons:
        if h == 1:
            S2.append(S[:][top:(bottom + 1)].sum(axis=0))
            top = bottom + 1
        bottom += 1
    S2.append(S[:][top:].sum(axis=0))
    while right <= W - 1:
        if not satisfy(left, right, S2):
            # 無理(ブロックの中のホワイトチョコの数をk以下にできない)だったら-1を返す
            if left == right:
                return -1
            left = right
            answer += 1
        else:
            right += 1
    return answer

answer = (H - 1) * (W - 1)

# result = greedy([0, 1, 0])

for i in range(0, 2 ** (H - 1)):
    horizons = list(map(int, list(bin(i)[2:].zfill(H - 1))))
    result = greedy(horizons)
    if result > 0 and result < answer:
        answer = result

print(answer)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

if S.sum() <= K:
    print(0)
    exit(0)

def satisfy(left, right, S2):
    global K
    top = 0
    for row in S2:
        if row[left:(right + 1)].sum() > K:
            return False
    return True

# ex. horizons = [0, 0, 1, 0, 0, 1]
def greedy(horizons):
    global W, S
    answer = sum(horizons)
    left = 0
    right = 0
    # greedyに縦線を引いていく
    # TODO: 横線で分けた後のそれぞれのブロックで集計
    # ex.
    # S  = [[1, 1, 1, 0, 0],
    #       [1, 0, 0, 0, 1],
    #       [0, 0, 1, 1, 1]]
    # horizons = [0, 1]のとき,
    # S2 = [[2, 1, 1, 0, 0],
    #       [0, 0, 1, 1, 1]]
    # となる
    top = 0
    bottom = 0
    S2 = []
    for h in horizons:
        if h == 1:
            S2.append(S[:][top:(bottom + 1)].sum(axis=0))
            top = bottom + 1
        bottom += 1
    S2.append(S[:][top:].sum(axis=0))
    S2 = np.array(S2)
    # print(S2)
    # print('hoge')
    while right <= W - 1:
        if not satisfy(left, right, S2):
            # 無理(ブロックの中のホワイトチョコの数をk以下にできない)だったら-1を返す
            if left == right:
                return -1
            left = right
            answer += 1
        else:
            right += 1
    return answer

answer = (H - 1) * (W - 1)

# result = greedy([0, 1, 0])

for i in range(0, 2 ** (H - 1)):
    horizons = list(map(int, list(bin(i)[2:].zfill(H - 1))))
    result = greedy(horizons)
    if result > 0 and result < answer:
        answer = result

print(answer)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

if S.sum() <= K:
    print(0)
    exit(0)

def satisfy(left, right, horizons):
    global K, S
    top = 0
    white_chocos = 0
    for idx, h in enumerate(horizons):
        white_chocos += S[idx, left:(right + 1)].sum()
        if h == 1:
            bottom = idx
            # total = S[top:(bottom + 1), left:(right + 1)].sum()
            # total = sum(map(lambda row: sum(row[left:(right + 1)]), S[top:(bottom + 1)]))
            # print(horizons, top, bottom, left, right, total)
            if white_chocos > K:
                return False
            top = bottom + 1
            white_chocos = 0
    total = S[top:, left:(right + 1)].sum()
    # total = sum(map(lambda row: sum(row[left:(right + 1)]), S[top:]))
    # print(horizons, top, -1, left, right, total)
    if total > K:
        return False
    return True

# ex. horizons = [0, 0, 1, 0, 0, 1]
def greedy(horizons):
    global W
    answer = sum(horizons)
    left = 0
    right = 0
    # greedyに縦線を引いていく
    # 無理(ブロックの中のホワイトチョコの数をk以下にできない)だったら-1を返す
    while right <= W - 1:
        if not satisfy(left, right, horizons):
            if left == right:
                return -1
            left = right
            answer += 1
        else:
            right += 1
    return answer

answer = (H - 1) * (W - 1)

# result = greedy([0, 1, 0])

for i in range(0, 2 ** (H - 1)):
    horizons = list(map(int, list(bin(i)[2:].zfill(H - 1))))
    result = greedy(horizons)
    if result > 0 and result < answer:
        answer = result

print(answer)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

if sum(map(sum, S)) <= K:
    print(0)
    exit(0)

def satisfy(left, right, horizons):
    global K, S
    top = 0
    for idx, h in enumerate(horizons):
        if h == 1:
            bottom = idx
            total = S[top:(bottom + 1), left:(right + 1)].sum()
            # total = sum(map(lambda row: sum(row[left:(right + 1)]), S[top:(bottom + 1)]))
            # print(horizons, top, bottom, left, right, total)
            if total > K:
                return False
            top = bottom + 1
    total = S[top:, left:(right + 1)].sum()
    # total = sum(map(lambda row: sum(row[left:(right + 1)]), S[top:]))
    # print(horizons, top, -1, left, right, total)
    if total > K:
        return False
    return True

# ex. horizons = [0, 0, 1, 0, 0, 1]
def greedy(horizons):
    answer = sum(horizons)
    left = 0
    right = 0
    # greedyに縦線を引いていく
    # 無理(ブロックの中のホワイトチョコの数をk以下にできない)だったら-1を返す
    while right <= W - 1:
        if not satisfy(left, right, horizons):
            if left == right:
                return -1
            left = right
            answer += 1
        else:
            right += 1
    return answer

answer = (H - 1) * (W - 1)

# result = greedy([0, 1, 0])

for i in range(0, 2 ** (H - 1)):
    horizons = list(map(int, list(bin(i)[2:].zfill(H - 1))))
    result = greedy(horizons)
    if result > 0 and result < answer:
        answer = result

print(answer)

Submission status: Time Limit Exceeded

Solution code:
H, W, K = map(int, input().split())
S = []
for _ in range(H):
    S.append(list(map(int, list(input()))))

if sum(map(sum, S)) <= K:
    print(0)
    exit(0)

def satisfy(left, right, horizons):
    global K, S
    top = 0
    for idx, h in enumerate(horizons):
        if h == 1:
            bottom = idx
            total = sum(map(lambda row: sum(
                row[left:(right + 1)]), S[top:(bottom + 1)]))
            # print(horizons, top, bottom, left, right, total)
            if total > K:
                return False
            top = bottom + 1
    total = sum(map(lambda row: sum(row[left:(right + 1)]), S[top:]))
    # print(horizons, top, -1, left, right, total)
    if total > K:
        return False
    return True

# ex. horizons = [0, 0, 1, 0, 0, 1]
def greedy(horizons):
    answer = sum(horizons)
    left = 0
    right = 0
    # greedyに縦線を引いていく
    # 無理(ブロックの中のホワイトチョコの数をk以下にできない)だったら-1を返す
    while right <= W - 1:
        if not satisfy(left, right, horizons):
            if left == right:
                return -1
            left = right
            answer += 1
        else:
            right += 1
    return answer

answer = (H - 1) * (W - 1)

# result = greedy([0, 1, 0])

for i in range(0, 2 ** (H - 1)):
    horizons = list(map(int, list(bin(i)[2:].zfill(H - 1))))
    result = greedy(horizons)
    if result > 0 and result < answer:
        answer = result

print(answer)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3


def _f(H, W, S):
    '''
    >>> f = _f(3, 3, [[1, 0, 0], [1, 0, 1], [0, 1, 1]])
    >>> f(0, 0, 1, 1)
    1
    >>> f(0, 0, 3, 0)
    0
    >>> f(0, 0, 3, 1)
    2
    >>> f(1, 1, 3, 3)
    3
    >>> f(0, 0, 3, 3)
    5
    >>> f(2, 0, 3, 3)
    2
    '''
    acc = [[0] * (W + 1) for _ in range(H+1)]
    for h in range(1, H+1):
        for w in range(1, W+1):
            acc[h][w] = acc[h][w-1] + acc[h-1][w] - acc[h-1][w-1] + S[h-1][w-1]

    def f(sh, sw, eh, ew):
        return acc[eh][ew] + acc[sh][sw] - acc[sh][ew] - acc[eh][sw]

    return f

def _solve(H, W, K, S, c, f):
    #print(H, W, K, S, c, f)
    sw = 0
    cut = 0
    for ew in range(1, W+1):
        #print([(((sh, sw), (eh, ew)), f(sh, sw, eh, ew)) for sh, eh in c])    
        if any(f(sh, ew-1, eh, ew) > K for sh, eh in c):
            return float('inf')
        if any(f(sh, sw, eh, ew) > K for sh, eh in c):
            cut += 1
            sw = ew - 1
    return cut


def solve(H, W, K, S):
    from itertools import product, compress
    f = _f(H, W, S)
    ans = float('inf')
    for flag in product(range(2), repeat=H-1):
        t = (0,) + tuple(compress(range(1,H), flag)) + (H,)
        c = tuple(zip(t, t[1:]))
        ans = min(ans, _solve(H, W, K, S, c, f)+sum(flag))
    return ans


    

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools
def main():
    H, W, K = list(map(int, input().split()))
    S = [list(map(int, input())) for _ in range(H)]
    print(solve(H, W, K, S))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Time Limit Exceeded

Solution code:

import heapq
from collections import defaultdict, deque
# from math import ceil, factorial, gcd
from itertools import accumulate, permutations
import sys
import bisect


sys.setrecursionlimit(10 ** 7)
INF = float("inf")
MOD = 10 ** 9 + 7

si = lambda: input().strip()
ii = lambda: int(input())
mii = lambda: map(int, input().split())
msi = lambda: map(str, input().split())
lmii = lambda: list(map(int, input().split()))
lmsi = lambda: list(map(str, input().split()))
smii = lambda: sorted(map(int, input().split()))
# ----------

H, W, K = mii()
S = []
for i in range(H):
    S.append(si())

ans = INF
for div in range(1<<(H-1)):
    id = [0] * H
    g = 0
    for i in range(H):
        id[i] = g
        if div >> i & 1:
            g += 1

    c = [[0] * W for _ in range(g+1)]

    for i in range(H):
        for j in range(W):
            if S[i][j] == '1':
                c[id[i]][j] += 1

    now = defaultdict(int)

    def add(j):
        for i in range(g+1):
            now[i] += c[i][j]
        for i in range(g+1):
            if now[i] > K:
                return False
        return True

    num = g
    for j in range(W):
        if not add(j):
            num += 1
            now = defaultdict(int)
            if not add(j):
                num = INF
                break

    ans = min(ans, num)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from copy import deepcopy
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

H, W, K = map(int, input().split())
SHW = [list(map(int, list(input()))) for _ in range(H)]
SHW = np.array(SHW)
tSHW = SHW.T

def vcut(cuts: list):
    num = 0
    cuts = [0] + cuts + [H]

    iparts = [0]*(len(cuts)-1)
    parts = deepcopy(iparts)
    w = 0
    while w < W:
        for i, (sc, ec) in enu(zip(cuts, cuts[1:])):
            if K < parts[i]+sum(tSHW[w][sc:ec]):
                num += 1
                parts = deepcopy(iparts)
                break
            else:
                parts[i] += sum(tSHW[w][sc:ec])
        else:
            w += 1
    return num

res = (H-1)*(W-1)
for i in range(2**(H-1)):
    cnt = 0
    cuts = [] # cut index
    for j in range((H-1)):
        if ((i >> j) & 1):
            cnt += 1
            cuts.append(j+1)
    if res > cnt:
        cnt += vcut(cuts)
        if res > cnt:
            res = cnt

print(res)

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
from copy import deepcopy
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

H, W, K = map(int, input().split())
SHW = [list(map(int, list(input()))) for _ in range(H)]
tSHW = list(zip(*SHW))

def vcut(cuts: list):
    num = 0
    cuts = [0] + cuts + [H]

    iparts = [0]*(len(cuts)-1)
    parts = deepcopy(iparts)
    w = 0
    while w < W:
        for i, (sc, ec) in enu(zip(cuts, cuts[1:])):
            if K < parts[i]+sum(tSHW[w][sc:ec]):
                num += 1
                parts = deepcopy(iparts)
                break
            else:
                parts[i] += sum(tSHW[w][sc:ec])
        else:
            w += 1
    return num

res = (H-1)*(W-1)
for i in range(2**(H-1)):
    cnt = 0
    cuts = [] # cut index
    for j in range((H-1)):
        if ((i >> j) & 1):
            cnt += 1
            cuts.append(j+1)
    if res > cnt:
        cnt += vcut(cuts)
        if res > cnt:
            res = cnt

print(res)