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

Solution (Python):
from collections import defaultdict
H,W,K = map(int,input().split())
S = [0] * H
for i in range(H):
    S[i] = input()

INF = H + W - 2

def bi(x):
    global H
    o = [0]*(H-1)
    i = 0
    while x != 0:
        o[i] = x % 2
        i += 1
        x //= 2
    return o

def hoge(n):
    global K
    b = bi(n)
    d = defaultdict(set)
    j = 0
    for i in range(H):
        d[j].add(i)
        if i == H - 1:
            break
        if b[i]:
            j += 1
    dlen = len(d)
    T = [0]*dlen
    for k,V in d.items():
        T[k] = [0]*W
        for i in range(W):
            for v in V:
                T[k][i] += int(S[v][i])
            if T[k][i] > K:
                return INF
    ans = dlen - 1
    U = [T[x][0] for x in range(dlen)]
    for i in range(1,W):
        flag = 0
        for k in range(dlen):
            U[k] += T[k][i]
            if U[k] > K:
                flag = 1
        if flag == 1:
            ans += 1
            for k in range(dlen):
                U[k] = T[k][i]
    return ans

ANS = INF
for i in range(2**(H-1)):
    ANS = min(ANS,hoge(i))

print(ANS)

Solution (Python):
from itertools import product

H, W, K = map(int, input().split())
l = [[0]*W for _ in range(H)]
for i in range(H):
    for j, s in enumerate(input()):
        if s=="1":
            l[i][j] = 1

dp = [[0]*(W+1) for _ in range(H+1)]
for i in range(1, H+1):
    for j in range(1, W+1):
        dp[i][j] = l[i-1][j-1]+dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]

f=lambda lx,ly,rx,ry:dp[ry][rx]-dp[ly-1][rx]-dp[ry][lx-1]+dp[ly-1][lx-1]

ans = H*W
for i in product(range(2), repeat=H-1):
    candidate = []
    if any(i):
        start = 1
        for j, k in enumerate(i, start=1):
            if k:
                candidate.append((start, j))
                start = j+1
        candidate.append((start, H))
    else:
        candidate.append((1, H))
    
    q = [1]
    cutx = 0

    while q:
        s = q.pop()
        for t in range(s, W+1)[::-1]:
            if all(f(s, j, t, k)<=K for j, k in candidate):
                if t!=W:
                    q.append(t+1)
                    cutx += 1
                break
        else:
            cutx = H*W
    v = cutx+sum(i)
    ans = min(ans, v)

print(ans)

Solution (Python):
from itertools import product

H, W, K = map(int, input().split())
l = [[0]*W for _ in range(H)]
for i in range(H):
    for j, s in enumerate(input()):
        if s=="1":
            l[i][j] = 1

dp = [[0]*(W+1) for _ in range(H+1)]
for i in range(1, H+1):
    for j in range(1, W+1):
        dp[i][j] = l[i-1][j-1]+dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]

f=lambda lx,ly,rx,ry:dp[ry][rx]-dp[ly-1][rx]-dp[ry][lx-1]+dp[ly-1][lx-1]

ans = H*W
for i in product(range(2), repeat=H-1):
    candidate = []
    if any(i):
        start = 1
        for j, k in enumerate(i, start=1):
            if k:
                candidate.append((start, j))
                start = j+1
        candidate.append((start, H))
    else:
        candidate.append((1, H))
    
    q = [1]
    cutx = 0

    while q:
        s = q.pop()
        for t in range(s, W+1)[::-1]:
            if all(f(s, j, t, k)<=K for j, k in candidate):
                if t!=W:
                    q.append(t+1)
                    cutx += 1
                break
        else:
            cutx = H*W
    v = cutx+sum(i)
    ans = min(ans, v)

print(ans)

Solution (Python):
from collections import defaultdict
H, W, K = map(int, input().split())  
gridgraph = [list(input()) for _ in range(H)]
ans = 10**10

for i in range(1 << (H-1)):
    bits = []
    for j in range(H-1):
        bits.append((i >> j) & 1)  
    separate_row = True
    cnt = sum(bits)  
    all_accumulation = defaultdict(int)
    
    for j in range(W):
        now_area = 0
        now_accumulation = defaultdict(int)
        for i in range(H):
            
            
            now_accumulation[now_area] += int(gridgraph[i][j])
            if i != H-1:
                now_area += bits[i]
        
        if all([K >= v for v in now_accumulation.values()]):
            for key in now_accumulation.keys():
                all_accumulation[key] += now_accumulation[key]
            
            if all([K >= v for v in all_accumulation.values()]):
                continue
            else:
                cnt += 1
                
                all_accumulation = now_accumulation.copy()
        else:
            
            separate_row = False
            break
    if separate_row:
        ans = min(ans, cnt)
print(ans)

Solution (Python):
def main():
    H, W, K = map(int, input().split())
    S = [list(map(int,list(input()))) for _ in range(H)]
    
    ans = float('inf')
    for i in range(1<<H-1):
        cut = []
        for j in range(H):
            if (i >> j) & 1:
                cut.append(j+1)

        tmp_S = [[0] * W for _ in range(len(cut) + 1)]
        tmp_id = 0
        for i in range(H):
            if i in cut:
                tmp_id += 1
            for j in range(W):
                tmp_S[tmp_id][j] += S[i][j]
        
        isOK = True
        for i in range(len(cut) + 1):
            for w in range(W):
                if tmp_S[i][w] > K:
                    isOK = False

        if not isOK:
            continue

        cnt = len(cut)
        white = [0] * (len(cut)+1)

        flag = False
        for w in range(W):
            for i in range(len(cut) + 1):
                white[i] += tmp_S[i][w]
                if white[i] > K:
                    cnt += 1
                    flag = True
                    break
            if flag:
                for i in range(len(cut) + 1):
                    white[i] = tmp_S[i][w]
                flag = False
        ans = min(ans, cnt)

    print(ans)

                


if __name__ == "__main__":
    main()

Solution (Python):
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)

Solution (Python):
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 input()]
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)

Solution (Python):
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)

Solution (Python):
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()

Solution (Python):
import sys
input = sys.stdin.readline
input = sys.stdin.buffer.readline



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


def main():
	h,w,k=MI()
	G=[]
	for i in range(h):
		A=list(map(int,input().rstrip().decode()))
		G.append(A)
	

	for i in range(h):
		for j in range(w):
			if i!=0:
				G[i][j]+=G[i-1][j]
			if j!=0:
				G[i][j]+=G[i][j-1]
			if i!=0 and j!=0:
				G[i][j]-=G[i-1][j-1]
	

	B=[]
	for i in range(2**(h-1)):
		C=[0,h-1]
		for j in range(h):
			if i&(1<<j):
				C.append(j)
				C.append(j+1)
		C.sort()
		B.append(C)

	

	ans=10**10

	def check(x1,y1,x2,y2):
		ret=G[x2][y2]
		if x1 != 0:
			ret -= G[x1-1][y2]
		if y1 != 0:
			ret -= G[x2][y1-1]
		if x1 != 0 and y1 != 0:
			ret += G[x1-1][y1-1]
		return ret

	for D in B:
		
		cnt=len(D)//2-1
		l=0
		ww=0
		f=0
		while ww<w and f==0:
			for i,j in zip(D[0::2],D[1::2]):
				
				if check(i,l,j,ww)>k:
					
					if l==ww:
						f=1
					else:
						cnt+=1
						l=ww
					break
			ww+=1
			
		
		if f==0:
			ans=min(ans,cnt)
	print(ans)














if __name__ == "__main__":
	main()

Solution (Python):
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)

Solution (Python):
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
        
        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)

Solution (Python):
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
        
        for l in range(g):
            if 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)

Solution (Python):

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

    ans = H*W

    for i in range(0,1<<(H-1)):
        g = 0
        id = [0 for j in range(H)]
        for j in range(0,H):
            id[j] = g
            if i>>j&1 == 1:
                g += 1
        
        g_cnt = [0 for j in range(g+1)]
        c_ans = g
        j = 0
        div_w = 0
        while j < W:
            for k in range(0, H):
                if S[k][j] == '1':
                    g_cnt[id[k]] += 1
            for k in range(0,g+1):
                if g_cnt[k] > K:
                    c_ans += 1
                    g_cnt = [0 for j in range(g+1)]
                    if div_w == j:
                        c_ans += H*W
                        break
                    j -= 1
                    div_w = j
                    break
            j += 1
            if c_ans > ans:
                break
        
        ans = min(ans, c_ans)

    
    print(ans)


main()

Solution (Python):
import sys
 
readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)
 
 
def main():
    def divide_choco(bit):
        divrow_num = bin(bit).count("1") + 1  
        choco_current = [[0] * w for _ in range(divrow_num)]
 
        row_divided_cur = 0
 
        for col, piece in enumerate(choco[0]):
            choco_current[0][col] = piece
 
        for row in range(h - 1):
            if bit >> row & 1:
                row_divided_cur += 1
            for col, piece in enumerate(choco[row + 1]):
                choco_current[row_divided_cur][col] += piece
 
        return choco_current, divrow_num
 
    h, w, k = list(map(int, readline().split()))
    choco = []
 
    for i in range(h):
        choco_in = input()
        choco_add = [int(c) for c in choco_in]
        choco.append(choco_add)
 
    ans = INF
 
    for bit in range(1 << (h - 1)):
        choco_current, divrow_num = divide_choco(bit)
        choco_cursum = [0] * divrow_num
        is_exceed = False  
 
        ans_temp = bin(bit).count("1")
        if divrow_num > 1:
            for col in range(w):
                choco_currow = [choco_current[dr][col] for dr in range(divrow_num)]
                for drow, pieces in enumerate(choco_currow):
                    if pieces > k:
                        ans_temp += INF
                    elif choco_cursum[drow] + pieces > k:
                        is_exceed = True
 
                if is_exceed:
                    choco_cursum = [cc for cc in choco_currow]
                    ans_temp += 1
                    is_exceed = False
                else:
                    choco_cursum = [cc + cs for cc, cs in zip(choco_currow, choco_cursum)]
        else:
            choco_cursum = 0
            for pieces in choco_current[0]:
                if pieces > k:
                    ans_temp += INF
                elif choco_cursum + pieces > k:
                    choco_cursum = pieces
                    ans_temp += 1
                else:
                    choco_cursum = choco_cursum + pieces
 
        ans = min(ans, ans_temp)
 
    print(ans)
 
 
if __name__ == '__main__':
    main()

Solution (Python):
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 cond in product([True,False],repeat=(h-1)):
    cut = sum(cond)
    splits = [arr[0][:]]
    for i in range(1,h):
        if cond[i-1]:
            splits.append(arr[i][:])
        else:
            splits[-1] = [splits[-1][j]+arr[i][j] for j in range(w)]
    
    check = [max(i) for i in splits]
    if max(check) > k:
        break
    count = [i[0] for i in splits]
    
    div = cut
    for j in range(1,w):
        addarr = [count[i]+splits[i][j] for i in range(cut+1)]
        if max(addarr) > k:
            div += 1
            count = [splits[i][j] for i in range(cut+1)]
        else:
            count = addarr[:]
    ans = min(ans,div)
        
print(ans)

Solution (Python):
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 cond in product([True,False],repeat=(h-1)):
    cut = sum(cond); div = 0
    splits = [0] * (cut+1); splits[0] = arr[0][:]
    for i in range(1,h):
        if cond[i-1]:
            div += 1
            splits[div] = arr[i][:]
        else:
            splits[div] = [splits[div][j]+arr[i][j] for j in range(w)]
    
    check = [max(i) for i in splits]
    if max(check) > k:
        break
    count = [i[0] for i in splits]
    
    for j in range(1,w):
        addarr = [count[i]+splits[i][j] for i in range(cut+1)]
        if max(addarr) > k:
            div += 1
            count = [splits[i][j] for i in range(cut+1)]
        else:
            count = addarr[:]
    ans = min(ans,div)
        
print(ans)

Solution (Python):
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 i in product([True,False],repeat=(h-1)):
    cut = sum(i)
    splits = [0] * (cut+1)
    splits[0] = arr[0][:]
    tmp = 0
    div = cut
    for j in range(1,h):
        if i[j-1]:
            tmp += 1
            splits[tmp] = arr[j][:]
        else:
            splits[tmp] = [splits[tmp][idx]+arr[j][idx] for idx in range(w)]
    
    check = 0
    for j in splits:
        check = max(check,max(j))
    if check > k:
        break
    count = [splits[j][0] for j in range(cut+1)]
    
    for j in range(1,w):
        addarr = [count[idx]+splits[idx][j] for idx in range(cut+1)]
        if max(addarr) > k:
            div += 1
            count = [splits[idx][j] for idx in range(cut+1)]
        else:
            count = addarr[:]
    ans = min(ans,div)
        
print(ans)

Solution (Python):
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): 
    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 = min(ans, cand)

print(ans)

Solution (Python):
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)

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

ans = H*W

def countWhite(ytop, ybottom, xleft, xright):
    ret = sum([sum(s[xleft:xright]) for s in S[ytop:ybottom]])
    return ret
    

for h_div in range(1 << H-1):
    count = 0
    cut = [0]
    for i in range(H):
        if h_div >> i & 1:
            cut.append(i+1)
            count += 1
    cut.append(H)
    if count > ans:
        continue
    
    left = 0
    
    for right in range(1, W+1):
        white = 0
        for i in range(len(cut)-1):
            white = max(white, countWhite(cut[i], cut[i+1], left, right))
        
        if white > K:
            if left == right - 1: 
                break
            left = right - 1
            count += 1
            if count > ans:
                break
    else:
        if count < ans:
            ans = count

print(ans)

Solution (Python):
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)

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

def cnt(array):
    count = [0] * H
    split_cnt = 0
    for w in range(W):
        for h in range(H):
            if choco[h][w] == "1":
                count[array[h]] += 1
        if any(i > K for i in count):
            split_cnt += 1
            count = [0] * H
            for h in range(H):
                if choco[h][w] == "1":
                    count[array[h]] += 1
            if any(i > K for i in count):
                return 10 ** 20
    return split_cnt

def get_array(array):
    l = len(array)
    ret = [0] * l
    for i in range(1, l):
        ret[i] = ret[i-1] + array[i]
    return ret

ans = 10 ** 20

for p in product(range(2), repeat=H-1):
    p = get_array([0]+list(p))
    ans = min(ans, cnt(p)+max(p))

print(ans)

Solution (Python):

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


if h == 1:
    print(math.ceil(s//k))
    exit()




ans = h*w 
for i in range(2**(h-1)):
    cnt_white = [0] 
    
    ans_i = 0
    
    for bit in range(h-1):
        if i >> bit & 1:
            cnt_white.append(0)
            ans_i += 1
    
    c = 0
    last_div = 0
    while c < w:
        r_idx = 0
        
        for r in range(h):
            if b[r][c] == "1":
                cnt_white[r_idx] += 1
                
            if i >> r & 1:
                r_idx += 1
        
        if max(cnt_white) >= k+1:
            
            ans_i += 1
            if c == last_div:
                ans_i = h*w  
                break
            last_div = c
            c -= 1
            cnt_white = [0]*len(cnt_white)
            
        c += 1
    ans = min(ans,ans_i)
print(ans)

Solution (Python):

import copy

def minOp(h, w, k, yl, s):
    xl = []
    ks = [ 0 for i in range(len(yl) + 1) ]

    for x in range(w):
        py = 0
        cks = [ 0 for i in range(len(yl) + 1) ]
        for idx, y in enumerate(yl + [h - 1]):
            for yy in range(py, y + 1):
                if s[yy][x] == '1':
                    cks[idx] += 1

            py = y + 1

        over = False
        for idx, kk in enumerate(ks):
            if kk + cks[idx] > k:
                over = True

        if over:
            for ck in cks:
                if ck > k:
                    return (h - 1) + (w - 1)
            xl.append(x - 1)
            ks = copy.copy(cks)
        else:
            ks = list(map(lambda a, b: a + b, ks, cks))
            
    return len(xl) + len(yl)
    

def devideVertical(h, w, k, cy, yl, s):
    m = (h - 1) + (w - 1)
    for y in range(cy, h - 1):
        nyl = copy.copy(yl)
        nyl.append(y)
        m = min(m, devideVertical(h, w, k, y + 1, nyl, s))
    
    m = min(m, minOp(h, w, k, yl, s))
    return m

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

print(devideVertical(h, w, k, 0, [], s))

Solution (Python):
import itertools


def check(H, W, K, S, p):
    num_groups = p.count(True) + 1
    group_total = [0] * num_groups
    ret = p.count(True)

    for j in range(W):
        group_value = [0] * num_groups
        group_value[0] += int(S[0][j])
        group_idx = 0
        for i in range(H-1):
            if p[i]:
                group_idx += 1
            group_value[group_idx] += int(S[i+1][j])
        if max(group_value) > K:
            return float("inf")
        group_total_tmp = list(map(sum, zip(group_value, group_total)))
        if max(group_total_tmp) <= K:
            group_total = group_total_tmp
        else:
            group_total = group_value
            ret += 1
    return ret


def main():
    H, W, K = map(int, input().split())
    S = [input() for _ in range(H)]
    ans = float("inf")
    for p in itertools.product([True, False], repeat=H-1):
        ans = min(ans, check(H, W, K, S, p))
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
from itertools import combinations

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

C = [[0] * (W + 1) for _ in range(H + 1)]
for h in range(H):
    wc = 0
    for w in range(W):
        wc += (S[h][w] == '1')
        C[h + 1][w + 1] = C[h][w + 1] + wc

ans = 2000
for cuth in range(H):
    for comb in combinations([h for h in range(1, H)], cuth):
        comb = [0] + list(comb) + [H]
        wi, cutw = 0, 0
        for w in range(W):
            if max([C[comb[i]][w + 1] - C[comb[i]][wi] - C[comb[i - 1]][w + 1] + C[comb[i - 1]][wi] for i in range(1, len(comb))]) > K:
                if wi == w:
                    cutw = 2000
                wi, cutw = w, cutw + 1
        ans = min(ans, cuth + cutw)

print(ans)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    h,w,k = LI()
    aa = [[int(c) for c in S()] for _ in range(h)]

    def f(hs):
        l = len(hs)
        c = [0] * l
        r = l - 1
        for i in range(w):
            nc = [0] * l
            bf = False
            for j in range(l):
                for h in hs[j]:
                    nc[j] += aa[h][i]
                if nc[j] > k:
                    return -1
                if nc[j] + c[j] > k:
                    bf = True
            if bf:
                r += 1
                c = nc
            else:
                for j in range(l):
                    c[j] += nc[j]
        return r

    r = inf
    for bi in range(2**(h-1)):
        hs = [[0]]
        for i in range(h-1):
            if 2**i & bi > 0:
                hs.append([])
            hs[-1].append(i+1)
        t = f(hs)
        if t >= 0 and r > t:
            r = t

    return r


print(main())