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:
# Problem E - Dividing Chocolate

# input
H, W, K = map(int, input().split())
board = [[0]*W for i in range(H)]
for i in range(H):
    s = list(input())
    for j in range(W):
        board[i][j] = int(s[j])

# initialization
min_divide = 10**15

# pattern search
for i in range(2**(H-1)):
    # bit search
    h_pattern = [0]*(H-1)
    group_count = 1
    h_count = 0
    w_count = 0
    for j in range(H-1):
        if((i>>j)&1):
            h_pattern[j] = 1
            group_count += 1
            h_count += 1

    is_ok = True
    group_sum = [0]*group_count
    for w in range(W):
        cur_count = [0]*group_count
        cur_count_num = 0
        # 列そのものが条件を満たしているかチェック
        for h in range(H):
            if board[h][w]==1:
                cur_count[cur_count_num] += 1

            if cur_count[cur_count_num]>K:
                is_ok = False
                break

            if h<H-1 and h_pattern[h]==1:
                cur_count_num += 1

        if not is_ok:
            break

        # 現在の列をグループカウントに入れる
        is_smaller = True
        if w==0:
            is_smaller = True
        else:
            for c in range(group_count):
                if group_sum[c]+cur_count[c]>K:
                    is_smaller = False
        if is_smaller:
            for c in range(group_count):
                group_sum[c] += cur_count[c]
        else:
            # wで区切る
            for c in range(group_count):
                group_sum[c] = cur_count[c]
            w_count += 1

    if not is_ok:
        is_ok = True
        continue

    # update
    min_divide = min(min_divide, h_count + w_count)

# output
print(min_divide)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
# import math
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product                # product(iter, repeat=n)
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4


def main():
    mod = 1000000007                  # 10^9+7
    inf = float('inf')
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():  return int(input())
    def mi():  return map(int, input().split())
    def mi_0(): return map(lambda x: int(x)-1, input().split())
    def lmi(): return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():  return list(input())
    
    
    h, w, k = mi()
    L = []
    for _ in range(h):
        L.append(list(map(int, li())))
    L_trans = [[None] * h for _ in range(w)]
    for i in range(h):
        for j in range(w):
            L_trans[j][i] = L[i][j]
    d = 2 ** (h-1)
    cost = [float('inf')] * d
    for state in range(d):
        bit_count = bin(state)[2:].count('1')
        separated = [[0] * (bit_count + 1) for _ in range(w)]
        for i in range(w):
            current = 0
            for j in range(h):
                if j >= 1 and 1 << (j-1) & state:
                    current += 1
                if L_trans[i][j]:
                    separated[i][current] += 1
        previous = [0] * (bit_count + 1)
        cnt = 0
        # print(separated)
        for i in range(w):
            if any(map(lambda x: x > k, separated[i])):
                break
            if all(map(lambda x: x <= k, [elm + previous[ind] for ind, elm in enumerate(separated[i])])):
                # print(f"just add: {previous} {separated[i]}")
                for ind, elm in enumerate(separated[i]):
                    previous[ind] += elm    # 追加
            else:
                cnt += 1
                # print(f"count up: {previous} {separated[i]}")
                for ind, elm in enumerate(separated[i]):
                    previous[ind] = elm    # 上書き
        else:
            cost[state] = bit_count + cnt
    # print(cost)
    print(min(cost))
                

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
H,W,K = map(int,input().split())
S = [0] * H
for i in range(H):
    S[i] = input()

INF = H + W - 2

def bi(x):
    global H
    o = [0]*(H-1)
    i = 0
    while x != 0:
        o[i] = x % 2
        i += 1
        x //= 2
    return o

def hoge(n):
    global K
    b = bi(n)
    d = defaultdict(set)
    j = 0
    for i in range(H):
        d[j].add(i)
        if i == H - 1:
            break
        if b[i]:
            j += 1
    dlen = len(d)
    T = [0]*dlen
    for k,V in d.items():
        T[k] = [0]*W
        for i in range(W):
            for v in V:
                T[k][i] += int(S[v][i])
            if T[k][i] > K:
                return INF
    ans = dlen - 1
    U = [T[x][0] for x in range(dlen)]
    for i in range(1,W):
        flag = 0
        for k in range(dlen):
            U[k] += T[k][i]
            if U[k] > K:
                flag = 1
        if flag == 1:
            ans += 1
            for k in range(dlen):
                U[k] = T[k][i]
    return ans

ANS = INF
for i in range(2**(H-1)):
    ANS = min(ANS,hoge(i))

print(ANS)

Submission status: Accepted

Solution code:
from itertools import product

H, W, K = map(int, input().split())
l = [[0]*W for _ in range(H)]
for i in range(H):
    for j, s in enumerate(input()):
        if s=="1":
            l[i][j] = 1

dp = [[0]*(W+1) for _ in range(H+1)]
for i in range(1, H+1):
    for j in range(1, W+1):
        dp[i][j] = l[i-1][j-1]+dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]

f=lambda lx,ly,rx,ry:dp[ry][rx]-dp[ly-1][rx]-dp[ry][lx-1]+dp[ly-1][lx-1]

ans = H*W
for i in product(range(2), repeat=H-1):
    candidate = []
    if any(i):
        start = 1
        for j, k in enumerate(i, start=1):
            if k:
                candidate.append((start, j))
                start = j+1
        candidate.append((start, H))
    else:
        candidate.append((1, H))
    
    q = [1]
    cutx = 0

    while q:
        s = q.pop()
        for t in range(s, W+1)[::-1]:
            if all(f(s, j, t, k)<=K for j, k in candidate):
                if t!=W:
                    q.append(t+1)
                    cutx += 1
                break
        else:
            cutx = H*W
    v = cutx+sum(i)
    ans = min(ans, v)

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
H, W, K = map(int, input().split())  # H行, W列, 1エリア内にK個以下のホワイトチョコレートにしたい
gridgraph = [list(input()) for _ in range(H)]
ans = 10**10
# Hに関するビット全探索を行うイメージ
for i in range(1 << (H-1)):
    bits = []
    for j in range(H-1):
        bits.append((i >> j) & 1)  # iのjビット目が立っているかどうかを調べる
    separate_row = True
    cnt = sum(bits)  # 横に切る場所, 最終的に ans = min(ans, cnt)をする
    all_accumulation = defaultdict(int)
    # その列を区切るか区切らないかを貪欲法で判断していく
    for j in range(W):
        now_area = 0
        now_accumulation = defaultdict(int)
        for i in range(H):
            # iが変動していく
            # 今見ている列のものだけも、数えておく必要がある
            now_accumulation[now_area] += int(gridgraph[i][j])
            if i != H-1:
                now_area += bits[i]
        # その列を見終わったら、cntをインクリメントすることでリセットできる
        if all([K >= v for v in now_accumulation.values()]):
            for key in now_accumulation.keys():
                all_accumulation[key] += now_accumulation[key]
            # 累積されていたものに足した
            if all([K >= v for v in all_accumulation.values()]):
                continue
            else:
                cnt += 1
                # 今見ていたところの左側を分割して、累積部分の値を現在のものに変更する
                all_accumulation = now_accumulation.copy()
        else:
            # その行だけを見てもKを超えるものがあるなら行の分割の仕方が論外
            separate_row = False
            break
    if separate_row:
        ans = min(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
def main():
    H, W, K = map(int, input().split())
    S = [list(map(int,list(input()))) for _ in range(H)]
    
    ans = float('inf')
    for i in range(1<<H-1):
        cut = []
        for j in range(H):
            if (i >> j) & 1:
                cut.append(j+1)

        tmp_S = [[0] * W for _ in range(len(cut) + 1)]
        tmp_id = 0
        for i in range(H):
            if i in cut:
                tmp_id += 1
            for j in range(W):
                tmp_S[tmp_id][j] += S[i][j]
        
        isOK = True
        for i in range(len(cut) + 1):
            for w in range(W):
                if tmp_S[i][w] > K:
                    isOK = False

        if not isOK:
            continue

        cnt = len(cut)
        white = [0] * (len(cut)+1)

        flag = False
        for w in range(W):
            for i in range(len(cut) + 1):
                white[i] += tmp_S[i][w]
                if white[i] > K:
                    cnt += 1
                    flag = True
                    break
            if flag:
                for i in range(len(cut) + 1):
                    white[i] = tmp_S[i][w]
                flag = False
        ans = min(ans, cnt)

    print(ans)

                


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
inf = 100100100
ans = inf
H, W, K = map(int, input().split())
S = [0]*H
for i in range(H):
    S[i] = [int(x) for x in input()]
for i in range(2**(H-1)):
    group = [0]
    g = 0
    for j in range(H-1):
        if (i >> j) & 1:
            g += 1
        group.append(g)
    g += 1
    c = [[0 for _ in range(W)] for __ in range(g)]
    for j in range(H):
        for k in range(W):
            c[group[j]][k] += S[j][k]
    num = g-1
    now = [0]*g
    def large(now):
        for n in now:
            if n > K:
                return True
        else:
            return False
    def v_vec(twodlis, k):
        ans = []
        for lis in twodlis:
            ans.append(lis[k])
        return ans
    for k in range(W):
        for n in range(len(now)):
            now[n] = now[n] + v_vec(c,k)[n]
        if large(now):
            now = v_vec(c,k)
            num += 1
            if large(now):
                num = inf
                break
 
    ans = min(ans, num)
print(ans)

Submission status: Accepted

Solution code:
import sys
inf = 100100100
ans = inf
H, W, K = map(int, input().split())
S = [0]*H
for i in range(H):
    S[i] = [int(x) for x in sys.stdin.readline().strip()]
for i in range(2**(H-1)):
    group = [0]
    g = 0
    for j in range(H-1):
        if (i >> j) & 1:
            g += 1
        group.append(g)
    g += 1
    c = [[0 for _ in range(W)] for __ in range(g)]
    for j in range(H):
        for k in range(W):
            c[group[j]][k] += S[j][k]
    num = g-1
    now = [0]*g
    def large(now):
        for n in now:
            if n > K:
                return True
        else:
            return False
    def v_vec(twodlis, k):
        ans = []
        for lis in twodlis:
            ans.append(lis[k])
        return ans
    for k in range(W):
        for n in range(len(now)):
            now[n] = now[n] + v_vec(c,k)[n]
        if large(now):
            now = v_vec(c,k)
            num += 1
            if large(now):
                num = inf
                break

    ans = min(ans, num)
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
input = sys.stdin.buffer.readline

#sys.setrecursionlimit(10**9)

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def LI(): return list(map(int,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode('utf-8')

def main():
	h,w,k=MI()
	G=[]
	for i in range(h):
		A=list(map(int,input().rstrip().decode()))
		G.append(A)
	#print(G)

	for i in range(h):
		for j in range(w):
			if i!=0:
				G[i][j]+=G[i-1][j]
			if j!=0:
				G[i][j]+=G[i][j-1]
			if i!=0 and j!=0:
				G[i][j]-=G[i-1][j-1]
	#print(G)

	B=[]
	for i in range(2**(h-1)):
		C=[0,h-1]
		for j in range(h):
			if i&(1<<j):
				C.append(j)
				C.append(j+1)
		C.sort()
		B.append(C)

	#print(B)

	ans=10**10

	def check(x1,y1,x2,y2):
		ret=G[x2][y2]
		if x1 != 0:
			ret -= G[x1-1][y2]
		if y1 != 0:
			ret -= G[x2][y1-1]
		if x1 != 0 and y1 != 0:
			ret += G[x1-1][y1-1]
		return ret

	for D in B:
		#print(d)
		cnt=len(D)//2-1
		l=0
		ww=0
		f=0
		while ww<w and f==0:
			for i,j in zip(D[0::2],D[1::2]):
				#print(i,j)
				if check(i,l,j,ww)>k:
					#print(i,l,j,ww,check(i,l,j,ww))
					if l==ww:
						f=1
					else:
						cnt+=1
						l=ww
					break
			ww+=1
			#print(w,ww,cnt)
		#print(D,cnt)
		if f==0:
			ans=min(ans,cnt)
	print(ans)














if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:

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

    ans = H*W

    for i in range(0,1<<(H-1)):
        g = 0
        id = [0 for j in range(H)]
        for j in range(0,H):
            id[j] = g
            if i>>j&1 == 1:
                g += 1
        
        g_cnt = [0 for j in range(g+1)]
        c_ans = g
        j = 0
        div_w = 0
        while j < W:
            for k in range(0, H):
                if S[k][j] == '1':
                    g_cnt[id[k]] += 1
            for k in range(0,g+1):
                if g_cnt[k] > K:
                    c_ans += 1
                    g_cnt = [0 for j in range(g+1)]
                    if div_w == j:
                        c_ans += H*W
                        break
                    j -= 1
                    div_w = j
                    break
            j += 1
            if c_ans > ans:
                break
        
        ans = min(ans, c_ans)

    
    print(ans)


main()

Submission status: Accepted

Solution code:
import sys
 
readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)
 
 
def main():
    def divide_choco(bit):
        divrow_num = bin(bit).count("1") + 1  # 割った回数+1
        choco_current = [[0] * w for _ in range(divrow_num)]
 
        row_divided_cur = 0
 
        for col, piece in enumerate(choco[0]):
            choco_current[0][col] = piece
 
        for row in range(h - 1):
            if bit >> row & 1:
                row_divided_cur += 1
            for col, piece in enumerate(choco[row + 1]):
                choco_current[row_divided_cur][col] += piece
 
        return choco_current, divrow_num
 
    h, w, k = list(map(int, readline().split()))
    choco = []
 
    for i in range(h):
        choco_in = input()
        choco_add = [int(c) for c in choco_in]
        choco.append(choco_add)
 
    ans = INF
 
    for bit in range(1 << (h - 1)):
        choco_current, divrow_num = divide_choco(bit)
        choco_cursum = [0] * divrow_num
        is_exceed = False  # 超えてる場合True
 
        ans_temp = bin(bit).count("1")
        if divrow_num > 1:
            for col in range(w):
                choco_currow = [choco_current[dr][col] for dr in range(divrow_num)]
                for drow, pieces in enumerate(choco_currow):
                    if pieces > k:
                        ans_temp += INF
                    elif choco_cursum[drow] + pieces > k:
                        is_exceed = True
 
                if is_exceed:
                    choco_cursum = [cc for cc in choco_currow]
                    ans_temp += 1
                    is_exceed = False
                else:
                    choco_cursum = [cc + cs for cc, cs in zip(choco_currow, choco_cursum)]
        else:
            choco_cursum = 0
            for pieces in choco_current[0]:
                if pieces > k:
                    ans_temp += INF
                elif choco_cursum + pieces > k:
                    choco_cursum = pieces
                    ans_temp += 1
                else:
                    choco_cursum = choco_cursum + pieces
 
        ans = min(ans, ans_temp)
 
    print(ans)
 
 
if __name__ == '__main__':
    main()

Submission status: Accepted

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

from itertools import product
ans = 2000

for cond in product([True,False],repeat=(h-1)):
    cut = sum(cond)
    splits = [arr[0][:]]
    for i in range(1,h):
        if cond[i-1]:
            splits.append(arr[i][:])
        else:
            splits[-1] = [splits[-1][j]+arr[i][j] for j in range(w)]
    
    check = [max(i) for i in splits]
    if max(check) > k:
        break
    count = [i[0] for i in splits]
    
    div = cut
    for j in range(1,w):
        addarr = [count[i]+splits[i][j] for i in range(cut+1)]
        if max(addarr) > k:
            div += 1
            count = [splits[i][j] for i in range(cut+1)]
        else:
            count = addarr[:]
    ans = min(ans,div)
        
print(ans)

Submission status: Accepted

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

from itertools import product
ans = 2000

for cond in product([True,False],repeat=(h-1)):
    cut = sum(cond); div = 0
    splits = [0] * (cut+1); splits[0] = arr[0][:]
    for i in range(1,h):
        if cond[i-1]:
            div += 1
            splits[div] = arr[i][:]
        else:
            splits[div] = [splits[div][j]+arr[i][j] for j in range(w)]
    
    check = [max(i) for i in splits]
    if max(check) > k:
        break
    count = [i[0] for i in splits]
    
    for j in range(1,w):
        addarr = [count[i]+splits[i][j] for i in range(cut+1)]
        if max(addarr) > k:
            div += 1
            count = [splits[i][j] for i in range(cut+1)]
        else:
            count = addarr[:]
    ans = min(ans,div)
        
print(ans)

Submission status: Accepted

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

from itertools import product
ans = 2000

for i in product([True,False],repeat=(h-1)):
    cut = sum(i)
    splits = [0] * (cut+1)
    splits[0] = arr[0][:]
    tmp = 0
    div = cut
    for j in range(1,h):
        if i[j-1]:
            tmp += 1
            splits[tmp] = arr[j][:]
        else:
            splits[tmp] = [splits[tmp][idx]+arr[j][idx] for idx in range(w)]
    
    check = 0
    for j in splits:
        check = max(check,max(j))
    if check > k:
        break
    count = [splits[j][0] for j in range(cut+1)]
    
    for j in range(1,w):
        addarr = [count[idx]+splits[idx][j] for idx in range(cut+1)]
        if max(addarr) > k:
            div += 1
            count = [splits[idx][j] for idx in range(cut+1)]
        else:
            count = addarr[:]
    ans = min(ans,div)
        
print(ans)

Submission status: Accepted

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

ans = H*W

def countWhite(ytop, ybottom, xleft, xright):
    ret = sum([sum(s[xleft:xright]) for s in S[ytop:ybottom]])
    return ret
    

for h_div in range(1 << H-1):
    count = 0
    cut = [0]
    for i in range(H):
        if h_div >> i & 1:
            cut.append(i+1)
            count += 1
    cut.append(H)
    if count > ans:
        continue
    
    left = 0
    # ここどんなふうに縦に切っても条件を満たさない場合がある
    for right in range(1, W+1):
        white = 0
        for i in range(len(cut)-1):
            white = max(white, countWhite(cut[i], cut[i+1], left, right))
        
        if white > K:
            if left == right - 1: # 条件を満たす縦の切り方がなかった場合
                break
            left = right - 1
            count += 1
            if count > ans:
                break
    else:
        if count < ans:
            ans = count

print(ans)

Submission status: Accepted

Solution code:
from itertools import product
H, W, K = map(int, input().split())
choco = [list(input()) for _ in range(H)]

def cnt(array):
    count = [0] * H
    split_cnt = 0
    for w in range(W):
        for h in range(H):
            if choco[h][w] == "1":
                count[array[h]] += 1
        if any(i > K for i in count):
            split_cnt += 1
            count = [0] * H
            for h in range(H):
                if choco[h][w] == "1":
                    count[array[h]] += 1
            if any(i > K for i in count):
                return 10 ** 20
    return split_cnt

def get_array(array):
    l = len(array)
    ret = [0] * l
    for i in range(1, l):
        ret[i] = ret[i-1] + array[i]
    return ret

ans = 10 ** 20

for p in product(range(2), repeat=H-1):
    p = get_array([0]+list(p))
    ans = min(ans, cnt(p)+max(p))

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
h,w,k = map(int,input().split())
b =[]
for i in range(h):
    s = input()
    b.append(s)
# 縦の切り方を固定すれば、左から見て貪欲に考えることができる。
# どれかの切り方でK+1　以上1 のマスがあれば、そこで切る
if h == 1:
    print(math.ceil(s//k))
    exit()
# リストで現在のそれぞれのブロックの1の数を持つ

# 列の切断が入ったときに全て0に初期化
# bit 全探索は 2 ** h-1 存在する 
ans = h*w #INF
for i in range(2**(h-1)):
    cnt_white = [0] 
    # ループの中で宣言する
    ans_i = 0
    #前処理として、どこに切れ込みがあるかを見て、リストの構成
    for bit in range(h-1):
        if i >> bit & 1:
            cnt_white.append(0)
            ans_i += 1
    #print("i = ",i,cnt_white)
    c = 0
    last_div = 0
    while c < w:# 左から貪欲
        r_idx = 0
        
        for r in range(h):
            if b[r][c] == "1":#対応するブロックのcnt+=1
                cnt_white[r_idx] += 1
                #print("col = ",c,cnt_white,r_idx,ans_i)
            if i >> r & 1:#次にブロックが変わるのでidxを増やす
                r_idx += 1
        # 1行だけでmax(cnt_white) >= k+1になるときはその切り方では不可能
        if max(cnt_white) >= k+1:
            # 戻らないといけない
            ans_i += 1
            if c == last_div:
                ans_i = h*w  #INF
                break
            last_div = c
            c -= 1
            cnt_white = [0]*len(cnt_white)#初期化
            #print("initialize",last_div)
        c += 1
    ans = min(ans,ans_i)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/python3
import copy

def minOp(h, w, k, yl, s):
    xl = []
    ks = [ 0 for i in range(len(yl) + 1) ]

    for x in range(w):
        py = 0
        cks = [ 0 for i in range(len(yl) + 1) ]
        for idx, y in enumerate(yl + [h - 1]):
            for yy in range(py, y + 1):
                if s[yy][x] == '1':
                    cks[idx] += 1

            py = y + 1

        over = False
        for idx, kk in enumerate(ks):
            if kk + cks[idx] > k:
                over = True

        if over:
            for ck in cks:
                if ck > k:
                    return (h - 1) + (w - 1)
            xl.append(x - 1)
            ks = copy.copy(cks)
        else:
            ks = list(map(lambda a, b: a + b, ks, cks))
            
    return len(xl) + len(yl)
    

def devideVertical(h, w, k, cy, yl, s):
    m = (h - 1) + (w - 1)
    for y in range(cy, h - 1):
        nyl = copy.copy(yl)
        nyl.append(y)
        m = min(m, devideVertical(h, w, k, y + 1, nyl, s))
    
    m = min(m, minOp(h, w, k, yl, s))
    return m

(h, w, k) = map(int, input().split())
s = []
for i in range(h):
    s.append(input())

print(devideVertical(h, w, k, 0, [], s))

Submission status: Accepted

Solution code:
import itertools


def check(H, W, K, S, p):
    num_groups = p.count(True) + 1
    group_total = [0] * num_groups
    ret = p.count(True)

    for j in range(W):
        group_value = [0] * num_groups
        group_value[0] += int(S[0][j])
        group_idx = 0
        for i in range(H-1):
            if p[i]:
                group_idx += 1
            group_value[group_idx] += int(S[i+1][j])
        if max(group_value) > K:
            return float("inf")
        group_total_tmp = list(map(sum, zip(group_value, group_total)))
        if max(group_total_tmp) <= K:
            group_total = group_total_tmp
        else:
            group_total = group_value
            ret += 1
    return ret


def main():
    H, W, K = map(int, input().split())
    S = [input() for _ in range(H)]
    ans = float("inf")
    for p in itertools.product([True, False], repeat=H-1):
        ans = min(ans, check(H, W, K, S, p))
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from itertools import combinations

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

C = [[0] * (W + 1) for _ in range(H + 1)]
for h in range(H):
    wc = 0
    for w in range(W):
        wc += (S[h][w] == '1')
        C[h + 1][w + 1] = C[h][w + 1] + wc

ans = 2000
for cuth in range(H):
    for comb in combinations([h for h in range(1, H)], cuth):
        comb = [0] + list(comb) + [H]
        wi, cutw = 0, 0
        for w in range(W):
            if max([C[comb[i]][w + 1] - C[comb[i]][wi] - C[comb[i - 1]][w + 1] + C[comb[i - 1]][wi] for i in range(1, len(comb))]) > K:
                if wi == w:
                    cutw = 2000
                wi, cutw = w, cutw + 1
        ans = min(ans, cuth + cutw)

print(ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    h,w,k = LI()
    aa = [[int(c) for c in S()] for _ in range(h)]

    def f(hs):
        l = len(hs)
        c = [0] * l
        r = l - 1
        for i in range(w):
            nc = [0] * l
            bf = False
            for j in range(l):
                for h in hs[j]:
                    nc[j] += aa[h][i]
                if nc[j] > k:
                    return -1
                if nc[j] + c[j] > k:
                    bf = True
            if bf:
                r += 1
                c = nc
            else:
                for j in range(l):
                    c[j] += nc[j]
        return r

    r = inf
    for bi in range(2**(h-1)):
        hs = [[0]]
        for i in range(h-1):
            if 2**i & bi > 0:
                hs.append([])
            hs[-1].append(i+1)
        t = f(hs)
        if t >= 0 and r > t:
            r = t

    return r


print(main())

Submission status: Accepted

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

ret = W - 1 + H - 1

for i in range(1 << (H - 1)):
    sep = bin(i)[2:].rjust(H - 1, '0')[::-1]

    tile_idx = [0] * H
    cut = 0

    for j in range(H):
        tile_idx[j] = cut

        if j == H - 1:
            break

        if sep[j] == '1':
            cut += 1

    cnt_lst = [0] * (cut + 1)
    num_cnt = 0

    for w in range(W):
        col_new = [0] * (cut + 1)

        flag = False
        flag1 = False
        for h in range(H):
            if S[h][w] == 1:
                idx = tile_idx[h]
                col_new[idx] += 1

        for a in col_new:
            if a > K:
                flag1 = True
                break

        if flag1:
            break

        for k in range(cut + 1):
            if cnt_lst[k] + col_new[k] > K:
                num_cnt += 1
                for l in range(cut + 1):
                    cnt_lst[l] = col_new[l]

                flag = True
                break

        if not flag:
            for k in range(cut + 1):
                cnt_lst[k] += col_new[k]

    if not flag1:
        ret = min(ret, num_cnt + cut)


print(ret)

Submission status: Accepted

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

for i in range(1<<(H-1)):
    start = [0]
    end = []
    for j in range(H-1):
        if i & (1 << j):
            j += 1
            start.append(j)
            end.append(j)
    end.append(H)
    L = len(end)
    cnt = [0]*L
    dcnt = L-1
    fail = False
    for w in range(W):
        div = False
        idx = 0
        tmp = [0]*L
        for s,e in zip(start,end):
            for h in range(s,e): tmp[idx] += C[h][w]
            if tmp[idx] > K: 
                fail = True
                break
            if cnt[idx] + tmp[idx] > K:
                div = True
                cnt = tmp[:]
            else:
                cnt[idx] += tmp[idx]
            idx += 1
        if fail: break
        if div: dcnt += 1
    if fail: continue
    ans = min(dcnt,ans)

print(ans)