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:
h, w, k = map(int, input().split())
s = [list(map(int, list(input()))) for _ in range(h)]
result = []
for i in range(2**(h-1)):
    checker = format(i, "0"+str(h)+"b").count("1")
    x = 0
    c = [0 for _ in range(checker+1)]
    for j in range(w):
        num = i
        p = 0
        nex = [0 for _ in range(checker+1)]
        for m in range(h):
            nex[p] += s[m][j]
            p += num%2
            num = num >> 1
        
        if all(nex[m]+c[m] <= k for m in range(checker+1)):
            c = [c[I]+nex[I] for I in range(checker+1)]
        else:
            x += 1
            c = nex
    result.append(checker+x)
print(min(result))

Submission status: Time Limit Exceeded

Solution code:
# not resolved

H, W, K = [int(i) for i in input().split()]
array = []

for _ in range(H):
	line = [int(choco) for choco in list(input())]
	array.append(line)

h_split = H - 1
line = [0 for _ in range(W)]

ans = 100000000000

for div in range(1 << h_split):
	g = 0
	id = [0 for _ in range(H)]
	for i in range(H):
		id[i] = g
		if div >> i & 1: 
			g +=  1
	w_choco = [[0 for _ in range(W)] for _ in range(H)]

	for i in range(H):
		for j in range(W):
			w_choco[id[i]][j] +=  array[i][j]

	start = 0
	cnt = 0
	for w_split in range(1, W):
		for h in range(g+1):
			if sum(w_choco[h][start:w_split+1]) > K:
				cnt += 1
				start = w_split 

	
	num = cnt + g 
	if ans > num:
		ans = num
	
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# not resolved

import numpy as np

H, W, K = [int(i) for i in input().split()]
array = []

for _ in range(H):
	line = [int(choco) for choco in list(input())]
	array.append(line)

h_split = H - 1
line = [0 for _ in range(W)]

ans = 100000000000

for div in range(1 << h_split):
	g = 0
	id = [0 for _ in range(H)]
	for i in range(H):
		id[i] = g
		if div >> i & 1: 
			g +=  1
	w_choco = [[0 for _ in range(W)] for _ in range(H)]
	w_choco = np.array(w_choco)
	for i in range(H):
		w_choco[id[i]] +=  np.array(array[i])

	start = 0
	cnt = 0
	for w_split in range(1, W):
		for h in range(g+1):
			if np.sum(w_choco[h, start:w_split+1]) > K:
				cnt += 1
				start = w_split 

	
	num = cnt + g 
	if ans > num:
		ans = num
	
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# not resolved

import numpy as np

H, W, K = [int(i) for i in input().split()]
array = []

for _ in range(H):
	line = [int(choco) for choco in list(input())]
	array.append(line)

h_split = H - 1
line = [0 for _ in range(W)]

ans = 100000000000000

for div in range(1 << h_split):
	g = 0
	id = [0 for _ in range(H)]
	for i in range(H):
		id[i] = g
		if div >> i & 1: 
			g +=  1
	w_choco = [[0 for _ in range(W)] for _ in range(H)]
	w_choco = np.array(w_choco)
	for i in range(H):
		w_choco[id[i]] +=  np.array(array[i])

	start = 0
	cnt = 0
	for w_split in range(1, W):
		for h in range(H):
			if np.sum(w_choco[h, start:w_split+1]) > K:
				cnt += 1
				start = w_split 

	
	num = cnt + g 
	if ans > num:
		ans = num
	
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# Problem E - Dividing Chocolate

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

# initialization
min_divide = 10**10
s = [0]*(H-1) # 横線の入り方 0:無 1:有
is_ok = True

# search
for i in range(2**(H-1)): # bit全探索
    # sの初期化
    h_count = 0
    w_count = 0
    for j in range(H-1):
        if ((i>>j)&1):
            s[j] = 1
            h_count += 1
        else:
            s[j] = 0

    # 列の全探索
    s_score = [0]*H # 各区域のスコア
    s_cur = [0]*H
    for j in range(W):
        c = 0
        s_cur = [0]*H

        for k in range(H):
            if board[k][j]=='1':
                s_cur[c] += 1

            # Kを超えていないかのチェック
            if s_cur[c]>K:
                is_ok = False
                break

            # 次の遷移先(横線の有無でグループが別れる)
            if k+1<H:
                if s[k]==1:
                    c += 1
        # Kを超えていたらループ中止
        if not is_ok:
            break
        # 前の列のグループと足してみてKを超えていないかチェック
        # 超えていれば縦線分割を施す
        group_smaller = True
        if j>0:
            for c_num in range(c+1):
                if s_score[c_num]+s_cur[c_num]>K:
                    group_smaller = False
        else:
            group_smaller = True

        if group_smaller:
            for c_num in range(c+1):
                s_score[c_num] += s_cur[c_num]
        else:
            w_count += 1
            for c_num in range(c+1):
                s_score[c_num] = s_cur[c_num]

    if not is_ok:
        is_ok = True
        continue

    # for c_num in range(h_count+1):
    #     if s_score[c_num]>K:
    #         h_count = 10 ** 6

    # 縦線と横線の合計でmin_divideを更新
    min_divide = min(min_divide, w_count + h_count)

# output
print(min_divide)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import itertools

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

S = np.array([list(map(int, input())) for _ in range(H)])
s = np.zeros((H, W), dtype = int)
v = np.zeros(H, dtype = int)
ans_list = []

for pattern in itertools.product((True, False), repeat = H - 1):
    column = 0
    s[:, :] = 0
    for i in range(H - 1):
        if pattern[i] == False:
            s[column] += S[i]
        else:
            s[column] += S[i]
            column += 1
    s[column] += S[H - 1]

    if np.any(s > K):
        continue

    v[:] = 0
    count = sum(pattern)
    for i in range(W):
        v = v + s[:, i]
        if np.any(v > K):
            count += 1
            v = s[:, i].copy()

    ans_list.append(count)

ans = min(ans_list)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numpy as np

H, W, K = map(int, input().split())
grid = np.array([list(map(int, list(input()))) for _ in range(H)], dtype=np.int32)
min_cost = None


for H_div_pattern in itertools.product([0, 1], repeat=H-1):
    H_div_num = [i+1 for i, j in enumerate(H_div_pattern) if j == 1] + [H]
    sum_grid = np.zeros((len(H_div_num), W), dtype=np.int32)
    if len(H_div_num) != 0:
        start_H = 0
        for idx, div_num in enumerate(H_div_num):
            for w in range(W):
                sum_grid[idx, w] = np.sum(grid[start_H:div_num, w])
            start_H = div_num
    
    cost = len(H_div_num) - 1
    
    block_cost = sum_grid[:, 0]
    for w in range(1, W):
        tmp = sum_grid[:, w] + block_cost
        if (tmp <= K).all():
            block_cost = tmp
        else:
            block_cost = sum_grid[:, w]
            cost += 1
    
    if min_cost is None or min_cost > cost:
        min_cost = cost
    
print(min_cost)

Submission status: Time Limit Exceeded

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

ans=H*W
for row in range(1<<(H-1)):
    row_cut = str(bin(row))[2:].count("1")
    splits = [grid[0]]
    for i in range(H-1):
        if row & (1<<i):
            splits.append(grid[i+1][:])
        else:
            splits[-1]=[splits[-1][j]+grid[i+1][j] for j in range(W)]

    if any(max(v.count("1") for v in s)>S for s in splits):
        continue

    count=[[] for _ in range(len(splits))]
    for i,s in enumerate(splits):
        for v in s:
            count[i].append(v.count("1"))

    col_cut=0
    tmp_cnt=[count[i][0] for i in range(len(splits))]
    for i in range(1,W):
        merged_cnt=[tmp_cnt[j]+count[j][i] for j in range(len(splits))]
        if max(merged_cnt)>S:
            col_cut+=1
            tmp_cnt =[count[j][i] for j in range(len(splits))]
        else:
            tmp_cnt=merged_cnt
    ans = min(ans,col_cut+row_cut)


print(ans)

Submission status: Time Limit Exceeded

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

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
inf = 100100100
ans = inf
H, W, K = map(int, input().split())
S = []
for _ in range(H):
    S.append([int(x) for x in input()])
S = np.array(S)
for i in range(2**(H-1)):
    group = [0]
    g = 0
    for j in range(H-1):
        if (i >> j) & 1:
            g += 1
        group.append(g)
    group = np.array(group)
    g += 1
    c = np.array([[0]*W]*g)
    for j in range(H):
        for k in range(W):
            c[group[j],k] += S[j,k]
    num = g-1
    now = np.zeros(g)
    def large(now):
        for n in now:
            if n > K:
                return True
        else:
            return False
    for k in range(W):
        now += c[:,k]
        if large(now):
            now = c[:,k]
            num += 1
            if large(now):
                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 = []
inf = 100000
ans = inf
for i in range(H):
    S.append([int(x) for x in input()])
S = np.array(S)
for i in range(2**(H-1)):
    hlis = [0]
    for j in range(H-1):
        if ((i>>j) & 1):
            hlis.append(j+1)
    hlis.append(H)
    hlis = np.array(hlis)
    wkireme = 0
    numwkireme = 0
    Flag1 = True
    Flag2 = True
    w = 1
    while Flag1:
        for n in range(len(hlis)-1):
            s = np.sum(S[hlis[n]:hlis[n+1],wkireme:wkireme+w])
            if s > K:
                if w == 1:
                    Flag2 = False
                    Flag1 = False
                    break
                else:
                    wkireme = wkireme + w -1
                    numwkireme += 1
                    w = 1
                    break
        else:
            if wkireme + w >= W:
                Flag1 = False
            else:
                w += 1
    if Flag2:
        ans = min(ans, numwkireme + len(hlis) -2)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W, K = map(int, input().split())
S = []
inf = 100000
ans = inf
for _ in range(H):
    S.append([int(x) for x in input()])
for i in range(2**(H-1)):
    hlis = [0]
    for j in range(H-1):
        if ((i>>j) & 1):
            hlis.append(j+1)
    hlis.append(H)
    wkireme = 0
    numwkireme = 0
    Flag1 = True
    Flag2 = True
    w = 1
    while Flag1:
        for n in range(len(hlis)-1):
            s = 0
            for num in range(hlis[n],hlis[n+1]):
                s += sum(S[num][wkireme:wkireme+w])
            if s > K:
                if w == 1:
                    Flag2 = False
                    Flag1 = False
                    break
                else:
                    wkireme = wkireme + w -1
                    numwkireme += 1
                    w = 1
                    break
        else:
            if wkireme + w >= W:
                Flag1 = False
            else:
                w += 1
    if Flag2:
        ans = min(ans, numwkireme + len(hlis) -2)
print(ans)

Submission status: Time Limit Exceeded

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

def count(n):
    A = [0]
    c = 0
    i = 1
    while(n):
        if n & 1:
            A.append(i)
            c += 1
        n >>= 1
        i += 1
    A.append(H)
    return c, A


ans = 2000
for n in range(1 << (H-1)):
    c, A = count(n)
    X = [0]*(len(A)-1)
    j = 0
    flag=True
    while j < W:
        for k in range(len(A)-1):
            for i in range(A[k], A[k+1]):
                if S[i][j] == "1":
                    X[k] += 1
        for x in X:
            if x > K:
                if flag:
                    c += 10000
                    break
                flag = True
                c += 1
                X = [0]*(len(A)-1)
                break
        else:
            flag = False
            j += 1
        if c > 10000:
            break
    ans = min(ans, c)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import copy
    H,W,K=map(int,input().split())
    S=[]
    for _ in range(H):
        S.append([int(x) for x in list(input())])

    ans=(H-1)+(W-1)

    for i in range(2**(H-1)):
        check=[0]*H
        for j in range(H-1):
            if ((i>>j)&1):
                check[j+1]=check[j]+1
            else:
                check[j+1]=check[j]
        
        g=check[H-1]+1
        A=[0]*g
        c=0
        f=0
        for j in range(W):
            B=[0]*g
            for k in range(H):
                if S[k][j]==1:
                    B[check[k]]+=1
                if B[check[k]]>K:
                    c=10**4
                    f=1
                    break
            if f:
                break
            #print("AB",A,B)
            for l in range(g):
                if B[l]==0:
                    continue
                elif A[l]+B[l]>K:
                    c+=1
                    A=copy.copy(B)
                    break
                else:
                    A[l]+=B[l]
        ans=min(ans,c+g-1)

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

#sys.setrecursionlimit(10**9)

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

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

	an=10**10

	for i in range(1<<h-1):
		ans=h-1
		B=np.copy(G)
		for j in range(h):
			if i&(1<<j):
				ans-=1
				B[j+1]+=B[j]
				B[j]=[0]*w
		C=np.zeros(h)
		#print(B)

		for i in range(w):
			C+=B[:,i]
			#print(C)
			if np.max(C)>k:
				ans+=1
				C=B[:,i]
		an=min(an,ans)
		#print(ans)
	print(an)
















if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

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

#sys.setrecursionlimit(10**9)

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

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

	an=10**10

	for i in range(1<<h-1):
		ans=h-1
		B=np.copy(G)
		for j in range(h):
			if 1&(i>>j):
				ans-=1
				B[j+1]+=B[j]
				B[j]=[0]*w
		C=np.zeros(h)
		#print(B)

		for i in range(w):
			C+=B[:,i]
			#print(C)
			if np.max(C)>k:
				ans+=1
				C=B[:,i]
		an=min(an,ans)
		#print(ans)
	print(an)
















if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

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

ans=(H-1)+(W-1)

for i in range(2**(H-1)):
    check=[0]*H
    for j in range(H-1):
        if ((i>>j)&1):
            check[j+1]=check[j]+1
        else:
            check[j+1]=check[j]
    
    g=check[H-1]+1
    A=[0]*g
    c=0
    f=0
    for j in range(W):
        B=[0]*g
        for k in range(H):
            if S[k][j]==1:
                B[check[k]]+=1
            if B[check[k]]>K:
                c=10**4
                f=1
                break
        if f:
            break
        #print("AB",A,B)
        for l in range(g):
            if B[l]==0:
                continue
            elif A[l]+B[l]>K:
                c+=1
                A=copy.copy(B)
                break
            else:
                A[l]+=B[l]
    ans=min(ans,c+g-1)

print(ans)

Submission status: Time Limit Exceeded

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

ans=(H-1)+(W-1)

for i in range(2**(H-1)):
    check=[0]*H
    for j in range(H-1):
        if ((i>>j)&1):
            check[j+1]=check[j]+1
        else:
            check[j+1]=check[j]
    
    g=check[H-1]+1
    A=[0]*g
    c=0
    f=0
    for j in range(W):
        B=[0]*g
        for k in range(H):
            if S[k][j]==1:
                B[check[k]]+=1
            if B[check[k]]>K:
                c=10**4
                f=1
                break
        #print("AB",A,B)
        for l in range(g):
            if A[l]+B[l]>K:
                c+=1
                A=copy.copy(B)
                break
            else:
                A[l]+=B[l]
        if f:
            break
    ans=min(ans,c+g-1)

print(ans)

Submission status: Time Limit Exceeded

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

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

ans = H + W - 2

for ptn in range(1<<H-1): # 2^H - 1 通り
    cand = 0

    sep = [0] # 横方向の分割リスト、ここ天才
    for i in range(H-1):
        if((ptn >> i) & 1): # & を取ることで、上の桁を消せる
            sep.append(i+1)
            cand += 1
    sep.append(H)

    left = 0 # left は直前の分割
    for pos in range(W):
    	cur = [] # cur は今見てるホワイトチョコの個数のリスト

    	# 横方向に分割されている各部分について
    	for i in range(len(sep) - 1):
    		cur.append(sum[sep[i+1]][pos+1] - sum[sep[i+1]][left] - sum[sep[i]][pos+1] + sum[sep[i]][left])

    	if max(cur) > K:
    		if left == pos: # 縦に分割できない場合(一列しかない場合)
    			cand = H * W
    			break
    		else:
    			cand += 1
    			left = pos

    ans = min(ans, cand)

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(input())

sum = np.array([[0] * (w+1) for _ in range(h+1)], dtype=int)
for i in range(h):
    for j in range(w):
        sum[i+1][j+1] = sum[i][j+1] + sum[i+1][j] - sum[i][j] + (1 if s[i][j] == '1' else 0)

ans = h + w - 2
for ptn in range(1<<h-1):
    cand = 0

    sep = [0]
    for i in range(h-1):
        if((ptn >> i) & 1):
            sep.append(i+1)
            cand += 1
    sep.append(h)
    sep = np.array(sep, dtype=int)

    left = 0
    cur = np.array([0] * (len(sep) - 1), dtype=int)
    for pos in range(w):
        for i in range(len(sep)-1):
            cur[i] = sum[sep[i+1]][pos+1] - sum[sep[i+1]][left] - sum[sep[i]][pos+1] + sum[sep[i]][left]
        if max(cur) > k:
            if left == pos:
                cand = h * w
                break
            else:
                cand += 1
                left = pos
    ans = cand if cand < ans else ans

print(ans)

Submission status: Time Limit Exceeded

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

sum = [[0] * (w+1) for _ in range(h+1)]
for i in range(h):
    for j in range(w):
        sum[i+1][j+1] = sum[i][j+1] + sum[i+1][j] - sum[i][j] + (1 if s[i][j] == '1' else 0)

ans = h + w - 2
for ptn in range(1<<h-1):
    cand = 0

    sep = [0]
    for i in range(h-1):
        if((ptn >> i) & 1):
            sep.append(i+1)
            cand += 1
    sep.append(h)

    left = 0
    for pos in range(w):
        cur = []
        for i in range(len(sep)-1):
            cur.append(sum[sep[i+1]][pos+1] - sum[sep[i+1]][left] - sum[sep[i]][pos+1] + sum[sep[i]][left])
        if max(cur) > k:
            if left == pos:
                cand = h * w
                break
            else:
                cand += 1
                left = pos
    ans = cand if cand < ans else ans

print(ans)

Submission status: Time Limit Exceeded

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

from itertools import product
ans = 2000

for idx,cond in enumerate(product((True,False),repeat=h-1)):
    div = sum(cond)
    spl = [arr[0][:]]
    for i in range(h-1):
        if cond[i]:
            spl.append(arr[i+1][:])
        else:
            spl[-1] = [spl[-1][j] + arr[i+1][j] for j in range(w)]
    num = len(spl)
    cnt = [0]*num
    
    for v in range(w):
        tmp = [spl[i][v] for i in range(num)]
        if max(tmp) > k:
            break
        if max([cnt[i] + tmp[i] for i in range(num)]) > k:
            div += 1
            cnt = tmp[:]
        else:
            cnt  = [cnt[i] + tmp[i] for i in range(num)]
    else:    
        ans = min(ans,div)
            
print(ans)

Submission status: Time Limit Exceeded

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

from itertools import product
ans = [0]*(2**(h-1))

for idx,h_cond in enumerate(product((True,False),repeat=h-1)):
    div = sum(h_cond)
    splits = [arr[0][:]]
    for i in range(h-1):
        if h_cond[i]:
            splits.append(arr[i+1][:])
        else:
            splits[-1] = [splits[-1][j] + arr[i+1][j] for j in range(w)]
    block = len(splits)
    count = [0]*block
    
    for v_pos in range(w):
        tmp = [splits[i][v_pos] for i in range(block)]
        if max(tmp) > k:
            div = 2000
            break
        if max([count[i] + tmp[i] for i in range(block)]) > k:
            div += 1
            count = tmp[:]
        else:
            count  = [count[i] + tmp[i] for i in range(block)]
    
    ans[idx] = div
            
print(min(ans))

Submission status: Time Limit Exceeded

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

from itertools import product
import numpy as np
ans = [0] * (2**(h-1))
ans_index = 0

for horizontal_condition in product((True,False),repeat=h-1):
    count = np.zeros(h)
    divide = sum(horizontal_condition)
    trans_matrix = np.zeros((h,h))
    trans_matrix[0,0] = 1
    down = 0
    right = 0
    
    for i in horizontal_condition:
        if i:
            down += 1
        right += 1
        trans_matrix[down,right] = 1
        
    for vertical_divide in range(w):
        tmparr = np.array([int(i[vertical_divide]) for i in arr])
        addarr = np.dot(trans_matrix,tmparr)
        if max(count+addarr) > k:
            count = addarr
            divide += 1
        else:
            count += addarr
            
    ans[ans_index] = divide
    ans_index += 1
    
print(min(ans))

Submission status: Time Limit Exceeded

Solution code:
INF=1020

h, w, k = map(int, input().strip().split())
S = [list(map(int,list(input()))) for _ in range(h)]
# print(S)
ans=INF
for bi in range(2**(h-1)):
    tot=0
    hCut=[]
    for i in range(h-1):
        if bi>>i & 1:
            hCut.append(i)
            tot+=1
    cnt=[0]*(len(hCut)+1)
    j=0
    last=INF
    while True:
        if j>=w:
            break
        cntInd=0
        # print(j)
        for i in range(h):
            if cntInd<=len(hCut)-1:
                if i > hCut[cntInd]:
                    cntInd+=1
            #print(i,j)
            if int(S[i][j]):
                cnt[cntInd]+=1
        if max(cnt)>k:
            if last==j:
                tot=INF
                break
            last=j
            # j-=1
            for i in range(len(hCut)+1):
                cnt[i]=0
            tot+=1
        else:
            j+=1
        # print(cnt,tot)
    ans=min(ans,tot)
    # print("ans=",ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from io import StringIO


def main():
    h, w, k = map(int, input().split())
    s = ""
    for _ in range(h):
        s_ = input()
        s += " ".join(s_) + "\n"
    s = np.loadtxt(StringIO(s), dtype=np.int64)
    bit = 0

    def search_all(flags):
        res = 0
        divs = flags.sum() + 1
        sum_ = np.zeros((w, divs), dtype=np.int64)
        idx = 0
        for i in range(h):
            sum_[:, idx] += s[i]
            if flags[i]:
                idx += 1

        memo = np.zeros(divs, dtype=np.int64)
        for j in range(w):
            if (memo + sum_[j] > k).any():
                res += 1
                memo = sum_[j]
            else:
                memo += sum_[j]
        return res

    answer = None
    while bit < 1 << h - 1:
        flags = np.zeros(h, dtype=np.bool)
        for i in range(h - 1):
            if bit & (1 << i):
                flags[i] = True
        res = flags.sum() + search_all(flags)
        if answer is None:
            answer = res
        else:
            answer = min(answer, res)
        bit += 1

    print(answer)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from io import StringIO


def main():
    h, w, k = map(int, input().split())
    s = ""
    for _ in range(h):
        s_ = input()
        s += " ".join(s_) + "\n"
    s = np.loadtxt(StringIO(s), dtype=np.int64)
    bit = 0

    def search_all(flags):
        res = 0
        divs = flags.sum() + 1
        sum_ = np.zeros((divs, w), dtype=np.int64)
        idx = 0
        for i in range(h):
            sum_[idx] += s[i]
            if flags[i]:
                idx += 1

        memo = np.zeros(divs, dtype=np.int64)
        for j in range(w):
            if (memo + sum_[:, j] > k).any():
                res += 1
                memo = sum_[:, j]
            else:
                memo += sum_[:, j]
        return res

    answer = None
    while bit < 1 << h - 1:
        flags = np.zeros(h, dtype=np.bool)
        for i in range(h - 1):
            if bit & (1 << i):
                flags[i] = True
        res = flags.sum() + search_all(flags)
        if answer is None:
            answer = res
        else:
            answer = min(answer, res)
        bit += 1

    print(answer)


if __name__ == "__main__":
    main()