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:
import sys
import math
from collections import Counter

h, w, k = [int(s) for s in sys.stdin.readline().strip().split()]
s = [''] * h
for i in range(h):
    s[i] = sys.stdin.readline().strip()

# h, w, k = 3, 5, 3
# s = [
#     '11111',
#     '11111',
#     '11111'
# ]

# h, w, k = 10, 1000, 1
# s = ['1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111',
# '1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111',
# '1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111',
# '1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111',
# '1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111',
# '1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111',
# '1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111',
# '1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111',
# '1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111',
# '1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111'
#      ]


ans = float('inf')
for i in range(2 ** h):
    colors = [0]
    cur = 0
    cand = 0
    for div in range(h-1):
        if (i >> div) & 1:
            cur += 1
            colors.append(cur)
            cand += 1
        else:
            colors.append(cur)

    # print('i', i, 'colors', colors)
    impossible = False
    color_count = Counter()
    for j in range(w):
        col_color_count = Counter()
        for row in range(h):
            color = colors[row]
            # print('s', s)
            # print('row', row)
            # print('j', j)
            char = s[row][j]
            if char == '1':
                col_color_count[color] += 1

        has_break = False
        for col in range(cur+1):
            if col_color_count[col] > k:
                impossible = True
                break
            if col_color_count[col] + color_count[col] > k:
                has_break = True
        if impossible:
            break
        if has_break:
            color_count = col_color_count
            cand += 1
        else:
            for col in range(cur+1):
                color_count[col] += col_color_count[col]
    if not impossible:
        ans = min(ans, cand)
print(ans)

Submission status: Accepted

Solution code:

import itertools

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

choco = [input().strip() for h in range(H)]
cs = [[None for _ in range(W)] for _ in range(H)]  # 累積和

for w in range(W):
  now_cs = 0
  for h in range(H):
    now_cs += choco[h][w] == '1'
    cs[h][w] = now_cs

def devide_col(w, d):
  if len(d) == 0:  # 縦分割なし
    return [cs[-1][w]]
  d = sorted(d)
  if len(d) == 1:
    _d = d[0]-1
    return [cs[_d][w], cs[-1][w]-cs[_d][w]]
  
  result = []
  for i in range(len(d)):
    if i == 0:
      result.append(cs[d[0]-1][w])
    else:
      result.append(cs[d[i]-1][w]-cs[d[i-1]-1][w])
  result.append(cs[-1][w]-cs[d[-1]-1][w])
  return result

ans = float('inf')
for n_split in range(H):
  if n_split > ans: continue
  for split_pos in itertools.combinations(range(1,H), n_split):
    # 縦の分割方法が決まった
    # 横は貪欲
    now_ans = 0
    now_state = [0]*(n_split+1)
    for w in range(W):
      next_state = devide_col(w, split_pos)
      # print(w, split_pos, next_state)  # TMP
      if any(s > K for s in next_state):  # この縦分割では無理
        now_ans = float('inf')
        break
      now_state = [n+s for n,s in zip(now_state, next_state)]  # 足してみる
      if any(s > K for s in now_state):  # 分割する
        now_ans += 1
        now_state = next_state
    # print(split_pos, now_ans+n_split)
    ans = min(ans, now_ans+n_split)
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
from itertools import accumulate
from bisect import bisect_right

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def build_grid(H, W, intv, _type, space=True, padding=False):
    # 入力がスペース区切りかどうか
    if space:
        _input = lambda: input().split()
    else:
        _input = lambda: input()
    _list = lambda: list(map(_type, _input()))
    # 余白の有無
    if padding:
        offset = 1
    else:
        offset = 0
    grid = list2d(H+offset*2, W+offset*2, intv)
    for i in range(offset, H+offset):
        row = _list()
        for j in range(offset, W+offset):
            grid[i][j] = row[j-offset]
    return grid

def popcount(i):
    return bin(i).count('1')

H, W, K = MAP()
grid = build_grid(H, W, 0, int, space=0)

ans = INF
for S in range(1<<(H-1)):
    N = popcount(S) + 1
    A = list2d(N, W, 0)
    for w in range(W):
        A[0][w] = grid[0][w]
    h = 0
    for k in range(H-1):
        if S & 1<<k:
            h += 1
        for w in range(W):
            A[h][w] += grid[k+1][w]
    for i in range(N):
        A[i] = [0] + list(accumulate(A[i]))
    cnt = 0
    idx = 1
    while 1:
        nxt = INF
        for i in range(N):
            nxt = min(nxt, bisect_right(A[i], K+A[i][idx-1], lo=idx))
        if idx == nxt:
            cnt = INF
            break
        idx = nxt
        if idx == W+1:
            break
        cnt += 1
    ans = min(ans, N-1+cnt)
print(ans)

Submission status: Accepted

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

def check(Bss):
    L = len(Bss)
    accBs = [0] * L
    numCut = 0
    for i in range(W):
        for j in range(L):
            if Bss[j][i] > K:
                return H*W
            if accBs[j] + Bss[j][i] > K:
                accBs = [0] * L
                numCut += 1
                break
        for j in range(L):
            accBs[j] += Bss[j][i]
    return numCut

ans = H*W
for ptn in range(2**(H-1)):
    Bss = []
    Bs = Ass[0]
    numCut = 0
    for i in range(1, H):
        if (ptn>>(i-1)) & 1:  # 割る
            Bss.append(Bs)
            Bs = Ass[i]
            numCut += 1
        else:  # 割らない
            Bs = [B+A for B, A in zip(Bs, Ass[i])]
    Bss.append(Bs)

    numCut += check(Bss)
    ans = min(ans, numCut)

print(ans)

Submission status: Accepted

Solution code:
def count(x1,y1,x2,y2):
  ret=acum[y2][x2]
  if x1!=0:
    ret-=acum[y2][x1-1]
  if y1!=0:
    ret-=acum[y1-1][x2]
  if x1!=0 and y1!=0:
    ret+=acum[y1-1][x1-1]
  return ret

h,w,k=map(int,input().split())
board=[list(input()) for _ in range(h)]
acum=[[0]*(w+1) for _ in range(h)]
for i in range(h):
  for j in range(w):
    if board[i][j]=='1':
      acum[i][j]+=1
    if i!=0:
      acum[i][j]+=acum[i-1][j]
    if j!=0:
      acum[i][j]+=acum[i][j-1]
    if i!=0 and j!=0:
      acum[i][j]-=acum[i-1][j-1]
    if j==w:
      acum[i][j]=acum[i][j-1]
ans=10**18
for i in range(2**(h-1)):
  hlist=[]
  flag=format(i,'b')
  if len(flag)!=(h-1):
    flag='0'*((h-1)-len(flag))+flag
  for j in range((h-1)):
    if flag[j]=='1':
      hlist.append(j)
  hlist.append(h-1)
  prevx=0
  tmp=len(hlist)
  yoko=tmp-1
  tate=0
  for j in range(w):
    prevy=0
    for l in range(tmp):
      if count(prevx,prevy,j,hlist[l])>k:
        tate+=10**18
      if count(prevx,prevy,j,hlist[l])<=k and count(prevx,prevy,j+1,hlist[l])>k:
        tate+=1
        prevx=j+1
        break
      prevy=hlist[l]+1
  ans=min(ans,yoko+tate)
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    popcnt=lambda bit:bin(bit).count("1")
    h,w,k=MI()
    aa=[[0]+[int(c) for c in SI()] for _ in range(h)]
    aa=np.array(aa,dtype="i8")
    for i in range(h):
        aa[i]=np.cumsum(aa[i])
    #print(aa)
    ans=h+w
    for bit in range(1<<(h-1)):
        s=aa[0].copy()
        sn=popcnt(bit)+1
        ss=np.zeros((sn,w+1),dtype="i8")
        si=0
        for i in range(1,h):
            if bit>>(i-1)&1:
                ss[si]=s
                s=aa[i].copy()
                si+=1
            else:s+=aa[i]
        ss[si]=s
        #print(bin(bit))
        #print(ss)
        #print()
        cnt=popcnt(bit)-1
        j=0
        while j<w:
            cnt+=1
            mn=10**9
            for i in range(sn):
                nj=np.searchsorted(ss[i],ss[i][j]+k,side="right")-1
                mn=min(mn,nj)
            if mn==j:
                cnt=10**9
                break
            j=mn
        ans=min(ans,cnt)
    print(ans)

main()

Submission status: Accepted

Solution code:
def Donyoku(pattern):
    global w,k
    l=len(pattern)
    saisho=0
    now=[0]*l
    tasu=[0]*l
    for yoko in range(w):
        daijobu=True
        for i in range(l):
            hahen=pattern[i]
            tasu[i]=0
            for ha in hahen:
                tasu[i]+=ha[yoko]
            if(now[i]+tasu[i]>k):
                daijobu=False
            if(tasu[i]>k):
                return -1
        if(daijobu):
            for i in range(l):
                now[i]+=tasu[i]
        else:
            saisho+=1
            for i in range(l):
                now[i]=tasu[i]
        #print(now)
    return saisho
                
        


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

choco=[]
for i in range(h):
    s=input()
    temp=[0]*w
    for j in range(w):
        temp[j]=int(s[j])
    choco.append(temp)


if(w==1):
    temp=[]
    for i in range(h):
        temp.append(choco[i][0])
    choco=[temp]
    w=h
    h=1

#print(choco)

ans=10**6
for i in range(2**(h-1)):
    wari=[]
    gen=0
    sude=0
    for j in range(h):
        if((i>>j) & 1):
            wari.append(choco[gen:j+1])
            gen=j+1
            sude+=1
    wari.append(choco[gen:h])
    #print(i,"番目の試行")
    #for wa in wari:
    #    print(wa)
    don=Donyoku(wari)
    ima=sude+don
    #print(ima)
    if(ima<ans and don!=-1):
        ans=ima

if(w==1 and h==1):
    print(0)
else:
    print(ans)

Submission status: Accepted

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

S = [list(map(int, input())) for _ in range(H)]
accS = [[0] * (W + 1) for _ in range(H + 1)]

for h in range(H):
    for w in range(W):
        accS[h + 1][w + 1] = accS[h + 1][w] + accS[h][w + 1] - accS[h][w] + S[h][w]

def isOk(L, left, right):
    for top, bot in zip(L, L[1:]):
        if accS[bot][right] - accS[bot][left] - accS[top][right] + accS[top][left] > K:
            return False
    return True

ans = 10**18

for mask in range(1 << H):
    L = [0] + [d + 1 for d in range(H - 1) if (mask & (1 << d)) > 0] + [H]

    cnt = len(L) - 2
    left = 0
    while left < W:
        if not isOk(L, left, left + 1):
            cnt = 10**18
            break

        right = left + 1
        while right < W and isOk(L, left, right + 1):
            right += 1

        cnt += 1
        left = right

    ans = min(ans, cnt - 1)

print(ans)

Submission status: Accepted

Solution code:
H,W,K  =(map(int,input().split(" "))) #  H × W のグリッド
nums = [list(map(int,list(input())))  for  _ in range(H)]
ruiseki_2d = [ [0] * (W + 1)  for _ in range(H + 1) ] # 0 → 0
for w in range(W):
    for h in range(H):
        ruiseki_2d[h + 1][w + 1] =ruiseki_2d[h + 1][w] + ruiseki_2d[h][w + 1] + nums [h ][w]  - ruiseki_2d[h][w]


# Hの分割は決め打ち
# H =10 → 9箇所の分け目
# Wの分割は必要ならする
ans = 10 ** 10
for i in range(2 ** (H )):
    # print(i)
    cand = 0
    # print("pattern {}: ".format(i), end="")
    cuts = [0] #一番端っこでカット
    for j in range(0,H -1 ):  #
        if ((i >> j) & 1):  # j + 1の箇所でHを切る
            # print(i,j + 1)
            cuts.append(j + 1)
            cand += 1
    cuts.append(H)
    beforeW = 0 #個数が変化するのは beforeW からwの区間とwより右の区間
    for w in range(1,W + 1):
        mi = 10 ** 6
        ss = []
        for i in range(len(cuts) - 1): #広げたら超えてしまっていたら、その一個前で線を引く
            y1 = cuts[i]
            y2 = cuts[i + 1]
            x2  = w
            x1 = beforeW
            s = ruiseki_2d[y2][x2] -ruiseki_2d[y2][x1] -ruiseki_2d[y1][x2] +ruiseki_2d[y1][x1]
            ss.append(s)


        ma = max(ss)
        if ma > K :
            cand += 1
            beforeW = w -1
    ss = []
    for i in range(len(cuts) - 1):  # 広げたら超えてしまっていたら、その一個前で線を引く
        y1 = cuts[i]
        y2 = cuts[i + 1]
        x2 = W
        x1 = beforeW
        s = ruiseki_2d[y2][x2] - ruiseki_2d[y2][x1] - ruiseki_2d[y1][x2] + ruiseki_2d[y1][x1]
        ss.append(s)


    if max(ss) <= K :
        ans = min(cand,ans)
# if ruiseki_2d[-1][-1] <= K:
#     ans = 0
print(ans)

Submission status: Accepted

Solution code:
class CumulativeSum2D:
  def __init__(self,a):
    self.h=len(a)
    self.w=len(a[0])
    self.s=[(self.w+1)*[0]for _ in range(self.h+1)]
    for i in range(self.h):
      for j in range(self.w):
        self.s[i+1][j+1]=self.s[i+1][j]+self.s[i][j+1]-self.s[i][j]+a[i][j]
  def su(self,i1,j1,i2,j2):
    return self.s[i2+1][j2+1]-self.s[i1][j2+1]-self.s[i2+1][j1]+self.s[i1][j1]
  def prin(self):
    for i in self.s:print(i)
h,w,kk=map(int,input().split())
h-=1
b=[list(map(int,list(input())))for _ in range(h+1)]
bs=CumulativeSum2D(b)
ans=h+w-1
for i in range(2**h):
  bi=[-1]+[j for j in range(h)if (1<<j)&i]+[h]
  anss=len(bi)-2
  flag=False
  cut=[0]
  for k in range(w):
    for j in range(len(bi)-1):
      up=bi[j]+1
      down=bi[j+1]
      s=bs.su(up,cut[-1],down,k)
      if s>kk:
        if k==cut[-1]:flag=True
        else:cut.append(k)
        break
    if flag:break
  if flag:continue
  anss+=len(cut)-1
  ans=min(ans,anss)
print(ans)

Submission status: Accepted

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

a = [[1 for i in range(w)] for j in range(h)]

for i in range(h):
    s = input()
    for j in range(w):
        a[i][j] = int(s[j])

best_result = h * w + 1000

for m in range(2 ** (h - 1)):
    mask = m
    num_splits = 0
    splits = []
    i = 0
    while mask > 0:
        if (mask % 2) == 1:
            num_splits += 1
            splits.append(i)
        i += 1
        mask = mask // 2

    #print('mask = ', m, 'splits = ', splits, 'num_splits =', num_splits)

    counts = [0 for j in range(num_splits + 1)]
    current_counts = [0 for j in range(num_splits + 1)]
    result = num_splits

    for j in range(w):
        if result >= best_result:
            break
        split_index = 0
        success = True
        current_counts[0] = 0

        for i in range(h):
            if a[i][j] == 1:
                counts[split_index] += 1
                if counts[split_index] > k:
                    success = False

            current_counts[split_index] += a[i][j]

            if split_index < num_splits and i == splits[split_index]:
                split_index += 1
                current_counts[split_index] = 0

        if not success:
            result += 1
            #print('not success j = ', j, 'result = ', result, 'counts = ', counts)
            fail = False
            for x in range(num_splits + 1):
                if current_counts[x] > k:
                    fail = True
                    break

                counts[x] = current_counts[x]
            if fail: 
                result = best_result + 1
                break
            

    best_result = min(best_result, result)

print(best_result)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
from itertools import accumulate
from bisect import bisect_right

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def build_grid(H, W, intv, _type, space=True, padding=False):
    # 入力がスペース区切りかどうか
    if space:
        _input = lambda: input().split()
    else:
        _input = lambda: input()
    _list = lambda: list(map(_type, _input()))
    # 余白の有無
    if padding:
        offset = 1
    else:
        offset = 0
    grid = list2d(H+offset*2, W+offset*2, intv)
    for i in range(offset, H+offset):
        row = _list()
        for j in range(offset, W+offset):
            grid[i][j] = row[j-offset]
    return grid

def popcount(i):
    return bin(i).count('1')

H, W, K = MAP()
grid = build_grid(H, W, 0, int, space=0)

ans = INF
for S in range(1<<(H-1)):
    N = popcount(S) + 1
    A = list2d(N, W, 0)
    for w in range(W):
        A[0][w] = grid[0][w]
    h = 0
    for k in range(H-1):
        if S & 1<<k:
            h += 1
        for w in range(W):
            A[h][w] += grid[k+1][w]
    for i in range(N):
        A[i] = [0] + list(accumulate(A[i]))
    cnt = 0
    idx = 1
    while 1:
        nxt = INF
        for i in range(N):
            j = idx
            tgt = K + A[i][idx-1]
            while j < W+1 and A[i][j] <= tgt:
                j += 1
            nxt = min(nxt, j)
            # nxt = min(nxt, bisect_right(A[i], K+A[i][idx-1], lo=idx))
        if idx == nxt:
            cnt = INF
            break
        idx = nxt
        if idx == W+1:
            break
        cnt += 1
    ans = min(ans, N-1+cnt)
print(ans)