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:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
from itertools import product, accumulate, combinations, product
#import bisect# lower_bound etc
#import numpy as np
#from copy import deepcopy
#from collections import deque
def run():
    H,W,K = map(int, sysread().split())
    S = []
    for i in range(H):
        S.append(list(accumulate(list(map(int, list(input()))), lambda x,y:x+y)))
    for h in range(1, H):
        for w in range(W):
            S[h][w] += S[h-1][w]

    ret = float('inf')

    for idxes_ in product((0,1), repeat=H-1):
        l = 0
        r = 1
        idxes = [0]
        for i, val in enumerate(idxes_, 1):
            if val == 1:
                idxes.append(i)
        idxes.append(H)
        min_cut = len(idxes) - 2
        while r <= W:
            for i in range(len(idxes)-1):
                if idxes[i] == 0 and l == 0:
                    cri = S[idxes[i+1]-1][r-1]
                elif l == 0:
                    cri = S[idxes[i+1]-1][r-1] - S[idxes[i]-1][r-1]
                elif idxes[i] == 0:
                    cri = S[idxes[i+1]-1][r-1] - S[idxes[i+1]-1][l-1]
                else:
                    cri = S[idxes[i+1]-1][r-1] - S[idxes[i]-1][r-1] - S[idxes[i+1]-1][l-1] + S[idxes[i]-1][l-1]

                if cri > K:
                    r -= 1
                    if l == r:
                        min_cut = float('inf')
                        r = W+1
                        break
                    l = r
                    min_cut += 1
                    break
            r += 1
        ret = min(ret, min_cut)

    print(ret)




if __name__ == "__main__":
    run()

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
from itertools import product#accumulate, combinations, product
#import bisect# lower_bound etc
import numpy as np
#from copy import deepcopy
#from collections import deque
def run():
    H,W,K = map(int, sysread().split())
    S = []
    for i in range(H):
        S.append(list(map(int, list(input()))))
    S = np.array(S)
    ret = float('inf')
    for w in range(1, W):
        S[:,w] += S[:,w-1]
    for h in range(1, H):
        S[h,:] += S[h-1,:]
    S = S.tolist()
    for idxes_ in product((0,1), repeat=H-1):
        l = 0
        r = 1
        idxes = [0]
        for i, val in enumerate(idxes_, 1):
            if val == 1:
                idxes.append(i)
        idxes.append(H)
        min_cut = len(idxes) - 2
        while r <= W:
            for i in range(len(idxes)-1):
                if idxes[i] == 0 and l == 0:
                    cri = S[idxes[i+1]-1][r-1]
                elif l == 0:
                    cri = S[idxes[i+1]-1][r-1] - S[idxes[i]-1][r-1]
                elif idxes[i] == 0:
                    cri = S[idxes[i+1]-1][r-1] - S[idxes[i+1]-1][l-1]
                else:
                    cri = S[idxes[i+1]-1][r-1] - S[idxes[i]-1][r-1] - S[idxes[i+1]-1][l-1] + S[idxes[i]-1][l-1]

                if cri > K:
                    r -= 1
                    if l == r:
                        min_cut = float('inf')
                        r = W+1
                        break
                    l = r
                    min_cut += 1
                    break
            r += 1
        ret = min(ret, min_cut)

    print(ret)




if __name__ == "__main__":
    run()

Submission status: Accepted

Solution code:
import itertools
H,W,K = map(int,input().split())
S = []
for i in range(H):
  s= map(int,input())
  S.append(list(s))
l = list(itertools.product([0,1], repeat=H-1))
l = [list(li) for li in l]
for i in range(len(l)):
  l[i] = [j+1 for j in range(len(l[i])) if l[i][j] > 0]
  
S_t = [list(x) for x in zip(*S)]
for i in range(W):
  for j in range(1,H):
    S_t[i][j] += S_t[i][j-1]
flag = False  
min_cnt = H*W
for i in range(len(l)):
  cnt = 0
  bh = [0]+[li  for li in l[i] if li > 0]+[H]
  white = [0]*(len(bh)-2+1)
  j = 0
  while j < W:
    if flag == True:
      white = [0]*(len(bh)-2+1)
      cnt += 1
      flag = False
    for k in range(len(bh)-1):
      if bh[k] == 0:
        su = S_t[j][bh[k+1]-1]
      else:
        su = S_t[j][bh[k+1]-1]-S_t[j][max(0,bh[k]-1)]
      if white[k] + su > K:
        if su > K:
          j = W
          cnt = H*W+1
          flag = False
        else:
          flag = True
        break
      white[k] += su
    if flag == False:
      j += 1
  min_cnt = min(cnt+len(bh)-2,min_cnt)
  
print(min_cnt)

Submission status: Accepted

Solution code:
h, w, k = map(int, input().split())
s = [list(input()) for _ in range(h)]
# 2次元累積和
acum = [[0]*(w+1) for _ in range(h+1)]
for i in range(h):
    for j in range(w):
        acum[i+1][j+1] = acum[i][j+1] + acum[i+1][j] - acum[i][j] + int(s[i][j])
#print(acum)


def white_choco_count(x1, y1, x2, y2):
    return acum[y2][x2] - acum[y2][x1] - acum[y1][x2] + acum[y1][x1]


ans = float("inf")
for rows in range(2**(h-1)):
    count = 0
    hlist = []
    for i in range(h-1):
        if rows >> i & 1 == 1:
            count += 1  # 横線の数カウントしておく
            hlist.append(i+1)
    hlist.append(h)
    #print(hlist)
    x1 = 0
    for x2 in range(w):
        y1 = 0
        for y2 in hlist:
            if white_choco_count(x1, y1, x2, y2) > k:
                count += float("inf")
            # kを超えてはいけないが、一個右で縦に割るとｋを超える必要がある（貪欲にやるので）
            elif white_choco_count(x1, y1, x2, y2) <= k < white_choco_count(x1, y1, x2+1, y2):
                count += 1
                # 次のブロックにいくのでx1更新(ただしy1の更新はx2がｗまでおわったあとにしたいのでbreak使うとうまくいく）
                x1 = x2
                break
            y1 = y2
    # ここまでで、x2=0, 1, ..., w-1 までみたが、x2 = wのとき（ブロックの右端）を見てない
    y1 = 0
    for y2 in hlist:
        if white_choco_count(x1, y1, w, y2) > k:
            count += float("inf")
        y1 = y2
    #print(count)
    ans = min(ans, count)
print(ans)

Submission status: Accepted

Solution code:
import sys
#import numpy as np

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(IN())
mod=1000000007

#+++++
def ii(v, n):
	v += 2 ** 15
	ret = bin(v)[-n:]
	return ret

def v_sum(a,b):
	return [av+bv for av,bv in zip(a,b)]

def get_n(rr, mm, k, limit):
	ret = sum([int(c) for c in rr])
	o = mm[0]
	pp = []
	for index_i, is_cut in enumerate(rr):
		if is_cut == '1':
			pp.append(o)
			o = mm[index_i+1]
		else:
			o = v_sum(o, mm[index_i+1])
			
		if max(o) > k:
			return mod, None
			
	pp.append(o)
	
	ll = [pp[j][0] for j in range(len(pp))]
	for v in ll:
		if v > k:
			return mod, None
	
	cc = [0]*(len(mm[0]))
	for i in range(1, len(mm[0])):
		for il, v in enumerate(ll):
			if ll[il] + pp[il][i] > k:
				ret += 1
				if ret >= limit:
					return limit+1, None
				ll = [pp[j][i] for j in range(len(pp))]
				cc[i] = 1
				break
			else:
				ll[il] += pp[il][i]
	return ret, cc

def main():
	h, w, k = tin()
	mm=[]
	for _ in range(h):
		s = input()
		s = [int(c) for c in s]
		#s = np.array(s)
		mm.append(s)
		
	n = (h-1)*(w-1) + 1
	for i in range(2 ** (h-1)):
		rr = ii(i, h-1)
		tt, cut_info = get_n(rr, mm, k, n)
		if tt < n:
			n = tt
		
	print(n)
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:
from itertools import groupby, accumulate, product, permutations, combinations
def solve():
    H, W, K = map(int, input().split())
    S = [input() for _ in range(H)]
    cum = [[0]*(W+1) for _ in range(H+1)]
    for i in range(1,H+1):
        for j in range(1,W+1):
            cum[i][j]=cum[i-1][j]+cum[i][j-1]-cum[i-1][j-1]+int(S[i-1][j-1])
    ans = 2000
    for p in product([0,1],repeat=H-1):
        line = [0]
        p = list(p)
        cnt = sum(p)
        for i in range(1,H):
            if p[i-1]==1:
                line.append(i)
        line.append(H)
        w_s = 0
        w_e = 1
        b = False
        while w_e <= W:
            for i in range(len(line)-1):
                h_s = line[i]
                h_e = line[i+1]
                white = cum[h_e][w_e]+cum[h_s][w_s]-cum[h_e][w_s]-cum[h_s][w_e]
                if white > K:
                    if w_e == w_s+1:
                        b = True
                        break
                    else:
                        w_s = w_e-1
                        cnt += 1
                        break
            if b==True:
                break
            w_e += 1
        else:
            ans = min(ans,cnt)
    return ans
print(solve())

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#%% for atcoder uniittest use
import sys
input= lambda: sys.stdin.readline().rstrip()
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
#%%code
def resolve():
    H,W,K=pin()
    choco=[list(input()) for _ in range(H)]
    #think H<=10:bit full search
    ans=H+W #default
    #print(choco)
    for h in range(1<<(H-1)):#uekara h banme no yoko de waru
        tempans=0

        see=[]

        shiro=[0]
        for i in range(H):
            see.append(tempans)
            if (1<<i)&h:
                tempans+=1 
                shiro.append(0)
            
        #print(see,tempans,bin(h),"sth")
        #print(shiro,";")
        #yokoni krenai nara donkoku de jituhatokeru
        j=0
        while(j<W):
            f=1
            for n,s in enumerate(see):
                shiro[s]+=int(choco[n][j])
                if shiro[s]>K:#suguhidaride kiru
                    if j==0:#kirenai kara nasi                        
                        f=0
                        break
                    tempans+=1
                    shiro=[0]*len(shiro)
                    j-=1
                    break   
            if f==0:
                tempans=H*W
                break
            j+=1
            #print(j,shiro,"tochu") 
            
        #print(tempans,"tempans")
        ans=min(ans,tempans)
    print(ans)
#%%submit!
resolve()

Submission status: Accepted

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

choko = [[0]*W for _ in range(H)]

ans = 10**18

for divide in product(range(2), repeat=H - 1):
    cut = sum(divide)
    row = [0]
    for d in divide:
        if d:
            row.append(row[-1] + 1)
        else:
            row.append(row[-1])

    r = row[-1] + 1
    for i in range(r):
        for j in range(W):
            choko[i][j] = 0
    for i in range(H):
        for j in range(W):
            choko[row[i]][j] += S[i][j]

    if any(choko[i][0] > K for i in range(r)):
        continue

    now = [0] * r
    for j in range(W):
        if any(now[i] + choko[i][j] > K for i in range(r)):
            cut += 1
            now = [choko[i][j] for i in range(r)]
        else:
            for i in range(r):
                now[i] += choko[i][j]

    ans = min(ans, cut)

print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    H,W,K = map(int, readline().split())
    S = [list(map(int, readline().strip())) for j in range(H)]
    
    white = 0
    for line in S:
        white += sum(line)
 
    if white <= K:
        print(0)
        exit()
 
    # 横線の決め方を全探索
    ans = 10**5
    
    #yに横線Patternごとの列合計を作成
    #入力例１のPattern[bin(2)]場合、y=[[1,1,1,0,0], [1,0,1,1,2]]
    for pattern in range(2**(H-1)):
        # 初期化
        impossible = False
        x = 0
        ly = bin(pattern).count("1")
        y = [S[0]]
        line = 0
        for i in range(1,H):
            if (pattern >> i-1) & 1:
                line += 1
                y.append(S[i])
            else:
                y[line] = [y[line][j] + S[i][j] for j in range(W)]
 
        # 各列の値を加算していく
        count = [0]*(ly + 1) 
        for j in range(W):
            for i in range(line+1):
                if y[i][j] > K :
                    impossible = True
                    break
 
                count[i] += y[i][j]
                #print("横Pattern{} 縦列まで　{} カウント数{} 縦線の数{}".format(i, j, count[i], x))
                #横Patten毎にｊ列までのホワイトチョコ合計数をカウント、
                #カウント＞Kとなったら、縦線数を＋１、その列値でカウント数を初期化
                if count[i] > K:
                    x += 1
                    for i in range(line+1):
                        count[i] = y[i][j]
                    break
            #x縦線の数 + ly横線の数がAnsより大きくなったらBreak
            if x + ly > ans or impossible:
                impossible = True
                break
        if impossible:
            x = 10**6
        #x縦線の数 + ly横線の数がAnsより小さくなったらAnsを更新
        ans = min(ans, x + ly)
 
    print(ans)
 
 
main()

Submission status: Accepted

Solution code:
"""
References: <https://www.hamayanhamayan.com/entry/2020/03/22/231629>
"""
import sys
from itertools import product

input = sys.stdin.readline


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

    ans = float("inf")
    for comb in product(range(2), repeat=(H - 1)):
        n_cut = sum(comb)
        if n_cut >= ans:
            continue

        group = []
        g_id = 0
        for c in comb:
            group.append(g_id)
            if c == 1:
                g_id += 1
        group.append(g_id)

        w = 0
        while w < W:
            count = [0] * (g_id + 1)
            next_w = w
            for x in range(w, W):
                over_K = False
                for y in range(H):
                    if S[y][x] == "1":
                        count[group[y]] += 1
                        if count[group[y]] > K:
                            over_K = True
                            break
                if over_K:
                    break
                next_w += 1

            # Impossible: over K in one column
            if next_w == w:
                n_cut = float("inf")
                break
            w = next_w

            if over_K:
                n_cut += 1
            if n_cut >= ans:
                break

        if n_cut < ans:
            ans = n_cut

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

ans=float("inf")
for i in range(2**(h-1)):
    cut=[]
    linecount=0
    for j in range(h-1):
        if (i>>j)%2==1:
            cut.append(j)
    counter=[0]*(len(cut)+1)
    for j in range(w):
        ncounter=[0]*(len(cut)+1)
        area=0
        flag=False
        for k in range(h):
            ncounter[area]+=int(s[k][j])
            if counter[area]+ncounter[area]>K:
                if ncounter[area]>K:
                    linecount=float("inf")
                flag=True
            if k in cut:
                area+=1
        if flag:
            counter=ncounter[:]
            linecount+=1
        else:
            for l in range(len(cut)+1):
                counter[l]+=ncounter[l]
    ans=min(ans,linecount+len(cut))
print(ans)

Submission status: Accepted

Solution code:
h,w,k=map(int,input().split())
s=[list(map(int,list(input()))) for _ in range(h)]
def func(catyoko):
  cattate=0
  past=[0]*10
  for wi in range(w):
    now=[0]*10
    for i in range(1,len(catyoko)):
      for j in range(catyoko[i-1],catyoko[i]):
        now[i-1]+=s[j][wi]
    if max([past[i]+now[i] for i in range(10)])>k:
      if max(now)>k:
        return -10
      else:
        cattate+=1
      past=[nowi for nowi in now]
    else:
      for i in range(10):
        past[i]+=now[i]
  return cattate+len(catyoko)-2

# 横方向の割り方は2^(h-1)通りある。h<=10なので横方向の割り方は全探索する。
# 縦方向の割り方は貪欲法
ans=h+w
for i in range(2**(h-1)):
  catyoko=[0]
  for j in range(h-1):
    if ((i>>j) & 1):#立っているビットのところで処理が走る
      catyoko.append(j+1)
  catyoko.append(h)
  a=func(catyoko)
  #print(a,catyoko)
  if a>=0:
    ans=min(ans,a)
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

H, W, K = lr()
S = np.array([list(map(int, sr())) for _ in range(H)])
Scum = np.cumsum(S, axis=1)
INF = 10 ** 10
answer = INF
for pattern in range(1<<H-1):
    cnt = 0
    Tcum = Scum.copy()
    for i in range(H-1):
        if pattern>>i & 1:  # 切れ目
            cnt += 1
        else:
            Tcum[i+1] += Tcum[i]
    prev = -1
    w = 0
    Tcum = Tcum.tolist()
    while w < W:
        cut = False
        for i in range(H):
            if Tcum[i][w] - (Tcum[i][prev] if prev >= 0 else 0) > K:
                cut = True
                break
        if cut:
            if prev == w - 1:  # 1列でKをオーバー
                break
            cnt += 1
            prev = w - 1
        else:
            w += 1
    else:
        answer = min(answer, cnt)

print(answer)

Submission status: Accepted

Solution code:
H,W,K=map(int,input().split())
S=[list(map(int,list(input()))) for i in range(H)]
ans=H+W-2
for bit in range(2**(H-1)):
    divH=[0]
    for j in range(H-1):
        if(bit>>j&1):
            divH.append(j+1)
    divH.append(H)
    glen=len(divH)-1
    group=[0]*(glen)
    res=glen-1
    go=True
    for w in range(W):
        ok=True
        c=[0]*(glen)
        for g in range(glen):
            cum=0
            for h in range(divH[g],divH[g+1]):
                cum+=S[h][w]
            c[g]+=cum
            if cum>K:
                go=False
            if cum+group[g]>K:
                ok=False
        if not go:
            break
        if not ok:
            res+=1
            group=[c[i] for i in range(glen)]
        else:
            for i in range(glen):
                group[i]+=c[i]
    if not go:
        continue
    ans=min(ans,res)
print(ans)

Submission status: Accepted

Solution code:
H,W,K=map(int,input().split())
S=[list(map(int,list(input()))) for i in range(H)]
ans=H+W-2
for bit in range(2**(H-1)):
    divH=[0]
    for j in range(H-1):
        if(bit>>j&1):
            divH.append(j+1)
    divH.append(H)
    glen=len(divH)-1
    group=[0]*(glen)
    res=glen-1
    go=True
    w=0
    while w<W:
        ok=True
        c=[0]*(glen)
        for g in range(glen):
            cum=0
            for h in range(divH[g],divH[g+1]):
                cum+=S[h][w]
            c[g]+=cum
            if cum>K:
                go=False
                break
            if c[g]+group[g]>K:
                ok=False
        if not go:
            break
        if not ok:
            res+=1
            group=[0]*glen
        else:
            for i in range(glen):
                group[i]+=c[i]
            w+=1
    if not go:
        continue
    ans=min(ans,res)
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
from itertools import accumulate

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

H, W, K = lr()
S = [list(map(int, sr())) for _ in range(H)]
Scum = [list(accumulate(row)) for row in S]
# H方向はbit全探索、W方向はGreedyに
INF = 10 ** 10
answer = INF
for pattern in range(1<<(H-1)):
    slice = set()
    cnt = 0
    for i in range(H-1):
        if pattern>>i & 1:
            slice.add(i)
            cnt += 1
    slice.add(H-1)  # 最後の区切り
    w = 0
    prev = -1
    while w < W:
        cut = False
        white = 0
        for i in range(H):
            white += Scum[i][w] - (Scum[i][prev] if prev >= 0 else 0)
            if i in slice:
                if white > K:
                    cut = True
                    break
                white = 0
        if cut:
            if prev == w - 1:  # 1列でKをオーバーしたので無理
                break
            cnt += 1
            prev = w-1
        else:
            w += 1
    else:
        answer = min(answer, cnt)

print(answer)
# 43

Submission status: Accepted

Solution code:
h,w,K = map(int, input().split())
g = [[0]*w for _ in range(h)]
for i in range(h):
    s=input()
    for j in range(w):
        g[i][j] = s[j]
ans=1001001001
for i in range(1<<(h-1)):
    seg = [0]*h
    segnow = 0
    for j in range(h-1):
        if i & 1 << j:
            segnow += 1
        seg[j+1] = segnow

    segnow += 1
    flag = True
    div = 0
    cnt = [0 for _ in range(segnow)]
    for j in range(w):
        now = [0]*segnow
        for k in range(h):
            if g[k][j] == '1':
                cnt[seg[k]] += 1
                now[seg[k]] += 1
                if cnt[seg[k]] > K:
                    div+=1
                    for l in range(segnow):
                        cnt[l] = now[l]
        if max(now)>K:
            continue
    ans = min(ans,segnow-1+div)
print(ans)

Submission status: Accepted

Solution code:



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

accum_col = [[0 for _ in range(W)] for _ in range(H)]

for i in range(H):
    for j in range(W):
        if i == 0:
            accum_col[i][j] = S[i][j]
        else:
            accum_col[i][j] = accum_col[i-1][j] + S[i][j]

def cnt_white(x, a, b):
    if a == 0:
        return accum_col[b-1][x]
    else:
        return accum_col[b-1][x] - accum_col[a-1][x]

ans = H*W
for bit in range(1 << (H-1)):
    # 横に直線で割るが、その線の真下のindex
    horizs = [0]
    cnt_split = bin(bit).count("1")
    for i in range(H-1):
        if bit & (1 << i):
            """
            i=0でbitに1が立っていると、y=0と1の間を横一直線に割るので、次のブロックの始まりはy=1から。
            みたいな意味でi+1
            """
            horizs.append(i+1)
    
    horizs.append(H)
    # horizsの要素間がブロックなので-1
    # これまでの各ブロックの累積のホワイトチョコの個数
    prev = [0] * (len(horizs) - 1)
    for x in range(W):
        # 横位置でxの列の各ブロックのホワイトチョコの個数
        curr_col = [cnt_white(x, a, b) for a,b in zip(horizs, horizs[1:])]
        # 各ブロックの個数
        prev_curr = [curr_col[i] + prev[i] for i in range(len(horizs)-1)]
        if max(curr_col) > K:
            # 一行だけみてもKを超えるブロックがあるので、十分大きい値を足してアウトにする
            cnt_split += H*W
            break
        if max(prev_curr) > K:
            # ホワイトチョコが最も多いブロックでKを超えていれば、手前の列までで割る
            prev = curr_col
            cnt_split += 1
        else:
            # いずれもK以下であればそのままブロックを広げる
            prev = prev_curr
    
    ans = min(ans, cnt_split)

print(ans)

Submission status: Accepted

Solution code:

from bisect import bisect_left

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

"""
H <= 10までなので、横直線方向の割り方を全探索できそう
縦直線方向の割り方は貪欲か。
横直線の割方が決まったら、次は縦に割っていくが、ブロックの横幅を1にしても、ブロックないのホワイトチョコがKを超える場合もありうるので、その場合は、その横直線の割り方で条件を満たすことはできない


H=1や W=1の場合は普通に貪欲で。
"""


def is_over_K(lst, block_num):
    res = False
    for i in range(block_num):
        if lst[i] > K:
            res = True
            break
    return res


if H != 1 and W != 1:
    # 全区切りで割った場合が最大
    ans = (H-1) + (W-1)
    for bit in range(1 << (H-1)):
        can_split_h = True
        cnt_split_h = bin(bit).count("1")
        cnt_split_w = 0

        # 横直線方向で割る場合は、その箇所のindexを保持
        if cnt_split_h >= 1:
            idx_split_h = []
            for i in range(H-1):
                if bit & (1 << i):
                    idx_split_h.append(i)

        cnt_blocks = cnt_split_h + 1
        cnt_whites = [0] * (cnt_blocks)
        ex_cnt_whites = [0] * (cnt_blocks)

        for x in range(W):
            for y in range(H):
                if S[y][x] == "1":
                    if cnt_blocks > 1:
                        block_num = bisect_left(idx_split_h, y)
                    else:
                        block_num = 0

                    cnt_whites[block_num] += 1
            
            # それぞれKを超えていないか確認
            is_over = is_over_K(cnt_whites, cnt_blocks)

            
            if not is_over:
                # Kを超えないので、さらにxを追加して見ていく
                # xまでで各ブロックでホワイトチョコがいくつあるか保持（次のxでKを超えた場合に、差分を利用するので）
                for i in range(cnt_split_h+1):
                    ex_cnt_whites[i] = cnt_whites[i]
            else:
                # Kを超えるのでxの左の縦直線でわる
                cnt_split_w += 1
                # xの左の縦直線で割った場合のホワイトチョコの個数を求める（現在のxのみの個数）
                for i in range(cnt_blocks):
                    cnt_whites[i] -= ex_cnt_whites[i]
                    ex_cnt_whites[i] = cnt_whites[i]

                # 一列だけにしてもKを超えるなら、その横直線の分割はできない
                if is_over_K(cnt_whites, cnt_blocks):
                    can_split_h = False
                    break
            # 一列だけにしてもKを超えるブロックがあるので、この横直線の分割はできない
            if not can_split_h:
                break
        
        if can_split_h:
            ans = min(ans, cnt_split_h + cnt_split_w)

# H=1, W=1の場合忘れとった...
elif H == 1:
    ans = 0
    cnt = 0
    for i in range(W):
        if S[0][i] == "1":
            cnt += 1
        if cnt > K:
            ans += 1
            cnt = 1
else:
    ans = 0
    cnt = 0
    for i in range(H):
        if S[i][0] == "1":
            cnt += 1
        if cnt > K:
            ans += 1
            cnt = 1

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 = (h-1)+(w-1)
for i in range(2**(h-1)):
    d = [(i >> j) & 1 for j in range(h-1)]
    count, count_tmp = [0]*(sum(d)+1), [0]*(sum(d)+1)
    ans_, res = 0, 0
    flag = False
    for w_ in range(w):
        count[0] += s[0][w_]
        count_tmp[0] += s[0][w_]
        res += 1
        tmp = 0
        for h_ in range(1, h):
            if d[h_-1]: tmp += 1
            if s[h_][w_]:
                count[tmp] += 1
                count_tmp[tmp] += 1
        for j in count:
            if j > k:
                if res==1:
                    flag = True
                    break
                else:
                    for idx in range(sum(d)+1):
                        count[idx] = count_tmp[idx]
                    ans_ += 1
                    res = 1
                    break
        if flag: break
        count_tmp = [0]*(sum(d)+1)
    if flag: continue
    ans_ += sum(d)
    ans = min(ans, ans_)
print(ans)

Submission status: Accepted

Solution code:
def z(z_dic, v: int):
    if v in z_dic:
        return z_dic[v]
    z = 0
    if v == 2:
        z = 1
    elif v > 2:
        z = int(v*(v-1)/2)
    z_dic.setdefault(v, z)
    return z


def main():
    h, w, _k = map(int, input().split())
    s = []
    for i in range(h):
        line = input()
        s_line = []
        for j in range(w):
            s_line.append(int(line[j]))
        s.append(s_line)

    ok_cnt_min = h*w
    op_cnt = h - 1  # すき間の個数
    for i in range(2 ** op_cnt):
        op = [False] * op_cnt
        for j in range(op_cnt):
            if ((i >> j) & 1):
                op[op_cnt - 1 - j] = True

        s2 =[]
        current_sum = s[0]
        for k in range(op_cnt):
            if op[k]:
                s2.append(current_sum)
                current_sum = s[k+1]
            else:
                next_sum = [(current_sum[a] + s[k+1][a]) for a in range(w)]
                current_sum = next_sum

        s2.append(current_sum)
        s2len = len(s2)

        h_cut_cnt = len([x for x in op if x])
        if h_cut_cnt >= ok_cnt_min:
            break

        st = 0
        ed = 1
        cut_list = []
        dividable = True
        for j in range(1, w+1):
            _sum_max = 0
            if ed <= j:
                ed = j
            else:
                continue

            _sum_max = max([sum(s2[_h][st:ed]) for _h in range(s2len)])
            if _sum_max > _k:
                if ed - st > 1:
                    cut_list.append(ed - 1)
                    st = ed - 1
                else:
                    dividable = False
                    break
        if not dividable:
            continue
        else:
            cnt = h_cut_cnt
            cnt += len(cut_list)
            if cnt < ok_cnt_min:
                ok_cnt_min = cnt

    print(ok_cnt_min)



main()