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: Time Limit Exceeded

Solution code:

#####

import numpy as np
from numpy import int32
# from collections import Counter

#####

def getIntList(inp):
	return [int(_) for _ in inp]


from sys import stdin
import sys
sys.setrecursionlimit(10**8)

def getInputs():
	inputs=[]
	for line in stdin:
		line=line.split()
		inputs.append(line)
	return inputs

def main(inputs):
	h,w,k=getIntList(inputs[0])
	
	grid=np.empty((h,w),np.bool)
	for hi in range(h):
		grid[hi]=np.array([c=="1" for c in inputs[1+hi][0]])
	
# 	h=10
# 	w=1000
# 	k=10
# 	grid=np.random.randint(0,2,(h,w))
	
# 	print(grid.astype(int32))
# 	print()
# 	from matplotlib import pyplot as plt
# 	plt.imshow(grid)
# 	plt.show()
	
	divideHs={}
	
	divideHNum=0
	mi=None
	for divideHNum in range(2**(h-1)):
		divideH=np.empty(h+1, np.bool)
		for hi in range(h): divideH[hi+1]=divideHNum & (2**hi)
		divideH[0]=True
		divideH[-1]=True
# 		print("divideH", divideHNum, divideH)
		indexH=np.where(divideH)[0]
		nums=np.empty((len(indexH)-1, w), int32)
		for i,ih in enumerate(indexH[:-1]):
			nums[i]=grid[indexH[i]:indexH[i+1]].sum(axis=0)
		
		divideHs[divideHNum]=len(indexH)-2
	
	main2(h, w, k, grid.astype(int32), divideHs)
	
		

def main2(H,W,K,S, divideHs):
	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):
	  divideHNum=0
	  for tii,ti in enumerate(t):
	    if ti==1: divideHNum=divideHNum|(1<<(tii))
	  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
	  cnt=divideHs[divideHNum]
	  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)



if __name__=="__main__":
	inputs=getInputs()
# 	inputs=simInputs()
	main(inputs)

Submission status: Time Limit Exceeded

Solution code:
H, W, K = map(int, input().split())
s = []
INF = (H - 1) + (W - 1)
ans = INF

def add(col: int):
    for i in range(g):
        now[i] += c[i][col]
    for i in range(g):
        if now[i] > K:
            return False
    return True

for _ in range(H):
    s.append(list(input()))

for div in range(1 << (H - 1)):
    g = 0
    id = [0] * H
    for i in range(H):
        id[i] = g
        if div >> i & 1:
            g += 1
    g += 1
    now = [0] * g
    num = g - 1
    c = [[0 for _ in range(W)] for _ in range(H)]

    for i in range(H):
        for j in range(W):
            c[id[i]][j] += int(s[i][j])

    for j in range(W):
        if not add(j):
            num += 1
            now = [0] * g

            if not add(j):
                num = INF
                break

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

S = np.array(S)

ans = (H-1)*(W-1)
for bit in range(1<<(H-1)):
    ok = True
    groups = [[0]]
    for i in range(H-1):
        if bit & (1<<i):
            groups.append([i+1])
        else:
            groups[-1].append(i+1)
    tot = bin(bit).count('1')
    N = len(groups)
    if tot >= ans:
        continue
    cnts = [0]*N
    for w in range(W):
        block = [sum([S[i,w] for i in M]) for M in groups]
        if any(block[i] > K for i in range(N)) or tot >= ans:
            ok = False
            break
        else:
            cnts = [cnts[i]+block[i] for i in range(N)]
            if any(cnt > K for cnt in cnts):
                tot += 1
                cnts = block
    if not ok:
        continue
    ans = min(ans, tot)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def e_dividing_chocolate():
    # 参考: https://note.com/tanon_cp/n/ne70a87d249ed
    H, W, K = [int(i) for i in input().split()]
    Choco = [list(input()) for _ in range(H)]

    # 左上のマスを (0, 0)、右下のマスを (col, row) としたとき、2 点で張られる
    # 長方形区間の内部に含まれる 1 (ホワイトチョコレートのマス) の数を累積和で管理
    cumsum = [[0] * W for _ in range(H)]
    for row in range(H):
        for col in range(W):
            if Choco[row][col] == '1':
                cumsum[row][col] += 1
            if row != 0:
                cumsum[row][col] += cumsum[row - 1][col]
            if col != 0:
                cumsum[row][col] += cumsum[row][col - 1]
            if row != 0 and col != 0:
                cumsum[row][col] -= cumsum[row - 1][col - 1]

    def count_white_chocolate(x1, y1, x2, y2):
        """左上のマスを (x1, y1)、右下のマスを (x2, y2) としたとき、2 点で張られる
        長方形区間の内部に含まれる 1 (ホワイトチョコレートのマス) の数"""
        ret = cumsum[y2][x2]
        if x1 != 0:
            ret -= cumsum[y2][x1 - 1]
        if y1 != 0:
            ret -= cumsum[y1 - 1][x2]
        if x1 != 0 and y1 != 0:
            ret += cumsum[y1 - 1][x1 - 1]
        return ret

    ans = (H - 1) + (W - 1)  # 1 マスに分けてしまえば要求を満たすことは保証されている
    # 横の切り方は全探索する
    for bits in range(1 << (H - 1)):
        count = 0  # 何回チョコに切り込みを入れたか？

        # 横の切り込みをどこに入れるかを決める
        cut_row = []
        cut_flag = format(bits, 'b')[::-1]
        for k, flag in enumerate(cut_flag):
            if flag == '1':
                count += 1
                # k 行目と (k+1) 行目の間を切るとき、長方形区間の最下段は k 行目
                cut_row.append(k)
        cut_row.append(H - 1)  # チョコ全体での最下段も加えておく

        # col1-col2 の間は切り込みを入れないでもホワイトチョコが K 個以下である
        col1 = 0
        for col2 in range(W - 1):
            row1 = 0
            for row2 in cut_row:
                if count_white_chocolate(col1, row1, col2, row2) > K:
                    count = float('inf')  # 現在の横の切り込みの入れ方では要求を満たせない

                # col2 列目と col2+1 列目の間に縦に切り込みを入れなければならない
                if (count_white_chocolate(col1, row1, col2, row2) <= K
                        and count_white_chocolate(col1, row1, col2 + 1, row2) > K):
                    # ここで縦に切り込みを入れ、右の区画へ移動
                    count += 1
                    col1 = col2 + 1
                    break
                row1 = row2 + 1  # 下の区画へ移動

        # 最後に縦に切り込みを入れた区画の右の区画はまだ調べていないので、調べる
        row1 = 0
        for row2 in cut_row:
            if count_white_chocolate(col1, row1, W - 1, row2) > K:
                count = float('inf')
            row1 = row2 + 1

        ans = min(ans, count)
    return ans

print(e_dividing_chocolate())

Submission status: Time Limit Exceeded

Solution code:

#####

import numpy as np
from numpy import int32
# from collections import Counter

#####

def getIntList(inp):
	return [int(_) for _ in inp]


from sys import stdin
import sys
sys.setrecursionlimit(10**8)

def getInputs():
	inputs=[]
	for line in stdin:
		line=line.split()
		inputs.append(line)
	return inputs


def main(inputs):
	h,w,k=getIntList(inputs[0])
	
# 	print("k",k)
	
	grid=np.empty((h,w),np.bool)
	for hi in range(h):
		grid[hi]=np.array([c=="1" for c in inputs[1+hi][0]])
	
# 	print(grid.astype(int32))
# 	print()
# 	from matplotlib import pyplot as plt
# 	plt.imshow(grid)
# 	plt.show()
	
	divideHNum=0
	mi=None
	for divideHNum in range(2**(h-1)):
		divideH=np.empty(h+1, np.bool)
		for hi in range(h): divideH[hi+1]=divideHNum & (2**hi)
		divideH[0]=True
		divideH[-1]=True
# 		print(divideH)
		indexH=np.where(divideH)[0]
		nums=np.empty((len(indexH)-1, w), int32)
		for i,ih in enumerate(indexH[:-1]):
			nums[i]=grid[indexH[i]:indexH[i+1]].sum(axis=0)
		
# 		print(indexH)	
# 		print(nums)
# 		print()
		
		cum=np.cumsum(nums, axis=1)
# 		print(cum)
		
		divideW=0
		divideWSize=0
		prevNext=0
		while divideW<w:
			next=np.where((cum>k).any(axis=0))[0]
# 			print("next",next)
			if len(next)==0: break
			next=next[0]
			if next==prevNext:
				divideWSize=None
				break
			divideWSize+=1
			cum-=cum[:,next-1,None]
# 			print(next)
# 			print(cum)
# 		print("divideWSize",divideWSize)
# 		print()
		
		if divideWSize is not None:
			divideSize=divideWSize+(len(indexH)-2)
			if mi is None or divideSize<mi: mi=divideSize
		
		divideHNum+=1
		
		
	print(mi)
			
	
		
	

if __name__=="__main__":
	inputs=getInputs()
# 	inputs=simInputs()
	main(inputs)

Submission status: Time Limit Exceeded

Solution code:
import math
import numpy as np

def main():
    h,w,k = tuple([int(t)for t in input().split()])

    s = [[int(i) for i in list(input())] for _ in range(h)]
    
    cusum = np.array([accumelist(s_) for s_ in s])

    candidates = []

    for i in range(1<<(h-1)):
        subcu = divide(cusum,i)
        subcusum = np.empty((0,w),int)

        for sub_ in subcu:
            subcusum = np.append(subcusum,np.sum(sub_,axis=0,keepdims=True),axis=0)

        cutnum = 0
        j=0
        temp = [0]*subcusum.shape[0]

        for j in range(w):
            for l in range(subcusum.shape[0]):
                if subcusum[l][j]-temp[l]>k:
                    temp = subcusum.T[j-1]
                    cutnum+=1
                    break
        
        candidates.append(cutnum+bin(i).count('1'))

    print(min(candidates))
            
def divide(s,i):
    subs = []
    counter = 0
    pos = 0
    while i!= 0:
        counter +=1
        if i%2==1:
            subs.append(s[pos:counter])
            pos = counter
        i >>=1
 
    subs.append(s[pos:])
    return subs

def accumelist(s):
    if s == []:
        return []
    res = [s[0]]
    for i in range(1,len(s)):
        res.append(res[i-1]+s[i])

    return res
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

S = np.array(S)

ans = (H-1)*(W-1)
for bit in range(1<<(H-1)):
    ok = True
    blocks = S[0].copy().reshape(1,-1)
    for i in range(H-1):
        if bit & (1<<i):
            blocks = np.r_[blocks, S[i+1].copy().reshape(1,-1)]
        else:
            blocks[-1] += S[i+1].copy()
    tot = bin(bit).count('1')
    N = len(blocks)
    if tot >= ans:
        continue
    cnts = np.zeros(N)
    for w in range(W):
        if (blocks[:,w] > K).any() or tot >= ans:
            ok = False
            break
        else:
            cnts += blocks[:,w].copy()
            if (cnts > K).any():
                tot += 1
                cnts = blocks[:,w].copy()
    if not ok:
        continue
    ans = min(ans, tot)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

S = np.array(S)

ans = (H-1)*(W-1)
for bit in range(1<<(H-1)):
    ok = True
    blocks = S[0].copy().reshape(1,-1)
    for i in range(H-1):
        if bit & (1<<i):
            blocks = np.r_[blocks, S[i+1].copy().reshape(1,-1)]
        else:
            blocks[-1] += S[i+1].copy()
    tot = bin(bit).count('1')
    N = len(blocks)
    if tot >= ans:
        continue
    cnts = np.zeros(N)
    for w in range(W):
        if (blocks[:,w] > K).any():
            ok = False
            break
        else:
            cnts += blocks[:,w].copy()
            if (cnts > K).any():
                tot += 1
                cnts = blocks[:,w].copy()
    if not ok:
        continue
    ans = min(ans, tot)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
h, w, k = [int(i) for i in input().split()]
choco = ([input() for j in range(h)])
ans = float("inf")

for i in itertools.product([0,1], repeat=h-1):
    list_yoko = []
    list_temp = []
    list_temp.append(0)
    for j in range(h-1):
        if i[j] == 1:
            list_yoko.append(list_temp)
            list_temp = []
            list_temp.append(j+1)
        else:
            list_temp.append(j+1)
    else:
        list_yoko.append(list_temp)


    count = 0
    count_list = [0 for _ in range(len(list_yoko))]

    for j in range(w):
        count_list_ = [0 for _ in range(len(list_yoko))]

        for m in range(len(list_yoko)):
            for l in list_yoko[m]:
                count_list_[m] += int(choco[l][j])

        if max(count_list) > k :
            count = float("inf")

        else:
            if max([count_list[_] + count_list_[_] for _ in range(len(list_yoko))]) > k:
                count += 1
                count_list = count_list_[:]

            else:
                count_list = [count_list[_] + count_list_[_] for _ in range(len(list_yoko))]

    ans = min(count+sum(i), ans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w,k =map(int,input().split())
ma = []
for i in range(h):
    ma.append(list(map(int,list(input()))))
ans = [0]*2**(h-1)
for i in range(2**(h-1)):
    idx = [0]*h #縦の何枚目か
    group = 0
    for j in range(h):
        idx[j] = group
        if (i>>j & 1):
            group +=1
    ans[i] += idx[-1]#h方向の分割
    n = idx[-1]+1#縦に何枚あるか
    cnt = [0]*n ##各ブロックの白チョコの数
    div_w = 0 #w方向の分割
    for e in range(w):
        temp = [0]*n #一時的な列を保存
        for j in range(h):
            p = idx[j]
            cnt[p] += ma[j][e]
            temp[p] += ma[j][e]
        if max(cnt) >k:
            div_w +=1
            cnt = temp
        if max(temp) >k:#この時h方向の分割そのものがだめ
            div_w = 10**9
            break
    ans[i] += div_w
print(min(ans))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

from copy import deepcopy
import numpy as np

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

S = [None] * H
for i in range(H):
    S[i] = list(map(int, list(input())))
# S = np.array(S)

h_sep_list = []


def allsum(A):
    ans = 0
    for a in A:
        for n in a:
            ans += n
    
    return ans


def rec(start_i, now_i, sep_list, H):
    # print(start_i, now_i)
    # print(sep_list)
    # print()
    if now_i == H-1:
        sep_list.append(S[start_i:])
        h_sep_list.append(sep_list)
        # print(h_sep_list)
        return None

    sep_list1 = deepcopy(sep_list)
    sep_list2 = deepcopy(sep_list)

    sep_list1.append(S[start_i: now_i+1])
    rec(now_i+1, now_i+1, sep_list1, H)

    rec(start_i, now_i+1, sep_list2, H)


def main():

    # h_sep_listに縦方向全ての場合の分割を保持
    rec(0, 0, [], H)
    
    # for k in range(len(h_sep_list)):
    #     # h_sep_list[k] = np.array(h_sep_list[k])
    #     print(h_sep_list[k])
    
    # print(h_sep_list)

    flag = False

    ans_list = [len(h_sep)-1 for h_sep in h_sep_list]
    for k, h_sep in enumerate(h_sep_list):
        accumulation = [None] * len(h_sep)
        # print(k, ans_list)
        
        i = 0
        while i < W:
            # j = i+1
            for m, bar in enumerate(h_sep):
                # print(h_sep)
                bar = np.array(bar)
                # print(bar)
                # block = bar[:, i: j]
                block = bar[:, i]
                # print(block, i, i+1)
                accumulation[m] = sum([cell for cell in bar[:, i]])
                # print(accumulation)
                # input()
                if accumulation[m] > K:
                    ans_list[k] = 10**10
                    # print(ans_list)
                    flag = True
                    break
            if flag:
                flag = False
                break
            # print("j=i+1 clear")
                    
            for j in range(i+2, W+1):
                for m, bar in enumerate(h_sep):
                    # print(h_sep)
                    bar = np.array(bar)
                    # print(bar)
                    # block = bar[:, i: j]
                    # print(bar)
                    # bar = np.array([[1, 1, 1, 1, 1], [0, 0, 0, 0, 0]])
                    # print(bar)
                    # print(bar[:, j-1])
                    # for row in bar[:, j-i]:
                    #     print(row)
                    #     exit()
                    accumulation[m] += sum([cell for cell in bar[:, j-1]])
                    # print(accumulation)
                    # print(bar[:, j-1], i, j)
                    # input()
                    if accumulation[m] > K:
                        ans_list[k] += 1
                        # print(ans_list)
                        i = j-1
                        flag = True
                        break
                if flag:
                    break
            if j == W:
                flag = False
                break
            
            if flag:
                flag = False
            else:
                i += 1
    
    return min(ans_list)


print(main())

Submission status: Time Limit Exceeded

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

h, w, K = [int(x) for x in input().split()]
s = [input().rstrip() for _ in range(h)]

ans = h + w - 2
for i in range(2 ** (h - 1)):
    new_s = []
    cnt = 0
    i_bin = bin(i)[2:].zfill(h - 1)
    add = []
    for j in range(h - 1):
        if i_bin[j] == "1":
            cnt += 1
            add.append(s[j])
            new_s.append(add)
            add = []
        else:
            add.append(s[j])
        if j == h - 2:
            add.append(s[-1])
            new_s.append(add)
    if h == 1:
        new_s = [s]
    total = [0] * len(new_s) # ブロックごとに、切った後~進んだ分の増えたホワイトチョコの個数を管理
    for k in range(w):
        tmp_list = [0]*len(new_s) # ブロックごとに、1つ進めて増えるホワイトチョコを管理
        flag = 0
        for l in range(len(new_s)):
            tmp = sum([int(new_s[l][x][k]) for x in range(len(new_s[l]))])
            if tmp > K:
                flag = 1
                break
            tmp_list[l] = tmp
            total[l] += tmp
        if flag:
            break
        for m in total: # 1つでもKを越えていたら直前で切る
            if m > K:
                cnt += 1
                total = tmp_list
                break
    if not flag:
        ans = min(ans, cnt)
print(ans)

Submission status: Time Limit Exceeded

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

h,w,k= map(int, input().split())
sn = [[-1 for i in range(h)] for i in range(w)]
for y in range(0,h):
    tmp = input()
    for x in range(0,w):
        sn[x][y] = int(tmp[x:x+1])
        sum_white = sn[x][y]

#sn_count = [[[[-1 for i in range(h)] for i in range(w)] for i in range(h)] for i in range(w)]

def countWhite(lineh, linew):
    global w,h,k,sn_count

    x_to=0
    y_to=0
    for areaw in range(0, len(linew) + 1):
        x_from = x_to
        if  areaw < len(linew):
            x_to = linew[areaw]-1
        else:
            x_to = w
        for areah in range(0, len(lineh) + 1):
            y_from = y_to
            if  areah < len(lineh):
                y_to = lineh[areah]-1
            else:
                y_to = h

            # キャッシュを参照
            #if sn_count[x_from][y_from][x_to-1][y_to-1] >= 0:
            #    if sn_count[x_from][y_from][x_to-1][y_to-1] > k:
            #        return False
            #    else:
            #        continue

            # 数え上げる
            count = 0
            for x in range (x_from,x_to):
                for y in range (y_from,y_to):
                    count += sn[x][y]
                    #sn_count[x_from][y_from][x_to-1][y_to-1] = count
                    if count > k:
                        return False
        # 上からに戻す
        y_to=0
    return True


def getLines(count,line_max,range_from=1):
    ret = []
    if count == 0:
        return [[]]
    for i in range(range_from,line_max+1):
        datas = []
        datas.append(i)
        while len(datas) != count:
            lines = getLines(count-1,line_max,i+1)
            if len(lines) > 0:
                for line in lines:
                    tmp = datas[:]
                    tmp.extend(line)
                    if(len(tmp) == count):
                        ret.append(tmp)
                break
            else:
                #
                break
        if len(datas) == count:
            ret.append(datas)

    return ret

if countWhite([],[]):
    print(0)
    exit()

# 一番効率的にわけたとしても以下の数だけエリアが必要
area_count_min = math.ceil(sum_white / k)

def setNextLineCount():
    global linew_count,lineh_count,line_count,area_count_min
    area_count = 0
    while area_count < area_count_min:
        linew_count += 1
        lineh_count -= 1
        if lineh_count < 0:
            line_count += 1
            if line_count >= 9:
                # H<=10なので
                lineh_count = 9
                linew_count = line_count - lineh_count
            else:
                lineh_count = line_count
                linew_count = 0
        area_count = (lineh_count +1) * (linew_count+1)

not_find_flg = True
line_count = lineh_count = linew_count =0
setNextLineCount()
while not_find_flg:
    linehs = getLines(lineh_count,h-1)
    linews = getLines(linew_count,w-1)
    for lineh in linehs:
        break2_flg = False
        for linew in linews:
            if countWhite(lineh,linew):
                not_find_flg = False
                break2_flg = True
                break
        if break2_flg:
            break

    if not_find_flg:
        # ラインの数の調整
        setNextLineCount()

print(line_count)

Submission status: Time Limit Exceeded

Solution code:
from operator import add
import sys
sys.setrecursionlimit(10 ** 7)

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


# 解説見た

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

# 全部のカットを試す
ans = 10 ** 5
for h in range(2 ** (H - 1)):
    # 分割できるか
    ok = False

    # 先に横の分割の数
    row = 1
    for i in range(H - 1):
        row += (h >> i) & 1

    num_cut = row - 1
    cnt = [0] * row

    #print("cut == ", h, "row == ", row)

    # 列は貪欲にカット
    for c in range(W):
        idx = 0
        tmp_cnt = [0] * row
        for r in range(H):

            if r != 0 and (h >> r - 1) & 1:
                idx += 1

            tmp_cnt[idx] += MEIJI[r][c]

        # チェック
        new_cnt = list(map(add, cnt, tmp_cnt))

        if any([K < x for x in new_cnt]):
            cnt = tmp_cnt
            num_cut += 1
        else:
            ok = True
            cnt = new_cnt

        #print("column:", c, tmp_cnt)

    if ok:
        ans = min(num_cut, ans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
#input = sys.stdin.buffer.readline
 
def main():
    H,W,K = map(int,input().split())
    a = S = [list(map(int, list(input()))) for _ in range(H)]
    
    ans = 10**6
    for i in range(1<<H-1):
        cut,count = [-1],0
        for j in range(H-1):
            if (i>>j)&1 != 0:
                count += 1
                cut.append(j)
        cut.append(H-1)
        l = len(cut)-1
        use = [[0 for _ in range(W)] for _ in range(l)]
        for x in range(l):
            up,down = cut[x],cut[x+1]
            for y in range(up+1,down+1):
                for z in range(W):
                    use[x][z] += a[y][z]

        bl,yorn = [0 for _ in range(l)],True
        for right in range(W):
            st = [0 for _ in range(l)]
            for x in range(l):
                st[x] += use[x][right]
            if max(st) > K:
                yorn = False
                break
            else:
                for x in range(l):
                    bl[x] += st[x]
                if max(bl) > K:
                    count += 1
                    bl = st
        if yorn:
            ans = min(ans,count)
    
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
h,w,k= map(int, input().split())
sn = [[-1 for i in range(h)] for i in range(w)]
for y in range(0,h):
    tmp = input()
    for x in range(0,w):
        sn[x][y] = int(tmp[x:x+1])

sn_count = [[[[-1 for i in range(h)] for i in range(w)] for i in range(h)] for i in range(w)]

def countWhite(lineh, linew):
    global w,h,k,sn_count

    x_to=0
    y_to=0
    for areaw in range(0, len(linew) + 1):
        x_from = x_to
        if  areaw < len(linew):
            x_to = linew[areaw]-1
        else:
            x_to = w
        for areah in range(0, len(lineh) + 1):
            y_from = y_to
            if  areah < len(lineh):
                y_to = lineh[areah]-1
            else:
                y_to = h

            # キャッシュを参照
            if sn_count[x_from][y_from][x_to-1][y_to-1] >= 0:
                if sn_count[x_from][y_from][x_to-1][y_to-1] > k:
                    return False
                else:
                    continue

            # 数え上げる
            count = 0
            for x in range (x_from,x_to):
                for y in range (y_from,y_to):
                    count += sn[x][y]
                    sn_count[x_from][y_from][x_to-1][y_to-1] = count
                    if count > k:
                        return False
        # 上からに戻す
        y_to=0


    return True


def getLines(count,line_max,range_from=1):
    ret = []
    if count == 0:
        return [[]]
    for i in range(range_from,line_max+1):
        datas = []
        datas.append(i)
        while len(datas) != count:
            lines = getLines(count-1,line_max,i+1)
            if len(lines) > 0:
                for line in lines:
                    tmp = datas[:]
                    tmp.extend(line)
                    if(len(tmp) == count):
                        ret.append(tmp)
                break
            else:
                break
        if len(datas) == count:
            ret.append(datas)

    return ret

if countWhite([],[]):
    print(0)
    exit()


not_find_flg = True
line_count = lineh_count = 1
linew_count = 0
while not_find_flg:
    linehs = getLines(lineh_count,h-1)
    linews = getLines(linew_count,w-1)
    for lineh in linehs:
        break2_flg = False
        for linew in linews:
            if countWhite(lineh,linew):
                not_find_flg = False
                break2_flg = True
                break
        if break2_flg:
            break

    if not_find_flg:
        linew_count += 1
        lineh_count -= 1
        if lineh_count < 0:
            line_count += 1
            if line_count >= 9:
                # H<=10なので
                lineh_count = 9
                linew_count = line_count - lineh_count
            else:
                lineh_count = line_count
                linew_count = 0

print(line_count)

Submission status: Time Limit Exceeded

Solution code:
import sys
#input = sys.stdin.buffer.readline
 
def main():
    H,W,K = map(int,input().split())
    a = [list(input()) for _ in range(H)]
    
    for i in range(H):
        for j in range(W):
            a[i][j] = int(a[i][j])
    
    ans = 10**6
    for i in range(1<<H-1):
        cut,count = [-1],0
        for j in range(H-1):
            if (i>>j)&1 != 0:
                count += 1
                cut.append(j)
        cut.append(H-1)
        l = len(cut)-1
        use = [[0 for _ in range(W)] for _ in range(l)]
        for x in range(l):
            up,down = cut[x],cut[x+1]
            for y in range(up+1,down+1):
                for z in range(W):
                    use[x][z] += a[y][z]

        bl,yorn = [0 for _ in range(l)],True
        for right in range(W):
            st = [0 for _ in range(l)]
            for x in range(l):
                st[x] += use[x][right]
            if max(st) > K:
                yorn = False
                break
            else:
                for x in range(l):
                    bl[x] += st[x]
                if max(bl) > K:
                    count += 1
                    bl = st
        if yorn:
            ans = min(ans,count)
    
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
import numpy as np
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
	H, W, K = MAP()
	S = np.array([list(map(int, list(input()))) for _ in range(H)])

	ans = INF
	for x in product([0, 1], repeat=H-1):
		cut = np.sum(x)
		if cut >= ans:
				continue
		if np.any(x):
			lis = np.zeros((H, W+1))
			tmp_lis = np.zeros((W))
			idx = 0
			for i, n in enumerate(x):
				tmp_lis += S[i]
				if n:
					lis[idx][1:] += tmp_lis
					idx += 1
					tmp_lis = np.zeros((W))
					
			if H >= 2:
				tmp_lis += S[-1]
				lis[idx][1:] += tmp_lis
			if np.any(lis>K):
				continue
			lis = lis.cumsum(axis=1)
		else:
			lis = np.sum(S, axis=0)
			tmp = 0
			for n in lis:
				if n > K:
					cut = INF
					break
				tmp += n
				if tmp > K:
					cut += 1
					tmp = n
			ans = ans if ans <= cut else cut
			continue
		idx = 0
		while idx <= W:
			tmp_idx = 1001
			flag = False
			for i in range(len(lis)):
				for j in range(idx, W+1):
					if lis[i][j]-lis[i][idx] > K:  # 1番最初にKを超えるところを探す
						tmp_idx = tmp_idx if tmp_idx <= j else j
						flag = True
			if not flag:
				break
			idx = tmp_idx-1
			cut += 1
			if cut >= ans:
				break
		ans = ans if ans <= cut else cut

	print(ans)

if __name__ == '__main__':
	main()