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:
# E - Dividing Chocolate
import numpy as np

H, W, K = map(int, input().split())
S = np.zeros((H, W), dtype=np.int64)

ans = H*W

for i in range(H):
    S[i] = list(str(input()))

for m in range(2**(H-1)):
    wp = np.zeros((H, W), dtype=np.int64)
    wq = np.zeros((H, ), dtype=np.int64)
    wp[0] = S[0]
    h = 0
    tmp = 0
    for n in range(H-1):
        if m>>n&1:
            h += 1
            tmp += 1
        wp[h] += S[n+1]

    for j in range(W):
        wq += wp[:,j]
        if any([a > K for a in wq]):
            tmp += 1
            wq = wp[:,j]
    ans = min(ans, tmp)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w,lim = map(int,input().split())
S = []
ans = 10**10
for i in range(h):
    S.append(input())
for i in range(2**(h-1)):
    bit = ''
    cur = 1
    for j in range(h-1):
        if i&cur != 0:
            bit = '1'+bit
        else:
            bit = '0'+bit
        cur *= 2
    group = []
    if i == 0:
        group = [[i for i in range(h)]]
    else:
        div = []
        for j in range(len(bit)):
            if bit[j] == '0':
                div.append(j)
            else:
                div.append(j)
                group.append(div)
                div = []
        div.append(j+1)
        if len(div) != 0:
            group.append(div)
    num = [0]*len(group)
    cur = len(group)-1
    flag1 = True
    for j in range(w):
        next = [0]*len(group)
        flag2 = True
        for k in range(len(group)):
            plus = 0
            for l in range(len(group[k])):
                if S[group[k][l]][j] == '1':
                    plus += 1
            if plus > lim:
                flag1 = False
                break
            elif plus+num[k] > lim:
                flag2 = False
                next[k] += plus
            else:
                next[k] += plus
        if flag1 == False:
            break
        else:
            if flag2 == False:
                cur += 1
                num = next
            else:
                for k in range(len(group)):
                    num[k] += next[k]
    if flag1:
        ans = min(ans, cur)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc159/tasks/abc159_e
import sys

ans = sys.maxsize
H, W, K = map(int, input().split())
s = [input() for _ in range(H)]

for h in range(1 << (H - 1)):
    g = 0
    ids = [-1 for _ in range(H)]
    for i in range(H):
        ids[i] = g
        if (h >> i) & 1:
            g += 1

    g += 1
    c = [[0] * W for _ in range(g)]
    for i in range(H):
        for j in range(W):
            c[ids[i]][j] = c[ids[i]][j] + (s[i][j] == '1')

    num = g - 1
    now = [0 for _ in range(g)]


    def add(j):
        for i in range(g):
            now[i] += c[i][j]

        for i in range(g):
            if now[i] > K:
                return False

        return True


    if num >= ans:
        continue

    for j in range(W):
        if not add(j):
            num += 1
            if num >= ans:
                continue
            now = [0 for _ in range(g)]
            if not add(j):
                num = sys.maxsize
                break

    ans = min(ans, num)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc159/tasks/abc159_e
import sys

ans = sys.maxsize
H, W, K = map(int, input().split())
s = [input() for _ in range(H)]
c = [[0 for _ in range(W)] for _ in range(10)]

for h in range(1 << (H - 1)):
    g = 0
    ids = [-1 for _ in range(H)]
    for i in range(H):
        ids[i] = g
        if (h >> i) & 1:
            g += 1

    g += 1
    for i in range(W):
        for j in range(g):
            c[j][i] = 0

    for i in range(H):
        for j in range(W):
            c[ids[i]][j] = c[ids[i]][j] + (s[i][j] == '1')

    num = g - 1
    now = [0 for _ in range(g)]


    def add(j):
        for i in range(g):
            now[i] += c[i][j]

        for i in range(g):
            if now[i] > K:
                return False

        return True


    if num >= ans:
        continue

    for j in range(W):
        if not add(j):
            num += 1
            if num >= ans:
                continue
            now = [0 for _ in range(g)]
            if not add(j):
                num = sys.maxsize
                break

    ans = min(ans, num)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc159/tasks/abc159_e
import sys

ans = sys.maxsize
H, W, K = map(int, input().split())
s = [input() for _ in range(H)]

for h in range(1 << (H - 1)):
    g = 0
    ids = [-1 for _ in range(H)]
    for i in range(H):
        ids[i] = g
        if (h >> i) & 1:
            g += 1

    g += 1
    c = [[0 for _ in range(W)] for _ in range(g)]
    for i in range(H):
        for j in range(W):
            c[ids[i]][j] = c[ids[i]][j] + (s[i][j] == '1')

    num = g - 1
    now = [0 for _ in range(g)]


    def add(j):
        for i in range(g):
            now[i] += c[i][j]

        for i in range(g):
            if now[i] > K:
                return False

        return True


    for j in range(W):
        if not add(j):
            num += 1
            now = [0 for _ in range(g)]
            if not add(j):
                num = sys.maxsize
                break

    ans = min(ans, num)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
H, W, K = map(int, input().split())
S = np.zeros((H, W))
for i in range(H):
    S[i] = np.array(list(map(int, list(input()))))

ans = 2000
for k in range(2 ** (H-1)):
    count = 0
    k_ = k
    while k_ > 0:
        if k_ % 2 == 1:
            count += 1
        k_ //= 2
#     print(k, count)

    white = np.zeros(H)
    for w in range(W):
        k_ = k
        ind = 0
        retu = np.zeros(H)
        for h in range(H):
            retu[ind] += S[h][w]
            if k_ % 2 == 1:
                ind += 1
            k_ //= 2
        white += retu
        if any(white > K):
            if any(retu > K):
                count = 2000
                break
            count += 1
            white = retu
#         print(white)
    ans = min(ans, count)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W, K = map(int, input().split())
S = [input() for _ in range(H)]
d = 2 ** (H - 1)
mcut = 1008
for i in range(d):
  L = [0 for _ in range(H)]
  for j in range(1, H):
    L[j] = L[j-1] + i % 2
    i //= 2
  C = [0 for _ in range(L[H-1]+1)]
  cutp, cutq = True, True
  cut = L[H-1]
  for m in range(W):
    for l in range(H):
      C[L[l]] += int(S[l][m])
    if cutq:
      cutq = False
      if max(C) > K:
        cutp = False
        break
    else:
      if max(C) > K:
        cut += 1
        C = [0 for _ in range(L[H-1]+1)]
        for l in range(H):
          C[L[l]] += int(S[l][m])
    if cutp == False:
      break
  if cutp:
    if cut < mcut:
      mcut = cut
print(mcut)

Submission status: Time Limit Exceeded

Solution code:
def main():
    H, W, K = map(int, input().split())
    chocolate = [list(map(int,list(input()))) for _ in range(H)]
    choco = [[0]*W for _ in range(H)]
    ids = [0] * H
    ans = 10 ** 9
    for bit in range(1<<(H-1)):
        group_id = 0
        for i in range(H):
            ids[i] = group_id
            if (bit>>i)&1:
                group_id += 1
        group_id += 1
        
        for i in range(group_id):
            for j in range(W):
                choco[i][j] = 0

        for i in range(H):
            for j in range(W):
                choco[ids[i]][j] += chocolate[i][j]
        
        if any(choco[i][j] > K for i in range(group_id) for j in range(W)):
            continue
        
        num = group_id - 1
        now = [0] * group_id
        def add(j):
            for i in range(group_id):
                now[i] += choco[i][j]
            if any(now[i] > K for i in range(group_id)):
                return False
            else:
                return True

        for j in range(W):
            if not add(j):
                num += 1
                now = [0] * group_id
                add(j)
        ans = min(ans, num)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    H, W, K = map(int, input().split())
    s = []
    for _ in range(H):
        *row, = map(int, input())
        s.append(row)

    ret = H * W
    for bits in range(1 << (H - 1)):
        # 水平カットで生成される2枚目以降の開始行
        # 0行目は確定で, 残りのカットを調べる
        # 次の変換が必要
        # [0,H) -> [1,H]

        group = [0] * H
        for j in range(H - 1):
            group[j + 1] = group[j] + (1 if (bits >> j) & 1 else 0)
        # group = [0,0,1,1,1,2,...]

        ctr = [0] * H
        add_v = [0] * H
        c, pc = 0, -1
        cut = bin(bits).count('1')
        while c < W:
            need_cut = False
            for r in range(H):
                g = group[r]
                add_v[g] += s[r][c]
                if ctr[g] + add_v[g] > K:
                    need_cut = True
                    break

            if need_cut:
                if pc == c:
                    cut = H * W
                    break
                ctr = [0] * H
                add_v = [0] * H
                cut += 1
                pc = c
                if cut >= ret:
                    break
                continue

            for g, _add_v in enumerate(add_v):
                ctr[g] += _add_v
            add_v = [0] * H
            pc = c
            c += 1

        ret = min(ret, cut)

    print(ret)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

ret = H * W
for bits in range(1 << (H - 1)):
    # 水平カットで生成される2枚目以降の開始行
    # 0行目は確定で, 残りのカットを調べる
    # 次の変換が必要
    # [0,H) -> [1,H]

    group = [0] * H
    for j in range(H - 1):
        group[j + 1] = group[j] + (1 if (bits >> j) & 1 else 0)
    # group = [0,0,1,1,1,2,...]

    ctr = [0] * H
    add_v = [0] * H
    c = 0
    cut = bin(bits).count('1')
    while c < W:
        need_cut = False
        for r in range(H):
            g = group[r]
            add_v[g] += s[r][c]
            if ctr[g] + add_v[g] > K:
                need_cut = True
                break

        if need_cut:
            ctr = [0] * H
            add_v = [0] * H
            cut += 1
            if cut >= ret:
                break
            continue

        for g, _add_v in enumerate(add_v):
            ctr[g] += _add_v
        add_v = [0] * H
        c += 1

    ret = min(ret, cut)

print(ret)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
def input(): return sys.stdin.readline().rstrip()

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

    ans = 10 ** 9

    for bit in range(1 << (H-1)):
        canSolve = True
        ord = defaultdict(int)
        N = 0
        for i in range(H):
            if bit & 1 << i:
                ord[i+1] = ord[i] + 1
                N += 1
            else:
                ord[i+1] = ord[i]
        add = 0
        nums = defaultdict(int)
        for w in range(W):
            one = defaultdict(int)
            ok = True
            for h in range(H):
                one[ord[h]] += int(S[h][w])
                nums[ord[h]] += int(S[h][w])
                if one[ord[h]] > K:
                    canSolve = False
                if nums[ord[h]] > K:
                    ok = False
            if not ok:
                add += 1
                nums = one
        if canSolve and ans > N + add:
            ans = N + add
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

ret = H * W
for bits in range(1 << (H - 1)):
    # 水平カットで生成される2枚目以降の開始行
    # 0行目は確定で, 残りのカットを調べる
    # 次の変換が必要
    # [0,H) -> [1,H]

    group = [0] * H
    for j in range(H - 1):
        group[j + 1] = group[j] + (1 if (bits >> j) & 1 else 0)
    # group = [0,0,1,1,1,2,...]

    ctr = [0] * H
    add_v = [0] * H
    c = 0
    cut = bin(bits).count('1')
    while c < W:
        need_cut = False
        for r in range(H):
            g = group[r]
            add_v[g] += s[r][c]
            if ctr[g] + add_v[g] > K:
                need_cut = True
                break

        if need_cut:
            ctr = [0] * H
            add_v = [0] * H
            cut += 1
            continue

        for r in range(H):
            g = group[r]
            ctr[g] += add_v[g]
            add_v[g] = 0
        c += 1

    ret = min(ret, cut)

print(ret)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10 ** 7)
INF = 1001001001

H, W, K = map(int, input().split())
S = [list(map(int, list(input()))) for _ in range(H)]
# print(S)

ans = INF
for b in range(1<<(H-1)):
    g = 0
    idx = [0]*H
    for i in range(H-1):
        if b>>i&1:
            g += 1
        idx[i+1] = g
    g += 1
    cnt = [[0]*W for _ in range(g)]
    for i in range(H):
        for j in range(W):
            cnt[idx[i]][j] += S[i][j]
    num = g-1
    now = [0]*g

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

    for j in range(W):
        if add(j)==False:
            num += 1
            now = [0]*g
            if add(j)==False:
                num = INF
                break
    ans = min(ans, num)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, m, k = [int(i) for i in input().split()]

subsets = []
splits = [i for i in range(1, n)]
n -= 1
for i in range(2**n):
    x = []
    for j in range(n):
        if i&(1<<j):
            x.append(j)
    subsets.append(x)
n+=1
A = []
for i in range(n):
    A.append([int(j) for j in input()])
ans = n*m
for subset in subsets:
    cur_ans = len(subset)
    #print(subset)
    tmp = []
    col = 0
    subset.append(100000)
    running_sum = [0 for i in range(len(subset)+10)]    
    while col<m:
        row_ptr = 0    
        for row in range(n):
            if row > subset[row_ptr]:
                row_ptr += 1
            running_sum[row_ptr] += A[row][col]
            if running_sum[row_ptr] > k:
                col -= 1
                running_sum = [0 for i in range(len(subset)+10)]
                cur_ans += 1
                break
        col += 1                
    ans = min(ans, cur_ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def column_check(grp, grp_count, choco, h, j, k):
    """ 0:成功（更新も反映）  1:失敗（区切った結果を返す） 2:不可能 """
    # この行のグループ毎のカウント
    curr_count = [0] * len(grp_count)
    # 数える
    for i in range(h):
        if choco[i][j] == '0':
            continue
        curr_count[grp[i]] += 1
    # この行だけでk越えてたら現在の横の切り方では不可能
    for cc in curr_count:
        if cc > k:
            return 2
    # 左と合わせてkを越えないかチェック
    over = False
    for gc, cc in zip(grp_count, curr_count):
        if gc + cc > k:
            over = True
            break
    # 越えてたら、現在の行でgrp_countを更新
    if over:
        for i, cc in enumerate(curr_count):
            grp_count[i] = cc
        return 1
    # 越えてなかったら、加算
    for i, cc in enumerate(curr_count):
        grp_count[i] += cc
    return 0


def solve(h, w, k, choco):
    ans = 10 ** 9
    grp = [0] * h
    for bit in range(1 << (h - 1)):
        g = 0
        for i in range(h):
            grp[i] = g
            if (bit >> i) & 1:
                g += 1

        grp_count = [0] * (g + 1)
        tmp = 0
        possible = True
        for j in range(w):
            result = column_check(grp, grp_count, choco, h, j, k)
            if result == 2:
                possible = False
                break
            if result == 1:
                tmp += 1

        if not possible:
            continue

        ans = min(ans, tmp + bin(bit).count('1'))

    return ans


h, w, k = map(int, input().split())
choco = [input() for _ in range(h)]
print(solve(h, w, k, choco))

Submission status: Time Limit Exceeded

Solution code:
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, start=1) if p == 1] + [10]

    # 横方向へ割った後、各ブロックについて縦方向にホワイトチョコの数を修正
    rows = []
    for i in range(len(div) - 1):
        rows.append(np.sum(G[div[i]: div[i + 1]], axis=0))

    # 縦方向にすでにK個より多いホワイトチョコが含まれている場合はどうにもならない
    if [r for r in rows if np.any(r > K)]:
        continue

    tmp_ans = 0
    counts = [0] * len(rows)
    w = 0
    while w < W:
        for r in range(len(rows)):
            counts[r] += rows[r][w]
        if any([c > K for c in counts]):
            counts = [0] * len(rows)
            w -= 1
            tmp_ans += 1
        w += 1

    # 横に割った分を加算
    tmp_ans += len(div) - 2
    ans = min(ans, tmp_ans)

print(ans)

Submission status: Time Limit Exceeded

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

# main
result=H-1+W-1
for i in range(2**(H-1)):# O(2^H)
    tmp=bin(i)[2:].zfill(H-1)
    
    ii=0
    for iii in range(H-1):
        ii+=int(tmp[iii])
    Nk=[0]*(ii+1)
    Nw=0
    for iw in range(W):# O(W)
        Nh=0
        Nk0=[0]*(ii+1)
        for ih in range(H-1):# O(H)
            Nk[Nh]+=int(S[ih][iw])
            Nk0[Nh]+=int(S[ih][iw])
            if int(tmp[ih])==1:
                Nh+=1
        Nk[Nh]+=int(S[ih+1][iw])
        Nk0[Nh]+=int(S[ih+1][iw])
        if K<max(Nk):
            Nw+=1
            Nk=Nk0
        elif K<max(Nk0):
            Nh=H-1
            Nw=W-1
            break
    result=min(result,Nh+Nw)
print(result)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

stack=deque([str(1),str(0)])
result=H-1+W-1
while stack:# O(2^H)
    edge=stack.pop()
    if len(edge)<H-1:
        stack.append(edge+str(1))
        stack.append(edge+str(0))
    else:
        ii=0
        for i in range(H-1):
            ii+=int(edge[i])
        Nk=[0]*(ii+1)
        Nw=0
        for iw in range(W):# O(W)
            Nh=0
            Nk0=[0]*(ii+1)
            for ih in range(H-1):# O(H)
                if int(edge[ih])==0:
                    Nk[Nh]+=int(S[ih][iw])
                    Nk0[Nh]+=int(S[ih][iw])
                else:
                    Nk[Nh]+=int(S[ih][iw])
                    Nk0[Nh]+=int(S[ih][iw])
                    Nh+=1
            Nk[Nh]+=int(S[ih+1][iw])
            Nk0[Nh]+=int(S[ih+1][iw])
            if K<max(Nk):
                Nw+=1
                Nk=Nk0
            elif K<max(Nk0):
                Nh=H-1
                Nw=W-1
                break
        result=min(result,Nh+Nw)
print(result)

Submission status: Time Limit Exceeded

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

stack=[str(1),str(0)]
result=H-1+W-1
while stack:# O(2^H)
    edge=stack[-1]
    stack.pop(-1)
    if len(edge)<H-1:
        stack.append(edge+str(1))
        stack.append(edge+str(0))
    else:
        ii=0
        for i in range(H-1):
            ii+=int(edge[i])
        Nk=[0]*(ii+1)
        Nw=0
        for iw in range(W):# O(W)
            Nh=0
            Nk0=[0]*(ii+1)
            for ih in range(H-1):# O(H)
                if int(edge[ih])==0:
                    Nk[Nh]+=int(S[ih][iw])
                    Nk0[Nh]+=int(S[ih][iw])
                else:
                    Nk[Nh]+=int(S[ih][iw])
                    Nk0[Nh]+=int(S[ih][iw])
                    Nh+=1
            Nk[Nh]+=int(S[ih+1][iw])
            Nk0[Nh]+=int(S[ih+1][iw])
            if K<max(Nk):
                Nw+=1
                Nk=Nk0
            elif K<max(Nk0):
                Nh=H-1
                Nw=W-1
                break
        result=min(result,Nh+Nw)
print(result)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    H,W,K = map(int, readline().split())
    S = [list(map(int, readline().strip())) for j in range(H)]

    white = 0
    for line in S:
        white += sum(line)

    if white <= K:
        print(0)
        exit()

    ans = 10**5
    for i in range(2**(H-1)):
        impossible = False
        x = 0
        ly = bin(i).count("1")
        y_sum = [0]*(ly + 1)
        j = 0
        while j < W:
            m = 0
            y = [0]*(ly + 1)
            for k in range(H):
                if S[k][j] == 1:
                    y[m] += 1
                    if y[m] > K:
                        impossible = True
                        break
                    y_sum[m] += 1
                    if y_sum[m] > K:
                        x += 1
                        y_sum = [0]*(ly + 1)
                        j -= 1
                        break
                if (i >> k) & 1:
                    m += 1
            j += 1
            if impossible:
                x = 10**6
                break

        ans = min(ans, x + ly)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    H,W,K = map(int, readline().split())
    S = [readline().strip() for j in range(H)]

    white = []
    for line in S:
        white.append(line.count("1"))
    white_total = sum(white)

    if white_total <= K:
        print(0)
        exit()

    # 横線の決め方を全探索
    ans = 10**5
    for pattern in range(2**(H-1)):
        # 初期化
        impossible = False
        x = 0
        ly = bin(pattern).count("1")
        y = [[0]*W]*(ly + 1)
        line = 0
        for i in range(H):
            y[line] = [y[line][j] + int(S[i][j]) for j in range(W)]
            if (pattern >> i) & 1:
                line += 1

        # 各列の値を加算していく
        count = [0]*(ly + 1) 
        for col in zip(*y):
            # Kより大きい値を加算する場合は不成立
            if any(a > K for a in col):
                impossible = True
                break
            for i, a in enumerate(col):
                count[i] += a
                # 和がKより大きければカット数を増やす
                if count[i] > K:
                    x += 1
                    count = list(col) 
                    break
        if impossible:
            x = 10**6

        ans = min(ans, x + ly)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import itertools

H, W, K = map(int, input().split())
choco = []
for i in range(H):
    choco.append([int(x) for x in list(input())])

arr = np.array(choco)

# W方向にGREEDY
count = H*W

rows = [x for x in range(1,H)]

for k in range(H):

    # H 方向の切込みの組み合わせ
    combs = list(itertools.combinations(rows,k))

    # H 方向に切り込み
    for comb in combs:

        t = [0]
        t.extend(comb)
        t.append(10)
        t.sort()

        # col = [0,1,W]
        left = 0
        ans = []

        noanswer = False

        for right in range(1,W+1):

            # print(right)
            # print(comb)
            # 全 H で成立するか？
            for j in range(len(t)-1):

                if arr[t[j]:t[j+1],left:right].sum() > K:
                    # どこかで K を超えたら、割る

                    if left == right - 1:
                        # 不成立
                        noanswer = True
                        break

                    left = right - 1                
                    ans.append(left)

        if not noanswer:
            tmp = len(ans) + len(comb)
            count = min(count,tmp)

print(count)

Submission status: Time Limit Exceeded

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

L = [[0]*(W) for _ in range(H)]
for i in range(H):
    for j in range(W):
        if S[i][j] == "1":
            L[i][j] = 1
        
ans = H*W
for i in range(2**(H-1)):
    cnt = 0
    used = [0]*W
    memo = []
    for j in range(H-1):
        if i & (1<<j):
            cnt += 1
            memo.append(j+1)
    memo.append(H)
    num = [0]*(cnt+1)
    for j in range(W):
        idx = 0
        for k in range(H):
            if memo[idx] == k:
                idx += 1
            num[idx] += L[k][j]
        f = False
        for k in range(len(num)):
            if num[k] > K:
                f = True
                break
        if f:
            if j == 0 or used[j-1] == 1:
                cnt = H*W
                break
            used[j-1] = 1
            cnt += 1
            num = [0]*len(num)
            idx = 0
            for k in range(H):
                if memo[idx] == k:
                    idx += 1
                num[idx] += L[k][j]
    ans = min(ans, cnt)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


INF = 1e40


def main():
    # input
    h, w, k = [int(v) for v in input().split(' ')]
    arr = np.zeros((h, w), np.uint8)
    for i in range(h):
        arr[i, :] = np.array([int(c) for c in input()], np.uint8)

    ans = INF
    for i in range(2 ** (h - 1)):
        g = int(0)
        g_arr = np.zeros((h, w), np.int64)
        for j in range(h):
            g_arr[g, :] += arr[j, :]
            if (i >> j) & 1:
                g += 1
        g += 1
        g_arr = g_arr[:g, :]

        count = np.zeros(g, np.int64)
        for j in range(w):
            if np.max(g_arr[:, j]) > k:
                g = INF
                break

            count += g_arr[:, j]
            if np.max(count) > k:
                count = g_arr[:, j]
                g += 1
        ans = min(ans, g - 1)

    print(int(ans))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import copy

def isCont(l):
    return bool(l[-1]+l[-2] <= k)

def cutChoco(l):
    l[-2] += l[-1]
    l.pop(-1)
    

h, w, k = map(int,input().split())
ans = (w-1)*(h-1)+1
s = [[0 for i in range(w)] for j in range(h)]
#ここからコンテスト後
for i in range(h):
    row = input()
    for j in range(w):
        s[i][j] = int(row[j])
#print(s)

for i in range(2**(h-1)):
#    print('----{}----'.format(str(bin(i))))
    t = copy.deepcopy(s)
    div = 0
    for j in range(h-1):
#        print(j, i>>j, (i>>j)&1, div)
        if ((i >> j) & 1) == 1:
            t[j+1-div] = [x + y for (x,y) in zip(t[j-div], t[j+1-div])]
            t.pop(j-div)
            div += 1
    div = h-1-div
#    print(div,t)
    count = [0]*len(t)
    for n in range(w):
#        print('----{}----'.format(n))
        if len(t[0]) == 1:
#            print(div)
            break
        contflag = 1
        for item in t:
#            print(item)
            contflag *= isCont(item)
        if contflag == 1:
            for item in t:
                cutChoco(item)
        else:
            div += 1
            for item in t:
                item.pop(-1)
    ans = min(ans,div)            

print(ans)

'''
綺麗にやろうとしすぎないこと
rowsum = []
s = []
for i in range(h):
    row = input()
    s.append(row)
    wsum = 0
    for item in row:
        wsum += int(item)
    rowsum.append(wsum)
print(s)
print(rowsum)
if sum(rowsum) <= k:
    print(0)
    exit()
'''


'''
colsum = []
for j in range(w):
    csum = 0
    for k in range(h):
        csum += s[k][j]
    colsum.append(csum)

print(max(rowsum))
print(max(colsum))
'''

Submission status: Time Limit Exceeded

Solution code:
h,w,K = map(int,input().split())
sij = [input() for j in range(h)]

num = 2**(h-1)
hon = 10**18

for i in range(num):
    tmp = format(i,'0'+str(h)+'b')
    #print(tmp,tmp,tmp,tmp)
    yoko_hon = sum(list(map(int,tmp)))+1
    blk = [0]*(yoko_hon)
    #blk_num = 0
    tmp_col = 0
    tmp_hon = yoko_hon-1
    flag = True
    ok_flag = True
    for j in range(w):
        tmp_blk = [0]*(yoko_hon)
        blk_num = 0
        for k in range(h):
            if tmp[k] == str(1):
                blk_num += 1
            #print(blk_num,tmp_blk)
            tmp_blk[blk_num] += int(sij[k][j])
            #print(blk[blk_num] , tmp_blk[blk_num],k)
            if blk[blk_num] + tmp_blk[blk_num] > K:
                flag = False
                continue
        
        #print(ok_flag,flag,tmp_blk,blk)
        if flag == False:
            for l in range(yoko_hon):
                if tmp_blk[l] > K:
                    ok_flag = False
                    break
                blk[l] = tmp_blk[l]
            tmp_hon += 1
            tmp_col = 0
            flag = True
        else:
            for l in range(yoko_hon):
                blk[l] += tmp_blk[l]
                tmp_col += 1
        if ok_flag == False:
            break
            
    #print(ok_flag)
    if ok_flag == False:
        ok_flag = True
        continue
    #exit()
    hon = min(tmp_hon,hon)
    
print(hon)