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


import sys
from itertools import accumulate
from bisect import bisect_right

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def build_grid(H, W, intv, _type, space=True, padding=False):
    
    if space:
        _input = lambda: input().split()
    else:
        _input = lambda: input()
    _list = lambda: list(map(_type, _input()))
    
    if padding:
        offset = 1
    else:
        offset = 0
    grid = list2d(H+offset*2, W+offset*2, intv)
    for i in range(offset, H+offset):
        row = _list()
        for j in range(offset, W+offset):
            grid[i][j] = row[j-offset]
    return grid

def popcount(i):
    return bin(i).count('1')

H, W, K = MAP()
grid = build_grid(H, W, 0, int, space=0)

ans = INF
for S in range(1<<(H-1)):
    N = popcount(S) + 1
    A = list2d(N, W, 0)
    for w in range(W):
        A[0][w] = grid[0][w]
    h = 0
    for k in range(H-1):
        if S & 1<<k:
            h += 1
        for w in range(W):
            A[h][w] += grid[k+1][w]
    for i in range(N):
        A[i] = [0] + list(accumulate(A[i]))
    cnt = 0
    idx = 1
    while 1:
        nxt = INF
        for i in range(N):
            j = idx
            tgt = K + A[i][idx-1]
            while j < W+1 and A[i][j] <= tgt:
                j += 1
            nxt = min(nxt, j)
            
        if idx == nxt:
            cnt = INF
            break
        idx = nxt
        if idx == W+1:
            break
        cnt += 1
    ans = min(ans, N-1+cnt)
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols
    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])
    return ret


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_map_as_int(H):
    '''
    
    '''
    ret = []
    for _ in range(H):
        ret.append([1 if s == '
        
        
    return ret


class cumsum2d:  
    def __init__(self, ls: list):
        '''
        2次元のリストを受け取る
        '''
        from itertools import product
        H = len(ls)
        W = len(ls[0])
        self.ls_accum = [[0] * (W + 1)]
        for l in ls:
            self.ls_accum.append([0] + l)

        
        for i, j in product(range(1, H + 1), range(1, W + 1)):
            self.ls_accum[i][j] += self.ls_accum[i - 1][j]
        
        for i, j in product(range(1, H + 1), range(1, W + 1)):
            self.ls_accum[i][j] += self.ls_accum[i][j - 1]

    def total(self, i1, j1, i2, j2):
        '''
        点(i1,j1),(i1,j2),(i2,j1),(i2,j2)の4点が成す四角の中の合計を取り出す
        ただし i1<=i2, j1<=j2
        ただし、i軸に関しては[i1,i2),j軸に関しては[j1,j2)の半開区間である
        '''
        return self.ls_accum[i2][j2] - self.ls_accum[i1][j2] \
            - self.ls_accum[i2][j1] + self.ls_accum[i1][j1]


class cumsum1d:  
    def __init__(self, ls: list):
        '''
        1次元リストを受け取る
        '''
        from itertools import accumulate
        self.ls_accum = [0] + list(accumulate(ls))

    def total(self, i, j):
        
        return self.ls_accum[j] - self.ls_accum[i]


def iter_p_adic(p, length):
    '''
    連続して増加するp進数をリストとして返す。lengthはリストの長さ
    return
    ----------
    所望のp進数リストを次々返してくれるiterator
    '''
    from itertools import product
    tmp = [range(p)] * length
    return product(*tmp)


MOD = 10**9 + 7

from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  







H, W, K = read_ints()
S = read_map(H)
S_cums = []
for s in S:
    S_cums.append(cumsum1d(map(int, list(s))))



def ret_renketusum(p, i, j):
    
    ma = S_cums[0].total(i, j)
    tmp = S_cums[0].total(i, j)
    for k, pp in enumerate(p, start=1):
        if pp == 1:  
            ma = max(ma, tmp)
            tmp = S_cums[k].total(i, j)
        else:
            tmp += S_cums[k].total(i, j)
    ma = max(ma, tmp)
    return ma


ans = 1000000000
for p in iter_p_adic(2, H - 1):
    
    l = 0
    r = 1
    n_cut = 0
    while r <= W:
        
        if ret_renketusum(p, l, r) > K:
            if r - l == 1:
                n_cut = 1000000000000
                break
            n_cut += 1
            l = r - 1
            r = l
        r += 1
    ans = min(n_cut + sum(p), ans)

print(ans)

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

S = []
for _ in range(H):
    S.append(input())

ans = H * W

for c in range(2**(H-1)):
    num_lines = 0

    g = {}
    tmp = c
    g_index = 0
    for h in range(H):
        g[h] = g_index 
        num_groups = g_index 
        if tmp % 2 == 1:
            g_index += 1
        tmp //= 2

    num_groups += 1

    num_lines = num_groups - 1 

    g_sum = [0] * num_groups

    for w in range(W):
        tmp = g_sum[:]

        ok = True
        ok2 = True
        for h in range(H):
            tmp[g[h]] += int(S[h][w])
        
            if tmp[g[h]] > K :
                
                ok = False
                if g_sum[g[h]] == 0:
                    ok2 = False

        if ok :
            g_sum = tmp
        else:
            if ok2:
                g_sum = [tmp[gi] - g_sum[gi] for gi in range(num_groups)]
                num_lines += 1
            else:
                break

    if not ok2:
        continue

    if ans > num_lines:
        ans = num_lines


print(ans)

Solution (Python):
from itertools import product
INFTY = 10**4
H,W,K = map(int,input().split())
S = [list(map(int,list(input()))) for _ in range(H)]
cmin = INFTY
for x in product((0,1),repeat=H-1):
    cur = 0
    cnt = 0
    h = sum(x)+1
    A = [0 for _ in range(h)]
    for j in range(W):
        ind = 0
        A0 = [0 for _ in range(h)]
        for i in range(H):
            if i<H-1 and x[i]==1:
                A0[ind] += S[i][j]
                ind += 1
            else:
                A0[ind] += S[i][j]
        B = [A[i]+A0[i] for i in range(h)]
        if max(A0)>K:
            cnt = INFTY
            break
        if max(B)>K:
            cur = j
            cnt += 1
            A = A0[:]
        else:
            A = B[:]
    cmin = min(cmin,cnt+sum(x))
print(cmin)

Solution (Python):
import sys,math,copy,queue,itertools
sys.setrecursionlimit(10**7)

def LI(): return [int(x) for x in sys.stdin.readline().split()]
INF = 10000
MOD = 10**9 + 7
DD = ((1,0),(0,1),(-1,0),(0,-1))
H,W,K = LI()
C = [[int(x) for x in input()] for _ in range(H)]

min_cnt = INF
for y in range(2**H):
    cnt = 0
    bit = 1
    shikiri = [False] * H
    for b in range(H):
        if y & bit:
            shikiri[b] = True     
            cnt +=1
        bit = bit << 1
    ct = [0] * H
    x = 0
    bx = 0
    while x < W:
        ix = 0
        for i in range(H):
            ct[ix] += C[i][x]
            if shikiri[i] : ix = i+1
        if max(ct) > K:
            if x != bx:
                cnt += 1
                ct = [0] * H
                bx = x
            else:
                cnt = INF
                break
        else:
            x = x + 1

    min_cnt = min(min_cnt,cnt)
print (min_cnt)

Solution (Python):
ans=10**8
h,w,K=map(int,input().split())
s=[]
import copy
def two(x):
	return "0"*(h-1-len(bin(x)[2:]))+bin(x)[2:]
for i in range(h):
	s.append(input())
for i in range(2**(h-1)):
	r=two(i)
	pre_ans=r.count("1")
	d=[0]*(pre_ans+1)
	dd=copy.copy(d)
	cnt=0
	for j in range(w):
		now=0
		for k in range(h):
			if s[k][j]=="1":
				d[now]+=1
			if k!=h-1:
				if r[k]=="1":
					now+=1
		if max(d)>K:
			e=[]
			for x in range(len(d)):
				e.append(d[x]-dd[x])
			d=copy.copy(e)
			cnt+=1
		if max(d)>K:
			cnt=10**7
		dd=copy.copy(d)
	pre_ans+=cnt
	ans=min(ans,pre_ans)
print(ans)

Solution (Python):
def chk(area):
    num=0
    l=len(area)
    cnt=[0 for _ in range(l)]

    for i in range(w):
        for j in range(h):
            cnt[area[j]]+=choko[i][j]

        if max(cnt)>k:
            if i>0: num+=1
            cnt=[0 for _ in range(l)]
            for j in range(h):
                cnt[area[j]]+=choko[i][j]
            if max(cnt)>k: return 10**10

    return num

h,w,k=map(int,input().split())
s=[input() for _ in range(h)]
choko=[[int(s[i][j]) for i in range(h)] for j in range(w)]

area=[0 for i in range(h)]
ans=10**10

for v in range(0,2**(h-1)):
    p=bin(v)[2:].zfill(h-1)
    for i in range(h-1):
        if p[i]=="1": area[i+1]=area[i]+1
        else: area[i+1]=area[i]

    tmp1=sum([int(p[i]) for i in range(h-1)])+chk(area)
    ans=min(ans,tmp1)

print(ans)

Solution (Python):

H,W,K = map(int,input().split())
S = [list(map(int,input())) for _ in range(H)]
ans = float("inf")
for i in range(2**(H-1)):
    kari = 0
    l = [0]*H
    if H > 1:
        for j in range(0,H-1):
            if i >> j & 1:
                l[j+1] = l[j]+1
                kari += 1
            else:
                l[j+1] = l[j]
    num = [0]*H

    for w in range(W):
        tmp = [0]*H
        for h in range(H):
            if S[h][w]:
                tmp[l[h]] += 1

        if max(tmp) > K:
            break

        if max([num[i]+tmp[i] for i in range(H)]) <= K:
            num = [num[i]+tmp[i] for i in range(H)]
            
            
        else:
            num = tmp
            kari += 1
    else:

        ans = min(ans,kari)
print(ans)

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

fans = 10 ** 5
for i in range(1 << (H-1)):
    slc = []
    scnt = 1
    ans = 0
    switch = 1
    for j in range(H-1):
        if (i >> j) % 2 == 1:
            slc.append(j+1)
            scnt += 1
            ans += 1
    slc.append(H)
    stock = [0] * scnt 
    for j in range(W):
        kari = [0] * scnt
        ss = slc[0]
        idx = 0
        for k in range(H):
            if ss == k:
                idx += 1
                ss = slc[idx]
            if S[k][j] == "1":
                kari[idx] += 1
            if kari[idx] > K:
                switch = 0
                break
        if switch == 0:
            break
        for k in range(scnt):
            if stock[k] + kari[k] <= K:
                stock[k] += kari[k]
            else:
                stock = kari
                ans += 1
                break
    if switch == 1:
        fans = min(fans, ans)

print(fans)

Solution (Python):

import re
import math
import itertools
from copy import deepcopy
import fractions
import random
from heapq import heappop,heappush
import time
import os
import sys
import datetime
from functools import lru_cache
readline=readline = sys.stdin.readline
sys.setrecursionlimit(2000)

alphabet="abcdefghijklmnopqrstuvwxyz"
mod=int(10**9+7)
inf=int(10**20)
def yn(b):
    if b:
        print("yes")
    else:
        print("no")
def Yn(b):
    if b:
        print("Yes")
    else:
        print("No")
def YN(b):
    if b:
        print("YES")
    else:
        print("NO")
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def fac_list(n,mod_=0):
    A=[1]*(n+1)
    for a in range(2,len(A)):
        A[a]=A[a-1]*a
        if(mod>0):A[a]%=mod_
    return A
def comb(n,r,mod,fac):
    if(n-r<0):return 0
    return (fac[n]*pow(fac[n-r],mod-2,mod)*pow(fac[r],mod-2,mod))%mod
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:
        return num
def get_primes(n,type="int"):
    A=[True]*(n+1)
    A[0]=False
    A[1]=False
    for a in range(2,n+1):
        if A[a]:
            for b in range(a*2,n+1,a):
                A[b]=False
    if(type=="bool"):return A
    B=[]
    for a in range(n+1):
        if(A[a]):B.append(a)
    return B
def is_prime(num):
    if(num<=2):return False
    i=2
    while i*i<=num:
       if(num%i==0):return False
       i+=1
    return True
def join(A,c=" "):
    n=len(A)
    A=list(map(str,A))
    s=""
    for a in range(n):
        s+=A[a]
        if(a<n-1):s+=c
    return s



def f():
    return 1

H,W,K=list(map(int,input().split()))
S=[list(map(int,list(input()))) for _ in range(H)]
R=[[0 for a in range(W)] for b in range(H+1)]
for a in range(W):
    cnt=0
    for b in range(H):
        if(S[b][a]==1):cnt+=1
        R[b+1][a]=cnt

ans=inf
for a in range(0,1<<(H-1)):
    x_siki=0
    B=bin_(a,H-1)
    ku=B.count(1)+1
    hi=[0]*ku
    f=True
    for b in range(W):
        now=[0]*ku

        sen=[0]
        for c in range(len(B)):
            if(B[c]==1):sen.append(c+1)
        sen.append(H)
        for c in range(len(sen)-1):
            now[c]=R[sen[c+1]][b]-R[sen[c]][b]
        if(max(now)>K):
            f=False
            continue
        for c in range(len(now)):
            hi[c]+=now[c]
        if max(hi)>K:
            x_siki+=1
            hi=now[:]
    if(f):ans=min(x_siki+ku-1,ans)
print(ans)

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

    ans = float('inf')
    for pattern in product([0, 1], repeat=H - 1):
        tmp_ans = 0
        div = [0] + [i for i, p in enumerate(pattern, start=1) if p == 1] + [100]
        grids = []
        for i in range(len(div) - 1):
            grids.append(G[div[i]: div[i + 1]])

        rows = []
        for grid in grids:
            row = []
            for w in range(W):
                v = 0
                for h in range(len(grid)):
                    v += grid[h][w]
                row.append(v)
            rows.append(row)

        w = 0
        d = set()
        df = False
        counts = [0] * len(rows)
        while w < W:
            for i, row in enumerate(rows):
                counts[i] += row[w]

            if [c for c in counts if c > K]:
                if w in d:
                    df = True
                    break
                d.add(w)
                tmp_ans += 1
                counts = [0] * len(rows)
            else:
                w += 1

            if df:
                break
        
        if not df:
            tmp_ans += len(div) - 2
            ans = min(ans, tmp_ans)

    print(ans)


if __name__ == '__main__':
    main()

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

white = [[0]*w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if i != 0:
            white[i][j] += white[i-1][j]
        if j != 0:
            white[i][j] += white[i][j-1]
        if i != 0 and j != 0:
            white[i][j] -= white[i-1][j-1]
        white[i][j] += choco[i][j]
ans = float('inf')
for i in range(2**(h-1)): 
    temp = format(i,'b').count('1') 
    hw = []
    j = i
    cnt = 0
    while j >0:
        if j&1:
            hw.append(cnt)
        cnt += 1
        j = j >> 1
    hw.append(h-1)
    now = -1
    
    flag = True
    for l in range(len(hw)):
        if l == 0:
            if white[hw[l]][0] > k:
                flag = False
                break
        else:
            if white[hw[l]][0] - white[hw[l-1]][0] > k:
                flag = False
                break
    if not flag:
        continue
    elif w == 1:
        ans = min(ans,temp)
        continue

    for j in range(w-1):
        flag = True
        if now == -1:
            for l in range(len(hw)):
                if l == 0:
                    if white[hw[l]][j+1] > k:
                        flag = False
                        break
                else:
                    if white[hw[l]][j+1] - white[hw[l-1]][j+1] > k:
                        flag = False
                        break
            if not flag:
                now = j
                temp += 1
        else:
            for l in range(len(hw)):
                if l == 0:
                    if white[hw[l]][j+1] - white[hw[l]][now] > k:
                        flag = False
                        break
                else:
                    if white[hw[l]][j+1] - white[hw[l]][now] - white[hw[l-1]][j+1] + white[hw[l-1]][now]> k:
                        flag = False
                        break
            if not flag:
                now = j
                temp += 1
    ans = min(ans,temp)
print(ans)

Solution (Python):
H,W,K=map(int,input().split())
S=[list(map(int,list(input()))) for i in range(H)]
ans=float("inf")

for i in range(1<<(H-1)):
    cnt=0
    
    lst=[0]*H
    qqq=0
    for j in range(H-1):
        if i&(1<<j)==0:
            lst[j+1]=qqq
            continue
        else:
            qqq+=1
            lst[j+1]=qqq
            cnt+=1
    data=[0]*H
    for j in range(W):
        for k in range(H):
            data[lst[k]]+=S[k][j]
            if data[lst[k]]>K:
                cnt+=1
                break
        else:
            continue
        data=[0]*H
        for k in range(H):
            data[lst[k]]+=S[k][j]
            if data[lst[k]]>K:
                break
        else:
            continue
        break
    else:
        ans=min(ans,cnt)
print(ans)

Solution (Python):


from itertools import accumulate, product
def main():
    H, W, K = map( int, input().split())
    S = [ list( map( int, list( input()))) for _ in range(H)]
    ans = 10**5
    cnt = 0
    AS = [ [0] + list( accumulate(S[i])) for i in range(H)]
    
    
    SAS = []
    for a in AS:
        SAS.extend(a)
    for P in product( range(2), repeat=H-1):
    
    
    
    
    
        now = sum(P)
        if ans < now:
            continue
        start = 0
        goal = 0
        
        while start < W:
            for i in range(start, W):
                cnt = 0
                check =True
                for j in range(H):
                    
                    
                    
                    cnt += SAS[j*(W+1)+i+1] - SAS[j*(W+1)+start]
                    if j == H-1:
                        if cnt > K:
                            check = False
                            break
                    else:
                        if P[j] == 1:
                            if cnt > K:
                                check = False
                                
                                break
                            cnt = 0
                if check:
                    goal += 1
            if start == goal:
                start = W+1
                now = 10**5
                break
            
            start = goal
            if goal < W:
                
                now += 1
            
        
        if now < ans:
            ans = now
    print(ans)
                
if __name__ == '__main__':
    main()

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

ans = None
for i in range(2**(h - 1)):
    t = 0
    to_add = [0]
    for a in range(h - 1):
        if i & (2**a):
            t += 1
        to_add.append(t)
    n_h = t
    n_w = 0
    zz = [0 for _ in range(n_h + 1)]
    cnts = zz.copy()
    is_new = True
    is_fail = False
    for x in range(w):
        is_over = False
        for y in range(h):
            z = to_add[y]
            cnts[z] += ar[y][x]
            if cnts[z] > k:
                is_over = True
                break
        if is_over:
            n_w += 1
            if ans is not None and ans <= n_h + n_w:
                break
            cnts = zz.copy()
            for y in range(h):
                z = to_add[y]
                cnts[z] += ar[y][x]
                if cnts[z] > k:
                    is_fail = True
                    break
            if is_fail:
                break
    if not is_fail and (ans is None or ans > n_h + n_w):
        ans = n_h + n_w
print(ans)

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

sum_w = [[0] * (w+1) for _ in range(h)]
for i in range(h):
    for j in range(1,w+1):
        sum_w[i][j] = sum_w[i][j-1] + s[i][j-1]






sums = []
for i in range(h):
    sums.append([[0] * w for _ in range(h+1)])

for i in range(h):
    for j in range(i+1,h+1):
        for l in range(w):
            sums[i][j][l] = sums[i][j-1][l] + sum_w[j-1][l+1]

ans = h + w
for i in range(2**(h-1)):
    nums = []
    for j in range(h-1):
        if((i >> j)&1 == 1):
            nums.append(j+1)
    tmp = len(nums)
    nums.append(h)
    
    head = 0
    checks = []
    for j in nums:
        checks.append(sums[head][j])
        head = j
    
    

    minus_num = [0] * len(checks)
    w_now = 0
    NG_flag = 0
    cut_flag = 0
    for j in range(w):
        if(NG_flag == 1):
            break
        for l in range(len(checks)):
            check_num = checks[l][j] - minus_num[l]
            if(check_num > k):
                if(w_now == 0):
                    
                    NG_flag = 1
                    break
                cut_flag = 1
                break


        if(cut_flag==1):
            
            tmp += 1
            for l in range(len(checks)):
                minus_num[l] = checks[l][j-1]
                check_num = checks[l][j] - minus_num[l]
                if(check_num > k):
                    NG_flag=1
                    break
            cut_flag = 0
            w_now = 1
        else:
            w_now += 1

    
    
    if(NG_flag==0):
        ans = min(ans, tmp)
        


print(ans)

Solution (Python):
h, w, K = map(int, input().split())
s = [list(map(int, input())) for _ in range(h)]

def cumsum(s):
    n = len(s)
    cs = [0] * (n+1)
    for i in range(n):
        cs[i+1] = cs[i] + s[i]
    return cs
cums = [cumsum(c) for c in s]
ans = float("inf")    

for i in range(2 ** (h-1)):
    seps = [(i >> j) & 1 for j in range(h-1)] + [1]
    c = [[0] * (w+1) for _ in range(sum(seps))]
    idx = 0
    for j in range(h):
        for k in range(w+1):
            c[idx][k] += cums[j][k]
        if seps[j]: idx += 1
    
    flg = False
    for j in range(len(c)):
        for k in range(w):
            if c[j][k+1]-c[j][k] > K:
                flg = True
    if flg: continue                

    res = 0
    left = 0
    for j in range(w-1):
        for cc in c:
            if cc[j+2] - cc[left] > K:
                break
        else: continue
        res += 1
        left = j+1
    
    ans = min(ans, res+sum(seps)-1)

print(ans)

Solution (Python):

import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

def check(sets):
  n = len(sets)
  data = [0]*n
  count = 0
  result_bit = 0
  for j in range(w):
    tmp = [0]*n
    for i in range(h):
      tmp[bisect.bisect_left(sets,i)]+=S[i][j]
      
    F = 0
    for i in range(n):
      if tmp[i] > K:return -1
      if data[i] + tmp[i] > K:
        F = 1
      else:
        data[i] += tmp[i]
    if F:
      result_bit |= (1<<j-1)
      for i in range(n):
        data[i] = tmp[i]
  return result_bit
    
    
    
    
    
    
    
  return  result_bit

h,w,K = map(int,input().split())
S = [list(map(int,input())) for i in range(h)]
for bit in range(2**(h-1)):
  sets = []
  for k in range(h-1):
    if (bit >> k) & 1:
      sets.append(k)
  sets.append(h)
  re = check(sets)
  
  if re == -1: continue
  mans = min(mans,collections.Counter(bin(bit))["1"] + collections.Counter(bin(re))["1"])
  
print(mans)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
from re import split
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy
import re

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7

h, w, k = LI()
s = []
for _ in range(h):
    s += [[int(i) for i in list(S())]]
ans = INF
for j in range(2 ** (h - 1)):
    L = []
    last = 0
    for m in range(h - 1):
        if j >> m & 1:
            L += [(last, m + 1)]
            last = m + 1
    L += [(last, h)]
    now = [0] * len(L)
    last_x = 0
    cnt = len(L) - 1
    flag2 = 0
    flag = 0
    x = 0
    while x < w:
        flag3 = 0
        K = [s[y][x] for y in range(h)]
        for i in range(len(L)):
            l, r = L[i]
            k_sum = sum(K[l:r])
            if now[i] + k_sum > k:
                cnt += 1
                if flag == 0:
                    flag2 = 1
                    break
                else:
                    flag = 0
                    now = [0] * len(L)
                    flag3 = 1
                    break
            else:
                now[i] += k_sum
        else:
            flag = 1
        if flag3:
            continue
        if flag2:
            break
        x += 1
    else:
        ans = min(ans, cnt)


print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(700000)
from itertools import product

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

def print_l(l):
    print(' '.join(map(str, l)))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

h, w, k = l_in()
S = list(map(lambda _: s_in(), range(h)))

sums = [[0 for _ in range(w)] for _ in range(h)]

sums[0][0] = int(S[0][0])

for i in range(1, h):
    sums[i][0] = sums[i-1][0] + int(S[i][0])

for j in range(1, w):
    sums[0][j] = sums[0][j-1] + int(S[0][j])

for i in range(1, h):
    for j in range(1, w):
        sums[i][j] = sums[i][j-1] + sums[i-1][j] - sums[i-1][j-1] + int(S[i][j])

def sq(x1, x2, y1, y2):
    if x1 > 0 and y1 > 0:
        return -sums[x1-1][y2] - sums[x2][y1-1] + sums[x1-1][y1-1] + sums[x2][y2]
    if x1 > 0 and y1 == 0:
        return -sums[x1-1][y2] + sums[x2][y2]
    if x1 == 0 and y1 > 0:
        return -sums[x2][y1-1] + sums[x2][y2]
    if x1 == 0 and y1 == 0:
        return sums[x2][y2]

def exec(i, list):
    current = i
    while current < h:
        exec(current, )

        current += 1

res = h*w




for ss in product('01', repeat=h-1):
    lis = []
    start = 0
    current = 0
    for s in ss:
        if s == '1':
            lis.append((start, current))
            start = current + 1
        current += 1
    lis.append((start, h-1))

    
    j1 = 0
    cut = 0
    for j2 in range(w-1):
        for i1, i2 in lis:
            if sq(i1, i2, j1, j2) <= k and sq(i1, i2, j1, j2+1) > k:
                
                cut += 1
                j1 = j2+1


    
    
    
    if all(sq(i1, i2, j1, w-1) <= k for i1, i2 in lis):
        cut += 1
        res = min(res, cut-1+len(lis)-1)

print(res)