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 itertools

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

# process
ans = H*W

for divr in range(1<<(H-1)):    # 横方向の分割を総当たり
    row = 0
    Sr = [[S[0][i] for i in range(W)]]
    for i in range(1, H):
        if 1&(divr>>i-1):
            row += 1
            Sr.append([S[i][j] for j in range(W)])
        else:
            Sr[row] = [Sr[row][j]+S[i][j] for j in range(W)]

    # 縦方向の分割を加算
    cnt = [0]*(row+1)
    ans_ = row
    flg = True
    for i in range(W):
        for j in range(row+1):
            if Sr[j][i] > K:
                flg = False
                break
            cnt[j] += Sr[j][i]
            if cnt[j] > K:
                ans_ += 1
                cnt = [0]*(row+1)
                for l in range(row+1):
                    cnt[l] += Sr[l][i]
                break

        if ans_ >= ans or not flg:
            break

    if flg:
        ans = min(ans, ans_)

# output
print(ans)

Submission status: Accepted

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

# bit全探索
for i in range(2**(H-1)): 
    start = [0]
    end = []
    for j in range(H-1):
        if i >> j & 1 == 1:
            j += 1
            start.append(j)
            end.append(j)
    end.append(H)
    L = len(end)
    # 横に割った回数
    divcnt = L-1
    # 横に割った区割りごとの白チョコの個数
    wcnt = [0]*L
    # 探索列の横に割った区割りごとの白チョコの個数
    tmp = [0]*L
    for w in range(W):
        # 探索列の直前で縦に割ったか
        flag = False
        for idx in range(L):
            cnt = 0
            for h in range(start[idx],end[idx]):
                cnt += S[h][w]
                if cnt > K: break
            else:
                tmp[idx] = cnt
                wcnt[idx] += cnt
                if wcnt[idx] > K: flag = True
                continue
            break
        else:
            if flag:
                # 縦に割ったらその列から数え直し
                wcnt = tmp[:]
                divcnt += 1
            continue
        break
    else:
        ans = min(ans,divcnt)

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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


def cut(bit):

    """
    横の切れ目の場所をビットで管理する。
    "00...0" <= bit <= "11...1"(H - 1桁)の時に、縦に入れる切れ目の最小回数を返す。
    """

    end = [] # 板チョコを横区切りにした結果、上から何段目で各板チョコのピースが終わるか
    for i in range(H - 1):
        if bit[i] == '1':
            end.append(i)
    end.append(H - 1)
    chocolates = [0] * (len(end))
    #print("end={}".format(end))

    """
    ここまでで板チョコを横に切ったわけだが、こうして分割した横長の部分板チョコを
    上からsection = 0, 1, 2,..., len(end)-1と呼び分けることにする。
    """

    cut = 0
    whites_sum = [0] * len(end) # w列目までの白チョコの累積数をsectionごとに管理。cutが入れば初期化。
    for w in range(W):
        whites = [0] * len(end) # whites[section] = (w列目にある白チョコをsectionごとに保存)
        section = 0 # 現在のsection
        coarse = False # 横切りが荒過ぎて１列に白チョコがK個より多く並んだ場合に探索を打ち切るフラグ

        for h in range(H + 1):
            # sectionを跨いだ場合の処理
            if h > end[section]:
                if whites[section] > K:
                    coarse = True
                    break
                elif whites_sum[section] + whites[section] > K:
                    cut += 1
                    whites_sum = whites
                    whites = [0] * len(end)
                    section += 1
                else:
                    whites_sum[section] += whites[section]
                    section += 1

            # 白チョコカウント
            if h < H and S[h][w] == '1':
                whites[section] += 1

        # coarseフラグが立っていたら-1を返す。
        if coarse:
            return -1
    return cut


ans = 10 ** 10
for h in range(2 ** (H - 1)):
    bit = bin(h)[2:] # "0b..."を除くため
    l = len(bit)
    bit = '0' * (H - 1 - l) + bit # bitの桁数をH - 1にする。
    #print("bit={}".format(bit))

    vertical_cuts = cut(bit)
    if vertical_cuts != -1:
        preans = vertical_cuts + bit.count('1')
        ans = min(ans, preans)
        #print("vertical_cut={}, cut={} -> ans={}".format(vertical_cuts, preans, ans))


print(ans)

Submission status: Accepted

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

def out(l,ll):
    for z in range(ll):
        if l[z] > k:
            return True
    return False

def A(lt, hon):
    noww = [0] * (hon + 1)
    yoko = 0
    for j in range(w):
        kari = [0] * (hon + 1)
        for x in range(hon + 1):
            for y in range(lt[x], lt[x+1]):
                if s[y][j] == "1":
                    kari[x] += 1
        if out(kari, hon+1):
            return h * w
        
        neww = []
        for x in range(hon + 1):
            neww.append(noww[x] + kari[x])
        if out(neww, hon+1):
            yoko += 1
            noww = kari
        else:
            noww = neww
    return yoko + hon

ans = h * w

for i in range(2 ** (h-1)):
    tate = [0]
    honsu = 0
    for j in range(h-1):
        if ((i >> j) & 1):
            tate.append(j + 1)
            honsu += 1
    tate.append(h)
    ans = min(ans, A(tate, honsu))

print(ans)

Submission status: Accepted

Solution code:
import itertools
 
H,W,K=map(int, input().split())
S=[]
for _ in range(H):
  S.append([int(s) for s in input()])
 
ans=2000
for t in itertools.product([0,1],repeat=H-1):
  cnt=t.count(1)
  lst=[[s for s in S[0]]]
  for h in range(H - 1):
    if t[h]==1:
      lst.append(S[h+1])
    else:
      lst[-1]=[lst[-1][i]+S[h+1][i] for i in range(W)]
  L=len(lst)
  R=[0]*L
  for w in range(W):
    if max(lst[i][w] for i in range(L))>K:
      break
    tmp=[R[i]+lst[i][w] for i in range(L)]
    if max(tmp)>K:
      cnt+=1
      R=[lst[i][w] for i in range(L)]
    else:
      R=tmp
  else:
    ans=min(ans,cnt)
print(ans)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def MAP(): return map(int, input().split())
inf = sys.maxsize

h, w, k = MAP()
s = [[int(i) for i in STR()] for _ in range(h)]

ans = inf
for i in range(2 ** (h - 1)): #縦方向の割り方を全探索 O(500)
    hdiv = [1 for _ in range(h)]
    for j in range(h - 1):
        tmp = 2 ** j
        hdiv[j] = 1 if i & tmp else 0
    sh = sum(hdiv)
    tmpans = sh - 1
    wdiv = [0 for _ in range(w - 1)]
    partsum = [0 for _ in range(sh + 1)]
    j = 0
    cnt = 0
    while j < w: #O(2 * 10 ** 4)
        tmp = 0
        idx = 0
        for kk in range(h): #O(10)
            tmp += s[kk][j]
            if hdiv[kk]:
                partsum[idx] += tmp
                tmp = 0
                idx += 1
        flag = True
        for kk in range(sh + 1):
            if partsum[kk] > k:
                tmpans += 1
                partsum = [0 for _ in range(sh + 1)]
                flag = False
        if flag:
            j += 1
            cnt = 0
        else:
            cnt += 1
        if cnt > 2:
            tmpans = inf
            break
    ans = min(ans, tmpans)
print(ans)

Submission status: Accepted

Solution code:
import sys
inf = sys.maxsize

if __name__ == '__main__':
    h, w, k = map(int, sys.stdin.readline().strip().split())
    s = [[int(i) for i in sys.stdin.readline().strip()] for _ in range(h)]
    
    ans = inf
    for i in range(2 ** (h - 1)): #縦方向の割り方を全探索 O(512)
        hdiv = [1 if i & 2 ** j else 0 for j in range(h - 1)]
        hdiv.append(1)
        sh = sum(hdiv)
        tmpans = sh - 1
        partsum = [0 for _ in range(sh)]
        partsum_p = [0 for _ in range(sh)]
        j = 0
        for j in range(w): #O(10 ** 3)
            tmp = 0
            idx = 0
            flag = False
            for kk in range(h): #O(10)
                tmp += s[kk][j]
                if hdiv[kk]:
                    partsum_p[idx] = partsum[idx]
                    partsum[idx] += tmp
                    if partsum[idx] > k and not flag:
                        tmpans += 1
                        flag = True
                    tmp = 0
                    idx += 1
            if flag:
                partsum = [partsum[l] - partsum_p[l] for l in range(sh)]
                partsum_p = [0 for _ in range(sh)]
                for kk in range(sh):
                    if partsum[kk] > k:
                        tmpans = inf
                        break
        ans = min(ans, tmpans)
    print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations

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

map = [None] * H
for i in range(H):
  map[i] = [int(c) for c in input().strip()]


def a(heights=[]) -> int:
  assert len(heights) > 0
  count = len(heights) - 1

  total = {i: (0, 0) for i in range(len(heights))}
  for i in range(W):
    violate = False
    for j, height in enumerate(heights):
      n = 0
      for k in range(height[0], height[1]):
        n += map[k][i]
      if n > K:
        return -1
      total[j] = (total[j][0] + n, n)
      if total[j][0] > K:
        violate = True
    if violate:
      count += 1
      for j in range(len(heights)):
        tmp = total[j][1]
        total[j] = (tmp, tmp)
  return count


patterns = [[(0, H)]]
iterable = [i + 1 for i in range(H - 1)]
for r in range(1, H):
  for c in combinations(iterable, r):
    pattern = []
    last = 0
    for i in c:
      pattern.append((last, i))
      last = i
    pattern.append((last, H))
    patterns.append(pattern)

print(min(filter(lambda x: x >= 0, [a(p) for p in patterns])))

Submission status: Accepted

Solution code:
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:]
    if ans < sp.count("1"):
        continue
    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)

Submission status: Accepted

Solution code:
import itertools
H, W, K = map(int,input().split())
S = [list(map(int,list(input()))) for _ in range(H)]
def check(k):
    if k <= K:
        return(True)
    else:
        return(False)
        
noans = 0
def make_lst(i):
    global noans, lst, havelst
    temp = S[0][i]
    for h in range(H-1):
        if y[h]:
            lst.append(temp)
            temp = S[h+1][i]
        else:
            temp += S[h+1][i]
    lst.append(temp)
    if check(max(lst)):
        havelst = 1
    else:
        noans = 1
#    print(y,i,lst, "makelst")
               
def nocut(i):
    global cutnum, lst, havelst, noans
    prelst = []
    temp = S[0][i]
    if i == W-1:
        if not check(temp):
            noans = 1
    j = 0
    for h in range(H-1):            
        if y[h]:
            lst[j] += temp
            prelst.append(temp)
            j += 1
            temp = S[h+1][i]
        else:
            temp += S[h+1][i]
        if i == W-1:
            if not check(temp):
                noans = 1
    prelst.append(temp)
    lst[-1] += temp
    if check(max(lst)):
#        print(y,i,lst,"nocut", "cutnum = ",cutnum)
        return(True)
    else:
        cutnum += 1
        lst = prelst        
#        print(y,i,lst,"cut","cutnum =",cutnum)
        
                 
ans = float("inf")    
for y in itertools.product((0, 1), repeat=H-1):
    havelst = 0
    lst = []
    cutnum = sum(y)
    for x in range(W):
        if noans:
            break
        if havelst:
            nocut(x)
        else:
            make_lst(x)
#    print(y,cutnum)
    if noans:
        noans = 0
        continue
    else:
        ans = min(cutnum, ans)
print(ans)

Submission status: Accepted

Solution code:
import itertools
H, W, K = map(int,input().split())
S = [list(map(int,list(input()))) for _ in range(H)]
def check(k):
    if k <= K:
        return(True)
    else:
        return(False)
        
noans = 0
def make_lst(i):
    global noans, lst, havelst
    temp = S[0][i]
    for h in range(H-1):
        if y[h]:
            lst.append(temp)
            temp = S[h+1][i]
        else:
            temp += S[h+1][i]
    lst.append(temp)
    if check(max(lst)):
        havelst = 1
    else:
        noans = 1
#    print(y,i,lst, "makelst")
               
def nocut(i):
    global cutnum, lst, havelst, noans
    prelst = []
    temp = S[0][i]
    if i == W-1:
        if not check(temp):
            noans = 1
    j = 0
    for h in range(H-1):            
        if y[h]:
            lst[j] += temp
            prelst.append(temp)
            j += 1
            temp = S[h+1][i]
        else:
            temp += S[h+1][i]
        if i == W-1:
            if not check(temp):
                noans = 1
    prelst.append(temp)
    lst[-1] += temp
    if check(max(lst)):
#        print(y,i,lst,"nocut", "cutnum = ",cutnum)
        return(True)
    else:
        cutnum += 1
        lst = prelst        
#        print(y,i,lst,"cut","cutnum =",cutnum)
        
                 
ans = float("inf")    
for y in itertools.product((0, 1), repeat=H-1):
    havelst = 0
    lst = []
    cutnum = sum(y)
    for x in range(W):
        if noans:
            break
        if havelst:
            nocut(x)
        else:
            make_lst(x)
#    print(y,cutnum)
    if noans:
        noans = 0
        continue
    else:
        ans = min(cutnum, ans)
print(ans)

Submission status: Accepted

Solution code:
#!python3

import itertools


INF = 10 ** 5

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


def solve(w, l):
    n = len(l) + 1
    ans = 0
    if n == 1:
        dp = 0
        for j in range(W):
            x = w[-1][j]
            if x > K:
                return INF
            dp += x
            if dp > K:
                ans += 1
                dp = x
    else:
        dp = [0] * n
        for j in range(W):
            x = [0] * n
            b = False
            for i in range(n):
                if i == 0:
                    x[i] = w[l[i]][j]
                elif i == n - 1:
                    x[i] = w[-1][j] - w[l[-1]][j]
                else:
                    x[i] = w[l[i]][j] - w[l[i-1]][j]
                if x[i] > K:
                    return INF
                dp[i] += x[i]
                if dp[i] > K:
                    b = True
            if b:
                dp = x
                ans += 1
    return ans


def main():
    w = [S[0]]
    for i in range(1, H):
        w.append([w[i-1][j] + S[i][j] for j in range(W)])

    ans = INF
    num_list = [i for i in range(H - 1)]
    for i in range(H):
        comb_list = itertools.combinations(num_list, i)
        for l in comb_list:
            ans = min(ans, i + solve(w, l))

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
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:]
    if ans < sp.count("1"):
        continue
    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)

Submission status: Accepted

Solution code:
#na-
import itertools
H, W, K = map(int,input().split())
S = [list(map(int,list(input()))) for _ in range(H)]
def check(k):
    if k <= K:
        return(True)
    else:
        return(False)
        
noans = 0
def make_lst(i):
    global noans, lst, havelst
    temp = S[0][i]
    for h in range(H-1):
        if y[h]:
            lst.append(temp)
            temp = S[h+1][i]
        else:
            temp += S[h+1][i]
    lst.append(temp)
    if check(max(lst)):
        havelst = 1
    else:
        noans = 1
               
def nocut(i):
    global cutnum, lst, havelst
    prelst = []
    temp = S[0][i]
    j = 0
    for h in range(H-1):
        if y[h]:
            lst[j] += temp
            prelst.append(temp)
            j += 1
            temp = S[h+1][i]
        else:
            temp += S[h+1][i]
    prelst.append(temp)
    lst[-1] += temp
    if check(max(lst)):
        return(True)
    else:
        cutnum += 1
        lst = prelst        
                 
ans = float("inf")
cutlst = []    
for y in itertools.product((0, 1), repeat=H-1):
    havelst = 0
    lst = []
    cutnum = sum(y)
    for x in range(W):
        if noans:
            break
        if havelst:
            nocut(x)
        else:
            make_lst(x)
    if noans==1:
        noans = 0
        continue
    ans = min(cutnum, ans)
print(ans)

Submission status: Accepted

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

choco = [[0] * w for _ in range(h)]

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

ans = float("inf")
for bit in range(1 << (h - 1)):
    idx = [0] * h
    group = 0
    for i in range(h):
        idx[i] = group
        if (bit >> i) & 1:
            group += 1
    group += 1
    array = [[0] * w for _ in range(group)]
    for j in range(w):
        for i in range(h):
            array[idx[i]][j] += choco[i][j]

    cnt = group - 1
    cum = [0] * group
    canAdd = True
    for i in range(w):
        for j in range(group):
            if cum[j] > k:
                canAdd = False

        if ans <= cnt:
            canAdd = False

        if canAdd is False:
            break

        for j in range(group):
            tmp = cum[j] + array[j][i]
            if tmp > k:
                cnt += 1
                for l in range(group):
                    cum[l] = array[l][i]
                break
            cum[j] += array[j][i]

    if canAdd:
        ans = min(ans, cnt)

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
H,W,K = map(int, input().split())
C = np.array([list(map(int, input())) for _ in range(H)])
C = np.hstack([np.zeros([H,1]),C])
np.cumsum(C, axis=1, out=C)
ans = 10**5
for s in range(1<<(H-1)):
	ind = 0
	A = np.zeros([1,W+1])
	for i in range(H):
		if s >> i & 1 == 1:
			A = np.vstack([A,C[ind:i+1,:].sum(axis=0)])
			ind = i+1
	A = np.vstack([A,C[ind:].sum(axis=0)])

	ind = 0
	cnt = 0
	while True:
		cut = 10**3+2
		for a in A:
			cut = min(cut, np.searchsorted(a,a[ind]+K,side='right'))
		if cut == W+1:
			break
		if ind == cut-1:
			cnt = 10**4+2
			break
		else:
			ind = cut-1
		cnt += 1

	h_cnt = 0
	for i in range(H):
		if s >> i & 1 == 1:
			h_cnt += 1

	ans = min(ans, cnt+h_cnt)

print(ans)

Submission status: Accepted

Solution code:
import sys
from bisect import *
from heapq import *
from collections import *
from itertools import *
from functools import *
from math import *

sys.setrecursionlimit(100000000)
input = lambda: sys.stdin.readline().rstrip()

H, W, K = map(int, input().split())
S = [input() for _ in range(H)]
mi = None

def _max(iterable):
    ma = 0
    for i in iterable:
        ma = max(ma, i)
    return ma

for i in range(2 ** (H - 1)):
    # div[j] is true if row j and row j + 1 is divided
    div = [(i & (1 << j)) > 0 for j in range(H - 1)]
    group = [0] * H
    for j in range(H - 1):
        group[j + 1] = group[j] + 1 if div[j] else group[j]
    count = Counter()
    ans = div.count(True)
    ok = True
    for j in range(W):
        tmp = Counter()
        for k in range(H):
            if S[k][j] == '1':
                tmp[group[k]] += 1
        if _max(tmp.values()) > K:
            ok = False
        elif _max((tmp + count).values()) <= K:
            count += tmp
        else:
            count = tmp
            ans += 1
    if ok and (mi is None or ans < mi):
        mi = ans

print(mi)

Submission status: Accepted

Solution code:
from collections import defaultdict
h,w,k = map(int,input().split())

s = [[0 for _ in range(w)] for _ in range(h)]

for i in range(h):
    s[i] = [int(s) for s in list(input())]

#入力終了

def num_to_g(num):
    #10進数から2進数に変換し、縦向きのグループ分けをする(num < 2**(h-1))
    g_index = {}
    index = 1
    for i in range(h+1):
        g_index[i] = index
        bl = (num>>i)%2
        if(bl == 1):
            index += 1
    
    return g_index
    


def get_white(choco_tmp,w,group_num):
    
    for i in range(h):
        if(s[i][w]==1):
            choco_tmp[group_num[i]] += 1
    
    return choco_tmp


def greedy(num):
    div = num_to_g(i)
    res = max(div.values())-1
    choco = defaultdict(int)
    for j in range(w):
        choco = get_white(choco,j,div)
        
        if any(c>k for c in choco.values()):
            choco = defaultdict(int)
            choco = get_white(choco,j,div)
            
            if any(c>k for c in choco.values()):
                return 10**9 + 1
            else:
                res += 1
       
    return res        
            
                
        
#print(greedy(2))

mx = 2**(h-1)                
ans = h+w-1
for i in range(mx):
    ans = min(ans,greedy(i))

print(ans)

Submission status: Accepted

Solution code:
from itertools import product

INF = float("inf")

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

T = [t for t in zip(*S)]
if sum(map(sum, T)) <= K:
    print(0)
    quit()

ans = INF
for P in product([0, 1], repeat=H - 1):
    cnt = sum(P)
    if cnt >= ans:
        continue

    II = [[0]]
    for i, p in enumerate(P, 1):
        if p:
            II.append([])
        II[-1].append(i)

    A = [0] * len(II)
    for t in T:
        for i, I in enumerate(II):
            A[i] += sum(t[x] for x in I)

        if any(a > K for a in A):
            cnt += 1
            if cnt >= ans:
                break

            A = [sum(t[x] for x in I) for I in II]
            if any(a > K for a in A):
              cnt = INF
              break

    ans = min(ans, cnt)

print(ans)

Submission status: Accepted

Solution code:
from itertools import product

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

T = [t for t in zip(*S)]
if sum(map(sum, T)) <= K:
    print(0)
    quit()

ans = float("inf")
for P in product([0, 1], repeat=H - 1):
    cnt = sum(P)
    if cnt >= ans:
        continue

    II = [[0]]
    for i, p in enumerate(P, 1):
        if p:
            II.append([])
        II[-1].append(i)

    A = [0] * len(II)
    for t in T:
        for i, I in enumerate(II):
            A[i] += sum(t[x] for x in I)

        if any(a > K for a in A):
            cnt += 1
            if cnt >= ans:
                break

            A = [sum(t[x] for x in I) for I in II]
            if any(a > K for a in A):
              cnt = 1 + ans
              break

    ans = min(ans, cnt)

print(ans)

Submission status: Accepted

Solution code:
import copy

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

# 最終的に出力する操作回数の最小値
ans = h + w - 2

for i in range(2 ** (h-1)):
    # bit全探索によるcutの仕方
    cutIdx = [0] * (h-1)
    for j in range(h-1):
        cutIdx[j] = (i >> j) & 1
    #print('cI : ', cutIdx)

    # cutする場所を示したリスト
    div = []
    cut_row_begin, cut_row_end = 0, 1
    for j in range(h-1):
        if cutIdx[j] == 0:
            # cutしない
            cut_row_end += 1
        else:
            # cutする
            div.append((cut_row_begin, cut_row_end))
            cut_row_begin = cut_row_end
            cut_row_end += 1
    div.append((cut_row_begin, cut_row_end))
    #print('div: ', div)

    # 既にここまででcutされている回数
    cnt = sum(cutIdx)
    #print(cnt)

    # divごとのホワイトチョコの数をカウント
    whiteCnt = [0] * len(div)

    # まずは1列目をチェック
    for a in range(len(div)):
        cal = 0
        for b in range(div[a][0], div[a][1]):
            cal += s[b][0]
        whiteCnt[a] = cal
    #print('wC : ', whiteCnt)

    # もしこの時点でwhiteCntの要素でkを超えるものがあるとき
    # その横の切り方は不可能なのでbreak
    if max(whiteCnt) > k:
        continue

    # Wが1ならそこで終わり
    if w == 1:
        ans = min(ans, cnt)

    # 次行のホワイトチョコ数を保持
    search = [0] * len(div)

    # 2列目以降を同様にチェックしていく
    for a in range(1, w):
        # その次行のホワイトチョコの数
        for b in range(len(div)):
            cal = 0
            for c in range(div[b][0], div[b][1]):
                cal += s[c][a]
            search[b] = cal

        # その行単体でmax値とkを比べる
        # オーバーしていればcut不可
        if max(search) > k:
            break

        # greedy
        for b in range(len(div)):
            if whiteCnt[b] + search[b] > k:
                # cut対象
                cnt += 1
                whiteCnt = copy.copy(search)
                break
            else:
                whiteCnt[b] += search[b]
    #print('cnt: ', cnt)
    ans = min(ans, cnt)

print(ans)

Submission status: Accepted

Solution code:
h,w,k=map(int,input().split())
ans=10**9
choco=[list(input()) for i in range(h)]
sumL=[[0 for i in range(w+1)] for j in range(h+1)]
for i in range(h):
    for j in range(w):
        sumL[i][j]=sumL[i-1][j]+sumL[i][j-1]-sumL[i-1][j-1]+int(choco[i][j])
for stat in range(2**(h-1)):
    cnt=0;previous=-1
    flg=0
    cut=format(stat,"b").zfill(h-1)
    cutl=[]
    for hi in range(h-1):
        if cut[hi]=="1":
            cutl.append(hi)
            cnt+=1
    cutl.append(h-1)
    cutl.append(-1)
    for yoko in range(w):
        for seg in range(len(cutl)):
            if sumL[cutl[seg]][yoko]-sumL[cutl[seg]][previous]-sumL[cutl[seg-1]][yoko]+sumL[cutl[seg-1]][previous]>k and yoko-previous<=1:flg=1
            elif sumL[cutl[seg]][yoko]-sumL[cutl[seg]][previous]-sumL[cutl[seg-1]][yoko]+sumL[cutl[seg-1]][previous]>k:previous=yoko-1;cnt+=1
            
    if not flg and cnt < ans:ans=cnt
    
print(ans)

Submission status: Accepted

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

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

for i in range(2**(H-1)):
    cut = 0

    yoko = [choco[0]]
    for j in range(H-1):
        if (i>>j) & 1 == 1:
            # 折った
            cut += 1
            yoko.append(choco[j+1])
        else:
            # 折らない -> まとめる
            yoko[-1] = [a + b for a, b in zip(yoko[-1], choco[j+1])]

    count = [yoko[i][0] for i in range(cut+1)]

    if max(count) > K:
        continue

    for x in range(1, W):
        now_count = [yoko[y][x] for y in range(len(count))]
        next_count = [a + b for a, b in zip(now_count, count)]
        if max(next_count) > K:
            # 折る
            count = now_count
            cut += 1
        else:
            # 折らない
            count = next_count

    ans = min(ans, cut)

print(ans)

Submission status: Accepted

Solution code:
from collections import *
from heapq import *
from itertools import *
from fractions import gcd
import sys
from decimal import *
import copy
input=lambda :sys.stdin.readline().rstrip()


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

value=H+W-1
if H==1:
    count=0
    countL=0
    w=0
    while w<W:
        if S[0][w]=="1":
            count+=1
        if count>K:
            countL+=1
            count=0
        else:
            w+=1
    print(countL)
else:
    for i in range(2**(H-1)):
        lst=[i>>m&1 for m in range(H-1)]#0なら線がある
        count=[0 for i in range(lst.count(0)+1)]
        count_zero=copy.copy(count)
        idx={}
        c=0
        for h in range(H-1):
            idx[h]=c
            if lst[h]==0:
                c+=1
        idx[H-1]=c
        flag=0
        w=0
        pre_w=0
        countL=lst.count(0)
        while w<W:
            for h in range(H):

                if S[h][w]=="1":
                    count[idx[h]]+=1
            if max(count)>K:
                if pre_w==w:
                    flag=1
                    break

                pre_w=w
                countL+=1
                count=copy.copy(count_zero)
            else:
                w+=1

        if not flag:
            value=min(value,countL)
    print(value)

Submission status: Accepted

Solution code:
from itertools import product

h, w, k = list(map(int, input().split()))
s = [list(map(int, list(input()))) for i in range(h)]
INF = float("inf")
ans = INF
for bits in product([0, 1], repeat=h-1):
    cnt = sum(bits)
    cuts = [0]+[i + 1 for i, x in enumerate(bits) if x == 1]+[h]
    data = [[0]*w for _ in range(len(cuts)-1)]
    for i in range(len(cuts)-1):
        target = s[cuts[i]:cuts[i+1]]
        for tt in target:
            for j, t in enumerate(tt):
                data[i][j] += t
    check = [[0]*(w+1) for _ in range(len(data))]
    flag = False
    for j in range(w):
        if flag:
            continue
        change = False
        for i in range(len(data)):
            if check[i][j] + data[i][j] > k:
                change = True
                break
        if change:
            for i in range(len(data)):
                if data[i][j] <= k:
                    check[i][j+1] = data[i][j]
                else:
                    flag = True
                    break
            cnt += 1
        else:
            for i in range(len(data)):
                check[i][j+1] = check[i][j] + data[i][j]
    if flag:
        continue
    ans = min(ans, cnt)
print(ans)