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):
def inputs(): return [int(x) for x in input().split()]
from collections import defaultdict
def popcnt(n):
    c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff)
    return c
h,w,k= inputs()
s = [list(input()) for _ in range(h)]
res = 10**8
for bit in range(0,1<<h):
    l = popcnt(bit)
    cnt = [0]*(l+1)
    cnt2 = []
    ans = 0
    for i in range(w):
        cnt1=0
        cnt2=[]
        for j in range(h):
            if bit&1<<j and j!=0:
                cnt1+=1
            if s[j][i]=="1":
                cnt[cnt1]+=1
                cnt2.append(cnt1)
                
                if k<cnt[cnt1]:
                    cnt = [0]*(l+1)
                    ans+=1
                    for m in cnt2:
                        cnt[m]+=1
                        if k<cnt[m]:
                            ans+=10**9
    
    res = min(res,ans+l)
print(res)

Solution (Python):
H, W, K = map(int, input().split())
X = []
import sys;input=sys.stdin.readline
for _ in range(H):
    X.append(input().strip())

ks = [[0]*(W+1) for _ in range(H+1)]

for i in range(1, H+1):
    for j in range(1, W+1):
        ks[i][j] = ks[i][j-1] + ks[i-1][j] - ks[i-1][j-1] + int(X[i-1][j-1])




R = 10**18
for ii in range(2**(H-1)):
    i = ii
    c = 0
    cs = []
    while i:
        if i%2:
            cs.append(c)
        i //= 2
        c += 1
    b = 0
    r = 0
    cs.append(H-1)

    tmp = []
    fff = False
    for j in range(1, W+1):
        cb = 0
        for c in cs:

            if ks[c+1][j] - ks[c+1][b] - ks[cb][j] + ks[cb][b] > K:
                if j - b == 1:
                    fff = True
                tmp.append(j)
                r += 1
                b = j-1
                break
            cb = c+1
    if fff:
        continue


    R = min(R, r+len(cs)-1)
print(R)

Solution (Python):
def main():
    import sys
    input=sys.stdin.readline
    h,w,k=map(int,input().split())
    S=[]
    for _ in range(h):
        s=list(map(int,list(input().rstrip())))
        S.append(s)
    ans=10**5
    for i in range(2**(h-1)):
        l=[0]
        for j in range(h-1):
            if i&1<<j:
                l.append(l[-1]+1)
            else:
                l.append(l[-1]) 
        ans_=l[-1]
        ll=[0]*h
        j=0
        flag=0
        while j<w:
            for p in range(h):
                ll[l[p]]+=S[p][j]
            if max(ll)>k and flag==0:
                flag=1
                ans_+=1
                ll=[0]*h
            elif max(ll)>k and flag==1:
                ans_=10**5
                break
            else:
                j+=1
                flag=0
        ans=min(ans,ans_)
    print(ans)
if __name__ == '__main__':
    main()

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

min_num = float("inf")
for i in range(1<<(h-1)):
    c = 0
    d = {0:0}
    bar = 0
    for ii in range(1,h):
        if i&(1<<(ii-1)):
            c += 1
            bar += 1
        d[ii] = c

    
    ss = [0]*(c+1)
    invalid = False
    for wi in range(w):
        flag = False
        ss_tmp = [0]*(c+1)
        for hi in range(h):
            if A[hi][wi] == "1":
                ss_tmp[d[hi]] += 1
                ss[d[hi]] += 1
                if ss_tmp[d[hi]] > k:
                    invalid = True
                if ss[d[hi]] > k:
                    flag = True

        if flag:
            ss = ss_tmp
            bar += 1
        
        

    if not invalid:
        min_num = min(min_num, bar)

    
    bar = bin(i).count("1")
    ss = [0] * (c + 1)
    invalid = False
    for wi in range(w-1, -1, -1):
        flag = False
        ss_tmp = [0] * (c + 1)
        for hi in range(h):
            if A[hi][wi] == "1":
                ss_tmp[d[hi]] += 1
                ss[d[hi]] += 1
                if ss_tmp[d[hi]] > k:
                    invalid = True
                if ss[d[hi]] > k:
                    flag = True

        if flag:
            ss = ss_tmp
            bar += 1
        
        

    if not invalid:
        min_num = min(min_num, bar)

print(min_num)

Solution (Python):
h,w,k = map(int,input().split())
choco = []
mcut = h+w
for i in range(h):
    choco.append(list(map(int,list(input()))))
for i in range(2**(h-1)):
    chocos = []
    cut = 0
    choco1 = choco[0][:]
    for j in range(h-1):
        if i >> j & 1:
            chocos.append(choco1)
            choco1 = choco[j+1][:]
            cut += 1
        else:
            for l in range(w):
                choco1[l] += choco[j+1][l]
    chocos.append(choco1)
    num = len(chocos)
    chocosum = [0 for _ in range(num)]
    flag = True
    for j in range(w):
        for l in range(num):
            if chocos[l][j] > k:
                flag = False
            chocosum[l] += chocos[l][j]
            if chocosum[l] > k:
                cut += 1
                chocosum = [chocos[_][j] for _ in range(num)]
                break
    if flag:
        mcut = min(cut,mcut)
print(mcut)

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

area = [input() for _ in range(H)]
ans = float('inf')
S = []
for w in range(W):
    s = [0, ]
    for h in range(H):
        if area[h][w] == '1':
            s.append(s[-1]+1)
        else:
            s.append(s[-1])
    S.append(s)

for i in range(1 << H-1):
    flag = False
    tmp_ans = 0

    tmp = 0
    flag1 = [False for _ in range(H)]
    flag1[-1] = True
    for j in range(H):
        if i >> j & 1 == 1:
            tmp_ans += 1
            flag1[j] = True
    T = tmp_ans+1
    counter = [0 for _ in range(T)]

    for w in range(W):
        tmp_counter = []
        before = 0
        for k, f in enumerate(flag1):
            if f:
                tmp_counter.append(S[w][k+1] - S[w][before])
                before = k+1
        
        for tmp in tmp_counter:
            if tmp > K:
                flag = True
        if flag:
            tmp_ans = float('inf')
            break

        for k, tmp in enumerate(tmp_counter):
            if counter[k]+tmp > K:
                tmp_ans += 1
                counter = tmp_counter
                break
            else:
                counter[k] += tmp
    ans = min(ans, tmp_ans)

print(ans)

Solution (Python):
import sys 
MOD = 10**9 +7
INF = 10**5

def main():
    h,w,k = map(int,input().split())
    grid = [[0] * (w + 1)] + [[0] + [int(i) for i in list(input())] for _ in range(h)]
    

    for i in range(h + 1):
        for j in range(1,w + 1):
            grid[i][j] += grid[i][j - 1]
    
    for i in range(1,h + 1):
        for j in range(w + 1):
            grid[i][j] += grid[i - 1][j]
    
    ans = INF
    for bit in range(1<<(h - 1)):
        flag = False
        cut = [0]
        for i in range(h - 1):
            if (bit>>i)&1:
                    cut.append(i + 1)
        cut.append(h)
        
        l = len(cut)
        cnt = l - 2
        c = 0
        for j in range(1,w + 1):
            for i in range(1,l):
                
                a = cut[i - 1]
                b = cut[i]
                if grid[b][j] - grid[b][c] - grid[a][j] + grid[a][c] > k:
                    if j != 1:
                        c = j - 1
                        cnt += 1
                        break
                    else:
                        flag = True
                        break
            if flag:
                break
        if flag == False:
            ans = min(ans,cnt)
    
    print(ans)

if __name__=='__main__':
    main()

Solution (Python):
import numpy as np
h, w, k = list(map(int, input().split()))
ss = []
for _ in range(h):
    s = list(map(int, list(input())))
    ss.append(s)

from itertools import product

mi = 1e9
ss = np.array(ss)
sss = np.cumsum(ss, axis = 1)
for binary in product([0, 1], repeat=h - 1):
    binary  = [0] + list(binary)
    
    ssss = [0]
    for j in range(h):
        if binary[j] == 1:
            ssss.append(sss[j])
        else:
            ssss[-1] = sss[j] + ssss[-1]
        
    ssss = np.array(ssss)
    if np.max(np.diff(ssss, axis = 1)) > k:
        continue
    
    count = 0
    for i in range(w):
        if max(ssss[:, i]) > k:
            ssss -= ssss[:, i - 1][:, None]
            count += 1
    count += sum(binary)


    if count < mi:
        mi = count
print(mi)

Solution (Python):
from pprint import pprint
h, w, k = map(int, input().split())
maze = []
ts = []
for _ in range(h):
    l = input()
    l = list(map(int, list(l)))
    
    x = 0
    tmps = []
    for j in range(w):
        x += l[j]
        tmps.append(x)
    ts.append(tmps)
    maze.append(l)




bin_a = ["{:09b}".format(a) for a in range(0, 2 ** (h - 1))]

res = 9999999
for cutpat in bin_a:
    cutpat = cutpat[::-1]
    
    cutsum = [0] * 10
    gr = [-1] * 10
    gr[0] = 0
    grnum = 0
    for i in range(1, h):
        if cutpat[i - 1] == "1":
            grnum += 1
        gr[i] = grnum
    

    firstFail = False

    cutcount = cutpat.count("1") 
    for i in range(w): 
        
        for j in range(h):
            cutsum[ gr[j] ] += maze[j][i]
        
        isFail = False
        for j in range(h):
            
            if cutsum[j] > k:
                
                isFail = True
                if i == 0:
                    firstFail = True
        if isFail:
            
            cutcount += 1
            cutsum = [0] * 10
            for j in range(h):
                cutsum[gr[j]] += maze[j][i]
            for j in range(h):
                
                if cutsum[j] > k:
                    isFail = True
                    if i == 0:
                        firstFail = True

    if firstFail:
        continue

    res = min(res, cutcount)

print(res)

Solution (Python):
h,w,kk = map(int,input().split())
arr = []
for i in range(h):
    arr.append(list(map(int,list(input()))))

h_loop = 2**(h-1)
ans = 100000000
for i in range(h_loop):
    sep = format(i,'b').zfill(h-1)
    ups = sum(map(int,list(sep)))
    slash = ups
    buf = [0 for j in range(ups+1)]
    temp_buf = [0 for j in range(ups+1)]
    is_sep = False
    
    
    
    for j in range(w):
        
        
        b_ind = 0
        is_sep = False
        for k in range(h):
            if k == 0:
                temp_buf[b_ind] += arr[k][j]
            else:
                if sep[k-1] == "1":
                    b_ind += 1
                    temp_buf[b_ind] += arr[k][j]
                else:
                    temp_buf[b_ind] += arr[k][j]

        for k in range(ups+1):
            if temp_buf[k] + buf[k] > kk :
                is_sep = True
        for k in range(ups+1):
            if buf[k] > kk :
                slash = 1000000000
        
        
        
        if is_sep:
            slash += 1
            buf = temp_buf
        else:
            for k in range(ups+1):
                buf[k] += temp_buf[k]

        temp_buf = [0 for j in range(ups + 1)]


    
    if ans > slash:
        ans = slash

print(ans)

Solution (Python):
def examA():
    N, M = LI()
    ans = N*(N-1)//2 + M*(M-1)//2
    print(ans)
    return

def examB():
    def judge(A):
        
        n = len(A)
        for i in range(n//2):
            if A[i]!=A[n-i-1]:
                return False
        return True
    S = SI()
    N = len(S)
    if not judge(S):
        print("No")
        return
    if judge(S[:(N-1)//2]) and judge(S[(N+1)//2:]):
        print("Yes")
    else:
        print("No")
    return

def examC():
    L = I()
    ans = (L/3)**3
    print(ans)
    return

def examD():
    N = I()
    A = LI()
    D = defaultdict(bool)
    C = Counter(A)
    M = 0
    for key,c in C.items():
        M += c*(c-1)//2
    
    
    ans = [0]*N
    for i in range(N):
        a = A[i]
        c = C[a]
        ans[i] = M -(c*(c-1)//2) + ((c-1)*(c-2)//2)
    for v in ans:
        print(v)
    return

def examE():
    H, W, K = LI()
    S = [SI()for _ in range(H)]
    SH = [[0] * (W + 1) for _ in range(H + 1)]
    for i in range(H):
        now = 0
        for j in range(W):
            now += int(S[i][j])
            SH[i + 1][j + 1] = SH[i][j + 1] + now

    def calc(a,b,c,d):
        return SH[c][d] - SH[a][d] - SH[c][b] + SH[a][b]

    ans = H+W-2
    mask = 2**(H-1)-1
    for i in range(mask+1):
        cut = [0]
        cur = 0
        for j in range(H-1):
            if i&(1<<j)==(1<<j):
                cut.append(j+1)
                cur += 1
        cut.append(H)
        L = [0]*(len(cut)-1)
        flag = True
        for w in range(W):
            now_L = [0]*(len(cut)-1)
            for s in range(len(cut) - 1):
                n = calc(cut[s], w, cut[s + 1], w + 1)
                now_L[s] = n
                if n+L[s]> K:
                    if n>K:
                        flag = False
                        cur = inf
                        break
                    cur += 1
                    L = [0] * (len(cut))
            if not flag:
                break
            for s in range(len(cut) - 1):
                L[s] += now_L[s]
        if not flag:
            continue
        ans = min(ans,cur)

    print(ans)
    return
"""
2 1 1
1
1
"""

def examF():
    N, S = LI()
    A = LI()
    dp = [[0]*N for _ in range(S*2)]

    ans = 0
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examE()

"""

"""

Solution (Python):
H,W,K=map(int,input().split())
S=[[int(c) for c in input()] for i in range(H)]
A=[[0]*(W+1) for i in range(H+W)]
for i in range(H):
    for j in range(W):
        A[i+1][j+1]=A[i+1][j]+A[i][j+1]-A[i][j]+S[i][j]
from itertools import product
r=2000
def v(l,r,t,b):
    return A[b][r]-A[t][r]-A[b][l]+A[t][l]
for x in product((0,1),repeat=H-1):
    l=0
    a=sum(x)
    for j in range(W):
        f=1
        t=0
        for k in range(H-1):
            if x[k]:
                if v(l,j+1,t,k+1)>K:
                    f=2 if l<j else 0
                    l=j
                t=k+1
        if v(l,j+1,t,H)>K:
            f=2 if l<j else 0
            l=j
        if f==2:
            a+=1
        elif f==0:
            a=-1
            break
    if a>=0:
        r=min(r,a)
print(r)

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

ans = float("inf")
for state in range(2 ** (H - 1)):
    flag = True

    
    yoko = 0
    for i in range(H - 1):
        if (state >> i) & 1:
            yoko += 1

    res = yoko

    
    cntHW = [0] * (yoko + 1)
    for j in range(W):
        
        now = 0
        
        cntH = [0] * (yoko + 1)
        for i in range(H):
            if S[i][j] == 1:
                cntH[now] += 1

            if (state >> i) & 1: 
                now += 1
        
        for cH in cntH:
            if cH > K:
                flag = False

        
        MAX = max(cH + cHW for cH,cHW in zip(cntH,cntHW))
        if MAX > K:
            res += 1
            cntHW = cntH[::]
        else:
            for i in range(yoko + 1):
                cntHW[i] += cntH[i]

    if flag:
        ans = min(ans, res)

print(ans)

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

    m = 10 * 1000
    for h in range(2 ** (H - 1)):
        T = []
        s = [0]
        c = 0
        for i in range(H - 1):
            if h & (1 << i):
                T.append(s)
                s = [i + 1]
                c += 1
            else:
                s.append(i + 1)
        T.append(s)
        C = [0] * len(T)
        CC = [0] * len(T)
        fail = False
        for w in range(W):
            split = False
            for i, t in enumerate(T):
                cc = 0
                for j in t:
                    if S[j][w] == '1':
                        cc += 1
                CC[i] = cc
                if C[i] + CC[i] > K:
                    split = True
            if split:
                for i in range(len(C)):
                    C[i] = CC[i]
                    if C[i] > K:
                        fail = True
                c += 1
            else:
                for i in range(len(C)):
                    C[i] += CC[i]
        if not fail:
            m = min(c, m)
    return m

print(main())

Solution (Python):
H, W, K = map(int, input().split())
chocolate = [input() for _ in range(H)]
cumsums = [[0] for _ in range(W)]
for w in range(W):
    for h in range(H):
        cumsums[w].append(cumsums[w][-1] + int(chocolate[h][w]))
ans = (H-1) + (W-1)
for bit in range(1 << (H-1)):
    h_splits = [0]
    temp = 0
    for l in range(H):
        if (bit >> l) & 1: h_splits.append(l+1); temp += 1
    h_splits.append(H)
    n_sp_hr = (len(h_splits) - 1)
    counter = [0] * n_sp_hr
    for w in range(W):
        admissible = True
        cumsum = cumsums[w]
        to_be_added = [0] * n_sp_hr
        for s in range(n_sp_hr):
            to_be_added[s] = cumsum[h_splits[s+1]] - cumsum[h_splits[s]]
            if to_be_added[s] > K: admissible = False; break
        if not admissible: break
        for s in range(n_sp_hr):
            counter[s] += to_be_added[s]
            if counter[s] > K: temp += 1; counter = to_be_added[:]; break
    else:
        ans = min(ans, temp)
print(ans)

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

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


ans = 10 ** 6
for i in range(2 ** (h-1)):
    sep = []
    tmp = [0]
    for j in range(h-1):
        if (i >> j) & 1:
            tmp.append(j+1)
        else:
            if tmp != []:
                sep.append(tmp)
            tmp = [j+1]
    sep.append(tmp)
    
    
    idx = 0
    cnt = 0
    for j in range(1,w+1):
        flg = False
        for l in sep:
            tmp_sum = sum([cum_s[x][j] - cum_s[x][idx] for x in l])
            if tmp_sum > k:
                if j - idx == 1:
                    cnt = 10 ** 6
                flg = True
        
        if flg:
            cnt += 1
            idx = j-1 
    
    ans = min(ans, len(sep)-1 + cnt)

if w == 1:
    x = sum([s[i] == '1' for i in range(h)])
    print(max(0, -(-x // k)-1))
elif h == 1:
    x = sum([s[0][i] == '1' for i in range(w)])
    print(max(0, -(-x // k)-1))
else:
    print(ans)

Solution (Python):

import sys
from itertools import product
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return map(int,input().split())
def LI(): return list(map(int,input().split()))

def main():
    H,W,K = MAP()
    S = [input() for _ in range(H)]
    accum_s = [[0]*W for _ in range(H)]

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

    answer = 10**9
    for p in product([0,1],repeat=H-1):
        one_index = [i for i in range(H-1) if p[i] == 1]
        one_index.append(H-1)
        score = 0
        prev_j = -1
        outflag = False

        for j in range(W):
            if outflag:
                break
            prev_i = 0
            for slice_index in one_index:
                group_count = 0
                
                while prev_i <= slice_index:
                    if prev_j == -1:
                        group_count += accum_s[prev_i][j]
                    else:
                        group_count += accum_s[prev_i][j] - accum_s[prev_i][prev_j]

                    prev_i += 1
                
                if group_count > K:
                    if prev_j == j-1:
                        outflag = True
                    score += 1
                    prev_j = j-1
                    break
        else:
            if answer > score+len(one_index)-1:
                answer = score+len(one_index)-1
    
    print(answer)


if __name__ == '__main__':
    main()

Solution (Python):
import copy
h,w,k=map(int,input().split())
s=[]
for i in range(h):
  s+=[[int(i) for i in input()]]
ans=h+w-2
for i in range(2**(h-1)):
  t=format(i,''.join(['0',str(h-1),'b']))
  a=sum([int(tt) for tt in t])
  h1=[0]+[ii+1 for ii in range(h-1) if t[ii]=='1']+[h]
  h2=[[h1[ii],h1[ii+1]] for ii in range(len(h1)-1)]
  j0=0
  slsum=[0]*len(h2)
  sl=[0]*len(h2)
  for j in range(w):
    for l in range(len(h2)):
      sl[l] = sum([s[ii][j] for ii in range(h2[l][0],h2[l][1])])
      slsum[l]+=sl[l]
      if sl[l]>k:
        a=-1
        break
    if a==-1:
      break
    if any([x>k for x in slsum]):
      slsum=copy.deepcopy(sl)
      a+=1
  if a==-1:
    continue
  ans=min(ans,a)
print(ans)

Solution (Python):
h,w,K = map(int,input().split())
cum = [[0 for _ in range(w+1)]]
for _ in range(h):
  tmp = input()
  add = [0]
  for j in range(w):
    add.append(add[-1]+int(tmp[j]))
  cum.append(add)
for i in range(h):
  for j in range(w):
    cum[i+1][j+1] += cum[i][j+1]
time = [0 for _ in range(h-1)]
def nex(time):
  for d in range(h-1):
    if time[d] == 0:
      time[d] = 1
      return time
    else:
      time[d] = 0
  else:
    return 'over'
can = []
while time != 'over':
  tmp = [0]
  for d in range(h-1):
    if time[d] == 1:
      tmp.append(d+1)
  tmp.append(h)
  
  l = len(tmp) - 1
  ans = l - 1
  now = 0
  att = 1
  for j in range(1,w+1):
    cand = []
    for k in range(l):
      cand.append(cum[tmp[k+1]][j] - cum[tmp[k+1]][now] - cum[tmp[k]][j] + cum[tmp[k]][now])
    
    if max(cand) > K:
      now = j - 1
      ans += 1
      cane = []
      for k in range(l):
        cane.append(cum[tmp[k+1]][j] - cum[tmp[k+1]][now] - cum[tmp[k]][j] + cum[tmp[k]][now])
        
          
        if max(cane) > K:
          ans += 1
          now = j
    
  else:
    can.append(ans)
  time = nex(time)
  
print(min(can))

Solution (Python):
import sys
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

h,w,k = na()
s = []
for i in range(h):
    o = list(map(int, list(ns())))
    q = 0
    r = []
    for x in o:
        q += x
        r.append(q)
    s.append(r)

ans = 1000000000000000000

for i in range(2**(h-1)):
    b = [0]*w
    c = []
    d = 0 
    for j in range(h):
        b = [x + y for (x, y) in zip(b, s[j])]
        if j == h:
            break
        if ((i >> j) & 1):
            c.append(b)
            b = [0]*w
            d += 1
    c.append(b)
    e = -1
    for p in range(w):
        flag = False
        for l in c:
            u = 0 if e == -1 else l[e]
            if l[p]-u > k:
                if p-e == 1:
                    flag = True
                    break
                e = p-1
                d += 1
                break
        if flag:
            d = 1000000000000000000
            break
    ans = min(ans, d)

print(ans)

Solution (Python):
import numpy as np
import time
import random

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

start = time.time()



s2 = [np.cumsum(row, dtype=np.int32) for row in s]

mi = 10 ** 9
seed = [0] * 1000 + [1] * 1000
selected = []


ls = [0]*(H-1)

num = 1
tmp = 0

s3 = np.zeros((num, W))
s3[0] = s2[0]
cnt = 0
for i in range(H - 1):
    if ls[i] == 0:
        s3[cnt] += s2[i + 1]
    else:
        cnt += 1
        s3[cnt] = s2[i + 1]
s3 = s3.T

hosei = np.zeros(num)
for w in range(W):
    if np.max(s3[:][w] - hosei) > K:
        tmp += 1
        if w != 0:
            hosei = s3[:][w - 1]
        else:
            tmp = 10 ** 9
if mi > tmp:
    mi = tmp



ls = [1]*(H-1)

num = H
tmp = num - 1

s3 = np.zeros((num, W))
s3[0] = s2[0]
cnt = 0
for i in range(H - 1):
    if ls[i] == 0:
        s3[cnt] += s2[i + 1]
    else:
        cnt += 1
        s3[cnt] = s2[i + 1]
s3 = s3.T

hosei = np.zeros(num)
for w in range(W):
    if np.max(s3[:][w] - hosei) > K:
        tmp += 1
        if w != 0:
            hosei = s3[:][w - 1]
        else:
            tmp = 10 ** 9
if mi > tmp:
    mi = tmp
    
while time.time() - start < 1.7:
    t = random.sample(seed, k=H - 1)
    if t in selected:
        continue
    selected.append(t)
    ls = t
    
    num = sum(ls) + 1
    tmp = num - 1
    
    s3 = np.zeros((num, W))
    s3[0] = s2[0]
    cnt = 0
    for i in range(H - 1):
        if ls[i] == 0:
            s3[cnt] += s2[i + 1]
        else:
            cnt += 1
            s3[cnt] = s2[i + 1]
    s3 = s3.T
    
    hosei = np.zeros(num)
    for w in range(W):
        if np.max(s3[:][w] - hosei) > K:
            tmp += 1
            if w != 0:
                hosei = s3[:][w - 1]
            else:
                tmp = 10 ** 9
    if mi > tmp:
        mi = tmp
z = 0
for row in s:
    z += np.sum(row)
if z <= K:
    mi = 0
print(mi)

Solution (Python):


ans = 10 ** 12


def main():
    import sys
    import numpy as np
    sys.setrecursionlimit(10 ** 6)
    from copy import deepcopy
    

    def dump(*args):
        sys.stderr.write(str(args))

    h, w, K = map(int, input().split())
    s = [list(map(int, list(input()))) for _ in range(h)]
    s = np.array(s).T
    s = s.tolist()
    

    waru = set()

    def dfs(i):
        if i == h-1:
            cho = [0] * (len(waru) + 1)
            bunkatsu = [False]*(w-1)
            sl = [0]
            sl.extend(list(waru))
            sl.append(h)
            t = len(waru)
            j = 0
            while j < w:
                for k in range(1, len(sl)):
                    
                    cho[k - 1] += sum(s[j][sl[k - 1]: sl[k]])
                
                for k in range(len(sl)-1):
                    if cho[k] > K:
                        if bunkatsu[j-1]:
                            return
                        cho = [0] * (len(waru) + 1)
                        bunkatsu[j-1] = True
                        t += 1
                        j -= 1
                j += 1
            
            global ans
            ans = min(ans, t)
            return
        waru.add(i+1)
        dfs(i + 1)
        waru.remove(i+1)
        dfs(i + 1)
    dfs(0)
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
def inpl():
    return list(map(int, input().split()))


def solve(i):
    def getChoco(choco, w):
        for i in range(H):
            if S[i][w] == "1":
                choco[t[i]] += 1
        return choco

    t = {}
    t[0] = 0
    x = 0
    for h in range(H - 1):
        if (i >> h) % 2 == 1:
            x += 1
            t[h + 1] = x
        else:
            t[h + 1] = x
    choco = [0 for _ in range(x + 1)]
    ret = x
    

    for w in range(W):
        choco = getChoco(choco, w)
        if any(c > K for c in choco):
            choco = getChoco([0 for _ in range(x + 1)], w)
            if any(c > K for c in choco):
                return H + W - 2
            else:
                ret += 1
    return ret


H, W, K = inpl()
S = [input() for _ in range(H)]

ans = H + W - 2
for i in range(2**(H - 1)):
    ans = min(ans, solve(i))

print(ans)

Solution (Python):
import bisect


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

    C = [[0] for _ in range(W)]
    for i in range(W):
        for j in range(H):
            if S[j][i] == "1":
                C[i].append(C[i][-1] + 1)
            else:
                C[i].append(C[i][-1])

    if W == 1:
        c = C[0]
        res = 0
        cut = 0
        for i in range(H):
            if c[i + 1] - c[cut] > K:
                res += 1
                cut = i
        return res

    res = 20000
    for i in range(2 ** (H - 1)):
        f = 0
        cut = [[0]]
        for j in range(H - 1):
            if (2 ** j) & i != 0:
                cut[-1].append(j + 1)
                cut.append([j + 1])
        cut[-1].append(H)
        lc = len(cut)
        tres = lc - 1
        w = [0 for _ in range(lc)]
        for k in range(W):
            if f == 1:
                break
            for j in range(lc):
                t = C[k][cut[j][1]] - C[k][cut[j][0]]
                if t > K:
                    f = 1
                    break
                w[j] += t
            if max(w) > K:
                tres += 1
                w = [C[k][cut[p][1]] - C[k][cut[p][0]] for p in range(lc)]
        if f == 0:
            res = min(res, tres)

    return res


print(main())

Solution (Python):
from itertools import product

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

ans = float("inf")
for pat in product([1, 0], repeat=h):
    prev = 2
    sm = -1
    for e in pat:
        if e != prev:
            sm += 1
        prev = e
    
    

    ss = [[0] * w for _ in range(h)]
    for wi in range(w):
        acc = 0
        prev = 2
        for hi, e in enumerate(pat):
            if e != prev:
                acc = 0
            if s[hi][wi]:
                acc += 1
            ss[hi][wi] = acc
            prev = e

    sss = [[0] * w for _ in range(h)]
    for hi in range(h):
        for wi in range(w):
            if wi == 0:
                sss[hi][wi] = ss[hi][wi]
            else:
                sss[hi][wi] = sss[hi][wi-1] + ss[hi][wi]

    base = [0] * h
    cp_prev = [0] * h
    for wi in range(w):
        mx = 0
        cp = [0] * h
        for hi in range(h):
            mx = max(mx, sss[hi][wi] - base[hi])
            cp[hi] = sss[hi][wi]
        if mx > k:
            if wi == 0:
                sm = 10000
            sm += 1
            base = cp_prev
        cp_prev = cp

    ans = min(ans, sm)

print(ans)