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 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]

        right,bl,yorn = 0,[0 for _ in range(l)],True
        while right < 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
                right += 1
        if yorn:
            ans = min(ans,count)
    
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import accumulate

readline = sys.stdin.readline
INF = 10 ** 9
h, w, k = map(int, readline().split())
s = [readline() for _ in range(h)]

ans = INF
for bit in range(2**h-1):
    cut = bin(bit).count('1')
    group = 0
    peace = [[0] * (bin(bit).count('1') + 1) for _ in range(w)]

    for i in range(w):
        group = 0
        for j in range(h):
            if s[j][i] == '1':
                peace[i][group] += 1
            if bit >> j & 1:
                group += 1

    if any(max(col) > k for col in peace):
        continue
    current = [0] * (bin(bit).count('1') + 1)
    for i in range(w):
        current = list(map(sum, zip(current, peace[i])))
        if max(current) > k:
            cut += 1
            current = peace[i]
    if ans > cut:
        ans = cut

print(ans)

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

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 = sum(x)
	if cut >= ans:
			continue
	if 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 (lis>K).sum():
			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 = min(ans, cut)
		continue
	idxs = []
	idx = 0
	while idx != W:
		for i in range(len(lis)):
			for j in range(idx, W+1):
				if lis[i][j]-lis[i][idx] > K:  # 1番最初にKを超えるところを探す
					idxs.append(j)

		if not idxs:  # 超えない
			break

		idx = min(idxs)-1
		idxs = []
		cut += 1
		if cut >= ans:
			break
	ans = min(ans, cut)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
input = sys.stdin.readline

def main():
    H, W, K = map(int, input().split())
    grid = [list(map(int, list(input().strip()))) for _ in range(H)]

    white_count = sum(sum(x) for x in grid)

    # 折れる箇所全部で折った数が最大値
    ans = (H - 1) * (W - 1)

    # 横線で割るパターン全てについて縦線での降り方を考える
    for i in range(2 ** (H - 1)):

        # 横方向に割った後のチョコの状態を生成
        snap = 0
        board = [[grid[0]]]
        for j in range(H-1):
            if ((i >> j) & 1):
                board.append([grid[j + 1]])
                snap += 1
            else:
                board[-1].append(grid[j + 1])

        w_count_board = [[] for _ in board]
        for x in range(W):
            # 縦方向に折るかのフラグ
            snap_flag = False
            for y, hori in enumerate(board):
                # その位置までおらなかった場合のチョコの個数を生成
                w_choco = sum(row[x] for row in hori)
                w_count_board[y].append(w_choco)

                # 上限超えたらおる
                if sum(w_count_board[y]) > K:
                    snap_flag = True

            # フラグがたってたら、x -1 まではおるので無視
            # チョコの個数カウントをx始まりで更新
            if snap_flag:
                w_count_board = [[wcb[-1]] for wcb in w_count_board]
                snap += 1

        ans = min(ans, snap)

    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

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 = sum(x)
	if 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 (lis>K).sum():
			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 = min(ans, cut)
		continue
	idxs = []
	idx = 0
	while idx != W:
		for i in range(len(lis)):
			for j in range(idx, W+1):
				if lis[i][j]-lis[i][idx] > K:  # 1番最初にKを超えるところを探す
					idxs.append(j)

		if not idxs:  # 超えない
			break

		idx = min(idxs)-1
		idxs = []
		cut += 1
	ans = min(ans, cut)

print(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):
        # print(k, ans_list)
        
        i = 0
        while i < W:
            # print("i: {}".format(i))

            j = i+1
            for bar in h_sep:
                # print(h_sep)
                bar = np.array(bar)
                # print(bar)
                block = bar[:, i: j]
                # print(block, i, j)
                # input()
                if allsum(block) > 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 bar in h_sep:
                    # print(h_sep)
                    bar = np.array(bar)
                    # print(bar)
                    block = bar[:, i: j]
                    # print(block, i, j)
                    # input()
                    if allsum(block) > 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:
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])

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

    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
            count = 0
            for x in range (x_from,x_to):
                for y in range (y_from,y_to):
                    count += sn[x][y]
                    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:
                # pr("lenelne")
                # pr(datas)
                # pr(lines)
                #
                # pr(datas)
                for line in lines:
                    tmp = datas[:]
                    tmp.extend(line)
                    if(len(tmp) == count):
                        ret.append(tmp)
                # pr(ret)
                break
            else:
                #
                break
        # pr(datas)
        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:
                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:
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])

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

    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
            count = 0
            for x in range (x_from,x_to):
                for y in range (y_from,y_to):
                    count += sn[x][y]
                    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:
                # pr("lenelne")
                # pr(datas)
                # pr(lines)
                #
                # pr(datas)
                for line in lines:
                    tmp = datas[:]
                    tmp.extend(line)
                    if(len(tmp) == count):
                        ret.append(tmp)
                # pr(ret)
                break
            else:
                #
                break
        # pr(datas)
        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
            lineh_count = line_count
            linew_count = 0

print(line_count)

Submission status: Time Limit Exceeded

Solution code:
H, W, K = map(int,input().split())
S = [list(map(int,input())) for _ in range(H)]
ans = float("inf")
for i in range(1<<(H - 1)):
    data = [S[0][0:]]
    for j in range(H - 1):
        if (i >> j) & 1:
            data.append([0] * W)
        for k in range(W):
            data[-1][k] += S[j + 1][k]
    if any([any([x > K for x in y]) for y in data]):
        continue
    cnt = len(data) - 1
    judge = [0] * len(data)
    for j in range(W):
        if any([judge[x] + data[x][j] > K for x in range(len(data))]):
            judge = [0] * len(data)
            cnt += 1
        judge = [judge[x] + data[x][j] for x in range(len(data))]
    ans = min(ans, cnt)
print(ans)

Submission status: Time Limit Exceeded

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

if True:
    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])
else:
    # h = 3
    # w = 5
    # k = 4
    # sn = [[1, 1, 0], [1, 0, 0], [1, 0, 1], [0, 0, 1], [0, 1, 1]]
    # h = 3
    # w = 5
    # k = 8
    # sn = [[1, 1, 0], [1, 0, 0], [1, 0, 1], [0, 0, 1], [0, 1, 1]]
    h = 4
    w = 10
    k = 4
    sn = [[1, 1, 0, 1], [1, 0, 0, 1], [1, 0, 1, 0], [0, 0, 1, 1], [0, 1, 1, 0], [1, 0, 0, 0], [0, 1, 1, 0], [0, 1, 0, 1], [1, 1, 0, 1], [0, 0, 1, 1]]


debug=False
def pr(data1,data2="",data3="",data4=""):
    global debug
    if debug:
        print("{},{},{},{}".format(str(data1),str(data2),str(data3),str(data4)))


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

    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
            pr(x_from,y_from,x_to,y_to)

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


    return True

if False:
    # 横方向のライン 1だったら0と1の間
    lineh = [2]
    # 縦方向のライン
    linew = [3]

    if countWhite(lineh,linew):
        pr("OK")
    else:
        pr("NG")

not_find_flg = True
line_count = 0
linew_count = 0
lineh_count = 0
# while not_find_flg:


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:
                # pr("lenelne")
                # pr(datas)
                # pr(lines)
                #
                # pr(datas)
                for line in lines:
                    tmp = datas[:]
                    tmp.extend(line)
                    if(len(tmp) == count):
                        ret.append(tmp)
                # pr(ret)
                break
            else:
                #
                break
        # pr(datas)
        if len(datas) == count:
            ret.append(datas)

    return ret

# print(getTmp(2,5))

# print(getLines(1, 4))
# exit()
if countWhite([],[]):
    pr("OK")
    print(0)
    exit()
else:
    pr("NG")


not_find_flg = True

line_count = lineh_count = 1
linew_count = 0
break2_flg = False
while not_find_flg:
    linehs = getLines(lineh_count,h-1)
    linews = getLines(linew_count,w-1)
    pr("lines h,w",linehs,linews)
    # pr(linehs)
    # exit()
    for lineh in linehs:
        for linew in linews:
            pr("line h,w",lineh,linew)
            if countWhite(lineh,linew):
                pr("OK")
                pr(linew)
                pr(lineh)
                not_find_flg = False
                break2_flg = True
            else:
                pr("NG")
        if break2_flg:
            break

    if not_find_flg:
        # ラインの数の調整
        pr(linew_count,lineh_count,line_count)
        linew_count += 1
        lineh_count -= 1
        if lineh_count < 0:
            line_count += 1
            lineh_count = line_count
            linew_count = 0

pr("line:::",linew,lineh)
print(line_count)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
H, W, K = map(int,input().split())
S = [list(map(int,input())) for _ in range(H)]
S = np.array(S)
ans = float("inf")
for i in range(1<<(H - 1)):
    data = np.array([[0] * W for _ in range(H)])
    data[0] += S[0]
    ind = 0
    for j in range(H - 1):
        if (i >> j) & 1:
            ind += 1
        data[ind] += S[j + 1]
    if np.max(data) > K:
        continue
    cnt = ind
    judge = np.array([0] * (ind + 1))
    for j in range(W):
        judge += data[:(ind + 1),j]
        if np.max(judge) > K:
            judge = np.array(data[:(ind + 1),j])
            cnt += 1
    ans = min(ans, cnt)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W,K = map(int, input().split())
S = []
ans = 10**9
for i in range(H):
  S.append(input())
for div in range(1<<(H-1)):
  ID = [0]*H
  g = 0
  for i in range(H):
    ID[i] = g
    if div>>i&1:
      g += 1
  g += 1
  c = [[0]*W for i in range(g)]
  for i in range(H):
    for j in range(W):
      if S[i][j]=='1':
        c[ID[i]][j] += 1
  num = g-1
  now = [0]*g
  def add(j):
    for i in range(g):
      now[i] += c[i][j]
    for i in range(g):
      if now[i]>K:
        return False
    return True
  for j in range(W):
    if not add(j):
      num += 1
      now = [0]*g
      if not add(j):
        num = 10**9
        break
  ans = min(ans,num)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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


min_cnt = H * W
for row_choice in range(2**(H-1)):
    S = np.copy(S_orig)
    row_splits = []
    for r in range(H-1):
        if (row_choice >> r) & 1:
            row_splits.append(r+1)
    if len(row_splits) >= min_cnt:
        continue
    splitted_rows = np.vsplit(S, row_splits)
    splitted_rows = np.array([np.sum(row, axis=0) for row in splitted_rows])
    splitted_rows_cum = np.hstack([np.zeros((splitted_rows.shape[0], 1), dtype=np.uint32), np.cumsum(splitted_rows, 1)])
    
    cnt = len(row_splits)
    start = 0
    for i in range(W+1):
        if (splitted_rows_cum[:, i] - splitted_rows_cum[:, start] > K).any():
        #if (splitted_rows[:, start: i].sum(axis=1) > K).any():
            start = i - 1
            cnt += 1
            if cnt == min_cnt:
                continue
    min_cnt = min([cnt, min_cnt])
    
print(min_cnt)

Submission status: Time Limit Exceeded

Solution code:
def main():
  h,*s=open(0)
  h,w,k=map(int,h.split())
  s=[list(map(int,t[:w]))for t in s]
  m=9e9
  for i in range(1<<h-1):
    t,v,l=[],0,1
    for j in range(h):
      if i>>j&1:
        t+=j+1,
        l+=1
    t+=h,
    c=[0]*l
    for i in range(w):
      b=f=g=0
      u=[]
      for j,x in enumerate(t):
        d,b=sum(s[j][i]for j in range(b,x)),x
        u+=d,
        if d>k:
          g=1
          break
        c[j]+=d
        f|=c[j]>k
      else:
        if f:
          c=u
          v+=1
      if g:break
    else:
      if v+l-1<m:m=v+l-1
  print(m)
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  h,*s=open(0)
  h,w,k=map(int,h.split())
  s=[list(map(int,t[:w]))for t in s]
  m=9e9
  for i in range(1<<h-1):
    t=[]
    b=v=l=0
    for j in range(h):
      if i>>j&1:
        t+=s[b:j+1],
        b=j+1
        l+=1
    t+=s[b:],
    l+=1
    c=[0]*l
    for i in range(w):
      f=g=0
      u=[]
      for j,d in enumerate(t):
        d=sum(d[i]for d in d)
        u+=d,
        if d>k:
          g=1
          break
        c[j]+=d
        f|=c[j]>k
      else:
        if f:
          c=u
          v+=1
      if g:break
    else:
      if v+l-1<m:m=v+l-1
  print(m)
main()

Submission status: Time Limit Exceeded

Solution code:
H, W, K = [int(i) for i in input().split()]
Shw = [[int(i) for i in input()] for _ in range(H)]
Swh = [[0 for _ in range(H)] for _ in range(W)]
for h in range(H):
  for w in range(W):
    Swh[w][h] = Shw[h][w]

def split_greedy(seps):
  splits = seps[:] + [H]
  n_s = len(splits)
  splits = [0] + splits
  hj = list(range(H))
  for j in range(n_s):
    for s in range(splits[j], splits[j+1]):
      hj[s] = j

  v_split = 0
  piece_counts = [0 for _ in range(n_s)]
  for w in range(W):
    col_counts = [0 for _ in range(n_s)]
    for h, j in enumerate(hj):
#      col_counts[j] += Shw[h][w]
      col_counts[j] += Swh[w][h]
    is_over = sum([p + c > K for p, c in zip(piece_counts, col_counts)]) > 0
    v_split += is_over
    piece_counts = [p * (1 - is_over) + c for p, c in zip(piece_counts, col_counts)]        
  return v_split

min_seps = H + W
for s in range(2**(H-1)):
  bins  = [int(i) for i in format(s, "0{}b".format(H-1))[::-1]]
  seps = [s + 1 for s, i in enumerate(bins) if i == 1]
  v_split = split_greedy(seps)
  n_seps = v_split + len(seps)
  min_seps = min(n_seps, min_seps)
print(min_seps)

Submission status: Time Limit Exceeded

Solution code:
def main():
  h,*s=open(0)
  h,w,k=map(int,h.split())
  s=[list(map(int,t[:w]))for t in s]
  m=9e9
  for i in range(1<<h-1):
    t=[]
    b=v=l=0
    for j in range(h):
      if i>>j&1:
        t+=s[b:j+1],
        b=j+1
        l+=1
    t+=s[b:],
    l+=1
    c=[0]*l
    for i in range(w):
      f=g=0
      u=[]
      for j in range(l):
        d=sum(t[i]for t in t[j])
        u+=d,
        if d>k:
          g=1
          break
        c[j]+=d
        f|=c[j]>k
      else:
        if f:
          c=u
          v+=1
      if g:break
    else:
      if v+l-1<m:m=v+l-1
  print(m)
main()

Submission status: Time Limit Exceeded

Solution code:
h,*s=open(0)
h,w,k=map(int,h.split())
s=[list(map(int,t[:w]))for t in s]
m=9e9
for i in range(1<<h-1):
  t=[]
  b=v=l=0
  for j in range(h):
    if i>>j&1:
      t+=s[b:j+1],
      b=j+1
      l+=1
  t+=s[b:],
  l+=1
  c=[0]*l
  for i in range(w):
    f=g=0
    u=[]
    for j in range(l):
      d=sum(t[i]for t in t[j])
      u+=d,
      if d>k:
        g=1
        break
      c[j]+=d
      f|=c[j]>k
    else:
      v+=f
      if f:c=u
    if g:break
  else:m=min(m,v+l-1)
print(m)

Submission status: Time Limit Exceeded

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

def split_greedy(seps):
  splits = seps[:] + [H]
  n_s = len(splits)
  splits = [0] + splits
  hj = list(range(H))
  for j in range(n_s):
    for s in range(splits[j], splits[j+1]):
      hj[s] = j

  v_split = 0
  piece_counts = [0 for _ in range(n_s)]
  for w in range(W):
    col_counts = [0 for _ in range(n_s)]
    for h, j in enumerate(hj):
      col_counts[j] += Shw[h][w]
    is_over = sum([p + c > K for p, c in zip(piece_counts, col_counts)]) > 0
    v_split += is_over
    piece_counts = [p * (1 - is_over) + c for p, c in zip(piece_counts, col_counts)]        
  return v_split

min_seps = H + W
for s in range(2**(H-1)):
  bins  = [int(i) for i in format(s, "0{}b".format(H-1))[::-1]]
  seps = [s + 1 for s, i in enumerate(bins) if i == 1]
  v_split = split_greedy(seps)
  n_seps = v_split + len(seps)
  min_seps = min(n_seps, min_seps)
print(min_seps)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from itertools import product

h, w, k = map(int, input().split())
s = np.array([list(map(int, input())) for _ in range(h)], dtype=np.int16)


def hsplit(pat):
    prev = 2
    ret = np.zeros((h + 1, w), dtype=np.int16)
    white = np.zeros(w, dtype=np.int16)
    cnt = 0
    for i, e in enumerate(pat):
        if e == prev:
            white += s[i]
        else:
            ret[cnt] = white.copy()
            white = s[i].copy()
            cnt += 1

        prev = e

    ret[cnt] = white.copy()
    cnt += 1

    return ret[1:cnt]


def greedy(arr):
    acc = np.zeros_like(arr, dtype=np.int16)
    ww = arr.shape[1]
    cnt = 0
    for i in range(ww):
        if i == 0:
            acc[:, i] = arr[:, i]
        else:
            acc[:, i] = acc[:, i-1] + arr[:, i]

        if acc[:, i].max() > k:
            cnt += 1
            acc[:, i] = arr[:, i]

    return cnt


ans = float("inf")
for pat in product([0, 1], repeat=h):
    if pat[0]:
        break

    hsp = hsplit(pat)

    if hsp.max() > k:
        continue

    wsp_cnt = greedy(hsp)
    hsp_cnt = hsp.shape[0] - 1

    cnt = hsp_cnt + wsp_cnt
    ans = min(ans, cnt)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
h, w, kkk = map(int, input().split())
choco = [0]*h
for i in range(h):
  choco[i] = input()
answer = h+w-2
for i in range(max([2**(h-1), 1])):
  flag = True
  board = [0]*(h-1)
  for j in range(h-1):
    if (i >> j)&1:
      board[j] = 1
  count = sum(board)
  key = [0]*(count+1)
  ans = count
  for p in range(w):
    max_board = [0]*(count+1)
    k = 0
    for q in range(h):
      if choco[q][p] == "1":
        max_board[k] += 1
      if q == h-1:
        if max(max_board) > kkk:
          flag = False
        break
      if board[q] == 1:
        k += 1
  if not flag:
    continue
  for p in range(w):
    k = 0
    for q in range(h):
      if choco[q][p] == "1":
        key[k] += 1
      if q == h-1:
        break
      if board[q] == 1:
        k += 1
    for u in range(count+1):
      if key[u] <= kkk:
        continue
      ans += 1
      key = [0]*(count+1)
      k = 0
      for q in range(h):
        if choco[q][p] == "1":
          key[k] += 1
        if q == h-1:
          break
        if board[q] == 1:
          k += 1
      break
  if ans < answer and flag:
    answer = ans
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from itertools import product

h, w, k = map(int, input().split())
s = np.array([list(map(int, input())) for _ in range(h)], dtype=np.int32)


def hsplit(pat):
    prev = 2
    ret = np.zeros((h + 1, w), dtype=np.int32)
    white = np.zeros(w, dtype=np.int32)
    cnt = 0
    for i, e in enumerate(pat):
        if e == prev:
            white += s[i]
        else:
            ret[cnt] = white.copy()
            white = s[i].copy()
            cnt += 1

        prev = e

    ret[cnt] = white.copy()
    cnt += 1

    return ret[1:cnt]


def greedy(arr):
    acc = np.zeros_like(arr, dtype=np.int32)
    ww = arr.shape[1]
    cnt = 0
    for i in range(ww):
        if i == 0:
            acc[:, i] = arr[:, i]
        else:
            acc[:, i] = acc[:, i-1] + arr[:, i]

        if acc[:, i].max() > k:
            cnt += 1
            acc[:, i] = arr[:, i]

    return cnt


ans = float("inf")
for pat in product([0, 1], repeat=h):
    if pat[0]:
        break

    hsp = hsplit(pat)

    if hsp.max() > k:
        continue

    wsp_cnt = greedy(hsp)
    hsp_cnt = hsp.shape[0] - 1

    cnt = hsp_cnt + wsp_cnt
    ans = min(ans, cnt)

print(ans)