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):
h,w,k=map(int,input().split())
l=[list(input()) for i in range(h)]

count=[]
for i in range(h):
  L=[0]
  for j in range(w):
    L.append(int(l[i][j])+L[-1])
  count.append(L)

b=[]
for i in range(2**(h-1)):
  b.append(format(i,'0'+str(h-1)+'b'))

ans=[]
cut=0
for i in range(len(b)):
  cutct=0
  cut=0
  f=0
  for j in range(1,w+1):
    ct=[]
    for j2 in range(h):
      ct.append(count[j2][j]-count[j2][cut])
    check=[]
    x=ct[0]
    for j3 in range(h-1):
      if b[i][j3]=='0':
        x+=ct[j3+1]
      else:
        check.append(x)
        x=ct[j3+1]
    check.append(x)
    if max(check)>k:
      if cut-j<=1:
        ctcheck=[]
        for j2 in range(h):
          ctcheck.append(count[j2][j-1]-count[j2][cut])
        check=[]
        x=ctcheck[0]
        for j3 in range(h-1):
          if b[i][j3]=='0':
            x+=ctcheck[j3+1]
          else:
            check.append(x)
            x=ctcheck[j3+1]
        check.append(x)
        if max(check)>k:
          f=1
      cut=j-1
      cutct+=1
    if cut==w-1:
      ctcheck=[]
      for j2 in range(h):
        ctcheck.append(count[j2][w]-count[j2][cut])
      check=[]
      x=ctcheck[0]
      for j3 in range(h-1):
        if b[i][j3]=='0':
          x+=ctcheck[j3+1]
        else:
          check.append(x)
          x=ctcheck[j3+1]
      check.append(x)
      if max(check)>k:
        f=1
  ct1=0
  for j4 in range(h-1):
    if b[i][j4]=='1':
      ct1+=1
  if f==0:
    ans.append(cutct+ct1)
print(min(ans))

Solution (Python):

from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    h,w,k = LI()
    a = [list(map(int, input())) for i in range(h)]
    s = [[0]*(w+1)]+[[0]+list(accumulate(i)) for i in a]
    for j in range(w+1):
        for i in range(h):
            s[i+1][j] += s[i][j]
    ans = float("inf")
    for b in range(1<<(h-1)):
        l = [0]
        for i in range(h-1):
            if b&(1<<i):
                l.append(i+1)
        l.append(h)
        ll = len(l)-1
        su = [0]*ll
        m = bin(b).count("1")
        p = 0
        f = 0
        for j in range(1,w+1):
            for i in range(ll):
                u = l[i]
                d = l[i+1]
                su[i] += s[d][j]-s[d][p]-s[u][j]+s[u][p]
                if su[i] > k:
                    m += 1
                    p = j-1
                    su = [0]*ll
                    for ii in range(ll):
                        u = l[ii]
                        d = l[ii+1]
                        su[ii] = s[d][j]-s[d][p]-s[u][j]+s[u][p]
                        if su[ii] > k:
                            f = 1
                    break
            p = j
            if f:
                m = float("inf")
                break
        if m < ans:
            ans = m
    print(ans)
    return


if __name__ == "__main__":
    solve()

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

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

n = H - 1
ans = H * W
for i in range(2 ** n):
    horizon = [0]
    length = 2
    for j in range(n):
        if ((i >> j) & 1):
            horizon.append(j + 1)
            length += 1
    horizon.append(H)
    vertical = 0
    y1 = 0
    for y2 in range(1, W + 1):
        for k in range(length - 1):
            x2 = horizon[k + 1]
            x1 = horizon[k]
            sq = s[x2][y2] - s[x1][y2] - s[x2][y1] + s[x1][y1]
            sq_pre = s[x2][y2 - 1] - s[x1][y2 - 1] - s[x2][y1] + s[x1][y1]

            if(sq > K):
                if(sq_pre > K):
                    vertical = 1e+9
                else:
                    vertical += 1
                    y1 = y2 - 1
                break
    if (vertical >= W):
        vertical = 1e+9
    ans = min(ans, (vertical) + (length - 2))
print(ans)

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

S = [0]*H
for i in range(H):
  S[i] = input()
Sdivs = []
mcnt = 1100
for b in itertools.product([0, 1], repeat=H-1):
  start = 0
  end = 1
  Sdivs=[]
  for a in b:
    if a==1:
      Sdivs.append(S[start:end])
      start = end
    end += 1
  Sdivs.append(S[start:end])
  cnt = sum(b)
  
  ones_cum = [0]*len(Sdivs)
  mark1,mark2 = True,True
  ws = [0]
  w = 1
  while w<W+1 and mark2:
    for i,Sdiv in enumerate(Sdivs):
      
      for s in Sdiv:
        ones_cum[i] += s[w-1]=='1'
      if ones_cum[i] > K:
        
        mark1 = False
        if w-1 == ws[-1]:
          
          mark2 = False
          break
        ws.append(w-1)
        w -= 1
        break
    if mark1 == False:
      mark1 = True
      ones_cum = [0]*len(Sdivs)
    w+=1
  
  if mark2 == False:
    continue
  cnt += len(ws)-1
  
  mcnt = min(mcnt,cnt)
print(mcnt)

Solution (Python):
from collections import Counter


H, W, K = [int(x) for x in input().split()]
grid = [[int(x) for x in input()] for r in range(H)]

best = float("inf")
for cuts in range(2 ** H):
    
    hCutIndices = [r for r in range(H) if (1 << r) & cuts]
    numCuts = len(hCutIndices)

    
    cumulativeCount = Counter()

    for c in range(W):
        
        columnCount = {}
        curr = 0
        for r in range(H):
            curr += grid[r][c]
            if (1 << r) & cuts or r == H - 1:  
                columnCount[r] = curr
                curr = 0

        
        if all(cumulativeCount[r] + columnCount[r] <= K for r in columnCount):
            for r in columnCount:
                cumulativeCount[r] += columnCount[r]
        else:
            
            numCuts += 1
            cumulativeCount = columnCount
            
            if any(counts > K for r, counts in columnCount.items()):
                numCuts = float("inf")
                break
    best = min(best, numCuts)

print(best)

Solution (Python):
import itertools

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

for i in range(h):
  s[i] = input()

cnt = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
  cnt[i][0] = int(s[i][0]) + (0 if i == 0 else cnt[i - 1][0])

for i in range(w):
  cnt[0][i] = int(s[0][i]) + (0 if i == 0 else cnt[0][i - 1])

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

num = [i for i in range(h - 1)]
ans = 99999
for i in range(0, h):
  for v in itertools.combinations(num, i):
    n = list(v)
    n.append(h - 1)
    
    _ans = i
    _left = -1
    for j in range(w):
      for _k in range(len(n)):
        if cnt[n[_k]][j] - (0 if _left < 0 else cnt[n[_k]][_left]) - (0 if _k == 0 else cnt[n[_k - 1]][j]) + (0 if _left < 0 or _k == 0 else cnt[n[_k - 1]][_left]) > k:
          if j - _left == 1:
            _ans = 99999
            break
          _left = j - 1
          j -= 1
          _ans += 1
          break
    ans = min(ans, _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):
H,W,K = map(int,input().split())

S = [0] * H
data = [[0]*W for i in range(H)]

for i in range(H):
    S[i] = list(map(int,list(str(input()))))

data[0][0] = S[0][0]

for i in range(1,W):
    data[0][i] = data[0][i-1] + S[0][i]

for i in range(1,H):
    data[i][0] = data[i-1][0] + S[i][0]

for i in range(1,H):
    for j in range(1,W):
        data[i][j] = data[i-1][j] + data[i][j-1] - data[i-1][j-1] + S[i][j]




m = 10**4
for i in range(2**(H-1)):
    cross = []
    tate = []
    for j in range(H-1):
        if i&(2**j) == 2**j:
            cross.append(j)
    
    
    det2 = 0
    start = 0
    for j in range(W):
        det = 0
        if len(cross) > 0:
            for k in range(len(cross)):
                if (k == 0 and start == 0 and data[cross[k]][j] > K):
                    det = -1
                    break
                elif (k == 0 and start != 0 and data[cross[k]][j] - data[cross[k]][start-1] > K):
                    det = -1
                    break
                elif (start == 0 and k != 0 and data[cross[k]][j]-data[cross[k-1]][j] > K):
                    det = -1
                    break
                elif (start != 0 and k != 0 and data[cross[k]][j]-data[cross[k]][start-1]-data[cross[k-1]][j]+data[cross[k-1]][start-1] > K):
                    det = -1
                    break
            if (start == 0 and data[H-1][j] - data[cross[-1]][j]> K):
                det = -1
            elif (start != 0 and data[H-1][j]-data[cross[-1]][j]-data[H-1][start-1]+data[cross[-1]][start-1] > K):
                det = -1
        
        
        else:
            if (start == 0 and data[H-1][j] > K):
                det = -1
            elif (start != 0 and data[H-1][j] - data[H-1][start-1] > K):
                det = -1
        if det == -1:
            if j == start:
                det2 = -1
                break
            else:
                tate.append(j-1)
                start = j
        
        
    
    if det2 == 0:
        
        m = min(m,len(cross)+len(tate))

print(m)

Solution (Python):
h,w,k = map(int,input().split())
a = [list(input()) for i in range(h)]
acc = [[0 for i in range(w+1)] for j in range(h+1)]
for i in range(1,h+1):
  for j in range(1,w+1):
    acc[i][j] = acc[i-1][j]
    if a[i-1][j-1] == "1":
      acc[i][j] += 1
for i in range(1,h+1):
  for j in range(1,w+1):
    acc[i][j] += acc[i][j-1]
ans = 1000000
def cut(x,y,up,left):
  return acc[x][y]-acc[x][left]-acc[up][y]+acc[up][left]
for i in range(2**(h-1)):
  sep = [0]
  for r in range(h-1):
    if i&1<<r:
      sep.append(r+1)
  sep.append(h)
  anstmp = len(sep)-2
  left = 0
  for j in range(1,w+1):
    if max(list(cut(sep[x],j,sep[x-1],left) for x in range(1,len(sep)))) > k:
      break
    if j<w and max(list(cut(sep[x],j+1,sep[x-1],left) for x in range(1,len(sep)))) > k:
      anstmp += 1
      left = j
  else:
    ans = min(ans,anstmp)
print(ans)

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


ans = float('inf')
for i in range(2**(H-1)):
    _ans = bin(i).count('1')
    chocos = [list(map(int, S[0]))]
    for j in range(H-1):
        if i >> j & 1:
            chocos.append(list(map(int, S[j+1])))
        else:
            for w in range(W):
                chocos[-1][w] += int(S[j+1][w])
    
    ns = len(chocos)
    nums = [0] * ns
    is_next = False
    flag = False
    for w in range(W):
        for j in range(ns):
            nums[j] += chocos[j][w]
            if chocos[j][w] > K:
                _ans = float('inf')
                flag = True
                break
            if nums[j] > K:
                _ans += 1
                is_next = True
                break
        if flag:
          flag = False
          break        
        if is_next:
            for j in range(ns):
                nums[j] = chocos[j][w]
            is_next = False
    
    ans = min(ans, _ans)

print(ans)

Solution (Python):
import sys
def ass(v):
    if not v:
        print(-1)
        sys.exit(0)

h, w, k = map(int, input().split())
grid = [[1 if v == '1' else 0 for v in input()] for _ in range(h)]


ass(h > 0 and w > 0 and k > 0)
for row in grid:
    ass(len(row) == w)


def count_ones(i):
    cnt = 0
    while i:
        if i & 1:
            cnt += 1
        i >>= 1
    return cnt

ans = h + w

for state in range(1 << h):
    j = 0
    vcnt = 0
    counters = [0] * (h + 1)
    is_ok = True
    while j < w:
        hi = 0
        i = 0
        local_counters = [0] * (h + 1)
        ass(len(counters) == len(local_counters))
        while i < h:
            if (1 << i) & state:
                hi = i
            
            
            ass(len(local_counters) > hi)
            ass(i < h and j < w)
            ass(len(grid) > i)
            ass(len(grid[i]) > j)
            local_counters[hi] += grid[i][j]
            i += 1
        for i, v in enumerate(local_counters):
            if v > k:
                is_ok = False
                break
            counters[i] += local_counters[i]
        if not is_ok:
            break
        
        
        if max(counters) > k:
            counters = local_counters[:]
            vcnt += 1

        j += 1


    if is_ok and ans > count_ones(state) + vcnt:
        ans = count_ones(state) + vcnt
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
def main():
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    S = [list(map(int, input().rstrip())) for _ in range(H)]

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

    def sm(a,b): 
        i1,j1 = a
        i2,j2 = b
        return C[i2][j2] - C[i1][j2] - C[i2][j1] + C[i1][j1]
    
    ans = 10**9
    for p in range(1<<(H-1)):
        ha = []
        i = 1
        tmp = 0
        p1 = p
        while p1:
            if p1&1: ha.append(i)
            i += 1
            p1 >>= 1
        tmp += len(ha)
        ha.append(H)
        
        j1, j2 = 0, 1
        flag = False
        while j2 <= W:
            mx = 0
            i1 = 0
            for i2 in ha:
                mx = max(mx, sm((i1,j1),(i2,j2)))
                i1 = i2
            
            if mx > K:
                if j2-j1==1:
                    flag = True
                    break
                tmp += 1
                j1 = j2-1
            else:
                j2 += 1
        if flag: continue
        
        ans = min(ans, tmp)

    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
import math
from collections import Counter

h, w, k = [int(s) for s in sys.stdin.readline().strip().split()]
s = [''] * h
for i in range(h):
    s[i] = sys.stdin.readline().strip()






















ans = float('inf')
for i in range(2 ** h):
    colors = [0]
    cur = 0
    cand = 0
    for div in range(h-1):
        if (i >> div) & 1:
            cur += 1
            colors.append(cur)
            cand += 1
        else:
            colors.append(cur)

    
    impossible = False
    color_count = Counter()
    for j in range(w):
        col_color_count = Counter()
        for row in range(h):
            color = colors[row]
            
            
            
            char = s[row][j]
            if char == '1':
                col_color_count[color] += 1

        has_break = False
        for col in range(cur+1):
            if col_color_count[col] > k:
                impossible = True
                break
            if col_color_count[col] + color_count[col] > k:
                has_break = True
        if impossible:
            break
        if has_break:
            color_count = col_color_count
            cand += 1
        else:
            for col in range(cur+1):
                color_count[col] += col_color_count[col]
    if not impossible:
        ans = min(ans, cand)
print(ans)

Solution (Python):

import itertools

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

choco = [input().strip() for h in range(H)]
cs = [[None for _ in range(W)] for _ in range(H)]  

for w in range(W):
  now_cs = 0
  for h in range(H):
    now_cs += choco[h][w] == '1'
    cs[h][w] = now_cs

def devide_col(w, d):
  if len(d) == 0:  
    return [cs[-1][w]]
  d = sorted(d)
  if len(d) == 1:
    _d = d[0]-1
    return [cs[_d][w], cs[-1][w]-cs[_d][w]]
  
  result = []
  for i in range(len(d)):
    if i == 0:
      result.append(cs[d[0]-1][w])
    else:
      result.append(cs[d[i]-1][w]-cs[d[i-1]-1][w])
  result.append(cs[-1][w]-cs[d[-1]-1][w])
  return result

ans = float('inf')
for n_split in range(H):
  if n_split > ans: continue
  for split_pos in itertools.combinations(range(1,H), n_split):
    
    
    now_ans = 0
    now_state = [0]*(n_split+1)
    for w in range(W):
      next_state = devide_col(w, split_pos)
      
      if any(s > K for s in next_state):  
        now_ans = float('inf')
        break
      now_state = [n+s for n,s in zip(now_state, next_state)]  
      if any(s > K for s in now_state):  
        now_ans += 1
        now_state = next_state
    
    ans = min(ans, now_ans+n_split)
print(ans)

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):
            nxt = min(nxt, bisect_right(A[i], K+A[i][idx-1], lo=idx))
        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):
H, W, K = map(int, input().split())
Ass = [list(map(int, input().rstrip())) for _ in range(H)]

def check(Bss):
    L = len(Bss)
    accBs = [0] * L
    numCut = 0
    for i in range(W):
        for j in range(L):
            if Bss[j][i] > K:
                return H*W
            if accBs[j] + Bss[j][i] > K:
                accBs = [0] * L
                numCut += 1
                break
        for j in range(L):
            accBs[j] += Bss[j][i]
    return numCut

ans = H*W
for ptn in range(2**(H-1)):
    Bss = []
    Bs = Ass[0]
    numCut = 0
    for i in range(1, H):
        if (ptn>>(i-1)) & 1:  
            Bss.append(Bs)
            Bs = Ass[i]
            numCut += 1
        else:  
            Bs = [B+A for B, A in zip(Bs, Ass[i])]
    Bss.append(Bs)

    numCut += check(Bss)
    ans = min(ans, numCut)

print(ans)

Solution (Python):
def count(x1,y1,x2,y2):
  ret=acum[y2][x2]
  if x1!=0:
    ret-=acum[y2][x1-1]
  if y1!=0:
    ret-=acum[y1-1][x2]
  if x1!=0 and y1!=0:
    ret+=acum[y1-1][x1-1]
  return ret

h,w,k=map(int,input().split())
board=[list(input()) for _ in range(h)]
acum=[[0]*(w+1) for _ in range(h)]
for i in range(h):
  for j in range(w):
    if board[i][j]=='1':
      acum[i][j]+=1
    if i!=0:
      acum[i][j]+=acum[i-1][j]
    if j!=0:
      acum[i][j]+=acum[i][j-1]
    if i!=0 and j!=0:
      acum[i][j]-=acum[i-1][j-1]
    if j==w:
      acum[i][j]=acum[i][j-1]
ans=10**18
for i in range(2**(h-1)):
  hlist=[]
  flag=format(i,'b')
  if len(flag)!=(h-1):
    flag='0'*((h-1)-len(flag))+flag
  for j in range((h-1)):
    if flag[j]=='1':
      hlist.append(j)
  hlist.append(h-1)
  prevx=0
  tmp=len(hlist)
  yoko=tmp-1
  tate=0
  for j in range(w):
    prevy=0
    for l in range(tmp):
      if count(prevx,prevy,j,hlist[l])>k:
        tate+=10**18
      if count(prevx,prevy,j,hlist[l])<=k and count(prevx,prevy,j+1,hlist[l])>k:
        tate+=1
        prevx=j+1
        break
      prevy=hlist[l]+1
  ans=min(ans,yoko+tate)
print(ans)

Solution (Python):
import numpy as np
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    popcnt=lambda bit:bin(bit).count("1")
    h,w,k=MI()
    aa=[[0]+[int(c) for c in SI()] for _ in range(h)]
    aa=np.array(aa,dtype="i8")
    for i in range(h):
        aa[i]=np.cumsum(aa[i])
    
    ans=h+w
    for bit in range(1<<(h-1)):
        s=aa[0].copy()
        sn=popcnt(bit)+1
        ss=np.zeros((sn,w+1),dtype="i8")
        si=0
        for i in range(1,h):
            if bit>>(i-1)&1:
                ss[si]=s
                s=aa[i].copy()
                si+=1
            else:s+=aa[i]
        ss[si]=s
        
        
        
        cnt=popcnt(bit)-1
        j=0
        while j<w:
            cnt+=1
            mn=10**9
            for i in range(sn):
                nj=np.searchsorted(ss[i],ss[i][j]+k,side="right")-1
                mn=min(mn,nj)
            if mn==j:
                cnt=10**9
                break
            j=mn
        ans=min(ans,cnt)
    print(ans)

main()

Solution (Python):
def Donyoku(pattern):
    global w,k
    l=len(pattern)
    saisho=0
    now=[0]*l
    tasu=[0]*l
    for yoko in range(w):
        daijobu=True
        for i in range(l):
            hahen=pattern[i]
            tasu[i]=0
            for ha in hahen:
                tasu[i]+=ha[yoko]
            if(now[i]+tasu[i]>k):
                daijobu=False
            if(tasu[i]>k):
                return -1
        if(daijobu):
            for i in range(l):
                now[i]+=tasu[i]
        else:
            saisho+=1
            for i in range(l):
                now[i]=tasu[i]
        
    return saisho
                
        


h,w,k=map(int,input().split())

choco=[]
for i in range(h):
    s=input()
    temp=[0]*w
    for j in range(w):
        temp[j]=int(s[j])
    choco.append(temp)


if(w==1):
    temp=[]
    for i in range(h):
        temp.append(choco[i][0])
    choco=[temp]
    w=h
    h=1



ans=10**6
for i in range(2**(h-1)):
    wari=[]
    gen=0
    sude=0
    for j in range(h):
        if((i>>j) & 1):
            wari.append(choco[gen:j+1])
            gen=j+1
            sude+=1
    wari.append(choco[gen:h])
    
    
    
    don=Donyoku(wari)
    ima=sude+don
    
    if(ima<ans and don!=-1):
        ans=ima

if(w==1 and h==1):
    print(0)
else:
    print(ans)

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

S = [list(map(int, input())) for _ in range(H)]
accS = [[0] * (W + 1) for _ in range(H + 1)]

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

def isOk(L, left, right):
    for top, bot in zip(L, L[1:]):
        if accS[bot][right] - accS[bot][left] - accS[top][right] + accS[top][left] > K:
            return False
    return True

ans = 10**18

for mask in range(1 << H):
    L = [0] + [d + 1 for d in range(H - 1) if (mask & (1 << d)) > 0] + [H]

    cnt = len(L) - 2
    left = 0
    while left < W:
        if not isOk(L, left, left + 1):
            cnt = 10**18
            break

        right = left + 1
        while right < W and isOk(L, left, right + 1):
            right += 1

        cnt += 1
        left = right

    ans = min(ans, cnt - 1)

print(ans)

Solution (Python):
H,W,K  =(map(int,input().split(" "))) 
nums = [list(map(int,list(input())))  for  _ in range(H)]
ruiseki_2d = [ [0] * (W + 1)  for _ in range(H + 1) ] 
for w in range(W):
    for h in range(H):
        ruiseki_2d[h + 1][w + 1] =ruiseki_2d[h + 1][w] + ruiseki_2d[h][w + 1] + nums [h ][w]  - ruiseki_2d[h][w]





ans = 10 ** 10
for i in range(2 ** (H )):
    
    cand = 0
    
    cuts = [0] 
    for j in range(0,H -1 ):  
        if ((i >> j) & 1):  
            
            cuts.append(j + 1)
            cand += 1
    cuts.append(H)
    beforeW = 0 
    for w in range(1,W + 1):
        mi = 10 ** 6
        ss = []
        for i in range(len(cuts) - 1): 
            y1 = cuts[i]
            y2 = cuts[i + 1]
            x2  = w
            x1 = beforeW
            s = ruiseki_2d[y2][x2] -ruiseki_2d[y2][x1] -ruiseki_2d[y1][x2] +ruiseki_2d[y1][x1]
            ss.append(s)


        ma = max(ss)
        if ma > K :
            cand += 1
            beforeW = w -1
    ss = []
    for i in range(len(cuts) - 1):  
        y1 = cuts[i]
        y2 = cuts[i + 1]
        x2 = W
        x1 = beforeW
        s = ruiseki_2d[y2][x2] - ruiseki_2d[y2][x1] - ruiseki_2d[y1][x2] + ruiseki_2d[y1][x1]
        ss.append(s)


    if max(ss) <= K :
        ans = min(cand,ans)


print(ans)

Solution (Python):
class CumulativeSum2D:
  def __init__(self,a):
    self.h=len(a)
    self.w=len(a[0])
    self.s=[(self.w+1)*[0]for _ in range(self.h+1)]
    for i in range(self.h):
      for j in range(self.w):
        self.s[i+1][j+1]=self.s[i+1][j]+self.s[i][j+1]-self.s[i][j]+a[i][j]
  def su(self,i1,j1,i2,j2):
    return self.s[i2+1][j2+1]-self.s[i1][j2+1]-self.s[i2+1][j1]+self.s[i1][j1]
  def prin(self):
    for i in self.s:print(i)
h,w,kk=map(int,input().split())
h-=1
b=[list(map(int,list(input())))for _ in range(h+1)]
bs=CumulativeSum2D(b)
ans=h+w-1
for i in range(2**h):
  bi=[-1]+[j for j in range(h)if (1<<j)&i]+[h]
  anss=len(bi)-2
  flag=False
  cut=[0]
  for k in range(w):
    for j in range(len(bi)-1):
      up=bi[j]+1
      down=bi[j+1]
      s=bs.su(up,cut[-1],down,k)
      if s>kk:
        if k==cut[-1]:flag=True
        else:cut.append(k)
        break
    if flag:break
  if flag:continue
  anss+=len(cut)-1
  ans=min(ans,anss)
print(ans)

Solution (Python):
h, w, k = map(int, input().split())

a = [[1 for i in range(w)] for j in range(h)]

for i in range(h):
    s = input()
    for j in range(w):
        a[i][j] = int(s[j])

best_result = h * w + 1000

for m in range(2 ** (h - 1)):
    mask = m
    num_splits = 0
    splits = []
    i = 0
    while mask > 0:
        if (mask % 2) == 1:
            num_splits += 1
            splits.append(i)
        i += 1
        mask = mask // 2

    

    counts = [0 for j in range(num_splits + 1)]
    current_counts = [0 for j in range(num_splits + 1)]
    result = num_splits

    for j in range(w):
        if result >= best_result:
            break
        split_index = 0
        success = True
        current_counts[0] = 0

        for i in range(h):
            if a[i][j] == 1:
                counts[split_index] += 1
                if counts[split_index] > k:
                    success = False

            current_counts[split_index] += a[i][j]

            if split_index < num_splits and i == splits[split_index]:
                split_index += 1
                current_counts[split_index] = 0

        if not success:
            result += 1
            
            fail = False
            for x in range(num_splits + 1):
                if current_counts[x] > k:
                    fail = True
                    break

                counts[x] = current_counts[x]
            if fail: 
                result = best_result + 1
                break
            

    best_result = min(best_result, result)

print(best_result)