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: Accepted

Solution code:
# https://atcoder.jp/contests/abc159/submissions/11108540

def main():
    def calc(group):
        ret = max(group)
        ctr = [0] * H
        for c in range(W):
            need_cut = False
            for r, g in enumerate(group):
                ctr[g] += s[r][c]
                if ctr[g] > K:
                    need_cut = True
                    break

            if need_cut:
                ctr = [0] * H
                ret += 1
                for r, g in enumerate(group):
                    ctr[g] += s[r][c]
                    if ctr[g] > K:
                        return H * W
                continue
        return ret

    def gen():
        from itertools import accumulate, product

        for prod in product(range(2), repeat=H - 1):
            group = [0]
            group.extend(accumulate(prod))
            yield calc(group)

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

    ret = min(gen())
    print(ret)


if __name__ == '__main__':
    main()

Submission status: Accepted

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, 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)

Submission status: Accepted

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

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

    ans = 10 ** 9

    for bit in range(1 << (H-1)):
        canSolve = True
        ord = [0] * (H + 1)
        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]
        nums = [0] * (H + 1)
        for w in range(W):
            one = [0] * (H + 1)
            overK = False
            for h in range(H):
                one[ord[h]] += S[h][w]
                nums[ord[h]] += S[h][w]
                if one[ord[h]] > K:
                    canSolve = False
                if nums[ord[h]] > K:
                    overK = True
            if not canSolve:
                break
            if overK:
                N += 1
                nums = one
        if canSolve and ans > N:
            ans = N
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
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 = [0] * (H + 1)
        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]
        nums = [0] * (H + 1)
        for w in range(W):
            one = [0] * (H + 1)
            overK = False
            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:
                    overK = True
            if not canSolve:
                break
            if overK:
                N += 1
                nums = one
        if canSolve and ans > N:
            ans = N
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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]
        nums = defaultdict(int)
        for w in range(W):
            one = defaultdict(int)
            overK = False
            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:
                    overK = True
            if not canSolve:
                break
            if overK:
                N += 1
                nums = one
        if canSolve and ans > N:
            ans = N
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())

choco_array = [[int(s) for s in input()] for _ in range(H)]
# print(choco_array)

ans = 100000

for i in range(1 << (H-1)):
    cut_h = 0
    cut_array = [0] * H
    for h in range(H-1):
        if i >> (h) & 1:
            cut_h += 1
        cut_array[h+1] = cut_h
    # print(cut_array)
    cut_w = 0
    now_count = [0] * (cut_h+1)
    for w in range(W):
        new_count = [0] * (cut_h+1)
        for h in range(H):
            new_count[cut_array[h]] += choco_array[h][w]
        ng_flag = 0
        # print(now_count, new_count)
        for i in range(cut_h+1):
            if new_count[i] > K:
                ng_flag = -1
                break
            if now_count[i] + new_count[i] > K:
                ng_flag = 1
                break
        if ng_flag == -1:
            cut_w = 10000
            break
        if ng_flag == 1:
            cut_w += 1
            for i in range(cut_h+1):
                now_count[i] = new_count[i]
        else:
            for i in range(cut_h+1):
                now_count[i] += new_count[i]
    ans = min(ans, cut_h+cut_w)

print(ans)

Submission status: Accepted

Solution code:
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
def resolve():
    H, W, K = lr()
    S = []
    for i in range(H):
        S.append([int(s) for s in sr()])
    ans = 2000
    idx = [0]*H
    for div in range(1<<(H-1)):
        g = 0
        for i in range(H):
            idx[i] = g
            if div>>i&1:
                g += 1
        g += 1
        c = [[0]*W for i in range(g)]
        for i in range(H):
            for j in range(W):
                c[idx[i]][j] += S[i][j]
        ok = True
        for i in range(g):
            for j in range(W):
                if c[i][j] > K:
                    ok = False
        if not ok:
            continue
        num = g-1
        now = [0]*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]*g
                add(j)
        ans = min(ans, num)
    print(ans)
resolve()

Submission status: Accepted

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)
    tmp = []
    col = 0
    subset.append(100000)
    running_sum = [0 for i in range(len(subset))]    
    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))]
                cur_ans += 1
                break
                
        col += 1                
        if cur_ans >= ans:
          break
    ans = min(ans, cur_ans)
print(ans)

Submission status: Accepted

Solution code:
H,W,K = map(int,input().split())
A = []
for i in range(H):
    b = list(input())
    b.append("0")
    A.append(b)

ans = 10**6
for i in range(2**(H-1)):
    p = "0" + str(H-1)
    bin_list = list(format(i,p+"b"))
    sec = []
    for i in range(H-1):
        if bin_list[i] == "1":
            sec.append(i)
    sec.append(H-1)
    l = len(sec)

    W_start = 0
    k = 0
    while(True):
        H_start = 0
        pross = 10**4
        for i in range(l):
            H_end = sec[i] + 1
            j = W_start
            c = 0
            while(True):
                for t in range(H_start,H_end):
                    if A[t][j] == "1":
                        c += 1
                j += 1
                if c > K or j > W:
                    pross = min(pross,j-W_start)
                    break
            H_start = sec[i] + 1

        k += 1
        W_start += pross-1
        if W_start > W-1 or pross == 1:
            break
    if pross != 1:
        ans = min(ans,k+l-2)

print(ans)

Submission status: Accepted

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を越えないかチェック
    for i, cc in enumerate(curr_count):
        grp_count[i] += cc
        # 越えてたら、grp_countを現在の行に上書き
        if grp_count[i] > k:
            grp_count[:] = curr_count
            return 1
    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: Accepted

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

    # 縦方向に貪欲に割っていく
    rows = [r.tolist() for r in rows]
    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: Accepted

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    S = [input().strip("\n") for _ in range(H)]
    Ans = 10 ** 20
    Wcount = [[0 for _ in range(W + 1)] for _ in range(H + 1)]
    for h in range(H):
        for w in range(W):
            Wcount[h+1][w+1] = Wcount[h][w + 1] + Wcount[h + 1][w] - Wcount[h][w] + int(S[h][w])
        
            
    #print(Wcount)
    Ans = H * W + 1
    for i in range(2 ** (H - 1)):
        B = [0]
        d = i
        Hcount = 0
        for j in range(H - 1):
            if d % 2 == 1:
                B.append(j + 1)
                Hcount += 1
            d //= 2
        B.append(H)
        leftbound = 0
        TotalBound = Hcount
        NG = False
        for w in range(1, W+1):
            for b in range(Hcount + 1):
                if Wcount[B[b+1]][w] - Wcount[B[b+1]][leftbound] - Wcount[B[b]][w] + Wcount[B[b]][leftbound] > K:
                    if leftbound + 1 == w: 
                        NG = True
                    else:
                        TotalBound += 1
                        leftbound = w - 1
                    break
            if NG: break
        else: Ans = min(TotalBound, Ans)
        #print(i, B, TotalBound)
    print(Ans)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

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 pattern in range(2**(H-1)):
        # 初期化
        impossible = False
        x = 0
        ly = bin(pattern).count("1")
        y = [S[0]]
        line = 0
        for i in range(1,H):
            if (pattern >> i-1) & 1:
                line += 1
                y.append(S[i])
            else:
                y[line] = [y[line][j] + S[i][j] for j in range(W)]

        # 各列の値を加算していく
        count = [0]*(ly + 1) 
        for j in range(W):
            for i in range(line+1):
                if y[i][j] > K :
                    impossible = True
                    break

                count[i] += y[i][j]
                if count[i] > K:
                    x += 1
                    for i in range(line+1):
                        count[i] = y[i][j] 
                    break
            if x + ly > ans or impossible:
                impossible = True
                break
        if impossible:
            x = 10**6

        ans = min(ans, x + ly)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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 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] + S[i][j] for j in range(W)]
            if (pattern >> i) & 1:
                line += 1

        # 各列の値を加算していく
        count = [0]*(ly + 1) 
        for j in range(W):
            for i in range(line+1):
                if y[i][j] > K :
                    impossible = True
                    break

                count[i] += y[i][j]
                if count[i] > K:
                    x += 1
                    for i in range(line+1):
                        count[i] = y[i][j] 
                    break
            if x + ly > ans or impossible:
                impossible = True
                break
        if impossible:
            x = 10**6

        ans = min(ans, x + ly)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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 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] + 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 x + ly > ans:
                impossible = True
                break
        if impossible:
            x = 10**6

        ans = min(ans, x + ly)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]

h,w,k=map(int,input().split())
s=[input() for i in range(h)]
# print(s)
ans=float('inf')
for i in range(2**(h-1)):
    tmp=1
    for j in range(h-1):
        if 1 & (i>>j):
            tmp+=1
    lst=[[0]*tmp for j in range(w)]

    for j in range(w):
        now=0
        for l in range(h):
            if s[l][j]=="1":
                lst[j][now]+=1
            if 1 & (i>>l):
                now+=1

    cnt=[0]*tmp
    cutcnt=0
    for j in range(w):
        flag=0
        for l in range(tmp):
            if cnt[l]+lst[j][l]>k:
                flag=1
    
        if flag==0:
            for l in range(tmp):
                cnt[l]+=lst[j][l]
        else:
            cutcnt+=1
            for l in range(tmp):
                cnt[l]=lst[j][l]
                if cnt[l]>k:
                    cutcnt=float('inf')
        # print(cnt)
    ans=min(cutcnt+tmp-1,ans)
    # print(lst)
    # print(cutcnt,tmp-1)
print(ans)

Submission status: Accepted

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 x + ly > ans:
                impossible = True
                break
        if impossible:
            x = 10**6

        ans = min(ans, x + ly)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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-1) + (W-1)


for k in range(H):
    
    # この時点で同じ回数以上切ることが確定なら終了
    if count <= k:
        break

    # H 方向に切り込み
    for comb in itertools.combinations(range(1,H),k):

        # スライスを作っておく
        t = (None,) + comb + (None,)
        s = [slice(t[j],t[j+1],) for j in range(len(t)-1)]
        
        sum_p = [0] * (k+1)
        
        cut = k
        
        for col in zip(*choco):

            # 各ブロック毎の合計を算出
            sum_a = [sum(col[b]) for b in s]
            
            # K を超えるブロックが存在していないか？
            if any(map(K.__lt__, sum_a)):
                # 不成立
                break
            
            # 前まで分割されていないブロックと合わせて、合計を算出
            
            sum_b = [x + y for x,y in zip(sum_p, sum_a)]

            if any(map(K.__lt__, sum_b)):
                cut += 1
                sum_p = sum_a
            else:
                sum_p = sum_b
                
                # 割った位置を記録
        
        else:
            count = min(count,cut)

print(count)

Submission status: Accepted

Solution code:
from itertools import accumulate


def solve(h, w, lim, choco):
    acc = [[0] + list(accumulate(int(c == '1') for c in s)) for s in choco]
    acc = list(zip(*acc))
    acc = [[0] + list(accumulate(s)) for s in acc]
    acc = list(zip(*acc))
    # print(*acc, sep='\n')

    ans = 10 ** 9
    # i:j  h方向の分割
    # k:l  w方向の分割
    for bit in range(1 << (h - 1)):
        k = 1
        tmp = 0
        while k < w:
            # print(bin(bit), k)
            i = 0
            l = w + 1
            sp = bit | 1 << (h - 1)
            while sp:
                b = sp & -sp
                sp ^= b
                j = b.bit_length()
                lt = k
                while lt <= w and acc[j][lt] - acc[j][k - 1] - acc[i][lt] + acc[i][k - 1] <= lim:
                    lt += 1
                if lt == k:
                    break
                l = min(l, lt)
                # print('i,j,k,l', i, j, k, l, lt)
                i = j
            else:
                k = l
                if k <= w:
                    tmp += 1
                continue
            break
        else:
            # print(tmp, bin(bit).count('1'))
            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: Accepted

Solution code:



def solve(choco, cut_pos, k):
    cuts = len(cut_pos) - 2
    blocks = [0] * (len(cut_pos) - 1)

    for col in zip(*choco):
        need_cut = False
        for i, blk in enumerate(zip(cut_pos, cut_pos[1:])):
            s, e = blk
            white = sum(col[s:e])
    
            if white > k:
                return float('inf')

            if blocks[i] + white > k:
                need_cut = True
                break
            else:
                blocks[i] += white

        if need_cut:
            for i, blk in enumerate(zip(cut_pos, cut_pos[1:])):
                s, e = blk
                blocks[i] = sum(col[s:e])

        cuts += need_cut
    # print('cuts:', cuts)
    return cuts


def main():
    h, w, k = map(int, input().split())

    choco = [[int(s) for s in list(input())] for _ in range(h)]
    min_cuts = float('inf')

    for cuts in range(1 << (h-1)):
        cut_pos = [0] + [i+1 for i in range(h-1) if cuts & (1 << i)] + [h]
        min_cuts = min(min_cuts, solve(choco, cut_pos, k))

    print(min_cuts)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from itertools import *
H, W, K = map(int, input().split())
S = [list(map(int, input())) for i in range(H)]
ans = 100000
for p in product([0,1],repeat=H-1):
    tmp_ans = sum(p)
    index = []
    for i,j in enumerate(p):
        if j == 1:
            index.append(i+1)
    count = [0] * (len(index) +1)
    for w in range(W):
        plate = [yoko[w] for yoko in S]
        tmp = [0]*(len(index)+1)
        if index == []:
            tmp[0] = sum(plate)
        else:
            tmp[0] = sum(plate[0:index[0]])
            for itr in range(len(index)):
                if itr == len(index) -1:
                    tmp[itr+1] += sum(plate[index[itr]:])
                else:
                    tmp[itr+1] += sum(plate[index[itr]:index[itr+1]])
        if max(tmp) > K :
            tmp_ans = 11111111111
        tmp_sum = [x+y for (x,y) in zip(count,tmp)]
        if max(tmp_sum) > K:
            tmp_ans +=1
            count = tmp
        else:
            count = tmp_sum
    if tmp_ans < ans:
        ans = tmp_ans

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
# start: 00:47


H,W,K = map(int,input().split())
S = [[0]*W for _ in range(H)]
for i in range(H):
    st = list(input())
    for j,t in enumerate(st):
        S[i][j] = int(t)
#%%

ans = 10**9+7
for i in range(1<<(H-1)):
    res = 0
    tmp = i
    h = [0]*(H-1)
    idx = (H-2)
    while tmp>0:
        if tmp&1:
            h[idx]=1
            res += 1
        idx -= 1
        tmp>>=1
    group = [0]*H
    for j in range(H-1):
        group[j+1] = group[j] + h[j]
    
    L = group[-1]+1
    count = [0]*(L)
    possible = True
    for j in range(W):
        nxt = [0]*(L)
        for k in range(H):
            if S[k][j]:
                nxt[group[k]] += 1
        
        cut = False
        for l in range(L):
            if count[l]+nxt[l]>K:
                cut = True
                break
        
        if cut:
            for l in range(L):
                if nxt[l]>K:
                    possible = False
                    break
                count[l] = nxt[l]
            else:
                res += 1
                continue
            break
            
        else:
            for l in range(L):
                count[l] += nxt[l]
    if possible:
        ans = min(ans,res)
print(ans)

Submission status: Accepted

Solution code:
sel='E'
#A
if sel=='A':
    N,M=map(int,input().split())
    ans=0
    ans+=M*(M-1)//2
    ans+=N*(N-1)//2
    print(ans)

#B
if sel=='B':
    def ispal(s):
        for i in range(len(s)//2+1):
            if s[i]!=s[-(i+1)]:
                return False
        return True

    S=input()
    N=len(S)
    if ispal(S) and ispal(S[:(N-1)//2]) and ispal(S[(N+3)//2-1:]):
        print('Yes')
    else:
        print('No')

#C
if sel=='C':
    L=int(input())
    print((L**3)/27)

#D
if sel=='D':    
    N=int(input())
    A=[int(i) for i in input().split()]
    kin=list(set(A))
    cnt={}
    for k in kin:
        cnt[k]=0
    for a in A:
        cnt[a]+=1
    SUM=0
    for k in kin:
        SUM+=cnt[k]*(cnt[k]-1)//2
    for a in A:
        if cnt[a]>=2:
            print(SUM-cnt[a]+1)
        else:
            print(SUM)
        
#E
if sel=='E':
    def add(in1, in2):
        return [a + b for a, b in zip(in1, in2)]

    def split(ar, k, w):
        a = 0
        if max(max(ar)) > k:
            return -1
        tm = ar[0]
        for i in range(1, w):
            tm = add(tm, ar[i])
            if max(tm) > k:
                a += 1
                tm = ar[i]
        return a        

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

    for i in range(2**(h-1)):
        data = []
        temp = s[0]
        sp = bin(i+2**h)[4:]
        for j in range(1, h):
            if sp[j-1] == "0":
                temp = add(temp, s[j])
            else:
                data.append(temp)
                temp = s[j]
        data.append(temp)
        ans_ = split([list(x) for x in zip(*data)], k, w)
        if ans_ == -1:
            continue
        ans_ += sp.count("1")
        if ans > ans_:
            ans = ans_
    print(ans)



# #F
# if sel=='F':
#     N,S=map(int,input().split())
#     A=[int(i) for i in input().split()]

Submission status: Accepted

Solution code:
h, w, k = map(int, input().split())
s = [list(map(int, input())) for _ in range(h)]
ans = float("inf")

for sep in range(1 << (h-1)):
    g_id = [0] * h
    cur = 0
    for i in range(h-1):
        g_id[i] = cur
        if sep >> i & 1: cur += 1
    g_id[h-1] = cur
    g_num = cur+1

    ng = False
    for i in range(w):
        tmp = [0] * g_num
        for j in range(h): tmp[g_id[j]] += s[j][i]
        if any([x > k for x in tmp]): ng = True; break
    if ng: continue

    res = g_num-1
    
    gs = [0] * g_num
    for i in range(h):
        gs[g_id[i]] += s[i][0]
    
    for i in range(1, w):
        tmp = gs[::]
        for j in range(h):
            tmp[g_id[j]] += s[j][i]
        if any([x > k for x in tmp]):
            res += 1
            gs = [0] * g_num
        for j in range(h): gs[g_id[j]] += s[j][i]

    ans = min(ans, res)

print(ans)

Submission status: Accepted

Solution code:
from itertools import *

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

cut_min = H+W-2

for r_cut in range(H):
  if cut_min <= r_cut:
    continue
  for r_pos in combinations(range(1, H), r_cut):
    r_pos = (None,)+r_pos+(None,)
    r_blocks = [slice(*r_pos[i:i+2]) for i in range(len(r_pos)-1)]
    
    cut = r_cut
    prev_sum = [0] * len(r_blocks)
    for col in zip(*S):
      curr_sum = [sum(col[b]) for b in r_blocks]
      if any(map(K.__lt__, curr_sum)):
        break
      next_sum = [x+y for x,y in zip(prev_sum, curr_sum)]
      if any(map(K.__lt__, next_sum)):
        cut += 1
        if cut_min <= cut:
          break
        prev_sum = curr_sum
      else:
        prev_sum = next_sum
    else:
      cut_min = cut
print(cut_min)