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:
# 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 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):
                cri = S[idxes[i]:idxes[i+1], r-1].sum()
                if l > 0:
                    cri -= S[idxes[i]:idxes[i+1], l-1].sum()
                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: Time Limit Exceeded

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 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):
                cri = S[idxes[i]:idxes[i+1], l:r].sum()
                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: Time Limit Exceeded

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

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)]
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 white[k] + sum(S_t[j][bh[k]:bh[k+1]]) > K:
        flag = True
        break
      white[k] += sum(S_t[j][bh[k]:bh[k+1]])
    if flag == False:
      j += 1
  min_cnt = min(cnt+len(bh)-2,min_cnt)
  
print(min_cnt)

Submission status: Time Limit Exceeded

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)]
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 white[k] + sum(S_t[j][bh[k]:bh[k+1]]) > K:
        flag = True
        break
      white[k] += sum(S_t[j][bh[k]:bh[k+1]])
    if flag == False:
      j += 1
  min_cnt = min(cnt+len(bh)-2,min_cnt)
  
print(min_cnt)

Submission status: Time Limit Exceeded

Solution code:
h, w, k = map(int, input().split())
C = [list(input()) for _ in range(h)]
# C[hCX][w]
ans = 10 ** 20
for s in range(2 ** (h - 1)):
    yoko = bin(s).count("1")
    white = [0] * (yoko + 2)
    cnt = 0
    # 横分割を足しておく
    cnt += yoko
    outflag = 0
    for j in range(w):
        now = 0
        for i in range(h):
            if outflag:
                break
            white[now] += int(C[i][j])
            if white[now] > k:
                # 縦分割をする時はkを超えた時。
                # kを超えたら1つ前で割ったことにするので、
                # その列をもう1回やり直す必要あり
                cnt += 1
                # 同じjのところをi=[0,i]までやり直す
                # 初期化
                white = [0] * (yoko + 2)
                now = 0
                # 0からiまでやり直す
                for t in range(i + 1):
                    white[now] += int(C[t][j])
                    if white[now] > k:
                        outflag = 1
                        break
                    if (s >> t) & 1 == 1:
                        now += 1
                continue
            if (s >> i) & 1 == 1:
                now += 1
        if outflag:
            break
    if outflag:
        outflag = 0
        continue
    ans = min(cnt, ans)
print(ans)

Submission status: Time Limit Exceeded

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 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 str(is_cut) == '1':
			pp.append(o)
			o = mm[index_i+1]
		else:
			o = 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 = list(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
			#pa(rr)
			#pa(cut_info)
		
	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: Time Limit Exceeded

Solution code:
def lis():return list(map(str,input().split()))
def inp():return map(int,input().split())
 
#import collections
#choco=collections.deque()
H,W,K=inp()
li=[]
white=0
for i in range (H):
    s=input()
    li.append(s)
    white+=li[i].count('1')
if white<=K:
    print(0)
    exit()
 
ans=H*W
for i in range(0,2**(H-1)):
    cut=bin(i)[2:]
    while len(cut)<H-1:
        cut='0'+cut
    sumh=cut.count('1') #先算出行中切的一刀总和
    cut+='0'         #最后一行默认值，方便后面切割操作
    #print(cut)
 
    suml=0
    l=0
    white=[0]*(sumh+1)
    #行如果一刀未切，需要一个累加器贪心，如果切了两刀，则需要三个累加器贪心
    while l<W:
        h=0
        t=0   #white的下标
        while h<H:
            if li[h][l]=='1':white[t]+=1
            if white[t]>K:#如果白巧克力超过K，则退回到当前列，在当前列增加一刀，行归零重新累加
                suml += 1
                l=l-1
                white=[0]*(sumh+1)   #当前增加一刀，退回当前列，重新计数
                break
            if cut[h]=='1':t+=1  #如果当前切了一刀，则换到下一个计数器
            h+=1
        l+=1
    ans=min(ans,sumh+suml)
print(ans)

Submission status: Time Limit Exceeded

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 get_n(rr, mm, k):
	ret = sum([int(c) for c in rr])
	o = mm[0]
	pp = []
	for index_i, is_cut in enumerate(rr):
		if str(is_cut) == '1':
			pp.append(o)
			o = mm[index_i+1]
		else:
			o = o+mm[index_i+1]
	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):
			#pa(pp[il][i]+ll[il])
			if pp[il][i] > k:
				return mod, None
			elif ll[il] + pp[il][i] > k:
				#pa((ll[il], pp[il][i]))
				ret += 1
				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():
	#a = int(input())
	h, w, k = tin()
	#s = input()
	mm=[]
	for _ in range(h):
		s = list(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)
		if tt < n:
			n = tt
			#pa(rr)
			#pa(cut_info)
		
	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: Time Limit Exceeded

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

ans = float("inf")

for pattern in product([0, 1], repeat = H - 1):
    div = [0] + [i for i, p in enumerate(pattern, 1) if p == 1] + [H]
    rows = []
    for i in range(len(div) - 1):
        row = []
        for j in range(W):
            tmp = 0
            for k in range(div[i], div[i + 1]):
                tmp += G[k][j]
            row.append(tmp)
        rows.append(row)
        
    flag = True
    for row in rows:
        if [r for r in row if r > K]:
            flag = False
            break
    if not flag:
        continue

    tmp_ans = 0
    cnt = [0] * len(rows)
    w = 0

    while w < W:
        for r in range(len(rows)):
            cnt[r] += rows[r][w]
        if [c for c in cnt if c > K]:
            cnt = [0] * len(rows)
            tmp_ans += 1
            w -= 1
        w += 1
    
    tmp_ans += pattern.count(1)
    ans = min(ans, tmp_ans)

print(ans)

Submission status: Time Limit Exceeded

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

ans = float("inf")

for pattern in product([0, 1], repeat = H - 1):
    div = [0] + [i for i, p in enumerate(pattern, 1) if p == 1] + [20]
    rows = []
    for i in range(len(div) - 1):
        rows.append(np.sum(G[div[i]: div[i + 1]], axis=0).tolist()) # 列方向

    flag = True
    for r in rows:
        if np.any(np.array(r) > K):
            flag = False
            break
    if not flag:
        continue

    tmp_ans = 0
    cnt = [0] * len(rows)
    w = 0

    while w < W:
        for r in range(len(rows)):
            cnt[r] += rows[r][w]
        if np.any(np.array(cnt) > K):
            cnt = [0] * len(rows)
            tmp_ans += 1
            w -= 1
        w += 1
    
    tmp_ans += pattern.count(1)
    ans = min(ans, tmp_ans)

print(ans)

Submission status: Time Limit Exceeded

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

ans = float("inf")

for pattern in product([0, 1], repeat = H - 1):
    div = [0] + [i for i, p in enumerate(pattern, 1) if p == 1] + [20]
    rows = []
    for i in range(len(div) - 1):
        rows.append(np.sum(G[div[i]: div[i + 1]], axis=0)) # 列方向

    flag = True
    for r in rows:
        if np.any(r > K):
            flag = False
            break
    if not flag:
        continue

    tmp_ans = 0
    cnt = [0] * len(rows)
    w = 0
    rows = [r.tolist() for r in rows]

    while w < W:
        for r in range(len(rows)):
            cnt[r] += rows[r][w]
        if np.any(np.array(cnt) > K):
            cnt = [0] * len(rows)
            tmp_ans += 1
            w -= 1
        w += 1
    
    tmp_ans += pattern.count(1)
    ans = min(ans, tmp_ans)

print(ans)

Submission status: Time Limit Exceeded

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

ans = float("inf")

for pattern in product([0, 1], repeat = H - 1):
    div = [0] + [i for i, p in enumerate(pattern, 1) if p == 1] + [20]
    rows = []
    for i in range(len(div) - 1):
        rows.append(np.sum(G[div[i]: div[i + 1]], axis=0)) # 列方向
    

    if [r for r in rows if np.any(r > K)]:
        continue

    tmp_ans = 0
    cnt = [0] * len(rows)
    w = 0
    rows = [r.tolist() for r in rows]

    while w < W:
        for r in range(len(rows)):
            cnt[r] += rows[r][w]
        if np.any(np.array(cnt) > K):
            cnt = [0] * len(rows)
            tmp_ans += 1
            w -= 1
        w += 1
    
    tmp_ans += pattern.count(1)
    ans = min(ans, tmp_ans)

print(ans)

Submission status: Time Limit Exceeded

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

ans = float("inf")

for pattern in product([0, 1], repeat = H - 1):
    div = [0] + [i for i, p in enumerate(pattern, 1) if p == 1] + [20]
    rows = []
    for i in range(len(div) - 1):
        rows.append(np.sum(G[div[i]: div[i + 1]], axis=0)) # 列方向

    tmp_ans = 0
    cnt = [0] * len(rows)
    w = 0
    flag = False
    rows = [r.tolist() for r in rows]

    while w < W:
        for r in range(len(rows)):
            cnt[r] += rows[r][w]
        if np.any(np.array(cnt) > K):
            if w == 0:
                flag = True
                break
            cnt = [0] * len(rows)
            tmp_ans += 1
            w -= 1
        w += 1
    
    if not flag:
        tmp_ans += pattern.count(1)
        ans = min(ans, tmp_ans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def lis():return list(map(str,input().split()))
def inp():return map(int,input().split())

#import collections
#choco=collections.deque()
H,W,K=inp()
li=[]
white=0
for i in range (H):
    s=input()
    li.append(s)
    white+=li[i].count('1')
if white<=K:
    print(0)
    exit()

ans=H*W
for i in range(0,2**(H-1)):
    cut=bin(i)[2:]
    while len(cut)<H-1:
        cut='0'+cut
    sumh=cut.count('1') #先算出行中切的一刀总和
    cut+='0'         #最后一行默认值，方便后面切割操作
    #print(cut)

    suml=0
    l=0
    white=[0]*(sumh+1)
    #行如果一刀未切，需要一个累加器贪心，如果切了两刀，则需要三个累加器贪心
    while l<W:
        h=0
        t=0   #white的下标
        while h<H:
            if li[h][l]=='1':white[t]+=1
            if white[t]>K:#如果白巧克力超过K，则退回到当前列，在当前列增加一刀，行归零重新累加
                suml += 1
                l=l-1
                white=[0]*(sumh+1)   #当前增加一刀，退回当前列，重新计数
                break
            if cut[h]=='1':t+=1  #如果当前切了一刀，则换到下一个计数器
            h+=1
        l+=1
    ans=min(ans,sumh+suml)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import product

import numpy as np

input = sys.stdin.readline


def main():
    H, W, K = map(int, input().split())
    S = np.zeros(shape=(H, W), dtype=np.uint16)
    for i in range(H):
        S[i] = list(map(int, input().rstrip()))

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

        # horizontal chocolates
        h_chocos = np.zeros(shape=(M, W), dtype=np.uint16)
        h = 0  # upper index
        m = 0
        for i, c in enumerate(comb):
            if c == 1:
                h_chocos[m] = np.sum(S[h:i+1, :], axis=0)
                h = i + 1
                m += 1
        h_chocos[m] = np.sum(S[h:, :], axis=0)

        total = np.zeros(shape=M, dtype=np.uint16)
        width = 0
        for w in range(W):
            total += h_chocos[:, w]
            width += 1
            if not np.all(total <= K):
                if width == 1:
                    n_cut = float("inf")
                    break
                n_cut += 1
                width += 1
                if n_cut >= ans:
                    break
                total = h_chocos[:, w]
        if n_cut < ans:
            ans = n_cut

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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
    while w < W:
        if np.any(Tcum[:, w] - (Tcum[:, prev] if prev >= 0 else 0) > K):
            if prev == w - 1:  # 1列でKをオーバー
                break
            cnt += 1
            prev = w - 1
        else:
            w += 1
    else:
        answer = min(answer, cnt)

print(answer)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
h,w,k=map(int,input().split())
s=np.array([list(map(int,list(input()))) for _ in range(h)])
def func(catyoko):
  cattate=0
  past=np.array([0]*10)
  now=np.array([0]*10)
  for wi in range(w):
    for i in range(1,len(catyoko)):
      now[i-1]=sum(s[catyoko[i-1]:catyoko[i],wi])
    if max(past+now)>k:
      if max(now)>k:
        return -10
      else:
        cattate+=1
      past=now.copy()
    else:
      past+=now
  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: Time Limit Exceeded

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.array([row.cumsum() for row in S])
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
    while w < W:
        if np.any(Tcum[:, w] - (Tcum[:, prev] if prev >= 0 else 0) > K):
            if prev == w - 1:  # 1列でKをオーバー
                break
            cnt += 1
            prev = w - 1
        else:
            w += 1
    else:
        answer = min(answer, cnt)

print(answer)

Submission status: Time Limit Exceeded

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)])
INF = 10 ** 10
answer = INF
for pattern in range(1<<H-1):
    cnt = 0
    T = S.copy()
    for i in range(H-1):
        if pattern>>i & 1:  # 切れ目
            cnt += 1
        else:
            T[i+1] += T[i]
    Tcum = np.array([row.cumsum() for row in T])
    prev = -1
    w = 0
    while w < W:
        cut = False
        if np.any(Tcum[:, w] - (Tcum[:, prev] if prev >= 0 else 0) > K):
            cut = True
        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: Time Limit Exceeded

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]):
                if cum>K:
                    go=False
                cum+=S[h][w]
            c[g]+=cum
            if cum+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: Time Limit Exceeded

Solution code:
def main():
    import numpy as np
    h, w, K = map(int, input().split())
    grid = np.array([list(map(int, list(input())))
                     for _ in [0]*h], dtype=np.int16)
    m = 10**9
    for i in range(2**(h-1)):
        i = (("0"*h)+bin(i)[2:])[-h:]
        memo = [0]+[j for j in range(1, h) if i[j-1] != i[j]]+[h]
        ans = len(memo)-1
        ans2 = [0]
        aa = ans2.append
        memo2 = [0]*ans
        j = 0
        flag = False
        while j < w:
            if flag:
                break
            p, l = memo[0], ans2[-1]
            for k, q in enumerate(memo[1:ans+1]):
                memo2[k] += np.sum(grid[p:q, j])
                p = q
                if memo2[k] > K:
                    aa(j)
                    memo2 = [0]*ans
                    if j == l:
                        flag = True
                    l = j
                    break
            else:
                j += 1
        if not flag:
            m = min(m, ans+(len(ans2)-2))
    print(m)


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import numpy as np
    h, w, K = map(int, input().split())
    grid = np.array([list(map(int, list(input())))
                     for _ in [0]*h], dtype=np.int16)
    m = 10**9
    for i in range(2**(h-1)):
        i = (("0"*h)+bin(i)[2:])[-h:]+"2"
        memo = [0]
        ma = memo.append
        [ma(j+1) for j in range(h) if i[j] != i[j+1]]
        ans = len(memo)-1
        ans2 = [0]
        aa = ans2.append
        memo2 = [0]*ans
        j = 0
        flag = False
        while j < w:
            if flag:
                break
            p, l = memo[0], ans2[-1]
            for k, q in enumerate(memo[1:ans+1]):
                memo2[k] += np.sum(grid[p:q, j])
                p = q
                if memo2[k] > K:
                    aa(j)
                    memo2 = [0]*ans
                    if j == l:
                        flag = True
                    l = j
                    break
            else:
                j += 1
        if not flag:
            m = min(m, ans+(len(ans2)-2))
    print(m)


main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import product

import numpy as np

input = sys.stdin.readline


def main():
    H, W, K = map(int, input().split())
    S = np.zeros(shape=(H, W), dtype=np.uint16)
    for i in range(H):
        S[i] = list(map(int, input().rstrip()))

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

        # horizontal chocolates
        h_chocos = np.zeros(shape=(M, W), dtype=np.uint16)
        h = 0  # upper index
        m = 0
        for i, c in enumerate(comb):
            if c == 1:
                h_chocos[m] = np.sum(S[h:i+1, :], axis=0)
                h = i + 1
                m += 1
        h_chocos[m] = np.sum(S[h:, :], axis=0)

        total = np.zeros(shape=M, dtype=np.uint16)
        for w in range(W):
            total += h_chocos[:, w]
            if not np.all(total <= K):
                n_cut += 1
                if n_cut >= ans:
                    break
                total = h_chocos[:, w]
        if n_cut < ans:
            ans = n_cut

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import product

import numpy as np

input = sys.stdin.readline


def main():
    H, W, K = map(int, input().split())
    S = np.zeros(shape=(H, W), dtype=np.uint8)
    for i in range(H):
        S[i] = list(map(int, input().rstrip()))

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

        # horizontal chocolates
        h_chocos = np.zeros(shape=(M, W), dtype=np.uint16)
        h = 0  # upper index
        m = 0
        for i, c in enumerate(comb):
            if c == 1:
                h_chocos[m] = np.sum(S[h:i+1, :], axis=0)
                h = i + 1
                m += 1
        h_chocos[m] = np.sum(S[h:, :], axis=0)

        total = np.zeros(shape=M, dtype=np.uint16)
        for w in range(W):
            total += h_chocos[:, w]
            if not np.all(total <= K):
                n_cut += 1
                total = h_chocos[:, w]
        if n_cut < ans:
            ans = n_cut

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
if __name__ == "__main__":
    h, w, k = map(int, input().split())
    s = []

    for _ in range(h):
        si = input()
        s.append(si)
    
    h_split = [0] * (h - 1)
    part = 0
    ans = float('inf')
    for mask in range(1 << (h - 1)):
        g = 0
        g_id = [0] * h
        for i in range(h):
            g_id[i] = g
            if mask >> i & 1 == 1:
                g += 1
        g += 1

        c = []
        for _ in range(g):
            c.append([0] * w)
        
        for i in range(h):
            for j in range(w):
                if s[i][j] == "1":
                    c[g_id[i]][j] += 1
        num = g - 1
        now = [0] * g

        for j in range(w):
            for i in range(g):
                now[i] += c[i][j]
            ok = True
            for i in range(g):
                if now[i] > k:
                    ok = False

            if not ok:
                num += 1
                now = [0] * g
                for i in range(g):
                    now[i] += c[i][j]
                ok = True
                for i in range(g):
                    if now[i] > k:
                        ok = False
                if not ok:
                    num = float('inf')
                    break
        ans = min(ans, num)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import product

import numpy as np

input = sys.stdin.readline


def main():
    H, W, K = map(int, input().split())
    S = np.zeros(shape=(H, W), dtype=np.uint8)
    for i in range(H):
        S[i] = list(map(int, input().rstrip()))

    ans = float("inf")
    for comb in product(range(2), repeat=H-1):
        h_chocos = []  # horizontal chocolates
        h = 0  # upper index
        for i, c in enumerate(comb):
            if c == 1:
                h_chocos.append(np.sum(S[h:i+1, :], axis=0))
                h = i + 1
        h_chocos.append(np.sum(S[h:, :], axis=0))

        n_cut = sum(comb)
        M = len(h_chocos)
        total = [0] * M
        for w in range(W):
            for i in range(M):
                total[i] += h_chocos[i][w]
            if not all(t <= K for t in total):
                n_cut += 1
                total = [0] * M
                for i in range(M):
                    total[i] += h_chocos[i][w]
        if n_cut < ans:
            ans = n_cut

    print(ans)


if __name__ == "__main__":
    main()