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:
from itertools import product


def makelist(BIT):
    LIST, tmp = [], s[0]
    for si, bi in zip(s[1:], BIT):
        if bi == 1:
            LIST.append(tmp)
            tmp = si[:]
        elif bi == 0:
            tmp = [t + sij for t, sij in zip(tmp, si)]
    else:
        LIST.append(tmp)
    return LIST


def solve(LIST):
    COST, cnt = 0, [li[0] for li in LIST]
    if any(num > k for num in cnt):
        return h * w
    for j in range(1, w):
        tmp = [t + li[j] for t, li in zip(cnt, LIST)]
        if any(num > k for num in tmp):
            COST += 1
            cnt = [li[j] for li in LIST]
        else:
            cnt = tmp[:]
    return COST


h, w, k = map(int, input().split())
s = [[int(sij) for sij in input()] for _ in range(h)]

ans = h * w
for bit in product([0, 1], repeat=(h - 1)):
    numlist = makelist(bit)
    ans = min(ans, solve(numlist) + sum(bit))
print(ans)

Submission status: Accepted

Solution code:
from itertools import product


def makelist(BIT):
    LIST, tmp = [], s[0]
    for si, bi in zip(s[1:], BIT):
        if bi == 1:
            LIST.append(tmp)
            tmp = si
        elif bi == 0:
            tmp = [t + sij for t, sij in zip(tmp, si)]
    else:
        LIST.append(tmp)
    return LIST


def solve(LIST):
    COST, cnt = 0, [li[0] for li in LIST]
    if any(num > k for num in cnt):
        return h * w
    for j in range(1, w):
        tmp = [t + li[j] for t, li in zip(cnt, LIST)]
        if any(num > k for num in tmp):
            COST += 1
            cnt = [li[j] for li in LIST]
        else:
            cnt = tmp[:]
    return COST


h, w, k = map(int, input().split())
s = [[int(sij) for sij in input()] for _ in range(h)]

ans = h * w
for bit in product([0, 1], repeat=(h - 1)):
    numlist = makelist(bit)
    ans = min(ans, solve(numlist) + sum(bit))
print(ans)

Submission status: Accepted

Solution code:
from itertools import product


def makelist(BIT):
    LIST, tmp = [], s[0]
    for si, bi in zip(s[1:], BIT):
        if bi == 1:
            LIST.append(tmp)
            tmp = si
        elif bi == 0:
            tmp = [t + sij for t, sij in zip(tmp, si)]
    else:
        LIST.append(tmp)
    return LIST


def solve(LIST):
    CNT, tmp = 0, [li[0] for li in LIST]
    if any(num > k for num in tmp):
        return h * w
    for j in range(1, w):
        cal = [t + li[j] for t, li in zip(tmp, LIST)]
        if any(num > k for num in cal):
            CNT += 1
            tmp = [li[j] for li in LIST]
        else:
            tmp = cal[:]
    return CNT


h, w, k = map(int, input().split())
s = [[int(sij) for sij in input()] for _ in range(h)]

ans = h * w
for bit in product([0, 1], repeat=(h - 1)):
    numlist = makelist(bit)
    ans = min(ans, solve(numlist) + sum(bit))
print(ans)

Submission status: Accepted

Solution code:
from itertools import product


def makelist(BIT):
    LIST, tmp = [], s[0]
    for i, bi in enumerate(BIT, 1):
        if bi == 1:
            LIST.append(tmp)
            tmp = s[i]
        elif bi == 0:
            tmp = [t + sij for t, sij in zip(tmp, s[i])]
    else:
        LIST.append(tmp)
    return LIST


def solve(LIST):
    CNT, tmp = 0, [li[0] for li in LIST]
    if any(num > k for num in tmp):
        return h * w
    for j in range(1, w):
        cal = [t + li[j] for t, li in zip(tmp, LIST)]
        if any(num > k for num in cal):
            CNT += 1
            tmp = [li[j] for li in LIST]
        else:
            tmp = cal
    return CNT


h, w, k = map(int, input().split())
s = [[int(sij) for sij in input()] for _ in range(h)]

ans = h * w
for bit in product([0, 1], repeat=(h - 1)):
    numlist = makelist(bit)
    ans = min(ans, solve(numlist) + sum(bit))
print(ans)

Submission status: Accepted

Solution code:
from itertools import product


def makelist(BIT):
    LIST, tmp = [], s[0]
    for i, bi in enumerate(BIT, 1):
        if bi == 1:
            LIST.append(tmp)
            tmp = s[i]
        elif bi == 0:
            tmp = [p + q for p, q in zip(tmp, s[i])]
    else:
        LIST.append(tmp)
    return LIST


def solve(LIST):
    CNT, tmp = 0, [l[0] for l in LIST]
    if any(num > k for num in tmp):
        return h * w
    for i in range(1, w):
        cal = [tmp[j] + LIST[j][i] for j in range(len(LIST))]
        if any(num > k for num in cal):
            CNT += 1
            tmp = [l[i] for l in LIST]
        else:
            tmp = cal
    return CNT


h, w, k = map(int, input().split())
s = [[int(sij) for sij in input()] for _ in range(h)]

ans = h * w
for bit in product([0, 1], repeat=(h - 1)):
    numlist = makelist(bit)
    ans = min(ans, solve(numlist) + sum(bit))
print(ans)

Submission status: Accepted

Solution code:
def numba_compile(numba_config):
    import os, sys
    if sys.argv[-1] == "ONLINE_JUDGE":
        from numba import njit
        from numba.pycc import CC
        cc = CC("my_module")
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature)(func)
            cc.export(func.__name__, signature)(func)
        cc.compile()
        exit()
    elif os.name == "posix":
        exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
        for func, _ in numba_config:
            globals()[func.__name__] = vars()[func.__name__]
    else:
        from numba import njit
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature, cache=True)(func)
        print("compiled!", file=sys.stderr)

import numpy as np

def solve(H, W, K, S):
    ans = 1<<60
    for s in range(1<<H-1):
        an = 0
        f = True
        mapping = np.zeros(H, dtype=np.int64)
        for i in range(H-1):
            if s>>i&1:
                an += 1
                mapping[i+1] = mapping[i]+1
            else:
                mapping[i+1] = mapping[i]
        if an >= ans:
            continue
        Cnt = np.zeros(mapping[-1]+1, dtype=np.int64)
        for x in range(W):
            for y in range(H):
                m = mapping[y]
                c = S[y, x]
                Cnt[m] += c
            if (Cnt > K).any():
                Cnt[:] = 0
                an += 1
                if an >= ans:
                    f = False
                    break
                for y in range(H):
                    m = mapping[y]
                    c = S[y, x]
                    Cnt[m] += c
                if (Cnt > K).any():
                    f = False
                    break
            if not f:
                break
        if f:
            ans = an
    return ans

numba_compile([
    [solve, "i8(i8,i8,i8,i8[:,:])"],
])

def main():
    H, W, K = map(int, input().split())
    S = np.empty((H, W), dtype=np.int64)
    for y in range(H):
        S[y] = np.array(list(input()), dtype=np.int64)
    ans = solve(H, W, K, S)
    print(ans)

main()

Submission status: Accepted

Solution code:
h,w,kk=list(map(int,input().split()))
s=[list(map(int,list(input()))) for i in range(h)]
l=[]
for i in range(2**(h-1)):
  ll=[0]
  for j in range(h-1):
    if i & 2**j:
      ll.append(ll[-1]+1)
    else:
      ll.append(ll[-1])
  l.append(ll)

mc=w+h
for i in l:
  c=[0 for i in range(h)]
  cc=0
  f=1
  #print(i,0)
  for j in range(w):
    #print(c)
    ff=0
    for k in range(h):
      c[i[k]]+=s[k][j]
    for k in range(h):
      if c[k]>kk:
        ff=1
        break
    if ff:
      cc+=1
      c=[0 for i in range(h)]
      for k in range(h):
        c[i[k]]+=s[k][j]
      for k in range(h):
        if c[k]>kk:
          f=1
      if f:
        cc=w+h
        #print(c)
        break
    f=0
  #print(cc)
  if mc>cc+len(set(i))-1:
    mc=cc+len(set(i))-1
print(mc)

Submission status: Accepted

Solution code:

def main():
    H,W,K=map(int,input().split())

    S=[]
    for i in range(H):
        col=list(map(int,list(input())))
        S.append(col)
    CumulativeS=[[S[i][0]] for i in range(H)]
    for i in range(len(S)):
        for j in range(1,len(S[i])):
            CumulativeS[i].append(CumulativeS[i][j-1]+S[i][j])
    for i in range(1,len(S)):
        for j in range(len(S[i])):
            CumulativeS[i][j]+=CumulativeS[i-1][j]
    all_bit=1<<H-1
    res=10000
    for bit in range(all_bit):
        wide_bound=[]
        for i in range(H-1):
            if (bit & (1<<i))!=0:
                wide_bound.append(i)
        res_=len(wide_bound)
        high_bound=[]
        high_flag=0
        for i in range(W):
            if len(high_bound)==0:
                for b in range(len(wide_bound)):
                    if b==0:
                        white_chocolate=CumulativeS[wide_bound[b]][i]
                    else:
                        white_chocolate=CumulativeS[wide_bound[b]][i]-CumulativeS[wide_bound[b-1]][i]

                    if white_chocolate>K:
                        if i-1<0:
                            high_flag=1
                            break
                        high_bound.append(i-1)
                        break
                    if b==len(wide_bound)-1:
                        white_chocolate=CumulativeS[H-1][i]-CumulativeS[wide_bound[b]][i]
                        if white_chocolate > K:
                            if i-1<0:
                                high_flag=1
                                break
                            high_bound.append(i - 1)


                if high_flag==1:
                    break

                if len(wide_bound)==0:
                    white_chocolate = CumulativeS[H - 1][i]
                    if white_chocolate>K:
                        if i-1<0:
                            high_flag=1
                            break
                        high_bound.append(i-1)

            else:
                for b in range(len(wide_bound)):
                    if b == 0:
                        white_chocolate = CumulativeS[wide_bound[b]][i]-CumulativeS[wide_bound[b]][high_bound[len(high_bound)-1]]
                    else:
                        white_chocolate = CumulativeS[wide_bound[b]][i] - CumulativeS[wide_bound[b - 1]][i]-CumulativeS[wide_bound[b]][high_bound[len(high_bound)-1]]+CumulativeS[wide_bound[b-1]][high_bound[len(high_bound)-1]]
                    if white_chocolate>K:
                        if i-1<0:
                            high_flag=1
                            break
                        high_bound.append(i-1)
                        break
                    if b == len(wide_bound) - 1:
                        white_chocolate = CumulativeS[H - 1][i] - CumulativeS[wide_bound[b]][i]-CumulativeS[H-1][high_bound[len(high_bound)-1]]+CumulativeS[wide_bound[b]][high_bound[len(high_bound)-1]]
                        if white_chocolate>K:
                            if i-1<0:
                                high_flag=1
                                break
                            high_bound.append(i-1)

                if high_flag==1:
                    break

                if len(wide_bound)==0:
                    white_chocolate = CumulativeS[H - 1][W - 1]-CumulativeS[H-1][high_bound[len(high_bound)-1]]
                    if white_chocolate>K:
                        if i-1<0:
                            high_flag=1
                            break

                        high_bound.append(i-1)
        res_+=len(high_bound)

        if res_<res and high_flag==0:
            res=res_

    print(res)

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
import itertools
H, W, K = [int(_) for _ in input().split()]
S = np.zeros((H + 1, W + 1), dtype=int)
S[1:, 1:] = [[int(_) for _ in input()] for _ in range(H)]
cum = S.cumsum(axis=0).cumsum(axis=1)
# print(cum)

ans = 10**10
for bs in itertools.product([True, False], repeat=H - 1):
    bs = [True] + list(bs) + [True]
#     print(bs)
    idxs = []
    for i, b in enumerate(bs):
        if b:
            idxs += [i]
    cum2 = np.array([cum[i2] - cum[i1] for i1, i2 in zip(idxs, idxs[1:])])
    i = 0
    cnt = sum(bs) - 3
    while i < W:
        di = min(
            np.searchsorted(c[i + 1:] - c[i], K, side='right') for c in cum2)
        if di == 0:
            cnt = 10**10
            break
        i += di
        cnt += 1
    ans = min(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/python3
import sys
input = lambda: sys.stdin.readline().strip()
h, w, k = [int(x) for x in input().split()]
s = [input() for _ in range(h)]

def add_pieces(pieces, column, ranges):
    global s
    for j in range(len(ranges)):
        L, R = ranges[j]
        pieces[j] += sum(1 for row in range(L, R) if s[row][column] == '1')

def get_ranges(mask):
    global h
    L = 0
    for i in range(h - 1):
        if mask & (1 << i):
            yield L, i + 1
            L = i + 1
    yield L, h

def cost(mask):
    global h, w, k
    ranges = list(get_ranges(mask))
    pieces = [0 for i in range(len(ranges))]
    ans = bin(mask).count('1')
    for column in range(w):
        add_pieces(pieces, column, ranges)
        if any(piece > k for piece in pieces):
            ans += 1
            pieces = [0 for i in range(len(ranges))]
            add_pieces(pieces, column, ranges)
            if any(piece > k for piece in pieces):
                return float('inf')
    return ans

print(min(cost(mask) for mask in range(1 << (h - 1))))

Submission status: Accepted

Solution code:
h, w, k = list(map(int, input().split()))

choco = [list(map(int, list(input()) )) for i in range(h)]

ans = h + w + 1

for h_cut in range(2**(h-1)):
    # 上位ビットが上側。1が切る、0が切らない
    num_cut_yoko = bin(h_cut).count("1") # 立っているビットの個数
    num_cut = num_cut_yoko
    w_last_cut_pos = -1
    valid = True

    count_white = [0] * (num_cut_yoko + 1)
    temp_dict = {}
    idx = 0
    temp_dict[0] = idx
    for i in range(1, h):
        # print('idx', 2 ** (-i+h-1) )
        if h_cut & (2 ** (-i+h-1) ):
            idx += 1
        # idx += h_cut & (2 ** (h-1) - i)
        temp_dict[i] = idx
    # print(temp_dict)

    iw = 0
    while iw < w:

        for ih in range(h):
            count_white[temp_dict[ih]] += choco[ih][iw]
        # print(iw, count_white)

        condition = max(count_white) > k
        if condition:
            if w_last_cut_pos < iw-1:
                # もしそこで切ってkを超えるなら、その手前で切る
                num_cut += 1
                w_last_cut_pos = iw - 1
                count_white = [0] * (num_cut_yoko + 1)
                # print('iw: ', iw, 'last: ', w_last_cut_pos)

            else:
                # 1つしか動かしてないのにk個を超えた場合は、この横方向の切り方で達成不可能なので、次のh_cutに進む
                # このとき切断回数の最小値の更新をしないように注意!
                valid = False
                break
        
        else:
            iw += 1
    
    if valid:
        ans = min(ans, num_cut)
    # print(num_cut)

print(ans)

Submission status: Accepted

Solution code:
h, w, k = list(map(int, input().split()))

choco = [list(map(int, list(input()) )) for i in range(h)]

choco_cumsum = [[0 for i in range(w)] for j in range(h)]

for i in range(h):
    choco_cumsum[i][0] = choco[i][0]
    for j in range(1, w):
        choco_cumsum[i][j] = choco_cumsum[i][j-1] + choco[i][j]

ans = h + w + 1

for h_cut in range(2**(h-1)):
    # 上位ビットが上側。1が切る、0が切らない
    num_cut_init = bin(h_cut).count("1") # 立っているビットの個数
    num_cut = num_cut_init
    w_last_cot_pos = -1
    valid = True

    temp_list = [0] * (num_cut_init + 1)
    temp_dict = {}
    idx = 0
    temp_dict[0] = idx
    for i in range(1, h):
        # print('idx', 2 ** (-i+h-1) )
        if h_cut & (2 ** (-i+h-1) ):
            idx += 1
        # idx += h_cut & (2 ** (h-1) - i)
        temp_dict[i] = idx
    # print(temp_dict)

    iw = 0
    while iw < w:

        for ih in range(h):
            temp_list[temp_dict[ih]] += choco[ih][iw]
        # print(iw, temp_list)

        condition = max(temp_list) > k
        if condition:
            if w_last_cot_pos < iw-1:
                # もしそこで切ってkを超えるなら、その手前で切る
                num_cut += 1
                w_last_cot_pos = iw - 1
                temp_list = [0] * (num_cut_init + 1)
                # print('iw: ', iw, 'last: ', w_last_cot_pos)

            else:
                # 1つしか動かしてない場合は土台無理なので次のh_cutに
                valid = False
                break
        
        else:
            iw += 1
    
    if valid:
        ans = min(ans, num_cut)
    # print(num_cut)

print(ans)

Submission status: Accepted

Solution code:
h, w, k = list(map(int, input().split()))

choco = [list(map(int, list(input()))) for i in range(h)]

ans = h + w + 1

for h_cut in range(2**(h-1)):
    # 上位ビットが上側。1が切る、0が切らない
    num_cut_yoko = bin(h_cut).count("1") # 立っているビットの個数
    num_cut = num_cut_yoko
    w_last_cut_pos = -1
    valid = True

    count_white = [0] * (num_cut_yoko + 1)
    temp_dict = {}
    idx = 0
    temp_dict[0] = idx
    for i in range(1, h):
        # print('idx', 2 ** (-i+h-1) )
        if h_cut & (2 ** (-i+h-1)):
            idx += 1
        # idx += h_cut & (2 ** (h-1) - i)
        temp_dict[i] = idx
    # print(temp_dict)

    iw = 0
    while iw < w:

        for ih in range(h):
            count_white[temp_dict[ih]] += choco[ih][iw]
        # print(iw, count_white)

        condition = max(count_white) > k
        if condition:
            if w_last_cut_pos < iw-1:
                # もしそこで切ってkを超えるなら、その手前で切る
                num_cut += 1
                w_last_cut_pos = iw - 1
                count_white = [0] * (num_cut_yoko + 1)
                # print('iw: ', iw, 'last: ', w_last_cut_pos)

            else:
                # 1つしか動かしてないのに、Kマスを超えてしまった場合は、この横の切り方では達成不可能なので次のh_cutに
                valid = False
                break
        
        else:
            iw += 1
    
    if valid:
        ans = min(ans, num_cut)
    # print(num_cut)

print(ans)

Submission status: Accepted

Solution code:
h, w, k = list(map(int, input().split()))

choco = [list(map(int, list(input()))) for i in range(h)]

choco_cumsum = [[0 for i in range(w)] for j in range(h)]

for i in range(h):
    choco_cumsum[i][0] = choco[i][0]
    for j in range(1, w):
        choco_cumsum[i][j] = choco_cumsum[i][j-1] + choco[i][j]

ans = h + w + 1

for h_cut in range(2**(h-1)):
    # 上位ビットが上側。1が切る、0が切らない
    num_cut_init = bin(h_cut).count("1") # 立っているビットの個数
    num_cut = num_cut_init
    w_last_cut_pos = -1
    valid = True

    count_white = [0] * (num_cut_init + 1)
    temp_dict = {}
    idx = 0
    temp_dict[0] = idx
    for i in range(1, h):
        # print('idx', 2 ** (-i+h-1) )
        if h_cut & (2 ** (-i+h-1) ):
            idx += 1
        # idx += h_cut & (2 ** (h-1) - i)
        temp_dict[i] = idx
    # print(temp_dict)

    iw = 0
    while iw < w:

        for ih in range(h):
            count_white[temp_dict[ih]] += choco[ih][iw]
        # print(iw, count_white)

        condition = max(count_white) > k
        if condition:
            if w_last_cut_pos < iw-1:
                # もしそこで切ってkを超えるなら、その手前で切る
                num_cut += 1
                w_last_cut_pos = iw - 1
                count_white = [0] * (num_cut_init + 1)
                # print('iw: ', iw, 'last: ', w_last_cut_pos)

            else:
                # 1つしか動かしてないのに、Kマスを超えてしまった場合は、この横の切り方では達成不可能なので次のh_cutに
                valid = False
                break
        
        else:
            iw += 1
    
    if valid:
        ans = min(ans, num_cut)
    # print(num_cut)

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

mp = [input() for _ in range(H)]

rlt = 1010

h = deque([[1]])

while h:
  t = h.pop()
  if len(t) == H:
    t.append(1)
    tmp = sum(t) - 2
    bs = tmp
    lst = [0]*H
    j = -1
    for i in range(len(t)-1):
      if t[i] == 1:
        j += 1
      lst[i] = j 
    cnt = [0]*(lst[-1]+1)
    for j in range(W):
      tcnt = [0]*(lst[-1]+1)
      f = 0
      for i in range(H):
        tcnt[lst[i]] += int(mp[i][j])
      for k in range(lst[-1]+1):
        if tcnt[k] > K:
          f = 2
          break
        cnt[k] += tcnt[k]
        if cnt[k] > K:
          f = 1
          break
      if f == 2:
        break
      if f == 1:
        tmp += 1
        for k in range(lst[-1]+1):
          cnt[k] = tcnt[k]
    if f < 2:
      rlt = min(rlt, tmp)
    
  else:
    for i in range(2):
      h.append(t+[i])

print(rlt)

Submission status: Accepted

Solution code:
import sys
import numpy as np
from itertools import combinations_with_replacement,product
def input(): return sys.stdin.readline().rstrip()

def culc(array,k,count):
    array=array.T
    cuts=np.zeros(array.shape[1])
    for i in range(array.shape[0]):
        if any(array[i]>k):
            return 10**6
        elif any(array[i]+cuts>k):
            cuts=array[i]
            count+=1
        else:
            cuts+=array[i]
    return count


def main():
    h,w,k=map(int, input().split())
    choco=np.zeros((h,w))
    for i in range(h):
        choco[i]=list(input())
    ans=10**6
    choco=choco.astype(np.int64)
    for bit in product([0,1],repeat=h-1):
        if sum(bit)>=ans:
            break
        chocos=choco.copy()
        cut=chocos[0].reshape([1,w])
        for i in range(h-1):
            if bit[i]==1:
                cut=np.concatenate([cut,chocos[i+1].reshape([1,w])])
            else:
                cut[-1]+=chocos[i+1]
        ans=min(ans,culc(cut,k,sum(bit)))
    print(ans)


if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys


def resolve(in_):
    H, W, K = map(int, next(in_).split())
    # n_choco = ord(b'0')
    w_choco = ord(b'1')
    S = [[1 if v == w_choco else 0 for v in line.strip()] for line in in_]
    # print(f'{H=} {W=} {K=}')
    # print(S)

    ans = 10000  # > (Hmax - 1) * (Wmax - 1)
    choco = [0] * H
    choco_temp = [0] * H
    for v in range(2 ** (H - 1)):
        # print(f'{v:04b}')
        ans_temp = sum(1 if v & (0b01 << i) else 0 for i in range(H - 1))
        for w in range(W):
            index = 0
            for h in range(H):
                choco_temp[index] += S[h][w]
                if v & (0b01 << h):
                    index += 1
            # print(f'b {choco=} {choco_temp=} {ans_temp=}')
            if all(a + b <= K for a, b in zip(choco, choco_temp[:index + 1])):
                # for i in range(len(choco)):
                for i in range(index + 1):
                    choco[i] += choco_temp[i]
                    choco_temp[i] = 0
            elif max(choco_temp) > K:
                ans_temp = 10000
                break
            else:
                # for i in range(len(choco)):
                for i in range(index + 1):
                    choco[i] = choco_temp[i]
                    choco_temp[i] = 0
                ans_temp += 1
            if ans_temp >= ans:
                break
            # print(f'a {choco=} {choco_temp=} {ans_temp=}')
        # print(f'{v:09b} {choco=} {ans_temp=}')
        ans = min(ans, ans_temp)
        for i in range(len(choco)):
            choco[i] = 0
            choco_temp[i] = 0
  
    return ans


def main():
    ans = resolve(sys.stdin.buffer)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import numpy as np
import numba
from numba import njit
from numba.types import Omitted
i4 = numba.int32
i8 = numba.int64

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit((i8[:, :], i8), cache=True)
def main(S, K):
    H, W = S.shape
    ans = H + W + 100
    for s in range(1 << H - 1):
        cost = 0
        T = S.copy()
        for i in range(H - 1):
            if s & 1 << i:
                T[i + 1] += T[i]
            else:
                cost += 1
        if np.any(T > K):
            continue
        cumsum = np.zeros(H, np.int64)
        for w in range(W):
            if np.any(cumsum + T[:, w] > K):
                cumsum[:] = 0
                cost += 1
            cumsum += T[:, w]
        ans = min(ans, cost)
    return ans

H, W, K = map(int, readline().split())
S = np.empty((H, W), np.int64)
for h in range(H):
    S[h] = np.array(list(readline().rstrip().decode()))

print(main(S, K))

Submission status: Accepted

Solution code:
from itertools import product
h, w, k = map(int, input().split())
s = list()
best_so_far = float('inf')
for _ in range(h):
  line = input()
  s.append(list(map(int, list(line))))
# loop over possible horizontal lines, 2**9=512 possibilities
horizontal_line_choices = product([False, True], repeat=h-1)
for chosen_indices in horizontal_line_choices:
  hyperrow_values = [s[0].copy()]
  for i in range(h-1):
    if chosen_indices[i]:
      hyperrow_values.append(s[i+1].copy())
    else:
      for dw in range(w):
        hyperrow_values[-1][dw] += s[i+1][dw]
  if any(value>k for row in hyperrow_values for value in row):
    continue
  # now got hyperrow_values, do a greedy search on vertical lines
  num_hyperrows = len(hyperrow_values)
  count_cuts = sum(chosen_indices)
  hyperrow_cumulative = [hyperrow_values[r][0] for r in range(num_hyperrows)]
  for j in range(1, w):
    if all(hyperrow_cumulative[r]+hyperrow_values[r][j]<=k for r in range(num_hyperrows)):
      for r in range(num_hyperrows):
        hyperrow_cumulative[r] += hyperrow_values[r][j]
    else:
      count_cuts += 1
      for r in range(num_hyperrows):
        hyperrow_cumulative[r] = hyperrow_values[r][j]
  best_so_far = min(best_so_far, count_cuts)
print(best_so_far)

Submission status: Accepted

Solution code:
from sys import exit
from itertools import product
import numpy as np
HWK,*sss = open(0).read().splitlines()
H,W,K = map(int, HWK.split())
sss = [list(map(int, list(ss))) for ss in sss]
sss = np.cumsum(sss, axis=0)
 
if H == 1 or W == 1:
    print(0--sss[-1][-1]//K)
    exit()
 
ans = float('inf')
for flgs in product([False, True], repeat=H-1):
    cnt = sum(flgs)
    tsss = sss[[*flgs, True]]
    tsss = np.concatenate((tsss[:1], np.diff(tsss, axis=0)), axis=0).T
 
    tmp = 0
    succ = True
    for cur in tsss:
        new = tmp + cur
        if new.max() <= K:
            tmp = new
        else:
            cnt += 1
            if cur.max() > K:
                succ = False
                break
            else:
                tmp = cur
#     print(flgs)
#     print(cnt, ans, tsss)
    if succ:
        ans = min(ans, cnt)
 
print(ans)

Submission status: Accepted

Solution code:
H,W,K=map(int,input().split())
S=[list(map(int,list(input()))) for i in range(H)]
C=[[0] for i in range(H)]
for i in range(H):
  for j in range(W):
    C[i].append(C[i][j]+S[i][j])
def f(b,l,r):
  R=[0]
  for i in range(H):
    R[-1]+=C[i][r+1]-C[i][l]
    if i!=H-1:
      if b&(1<<i):
        R.append(0)
  return max(R)

INF=10**12
P=INF
Q=0
L=0
for x in range(1<<(H-1)):
  Q=bin(x).count('1')
  L=0
  for i in range(W):
    if f(x,L,i)>K:
      Q+=1
      L=i
      if f(x,L,i)>K:
        Q=INF
        break
  P=min(P,Q)
print(P)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
H, W, K = map(int, readline().split())
S = [readline().decode().rstrip() for _ in range(H)]
INF = 10**30
data = [[0]*W for _ in range(H)]
for i in range(H):
    cnt = 0 
    for j in range(W):
        if S[i][j] == '1':
            data[i][j] += 1

ans_cnt = INF   
for bit_H in range(1 << (H-1)):
    cnt = 0
    ans = []
    new_data = []
    for i in range(H-1):
        if (bit_H >> i) & 1:
            ans.append(i)
    ans.append(H-1)
    tmp = [0]*W
    for i in range(H):
        for j in range(W):
            tmp[j] += data[i][j]
        if i in ans:
            new_data.append(tmp)
            tmp = [0]*W
    group = len(new_data)
    cnt += group-1
    white = [0] * group
    flag = True
    for i in range(W):
        diff = [0] * group
        for j in range(group):
            diff[j] += new_data[j][i]
            white[j] += new_data[j][i]
        max_diff = max(diff)
        if max_diff > K:
            flag = False
            break
        max_white = max(white)
        if max_white > K:
            cnt +=1
            white = diff[:]
    if flag:
        ans_cnt = min(ans_cnt,cnt)
print(ans_cnt)

Submission status: Accepted

Solution code:
h,w,k=map(int,input().split())
s=[[int(j) for j in input()] for i in range(h)]
def popcount(x):
    global h
    ret=0
    for i in range(h-1):
        ret+=(x>>i&1)
    return ret
#できない場合は除く
ans=1000000000000000
for i in range(2**(h-1)):
    p=popcount(i)
    div=[0]*(p+1)
    ans_sub=p
    f=False
    for j in range(w):
        now=0
        div[now]+=s[0][j]
        for l in range(h-1):
            if i>>l&1:
                now+=1
            div[now]+=s[l+1][j]
        if all(i<=k for i in div):
            continue
        else:
            div=[0]*(p+1)
            now=0
            div[now]=s[0][j]
            for l in range(h-1):
                if i>>l&1:
                    now+=1
                div[now]+=s[l+1][j]
            ans_sub+=1
            f=any(i>k for i in div)
    if not f:ans=min(ans,ans_sub)
print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import product

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


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

    R = [[0] * (W + 1) for _ in range(H + 1)]
    for h in range(H):
        for w in range(W):
            R[h + 1][w + 1] = R[h][w + 1] + R[h + 1][w] - R[h][w] + int(grid[h][w])

    res = f_inf
    for pattern in product([0, 1], repeat=H-1):
        cut_H = [idx + 1 for idx, p in enumerate(pattern) if p == 1] + [H]
        cnt_cut = sum(pattern)
        left = 0
        right = 1
        flg = 1
        while right <= W:
            if not flg:
                break
            up = 0
            for bottom in cut_H:
                cnt_w = R[bottom][right] - R[bottom][left] - R[up][right] + R[up][left]
                if cnt_w > K:
                    if right - left == 1:
                        flg = False
                    cnt_cut += 1
                    left = right - 1
                    break
                else:
                    up = bottom
            else:
                right += 1
        else:
            res = min(res, cnt_cut)
    print(res)


if __name__ == '__main__':
    resolve()