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 collections import defaultdict, deque, Counter
import math


from bisect import bisect_left, bisect_right
import heapq




input = sys.stdin.readline

getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = 10 ** 20
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)


def nck(n, k, kaijyo):
    return (npk(n, k, kaijyo) * divide(kaijyo[k])) % MOD


def npk(n, k, kaijyo):
    if k == 0 or k == n:
        return n % MOD
    return (kaijyo[n] * divide(kaijyo[n-k])) % MOD


def kaijyo(n):
    ret = [1]
    for i in range(1, n + 1):
        ret.append((ret[-1] * i)% MOD)
    return ret


def cut(pt, grid, k, h, w):
    pat = []
    for i in range(h-1):
        if pt % 2 == 1:
            pat.append("1")
        else:
            pat.append("0")
        pt //= 2

    
    slice = Counter(pat)["1"]
    pat = pat + ["0"]
    white = [0] * (slice + 1)
    ret = 0
    for i in range(w):
        tw = [0] * (slice + 1)
        dan = 0
        for j in range(h):
            if grid[j][i] == "1":
                tw[dan] += 1
            if pat[j] == "1":
                dan += 1

        if max(tw) > k:
            return INF
        reset = False
        for w1, w2 in zip(white, tw):
            if w1 + w2 > k:
                ret += 1
                reset = True
                break
        if reset:
            white = tw
        else:
            for up in range(slice + 1):
                white[up] += tw[up]

    return ret + slice

def solve():
    h, w, k = getList()
    grid = []
    for i in range(h):
        grid.append(getS())

    ans = INF
    for i in range(2 ** (h-1)):
        tmp = cut(i, grid, k, h, w)
        
        ans = min(ans, tmp)
    print(ans)


def main():
    n = getN()
    for _ in range(n):
        solve()


if __name__ == "__main__":
    
    solve()

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

H,W,K=map(int,input().split())
S=[list(map(int,list(input()))) for _ in range(H)]
ans=INF
for i in range(2**(H-1)):
    cnt=1+bin(i).count('1')
    tmp=cnt-1
    div=[0]*H
    for j in range(H-1):
        if (i>>j)&1:
            div[j+1]=div[j]+1
        else:
            div[j+1]=div[j]
    wc=[0]*cnt
    for x in range(W):
        tmp_wc=[0]*cnt
        f=False
        for y in range(H):
            if S[y][x]==1:
                tmp_wc[div[y]]+=1
                wc[div[y]]+=1
                if wc[div[y]]>K:
                    f=True
                if tmp_wc[div[y]]>K:
                    break
        else:
            if f:
                tmp+=1
                wc=tmp_wc
                tmp_wc=[0]*cnt
                f=False
            continue
        break
    else:
        ans=min(ans,tmp)
print(ans)

Solution (Python):
import sys
from itertools import combinations as combi
input = sys.stdin.readline
H, W, K = map(int, input().split())
S = [list(map(int, list(input())[: -1])) for _ in range(H)]
res = H + W - 2
for t in range(H):
  for c in combi([x for x in range(1, H)], t):
    s = set(c)
    table = [0] * (t + 1)
    rres = t + 0
    for x in range(W):
      i = 0
      y = 0
      while y < H:
        if y in s: i += 1
        table[i] += S[y][x]
        y += 1
        if table[i] > K: break
      else: continue
      rres += 1
      table = [0] * (t + 1)
      i = 0
      y = 0
      while y < H:
        if y in s: i += 1
        table[i] += S[y][x]
        y += 1
        if table[i] > K: break
      else: continue
      rres = H + W - 2
      break

    
    res = min(res, rres)
print(res)

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

h, w, kk = map(int, input().split())
ss = [[0 for _ in range(h)] for _ in range(w)]
for i in range(h):
    for j, c in enumerate(list(input().strip())):
        if c == '1':
            ss[j][i] = 1

ans = 100000
for i in range(2 ** (h - 1)):
    end = []
    for j in range(h - 1):
        if i & 2 ** j:
            end.append(j + 1)
    end.append(h)
    start = [0]
    for j in end:
        start.append(j)
    start.pop()
    sums = [0] * len(start)

    tans = len(start) - 1
    imp = False
    for j in range(w):
        reset = False
        for k, (s, e) in enumerate(zip(start, end)):
            sums[k] += sum(ss[j][s:e])
            if sums[k] > kk:
                reset = True
                break
        if reset:
            tans += 1
            for k, (s, e) in enumerate(zip(start, end)):
                sums[k] = sum(ss[j][s:e])
                if sums[k] > kk:
                    imp = True
        if imp:
            break
    if not imp:
        ans = min(ans, tans)

print(ans)

Solution (Python):
import numpy as np
import itertools
H, W, K = [int(_) for _ in input().split()]
S = np.zeros((H + 1, W + 1), dtype=int)
S[1:, 1:] = [[int(_) for _ in input()] for _ in range(H)]
cum = S.cumsum(axis=0).cumsum(axis=1)


ans = 10**10
for bs in itertools.product([True, False], repeat=H - 1):
    bs = [True] + list(bs) + [True]
    idxs = []
    for i, b in enumerate(bs):
        if b:
            idxs += [i]
    cum2 = np.array([cum[i2] - cum[i1] for i1, i2 in zip(idxs, idxs[1:])])
    i = 0
    cnt = sum(bs) - 3
    while i < W:
        di = min(
            np.searchsorted(c[i + 1:] - c[i], K, side='right') for c in cum2)
        if di == 0:
            cnt = 10**10
            break
        i += di
        cnt += 1
    ans = min(ans, cnt)
print(ans)

Solution (Python):
from itertools import accumulate

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

min_split = 10**10

for i in range(2**(h-1)):
    li = []

    for j in range(h-1):
        if (i >> j)&1:
            li.append(j)
    li.append(h-1)
    lin = [0]*w
    total = []

    over = False

    for l in range(h):
        for m in range(w):
            lin[m] += s[l][m]
            if lin[m] > k:
                over = True
        if l in li:
            total.append(lin)
            lin = [0]*w

    if over:
        continue

    now = 0
    t = len(total)
    count = t-1

    for n in range(t):
        total[n] = [0]+list(accumulate(total[n]))
    for o in range(1,w+1):
        for p in range(t):
            if total[p][o]-total[p][now] > k:
                now = o-1
                count += 1
                break

    min_split = min(min_split,count)

print(min_split)

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
INF = 1 << 60


def main():
    H, W, K = map(int, readline().split())
    S = read().split()

    ans = INF

    for bit in range(1 << (H - 1)):
        idx = [0] * H
        for i in range(H - 1):
            if bit & (1 << i):
                idx[i + 1] = idx[i] + 1
            else:
                idx[i + 1] = idx[i]

        res = idx[-1]
        n = idx[-1] + 1
        A = [0] * n

        for j in range(W):
            B = [0] * n
            ok = True
            for i in range(H):
                if S[i][j] == '1':
                    B[idx[i]] += 1
                    if B[idx[i]] > K:
                        ok = False
                        break

            if not ok:
                res = INF
                break

            divided = False
            for k in range(n):
                A[k] += B[k]
                if A[k] > K:
                    divided = True
                    break

            if not ok:
                res = INF
                break
            if divided:
                A = B
                res += 1

        if ans > res:
            ans = res

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from itertools import combinations

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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

    ans = INF

    for r in range(H):
        for comb in combinations(range(1, H), r):
            sep = [0]
            sep.extend(list(comb))
            sep.append(H)

            res = r
            A = [0] * (r + 1)

            for j in range(W):
                B = [0] * (r + 1)
                for k in range(r + 1):
                    for i in range(sep[k], sep[k + 1]):
                        if S[i][j] == '1':
                            B[k] += 1

                ok = True
                divided = False
                for k in range(r + 1):
                    if B[k] > K:
                        ok = False
                        break
                    if A[k] + B[k] > K:
                        divided = True
                        break
                    else:
                        A[k] += B[k]

                if not ok:
                    res = INF
                    break
                if divided:
                    A = B
                    res += 1

            if ans > res:
                ans = res

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import math
H, W, K = map(int, input().split())
S = [list(map(lambda x: int(x=='1'), input())) for _ in range(H)]


def cal_min_vert_div(hs):
    cnt = 0
    n_h_div = len(hs)
    n_white = [0]*n_h_div
    for i in range(W):
        for j in range(n_h_div):
            n_white[j] += hs[j][i]
            if n_white[j] > K:
                n_white = [hs[k][i] for k in range(n_h_div)]
                cnt += 1
                if max(n_white)>K:
                    return math.inf
                break
    return cnt

ans = math.inf

for mask in range(2**(H-1)):
    hs = []
    tmp = S[0]
    for i in range(H-1):
        if mask>>i & 1:
            hs.append(tmp)
            tmp = S[i+1]
        else:
            tmp = [tmp[w]+S[i+1][w] for w in range(W)]
    hs.append(tmp)
    tmp = cal_min_vert_div(hs)+sum(map(int, bin(mask)[2:]))
    ans = min(ans, tmp)
print(ans)

Solution (Python):

H, W, K = map(int, input().split())
S = [input() for _ in range(H)]
ans = 10**9
for bit in range((1 << (H-1))):
    vidx = []
    gok = True
    g = 0
    gid = [0] * H
    for i in range(H-1):
        if (bit >> i) & 1:
            g += 1
        gid[i+1] = g
    g += 1
    gnum = [0]*g
    vertical = 0
    for w in range(W):
        ok = True
        one = [0]*g
        for h in range(H):
            one[gid[h]] += int(S[h][w])
            gnum[gid[h]] += int(S[h][w])
            if one[gid[h]] > K:
                gok = False
            if gnum[gid[h]] > K:
                ok = False
        if not ok:
            vertical += 1
            vidx.append(w)
            gnum = one

    
    
    
    
    
    
    if gok:
        if ans > g-1 + vertical:
            ans = g-1 + vertical
            
            
            
        
if ans == 10**9:
    print(-1)
else:
    print(ans)

Solution (Python):
def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    h, w, k = map(int, input().split())
    field = [[] for i in range(h)]
    for i in range(h):
        field[i] = [int(s) for s in input()]
    import numpy as np
    field = np.array(field, dtype=int)
    inf = 10 **4
    ans = inf
    for i in range(2**(h-1)):
        prev = 0
        damy = []
        tmp_ans = format(i, 'b').count('1')
        for j in range(h-1):
            if (i >> j)&1:
                damy.append(field[prev:j+1].sum(axis=0))
                prev = j+1
        damy.append(field[prev:].sum(axis=0))
        damy = np.array(damy,dtype=int).T
        if (damy > k).any():
            continue

        prev = 0
        cnt_w = np.zeros(tmp_ans+1, dtype=int)
        for l in range(w):
            cnt_w += damy[l]
            if (cnt_w > k).any():
                cnt_w = damy[l]
                tmp_ans += 1
            
        ans = min(ans, tmp_ans)
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):

import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from collections import deque
from functools import lru_cache
import bisect
import re
import queue
import decimal


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [Scanner.string() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [Scanner.int() for i in range(n)]


def solve():
    H, W, K = Scanner.map_int()
    S = Scanner.string_list(H)
    ans = int(1e15)
    for i in range(1 << (H - 1)):
        cut = 0
        pc = 1
        whites = [[0 for _ in range(W)] for _ in range(H)]
        for j in range(H - 1):
            for w in range(W):
                whites[cut][w] += S[j][w] == '1'
            if i >> j & 1:
                cut += 1
                pc += 1
        for w in range(W):
            whites[cut][w] += S[-1][w] == '1'
        flag = True
        for line in whites:
            for cnt in line:
                if cnt > K:
                    flag = False
        if not flag:
            continue
        cnt = [0 for _ in range(pc)]
        for w in range(W):
            flag = True
            for j in range(pc):
                if cnt[j] + whites[j][w] > K:
                    flag = False
            if not flag:
                cnt = [0 for _ in range(pc)]
                cut += 1
            for j in range(pc):
                cnt[j] += whites[j][w]
        ans = min(ans, cut)
    print(ans)


def main():
    
    
    
    
    
    
    solve()


if __name__ == "__main__":
    main()

Solution (Python):
H, W, K = map(int, input().split())
S = [input() for _ in range(H)]
d = 2 ** (H - 1)
mcut = 1008
for i in range(d):
  L = [0 for _ in range(H)]
  for j in range(1, H):
    L[j] = L[j-1] + i % 2
    i //= 2
  C = [0 for _ in range(L[H-1]+1)]
  cutp, cutq = True, True
  cut = L[H-1]
  for m in range(W):
    for l in range(H):
      C[L[l]] += int(S[l][m])
    if cutq:
      cutq = False
      if max(C) > K:
        cutp = False
        break
    else:
      if max(C) > K:
        cut += 1
        C = [0 for _ in range(L[H-1]+1)]
        for l in range(H):
          C[L[l]] += int(S[l][m])
    if cutp == False:
      break
  if cutp:
    if cut < mcut:
      mcut = cut
print(mcut)

Solution (Python):


import sys
input=sys.stdin.readline

def main():
    H,W,K=map(int,input().split())
    mas=[input().strip("\n") for i in range(H)]
    mincut=H*W
    for bit in range(2**(H-1)):
        sep=[]
        for s in range(H-1):
            if (bit>>s)&1:
                sep.append(s)
        cutcnt=len(sep)
        cnt=[0]*(len(sep)+1)
        for j in range(W):
            ci=0
            cntt=cnt[:]
            for i in range(H):
                if mas[i][j]=="1":
                    cnt[ci]+=1
                if i in sep:
                    ci+=1
            if max(cnt)>K:
                for i in range(len(sep)+1):
                    cnt[i]-=cntt[i]
                cutcnt+=1
        if max(cnt)>K:
            cutcnt=10000000000
        if cutcnt<mincut:
            mincut=cutcnt
    print(mincut)
                
    
    
if __name__=="__main__":
    main()

Solution (Python):

INF = 1<<60
def resolve():
    def judge(j):
        for i in range(group):
            cnt_Wchoco[i] += div_G[i][j]
            if cnt_Wchoco[i] > K:
                return False
        return True

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

    ans = INF
    for bit in range(1<<(H-1)):
        group = 0 
        row = [0]*H
        for i in range(H):
            
            row[i] = group
            if bit>>i & 1:
                group += 1
        group += 1 

        
        div_G = [[0] * W for _ in range(group)]
        for i in range(H):
            for j in range(W):
                div_G[row[i]][j] += G[i][j]

        num = group-1
        cnt_Wchoco = [0]*group
        for j in range(W):
            if not judge(j):
                num += 1
                cnt_Wchoco = [0] * group
                if not judge(j):
                    num = INF
                    break
        ans = min(ans, num)

    print(ans)

if __name__ == "__main__":
    resolve()

Solution (Python):
from itertools import accumulate as acc

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

acc_list = [list(acc([0] + s)) for s in S]

def solve(l, x, limit):
    part_num = len(l)-1
    ok, ng = x, W+1
    while abs(ok-ng) > 1:
        mid = (ok+ng)//2
        score = 0
        for i in range(part_num):
            s = 0
            for j in range(l[i], l[i+1]):
                
                s += acc_list[j][mid] - acc_list[j][x]
            score = max(s, score)
        if score <= limit:
            ok = mid
        else:
            ng = mid
    return ok

min_num = 10**18
for i in range(1<<(H-1)):
    l = []
    for j in range(H-1):
        if (i>>j)&1:
            l.append(j+1)
    h_split_num = len(l)
    l = [0] + l + [H]
    x = solve(l, 0, K)
    w_split_num = 0
    flag = True
    while x < W:
        w_split_num += 1
        r = solve(l, x, K)
        if x == r:
            flag = False
            break
        x = r
    if flag:
        split_num = w_split_num + h_split_num
        min_num = min(split_num, min_num)

print(min_num)

Solution (Python):
from itertools import accumulate as acc

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

acc_list = [list(acc([0] + s)) for s in S]

def solve(l, x, limit):
    part_num = len(l)-1
    ok, ng = x, W+1
    while abs(ok-ng) > 1:
        mid = (ok+ng)//2
        score = 0
        for i in range(part_num):
            s = 0
            for j in range(l[i], l[i+1]):
                
                s += acc_list[j][mid] - acc_list[j][x]
            score = max(s, score)
        if score <= limit:
            ok = mid
        else:
            ng = mid
    return ok

min_num = 10**18
for i in range(1<<(H-1)):
    l = []
    for j in range(H-1):
        if (i>>j)&1:
            l.append(j+1)
    h_split_num = len(l)
    l = [0] + l + [H]
    x = solve(l, 0, K)
    w_split_num = 0
    flag = True
    while x < W:
        w_split_num += 1
        r = solve(l, x, K)
        if x == r:
            flag = False
            break
        x = r
    if flag:
        split_num = w_split_num + h_split_num
        min_num = min(split_num, min_num)

print(min_num)

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

INF = 10000

ans = INF
for bit in range(1 << (h - 1)):

    
    id = [0] * h
    group_idx = 0
    for i in range(h):
        id[i] = group_idx
        if (bit >> i) & 1:
            group_idx += 1

    group_num = group_idx + 1
    cnt = [[0] * w for _ in range(group_num)]
    for i in range(h):
        for j in range(w):
            cnt[id[i]][j] += int(s[i][j])

    
    flag = True
    for g in range(group_num):
        for j in range(w):
            if cnt[g][j] > k:
                flag = False
    if not flag:
        continue

    divnum = group_num - 1
    now = [0] * group_num
    cur = 0
    while cur < w:
        for g in range(group_num):
            now[g] += cnt[g][cur]
            if now[g] > k:
                divnum += 1
                now = [0] * group_num
                cur -= 1
                break
        cur += 1
    ans = min(ans, divnum)

print(ans)

Solution (Python):

import sys
sys.setrecursionlimit(10000)

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

def check(border, num):
    global H,W,K,S
    now = [0]*(num+1)
    add = 0
    for j in range(W):
        tmp = [0]*(num+1)
        for i in range(H):
            now[border[i]] += int(S[i][j])
            tmp[border[i]] += int(S[i][j])
        if max(now)>K:
            add += 1
            now = tmp
        if max(tmp)>K:
            return 10000
    return num+add

def rec(border, num, i):
    global H,W,K,S,ans
    if i<H:
        border[i] = num
        rec(border, num, i+1)
        border[i] = num+1
        rec(border, num+1, i+1)
    else:
        ans = min(ans, check(border, num))

rec([0]*H, 0, 1)
print(ans)

Solution (Python):
def main():
    
    import sys, math
    from itertools import permutations, combinations
    from collections import defaultdict, Counter, deque
    from math import factorial
    from bisect import bisect_left 
    sys.setrecursionlimit(10**7)
    enu = enumerate
    MOD = 10**9+7
    def input(): return sys.stdin.readline()[:-1]
    pl = lambda x: print(*x, sep='\n')

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

    from copy import deepcopy
    cS = [[0]*(W+1) for _ in range(H+1)]
    

    for h in range(1, H+1):
        for w in range(W):
            cS[h][w+1] = cS[h][w] + S[h-1][w]
    for w in range(1, W+1):
        for h in range(H):
            cS[h+1][w] = cS[h][w] + cS[h+1][w]
    

    mcut = 10**9
    for i in range(2**(H-1)):
        yoko = []
        for j in range(H):
            if ((i >> j) & 1):
                yoko.append(j+1)
        yoko = [0] + yoko + [H]
        
        
        
        cut = len(yoko)-2
        lastcut = 0 
        w = 1
        cannot = False
        while w < W+1:
            if cannot:
                w = W + 100
                break
            for ind, y in enu(yoko):
                if ind == 0:
                    continue
                v1 = cS[y][w]
                v2 = cS[yoko[ind-1]][w]
                v3 = cS[yoko[ind-1]][lastcut]
                v4 = cS[y][lastcut]
                val = v1 - v2 + v3 - v4
                
                if K < val:
                    cut += 1
                    if lastcut == w-1:
                        cannot = True
                    lastcut = w-1
                    break
            else:
                w += 1
            
        if not(cannot) and cut < mcut:
            
            mcut = cut

    print(mcut)
if __name__ == '__main__':
    main()

Solution (Python):
import sys

import math
import collections

import bisect
import itertools
import fractions

import copy

import decimal

import queue



sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7


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



def main():
    h, w, k = ns()
    mat = [list(input()) for _ in range(h)]

    
    
    
    

    ans = INF
    for i in range(2 ** (h - 1)):
        cut = format(i, "b").count("1")
        row = cut + 1

        cnt = [0 for _ in range(row)]

        idx_dic = dict()
        tmp_idx = 0
        for j in range(h):
            idx_dic[j] = tmp_idx
            if i >> j & 1:
                tmp_idx += 1

        tmp_ans = cut
        xi = 0
        brkflg = True
        while xi < w:
            yi = 0
            prev_brkflg = brkflg
            brkflg = False
            while yi < h:
                if mat[yi][xi] == "1":
                    cnt[idx_dic[yi]] += 1
                    if cnt[idx_dic[yi]] > k:
                        cnt = [0 for _ in range(row)]
                        xi -= 1
                        brkflg = True
                        tmp_ans += 1
                        break

                yi += 1
            if brkflg and prev_brkflg:
                tmp_ans = INF
                break
            xi += 1
        ans = min(ans, tmp_ans)

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys

import math
import collections

import bisect
import itertools
import fractions

import copy

import decimal

import queue



sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7


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



def main():
    h, w, k = ns()
    mat = [list(input()) for _ in range(h)]

    if h == 1:
        tmp = max(0, mat[0].count("1") - 1)
        print(tmp // k)
        exit(0)

    ans = INF
    for i in range(2 ** (h - 1)):
        cut = format(i, "b").count("1")
        row = cut + 1

        cnt = [0 for _ in range(row)]

        idx_dic = dict()
        tmp_idx = 0
        for j in range(h):
            idx_dic[j] = tmp_idx
            if i >> j & 1:
                tmp_idx += 1

        tmp_ans = cut
        xi = 0
        brkflg = True
        while xi < w:
            yi = 0
            prev_brkflg = brkflg
            brkflg = False
            while yi < h:
                if mat[yi][xi] == "1":
                    cnt[idx_dic[yi]] += 1
                    if cnt[idx_dic[yi]] > k:
                        cnt = [0 for _ in range(row)]
                        xi -= 1
                        brkflg = True
                        tmp_ans += 1
                        break

                yi += 1
            if brkflg and prev_brkflg:
                tmp_ans = INF
                break
            xi += 1
        ans = min(ans, tmp_ans)

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
h,w,K=map(int,input().split())
s=[list(input()) for i in range(h)]
from itertools import groupby
ans=10**18
for i in range(1<<h):
  pre=-1
  c=[]
  t_cnt=0
  op=[-1]*h
  for j in range(h):
    if i&(1<<j):op[j]=1
    else:op[j]=0
  gr=groupby(op)
  l=[]
  for key,g in gr:
    l.append(len(list(g)))
  c=[[0]*w for _ in range(len(l))]
  idx=0
  jdx=0
  for idx,li in enumerate(l):
    for k in range(li):
      for a in range(w):
        c[idx][a]+=int(s[jdx][a])
      jdx+=1
  
  t_cnt=len(c)-1
  t_cnt1=0
  c_mx=[0]*len(c)
  ok=True
  for a in range(w):
    for b in range(len(c)):
      if c[b][a]>K:
        ok=False
      c_mx[b]+=c[b][a]
      if c_mx[b]>K:
        t_cnt1+=1
        c_mx=[0]*len(c)
        for b in range(len(c)):
          c_mx[b]+=c[b][a]
        break
  if ok:
    ans=min(ans,t_cnt+t_cnt1)
if ans==10**18:
  print(0)
else:
  print(ans)

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

ans = 100000
for i in range(2**H):
    cnt = 0
    temp = i
    group = [0]*H
    for j in range(H):
        group[j] = cnt
        if temp & 1:
            cnt += 1
        temp >>= 1
    div = [0]*H
    for j in range(W):
        for k in range(H):
            if div[group[k]] + S[k][j] > K:
                cnt += 1
                div = [0]*H
                for l in range(H):
                    div[group[l]] += S[l][j]
                    if div[group[l]] > K:
                        cnt = 100000
                break
            else:
                div[group[k]] += S[k][j]
    ans = min(ans, cnt)
print(ans)

Solution (Python):
import sys
import itertools
import pprint
input = lambda: sys.stdin.readline().rstrip()

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

Stsum = [[0 for _ in range(W + 1)] for _ in range(H + 1)]
for i in range(H):
    for j in range(W):
        Stsum[i + 1][j + 1] = Stsum[i + 1][j] + S[i][j]
for j in range(W):
    for i in range(H):
        Stsum[i + 1][j + 1] += Stsum[i][j + 1]


def count_white(l, r, u, b):
    return Stsum[b][r] - Stsum[u][r] - Stsum[b][l] + Stsum[u][l]


def solve():

    comb = list(itertools.product(range(2), repeat=H - 1))

    ans = 10 ** 9 + 7
    for c in comb:

        hc = [0] + [i + 1 for i, x in enumerate(c) if x == 1] + [H]
        l, w = 0, 1
        cut_count = 0
        search = False
        p_cut = True

        while w <= W:
            cut = True
            for h in range(0, len(hc) - 1):
                if count_white(l, w, hc[h], hc[h + 1]) > K:
                    cut = False
                    break
            else:
                search = True

            if not cut:
                if search:
                    l = w - 1
                    cut_count += 1
                    search = False
                else:
                    p_cut = False
                    break
            else:
                w += 1

        if p_cut:
            ans = min(ans, cut_count + len(hc) - 2)

    print(ans)


if __name__ == '__main__':
    solve()

Solution (Python):
import sys
import itertools
import pprint
input = lambda: sys.stdin.readline().rstrip()

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

Stsum = [[0 for _ in range(W + 1)] for _ in range(H + 1)]
for i in range(H):
    for j in range(W):
        Stsum[i + 1][j + 1] = Stsum[i + 1][j] + S[i][j]
for j in range(W):
    for i in range(H):
        Stsum[i + 1][j + 1] += Stsum[i][j + 1]


def count_white(l, r, u, b):
    return Stsum[b][r] - Stsum[u][r] - Stsum[b][l] + Stsum[u][l]


def solve():

    comb = list(itertools.product(range(2), repeat=H - 1))

    ans = 10 ** 9 + 7
    for c in comb:

        hc = [0] + [i + 1 for i, x in enumerate(c) if x == 1] + [H]
        l, w = 0, 1
        cut_count = 0
        search = False
        p_cut = True

        while w <= W:
            cut = True
            for h in range(0, len(hc) - 1):
                if count_white(l, w, hc[h], hc[h + 1]) > K:
                    cut = False
                    break
            else:
                search = True

            if not cut:
                if search:
                    l = w - 1
                    cut_count += 1
                    search = False
                else:
                    p_cut = False
                    break
            else:
                w += 1

        if p_cut:
            ans = min(ans, cut_count + len(hc) - 2)

    print(ans)


if __name__ == '__main__':
    solve()