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())
S = [list(map(int, list(input()))) for _ in range(h)]

ans = 10**9+7

for i in range(1<<(h-1)):
    box = [[0] * w]
    bcnt = 0 

    box[bcnt] = [s + b for s, b in zip(S[0], box[bcnt])]

    
    
    
    for j in range(1, h):
        if (i >> (j-1)) & 1:
            bcnt += 1
            box.append([0] * w)
        box[bcnt] = [s + b for s, b in zip(S[j], box[bcnt])]

    
    if not all([all([i<=k for i in b]) for b in box]):
        continue

    
    cutcnt = len(box) - 1 
    cnt = [0] * len(box)    
    
    for m in range(w):
        for n in range(len(box)):
            cnt[n] += box[n][m] 
        if any([c > k for c in cnt]):  
            cutcnt += 1
            
            for n in range(len(box)):
                cnt[n] = box[n][m]
    ans = min(ans, cutcnt)

print(ans)

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

ans = 10**9+7

for i in range(1<<(h-1)):
    box = [[0] * w]
    bcnt = 0 

    box[bcnt] = [s + b for s, b in zip(S[0], box[bcnt])]

    
    
    
    for j in range(1, h):
        if (i >> (j-1)) & 1:
            bcnt += 1
            box.append([0] * w)
        box[bcnt] = [s + b for s, b in zip(S[j], box[bcnt])]

    
    if not all([all([i<=k for i in b]) for b in box]):
        continue

    
    cutcnt = len(box) - 1 
    cnt = [0] * len(box)    
    
    for m in range(w):
        for n in range(len(box)):
            cnt[n] += box[n][m] 
        if any([c > k for c in cnt]):  
            cutcnt += 1
            
            for n in range(len(box)):
                cnt[n] = box[n][m]
    ans = min(ans, cutcnt)

print(ans)

Solution (Python):


MAX = 10000

def makeMap(H, bits):
    M = [0]*H

    m = 0
    for i in range(H):
        M[i] = m

        if bits & 1:
            m += 1

        bits >>= 1

    return M


def getCounts(H,S,M,w):
    C = [0]*(M[-1]+1)

    for h in range(H):
        if S[h][w] == '1':
            C[M[h]] += 1

    return C


def f(H,W,K,S,bits):
    M = makeMap(H, bits)
    N = M[-1] + 1
    X = [0]*N
    ans = 0
    


    for w in range(W):
        C = getCounts(H,S,M,w)
        for i in range(N):
            if C[i] > K:
                return MAX

            X[i] += C[i]
            if X[i] > K:
                ans += 1
                X = C
                break



    return ans + N - 1
            
    
H,W,K = map(int, input().split())
S = [input() for _ in range(H)]



ans = MAX

for bits in range(2**(H-1)):
    ans = min(ans, f(H,W,K,S,bits))

print(ans)

Solution (Python):
h, w, kkk = map(int, input().split())
choco = [0]*h
for i in range(h):
  choco[i] = input()
answer = h+w-2
for i in range(max([2**(h-1), 1])):
  flag = True
  board = [0]*(h-1)
  for j in range(h-1):
    if (i >> j)&1:
      board[j] = 1
  count = sum(board)
  key = [0]*(count+1)
  ans = count
  for p in range(w):
    max_board = [0]*(count+1)
    k = 0
    for q in range(h):
      if choco[q][p] == "1":
        max_board[k] += 1
      if q == h-1:
        if max(max_board) > kkk:
          flag = False
        break
      if board[q] == 1:
        k += 1
  if not flag:
    continue
  for p in range(w):
    k = 0
    for q in range(h):
      if choco[q][p] == "1":
        key[k] += 1
      if q == h-1:
        break
      if board[q] == 1:
        k += 1
    for u in range(count+1):
      if key[u] <= kkk:
        continue
      ans += 1
      key = [0]*(count+1)
      k = 0
      for q in range(h):
        if choco[q][p] == "1":
          key[k] += 1
        if q == h-1:
          break
        if board[q] == 1:
          k += 1
      break
  if ans < answer and flag:
    answer = ans
print(answer)

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

ans = 10 ** 9


for i in range(2 ** (h - 1)):
  
  box = [[0] * w]
  
  bcnt = 0
  box[bcnt] = [s + b for s, b in zip(S[0], box[bcnt])]

  for j in range(1, h):
    if (i >> (j-1)) & 1:
      bcnt += 1
      box.append([0] * w)
    box[bcnt] = [s + b for s, b in zip(S[j], box[bcnt])]
  
  
  if not all([all([i <= k for i in b]) for b in box]):
    continue

  
  cutcnt = len(box) - 1
  
  cnt = [0] * len(box)
  for m in range(w):
    for n in range(len(box)):
      cnt[n] += box[n][m]
    
    if any([c > k for c in cnt]):
      cutcnt += 1
      for n in range(len(box)):
        cnt[n] = box[n][m]
  ans = min(ans, cutcnt)

print(ans)

Solution (Python):
from itertools import combinations
h, w, k = map(int, input().split())
S = [list(map(int, list(input()))) for _ in range(h)]

ans = 10 ** 9


for i in range(2 ** (h - 1)):
  
  box = [[0] * w]
  
  bcnt = 0
  box[bcnt] = [s + b for s, b in zip(S[0], box[bcnt])]

  for j in range(1, h):
    if (i >> (j-1)) & 1:
      bcnt += 1
      box.append([0] * w)
    box[bcnt] = [s + b for s, b in zip(S[j], box[bcnt])]
  
  
  if not all([all([i <= k for i in b]) for b in box]):
    continue

  cutcnt = len(box) - 1
  cnt = [0] * len(box)
  for m in range(w):
    for n in range(len(box)):
      cnt[n] += box[n][m]
    if any([c > k for c in cnt]):
      cutcnt += 1
      for n in range(len(box)):
        cnt[n] = box[n][m]
  ans = min(ans, cutcnt)

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:
        right = left
        while right < W and isOk(L, left, right + 1):
            right += 1

        if left == right:
            cnt = 10**18
            break

        cnt += 1
        left = right

    ans = min(ans, cnt - 1)

print(ans)

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

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

ans = H * W

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

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

    num_groups += 1
    num_lines = num_groups - 1 
    g_sum = [0] * num_groups

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

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

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

    if not ok2:
        continue

    if ans > num_lines:
        ans = num_lines


print(ans)

Solution (Python):

def main():
    from itertools import product
    import numpy as np

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

    if sum(sum(s) for s in S)<=K:
        print(0)
    else:
        answer = (H-1) * (W-1)
        for X in product([False,True], repeat=H-1):
            ans = np.sum(X)
            if ans >= answer:
                continue
            M = [[0]]
            for i, x in enumerate(X):
                if x:
                    M.append([])
                M[-1].append(i+1)
            D = [0]*len(M)
            for s in S:
                for k, m in enumerate(M):
                    D[k] += sum(s[i] for i in m)
                if any(d > K  for d in D):
                    ans += 1
                    if ans >= answer:
                        break
                    for k, m in enumerate(M):
                        D[k] = sum(s[i] for i in m)
                    
                    if any(d > K for d in D):
                        ans = answer + 1
                        break

            answer = min(answer,ans)

        print(answer)

main()

Solution (Python):

def main():
    from itertools import product
    import numpy as np

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

    if sum(sum(s) for s in S)<=K:
        print(0)
    else:
        answer = (H-1) * (W-1)
        for X in product([False,True], repeat=H-1):
            ans = np.sum(X)
            if ans >= answer:
                continue
            M = [[0]]
            for i, x in enumerate(X):
                if x:
                    M.append([])
                M[-1].append(i+1)
            D = [0]*len(M)
            for s in S:
                for k, m in enumerate(M):
                    D[k] += sum(s[i] for i in m)
                if any(d > K  for d in D):
                    ans += 1
                    if ans >= answer:
                        break
                    for k, m in enumerate(M):
                        D[k] = sum(s[i] for i in m)
                    
                    if any(d > K for d in D):
                        ans = answer + 1
                        break

            answer = min(answer,ans)

        print(answer)

main()

Solution (Python):

def all_sublist(lst):
    lstlst = []
    for i in range(2**len(lst)):
        sublst = []
        for j in range(len(lst)):
            if (i >> j) & 1 == 1:
                sublst.append(lst[j])
        lstlst.append(sublst)
    return lstlst



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


cutlst = all_sublist(list(range(1, H)))


cnt_min = 10**9 + 7
for cut in cutlst:
    
    SS = []
    cut.append(H)
    start = 0
    for stop in cut:
        T = []
        for w in range(W):
            tmp = 0
            for h in range(start, stop):
                tmp += S[h][w]
            T.append(tmp)
        SS.append(T)
        start = stop
    H0 = len(SS)
    
    if any([SS[h][w] > K for h in range(H0) for w in range(W)]):
        continue
    
    cnt = len(cut) - 1
    left = [0 for h in range(H0)]
    right = [SS[h][0] for h in range(H0)]
    for w in range(1, W):
        left, right = right, [right[h] + SS[h][w] for h in range(H0)]
        leftOK = all([left[h] <= K for h in range(H0)])
        rightNG = any([right[h] > K for h in range(H0)])
        
        if leftOK and rightNG:
            left = [0 for h in range(H0)]
            right = [SS[h][w] for h in range(H0)]
            cnt += 1
    cnt_min = min(cnt_min, cnt)
print(cnt_min)

Solution (Python):
import math
import time
from collections import deque
from collections import defaultdict
from copy import deepcopy
import heapq

mod = 10 ** 9 + 7
t = time.time()



def iip():
    ret = [int(i) for i in input().split()]
    if len(ret) == 1:
        return ret[0]
    return ret


def conbination(n, r, mod):
    if n < r:
        return 0

    if r == 0 or n == 0:
        return 1

    ret = 1
    for i in range(n-r+1, n+1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r+1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    
    return ret

def inv(n, mod):
    return power(n, mod-2)

def power(n, p):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p//2) ** 2) % mod
    if p % 2 == 1:
        return (n * power(n, p-1)) % mod

def main():
    H, W, K = iip()

    chocos = []
    for i in range(H):
        chocos.append(input())


    result = 9999
    for i in range(2**(H-1)):
        hbin = bin(i)[2:].zfill(H-1)

        lines = []
        cur = []
        for i in range(H):
            cur.append(i)
            if i <= H-2 and hbin[i] == "1":
                lines.append(cur)
                cur = []
        lines.append(cur)
        cnum = cracknum(lines, W, K, chocos) + hbin.count("1")
        result = min(result, cnum)

    print(result)

def cracknum(lines, W, K, chocos):
    volumes = [0 for i in lines]
    result = 0
    for x in range(W):
        crack = False
        for line, y_list in enumerate(lines):
            for y in y_list:
                if chocos[y][x] == "1":
                    volumes[line] += 1
                    
                    
                    if volumes[line] > K:
                        crack = True
                        
                        break
            if crack:
                break

        if crack:
            result += 1
            volumes = [0 for i in lines]
            for line, y_list in enumerate(lines):
                for y in y_list:
                    if chocos[y][x] == "1":
                        volumes[line] += 1
                        if volumes[line] > K:
                            return 9999
    
    return result





main()

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

minimum = (h - 1) * (w - 1)
for div_h in range(1 << (h - 1)):
  h_index = [0] * h
  cur_index = 0
  mask = 1 << (h - 2)
  for i in range(1, h):
    if div_h & mask:
      cur_index += 1
    h_index[i] = cur_index
    mask >>= 1
  white_choco = [0] * (cur_index + 1)
  divide = 0
  j = 0
  flag = False
  while j < w:
    for i in range(h):
      white_choco[h_index[i]] += s[i][j]
    if max(white_choco) > k:
      if flag:
        break
      flag = True
      white_choco = [0] * (cur_index + 1)
      divide += 1
    else:
      j += 1
      flag = False
  else:
    minimum = min(minimum, divide + cur_index)
print(minimum)

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

def count(li):
    if np.max(li) > k:
        return -1
    tmp = np.zeros(len(li), dtype=int)
    cnt = len(li)-1
    for i in range(w):
        tmp += li[:, i]
        if np.max(tmp) > k:
            cnt += 1
            if cnt >= ans:
                return -1
            tmp = li[:, i]
    return cnt

ans = 1000000
for i in range(2**(h-1)):
    r = 0
    l = []
    for j in range(h-1):
        if (i>>j)&1:
            l.append(np.sum(s[r:j+1, :], axis=0))
            r = j+1
    l.append(np.sum(s[r:, :], axis=0))
    if ans <= len(l)-1:
        continue
    cnt = count(np.vstack(l))
    if cnt>=0:
        ans = min(ans, cnt)
print(ans)

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

def nl(a, b):
    return [[0]*b for _ in range(a)]

def add(j):
    for i in range(g):
        now[i] += group_sum[i][j]
        if now[i] > K:
            return False
    return True

ans = float('inf')
for bit in range(1<<(H-1)):
    id_of = [0]*H
    g = 0
    
    for i in range(H):
        id_of[i] = g
        if bit >> i & 1:
            g += 1
    
    g += 1
    count = g - 1

    
    group_sum = nl(H, W)
    for i in range(H):
        for j in range(W):
            group_sum[id_of[i]][j] += S[i][j]

    
    now = [0]*g
    for j in range(W):
        if not add(j):
            count += 1
            now = [0]*g
            if not add(j):
                count = float('inf')
                break
    
    ans = min(ans, count)

print(ans)

Solution (Python):
import numpy as np


def solve(*args: str) -> str:
    h, w, k = map(int, args[0].split())
    white = np.array([[n for n in map(int, S)] for S in args[1:]])

    ret = h*w
    for b in range(2**(h-1)):
        h_cuts = list(i+1 for i in range(h-1) if (b >> i) & 1 == 1)
        count = len(h_cuts)
        if ret < count:
            continue

        A = np.array(list(x.sum(axis=0) for x in np.vsplit(white, h_cuts)))
        if (k < A).any():
            continue

        S = np.zeros((1, len(A)), dtype=int)
        for x in range(w):
            S += A[:, x]
            if (k < S).any():
                S = A[:, x]
                count += 1
                if ret < count:
                    break

        ret = min(ret, count)

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Solution (Python):
def main():
  H,W,K = map(int,input().split())
  import numpy as np
  from collections import deque
  ans = 10000
  S = np.array([list(map(int,list(input()))) for _ in range(H)])
  cum = [[0]*W for _ in range(H+1)]
  for j in range(W):
    for i in range(1,H+1):
      cum[i][j] = cum[i-1][j]+S[i-1][j]

  cum = np.array(cum)
  for i in range(2**(H-1)):
    j = 0
    q = deque([0])
    for h in range(H):
      if (i>>h)&1:
        q.append(h+1)
    q.append(H)
    t_a = len(q)-2
    if t_a>=ans:
      continue
    p = deque()
    judge = False
    for a in range(len(q)-1):
      x = cum[q[a+1]]-cum[q[a]]
      if (x>K).any():
        judge = True
        break
      else:
        p.append(list(x))

    if judge:
      continue
    n = len(p)
    l = [0]*n
    for w in range(W):
      y = [l[j]+p[j][w] for j in range(n)]
      if max(y)>K:
        t_a+=1
        l = [p[j][w] for j in range(n)]
        if t_a>=ans:
          judge = True
          break
      else:
        l = y
    if judge:
      continue
    ans = min(ans,t_a)

  print(ans)
  
main()

Solution (Python):
h,w,k=map(int,input().split())
S=[]
for i in range(h):
    s=int(input(),2)
    S.append(s)
ans=h+w-2
for i in range(2**(h-1)):
    flag=False
    now=0 
    cnt=0 
    y=0
    for j in range(h-1):
        if (i>>j)&1:
            y+=1
    C=[0]*(y+1) 
    for x in range(w):
        T=[] 
        for j in range(h):      
            cnt+=(S[j]>>x)&1
            if cnt>k:
                flag=True
                break
            if (i>>j)&1: 
                T.append(cnt)
                cnt=0
            if j==h-1: 
                T.append(cnt)
                cnt=0
        if flag:
            break
        for j in range(len(C)): 
            if C[j]+T[j]>k:
                now+=1
                C=T
                break
            else:
                C[j]+=T[j]
    if flag:
        continue
    ans=min(ans,now+y)
print(ans)

Solution (Python):
import sys

input = sys.stdin.readline

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

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


def f(i1, j1, i2, j2):
    return cs[i1][j1] - cs[i1][j2] - cs[i2][j1] + cs[i2][j2]


ans = h + w
for bit in range(1 << (h - 1)):
    border = [0]
    cand = 0
    for i in range(h):
        if (bit >> i) & 1:
            border.append(i + 1)
            cand += 1
    border.append(h)

    
    j0 = 0
    for j in range(w):
        for i in range(len(border) - 1):
            if f(border[i + 1], j + 1, border[i], j0) > k:
                cand += 1
                j0 = j
                break

    
    is_possible = True
    for i in range(len(border) - 1):
        if f(border[i + 1], w, border[i], j0) > k:
            is_possible = False
            break

    if is_possible:
        ans = min(ans, cand)
print(ans)

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

l=[]
id=[0]*H
tables=[[0 for _ in range(W)] for _ in range(H)]
gnum=0
ans=0
mi=float("inf")
impossibleflag=0
for k in range(pow(2,H-1)):
    for i in range(H):
        id[i]=gnum
        if (k>>i)&1:    
            gnum=gnum+1 
    gnum=gnum+1         
    
    tables = [[0 for _ in range(W)] for _ in range(H)]
    for i in range(H):
        for j in range(W):
            tables[id[i]][j]=tables[id[i]][j]+int(S[i][j])
    ans=ans+gnum-1  
    
    
    groupedwchoko=[0 for _ in range(gnum)]  
    for i in range(W):
        for j in range(gnum):
            groupedwchoko[j]=groupedwchoko[j]+tables[j][i]  
            
            if groupedwchoko[j]>K:      
                ans=ans+1               
                groupedwchoko = [0 for _ in range(gnum)]
                for l in range(gnum):
                    groupedwchoko[l]=tables[l][i]   
                    if tables[l][i]>K:              
                        ans=float("inf")            
                break
        
    
    if mi>ans:
        mi=ans
    gnum=0
    ans=0

print(mi)

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

def solve(l):
    choco = [0 for _ in range(len(l))]
    ans = 0
    for i in range(w):
        f = True
        tmp = [0 for _ in range(len(l))]
        for idx, vs in enumerate(l):
            for v in vs:
                if s[v][i]:
                    tmp[idx] += 1
        for j in range(len(l)):
            if choco[j] + tmp[j] > k:
                f = False
        if not f:
            ans += 1
            choco = [0 for _ in range(len(l))]
        for idx, vs in enumerate(l):
            for v in vs:
                if s[v][i]:
                    if choco[idx] + 1 > k:
                        return 10 ** 9
                    choco[idx] += 1
    return ans + len(l) - 1


ans = 10 ** 9
for i in range(2 ** (h-1)):
    div = []
    tmp = []
    for j in range(h):
        tmp.append(j)
        if ((i >> j) & 1):
            div.append(tmp)
            tmp = []
    div.append(tmp)
    res = solve(div)
    ans = min(ans, res)
print(ans)

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

bitcnt = [0]*(1<<h)
for i in range(1<<(h-1)):
    bitcnt[2*i] = bitcnt[i]
    bitcnt[2*i+1] = bitcnt[i]+1

ans = float("inf")
for state in range(1<<(h-1)):
    s = [0]*h
    ans_tmp = 0
    can = True
    for i in range(w):
        cnt = 0
        tmp = [0]*h
        for j in range(h):
            tmp[cnt] += board[j][i]
            if state&(1<<j) or j==h-1:
                cnt += 1
        if any(tmp[j]>k for j in range(cnt)):
            can = False
            break
        if all(s[j]+tmp[j]<=k for j in range(cnt)):
            for j in range(cnt):
                s[j] += tmp[j]
        else:
            s = tmp
            ans_tmp += 1
    if can:
        ans = min(ans, ans_tmp+bitcnt[state])

print(ans)

Solution (Python):
import sys

input = sys.stdin.readline

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

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


def f(i1, j1, i2, j2):
    return cs[i1][j1] - cs[i1][j2] - cs[i2][j1] + cs[i2][j2]


ans = h + w
for bit in range(1 << (h - 1)):
    border = [0]
    cand = 0
    for i in range(h):
        if (bit >> i) & 1:
            border.append(i + 1)
            cand += 1
    border.append(h)

    j0 = 0
    for j in range(w):
        for i in range(len(border) - 1):
            if f(border[i + 1], j + 1, border[i], j0) > k:
                cand += 1
                j0 = j

    is_possible = True
    for i in range(len(border) - 1):
        if f(border[i + 1], w, border[i], j0) > k:
            is_possible = False
            break

    if is_possible:
        ans = min(ans, cand)
print(ans)

Solution (Python):
import sys
import math
import string
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
from bisect import bisect, bisect_left, bisect_right

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)

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)):
    p = deque()
    for j in range(H - 1):
        if (i >> j) & 1:
            p.append(j + 1)
    num = len(p)
    if len(p) == 0:
        check = 0
        for j in range(W):
            temp_sum = sum([S[l][j] for l in range(H)])
            if temp_sum > K:
                num = INF
            if check + temp_sum > K:
                check = temp_sum
                num += 1
            else:
                check += temp_sum
    else:
        p.appendleft(0)
        p.append(H)
        check = [0] * (len(p) - 1)
        for j in range(W):
            for l in range(len(p) - 1):
                if p[l + 1] - p[l] == 1:
                    check[l] += S[l][j]
                else:
                    temp_sum = sum([S[t][j] for t in range(p[l], p[l + 1])])
                    if temp_sum > K:
                        num = INF
                        break
                    check[l] += temp_sum
            for l in check:
                if l > K:
                    num += 1
                    for k in range(len(p) - 1):
                        if p[k + 1] - p[k] == 1:
                            check[k] = S[k][j]
                        else:
                            temp_sum = sum([S[t][j] for t in range(p[k], p[k + 1])])
                            if temp_sum > K:
                                num = INF
                            check[k] = temp_sum
                    break
    if num < ans:
        ans = num
print(ans)

Solution (Python):
def make_bit(i):
    if i == h - 1:
        solve(t)
        return
    make_bit(i + 1)
    t[i] = 1
    make_bit(i + 1)
    t[i] = 0

def solve(u):
    global ans
    c = sum(u)
    x = [0] * (c + 1)
    y = [0] * h
    for i in range(h - 1):
        y[i + 1] = y[i] + u[i]
    for i in range(w):
        for j in range(h):
            x[y[j]] += int(s[j][i])
        if max(x) > k:
            c += 1
            x = [0] * c
            for j in range(h):
                x[y[j]] += int(s[j][i])
        if max(x) > k:
            c = 1919810
            break
    if ans > c:
        ans = c
    return

h, w, k = map(int, input().split())
s = [list(input()) for _ in range(h)]
t = [0] * (h - 1)
ans = 114514
make_bit(0)
print(ans)

Solution (Python):
import itertools

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


def solve(blocks):
    n_vert_cut = 0
    n_block = len(blocks)
    vals = [0 for _ in range(n_block)]

    for c in range(W):
        adds = [block[c] for block in blocks]
        if any(add > K for add in adds):
            return H * W

        sums = [val + add for val, add in zip(vals, adds)]
        if any(x > K for x in sums):
            n_vert_cut += 1
            vals = adds
        else:
            vals = sums

    return n_vert_cut + n_block - 1


ans = H * W
for mask in itertools.product([0, 1], repeat=H - 1):
    mask = [1] + list(mask) + [1]
    pivots = [r for r in range(H + 1) if mask[r]]
    blocks = [A[p1:p2] for p1, p2 in zip(pivots[:-1], pivots[1:])]
    blocks = [[sum(row[c] for row in block) for c in range(W)] for block in blocks]
    
    ans = min(ans, solve(blocks))
print(ans)

Solution (Python):
h,w,K=map(int,input().split())
data=[[0 for i in range(w+1)]]
for i in range(h):
    x=list(input())
    x.insert(0,0)
    for j in range(w+1):
        x[j]=int(x[j])
    data.append(x)
    
for i in range(h+1):
    for j in range(1,w+1):
        data[i][j]+=data[i][j-1]
        
for i in range(w+1):
    for j in range(1,h+1):
        data[j][i]+=data[j-1][i]
        


ans=10**10
for _ in range(2**(h-1)):
    st=choice=format(_,"0%ib"%(h-1))
    div=[0]
    sub=0
    for j in range(h-1):
        if st[j]=="1":
            div.append(j+1)
            sub+=1
    div.append(h)
    cnt=0
    nowindex=0
    for j in range(1,w+1):
        flag=True
        if nowindex==0:
            for k in range(1,len(div)):
                if data[div[k]][j]-data[div[k-1]][j]>K:
                    flag=False
                    break
            if flag is False:
                nowindex=j-1
                cnt+=1
                 
        else:
            for k in range(1,len(div)):
                if (data[div[k]][j]-data[div[k]][nowindex])-(data[div[k-1]][j]-data[div[k-1]][nowindex])>K:
                    flag=False
                    break
            if flag is False:
                nowindex=j-1
                cnt+=1
    subflag=True
    for k in range(1,len(div)):
        if (data[div[k]][w]-data[div[k]][nowindex])-(data[div[k-1]][w]-data[div[k-1]][nowindex])>K:
            subflag=False
    if subflag is True:
        ans=min(ans,sub+cnt)
print(ans)

Solution (Python):
H, W, K = map(int,input().split())
B = [input() for k in range(H)]
S = [[0]*(W+1) for k in range(H)]

for k in range(H):
    for l in range(W):
        if B[k][l] == "1":
            S[k][l+1] = S[k][l] + 1
        else:
            S[k][l+1] = S[k][l]

ans = 1000000
for k in range(2**(H-1)):
    t = [0]*W
    u = []
    for d in range(H):
        if (k>>d)&1 == 1:
            for l in range(W):
                t[l] += int(B[d][l])
        else:
            for l in range(W):
                t[l] += int(B[d][l])
            u.append(t)
            t = [0]*W
    temp = len(u)-1
    d = [0]*len(u)
    for i in range(len(u)):
        d[i] = u[i][0]
        if d[i] > K:
            temp = 1000000
    for j in range(1,W):
        for i in range(len(u)):
            if u[i][j] > K:
                temp = 1000000
                break
            d[i] += u[i][j]
            if d[i] > K:
                temp += 1
                for l in range(len(u)):
                    d[l] = u[l][j]
                break
    ans = min(ans,temp)
print(ans)