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


def resolve(in_):
    H, W, K = map(int, next(in_).split())
    
    w_choco = ord(b'1')
    S = [[1 if v == w_choco else 0 for v in line.strip()] for line in in_]
    
    

    ans = 10000  
    choco = [0] * H
    choco_temp = [0] * H
    for v in range(2 ** (H - 1)):
        
        ans_temp = sum(1 if v & (0b01 << i) else 0 for i in range(H - 1))
        for w in range(W):
            index = 0
            for h in range(H):
                choco_temp[index] += S[h][w]
                if v & (0b01 << h):
                    index += 1
            
            if all(a + b <= K for a, b in zip(choco, choco_temp[:index + 1])):
                
                for i in range(index + 1):
                    choco[i] += choco_temp[i]
                    choco_temp[i] = 0
            elif max(choco_temp) > K:
                ans_temp = 10000
                break
            else:
                
                for i in range(index + 1):
                    choco[i] = choco_temp[i]
                    choco_temp[i] = 0
                ans_temp += 1
            if ans_temp >= ans:
                break
            
        
        ans = min(ans, ans_temp)
        for i in range(len(choco)):
            choco[i] = 0
            choco_temp[i] = 0
  
    return ans


def main():
    ans = resolve(sys.stdin.buffer)
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
import numpy as np
import numba
from numba import njit
from numba.types import Omitted
i4 = numba.int32
i8 = numba.int64

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit((i8[:, :], i8), cache=True)
def main(S, K):
    H, W = S.shape
    ans = H + W + 100
    for s in range(1 << H - 1):
        cost = 0
        T = S.copy()
        for i in range(H - 1):
            if s & 1 << i:
                T[i + 1] += T[i]
            else:
                cost += 1
        if np.any(T > K):
            continue
        cumsum = np.zeros(H, np.int64)
        for w in range(W):
            if np.any(cumsum + T[:, w] > K):
                cumsum[:] = 0
                cost += 1
            cumsum += T[:, w]
        ans = min(ans, cost)
    return ans

H, W, K = map(int, readline().split())
S = np.empty((H, W), np.int64)
for h in range(H):
    S[h] = np.array(list(readline().rstrip().decode()))

print(main(S, K))

Solution (Python):
from itertools import product
h, w, k = map(int, input().split())
s = list()
best_so_far = float('inf')
for _ in range(h):
  line = input()
  s.append(list(map(int, list(line))))

horizontal_line_choices = product([False, True], repeat=h-1)
for chosen_indices in horizontal_line_choices:
  hyperrow_values = [s[0].copy()]
  for i in range(h-1):
    if chosen_indices[i]:
      hyperrow_values.append(s[i+1].copy())
    else:
      for dw in range(w):
        hyperrow_values[-1][dw] += s[i+1][dw]
  if any(value>k for row in hyperrow_values for value in row):
    continue
  
  num_hyperrows = len(hyperrow_values)
  count_cuts = sum(chosen_indices)
  hyperrow_cumulative = [hyperrow_values[r][0] for r in range(num_hyperrows)]
  for j in range(1, w):
    if all(hyperrow_cumulative[r]+hyperrow_values[r][j]<=k for r in range(num_hyperrows)):
      for r in range(num_hyperrows):
        hyperrow_cumulative[r] += hyperrow_values[r][j]
    else:
      count_cuts += 1
      for r in range(num_hyperrows):
        hyperrow_cumulative[r] = hyperrow_values[r][j]
  best_so_far = min(best_so_far, count_cuts)
print(best_so_far)

Solution (Python):
h,w,k = map(int, input().split())
s = [[int(c) for c in input()] for i in range(h)]
ans = 114514893
for bit in range(1 << (h-1)):
    cut = [-1]
    for i in range(h-1):
        if bit & (1 << i) : cut.append(i)
    cut.append(h-1)
    l = len(cut)-1
    count = l-1
    suml = [0 for i in range(l)]
    ok = True
    for i in range(w):
        sumtemp = [0 for ii in range(l)]
        flag2 = True 
        for j in range(l):
            for kk in range(cut[j]+1,cut[j+1]+1):
                sumtemp[j] = sumtemp[j] + s[kk][i]
            if sumtemp[j] > k:
                ok = False
                break
        if not ok : break
        for j in range(l):
            if suml[j]+sumtemp[j] > k:flag2 = False
        if flag2:
            for j in range(l):
                suml[j] = suml[j]+sumtemp[j]
        else:
            count += 1
            suml = sumtemp[:]   
    if not ok:continue
    ans = min(ans,count)
    
print(ans)

Solution (Python):
from sys import exit
from itertools import product
import numpy as np
HWK,*sss = open(0).read().splitlines()
H,W,K = map(int, HWK.split())
sss = [list(map(int, list(ss))) for ss in sss]
sss = np.cumsum(sss, axis=0)
 
if H == 1 or W == 1:
    print(0--sss[-1][-1]//K)
    exit()
 
ans = float('inf')
for flgs in product([False, True], repeat=H-1):
    cnt = sum(flgs)
    tsss = sss[[*flgs, True]]
    tsss = np.concatenate((tsss[:1], np.diff(tsss, axis=0)), axis=0).T
 
    tmp = 0
    succ = True
    for cur in tsss:
        new = tmp + cur
        if new.max() <= K:
            tmp = new
        else:
            cnt += 1
            if cur.max() > K:
                succ = False
                break
            else:
                tmp = cur


    if succ:
        ans = min(ans, cnt)
 
print(ans)

Solution (Python):
H,W,K=map(int,input().split())
S=[list(map(int,list(input()))) for i in range(H)]
C=[[0] for i in range(H)]
for i in range(H):
  for j in range(W):
    C[i].append(C[i][j]+S[i][j])
def f(b,l,r):
  R=[0]
  for i in range(H):
    R[-1]+=C[i][r+1]-C[i][l]
    if i!=H-1:
      if b&(1<<i):
        R.append(0)
  return max(R)

INF=10**12
P=INF
Q=0
L=0
for x in range(1<<(H-1)):
  Q=bin(x).count('1')
  L=0
  for i in range(W):
    if f(x,L,i)>K:
      Q+=1
      L=i
      if f(x,L,i)>K:
        Q=INF
        break
  P=min(P,Q)
print(P)

Solution (Python):

import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
H, W, K = map(int, readline().split())
S = [readline().decode().rstrip() for _ in range(H)]
INF = 10**30
data = [[0]*W for _ in range(H)]
for i in range(H):
    cnt = 0 
    for j in range(W):
        if S[i][j] == '1':
            data[i][j] += 1

ans_cnt = INF   
for bit_H in range(1 << (H-1)):
    cnt = 0
    ans = []
    new_data = []
    for i in range(H-1):
        if (bit_H >> i) & 1:
            ans.append(i)
    ans.append(H-1)
    tmp = [0]*W
    for i in range(H):
        for j in range(W):
            tmp[j] += data[i][j]
        if i in ans:
            new_data.append(tmp)
            tmp = [0]*W
    group = len(new_data)
    cnt += group-1
    white = [0] * group
    flag = True
    for i in range(W):
        diff = [0] * group
        for j in range(group):
            diff[j] += new_data[j][i]
            white[j] += new_data[j][i]
        max_diff = max(diff)
        if max_diff > K:
            flag = False
            break
        max_white = max(white)
        if max_white > K:
            cnt +=1
            white = diff[:]
    if flag:
        ans_cnt = min(ans_cnt,cnt)
print(ans_cnt)

Solution (Python):
h , w , k = map(int,input().split())
cho = [list(input()) for i in range(h)]
ans = 10**9
for i in range(2**(h-1)):
    cut = [0 for i in range(h)]
    for j in range(h-1):
        if i >> j & 1 == 1:
            cut[j+1] = cut[j]+1
        else:
            cut[j+1] = cut[j]
    maxcut = max(cut)+1
    cou = [0 for i in range(maxcut)]
    ccho = [[0 for i in range(w)] for j in range(maxcut)]
    for j in range(h):
        for l in range(w):
            ccho[cut[j]][l] += int(cho[j][l])
    tyu = maxcut - 1
    hukanou = False
    for j in range(w):
        flag = True
        for l in range(maxcut):
            if cou[l] + ccho[l][j] > k:
                flag = False
                break
        if flag:
            for l in range(maxcut):
                cou[l] += ccho[l][j]
        elif not flag:
            tyu += 1
            for l in range(maxcut):
                if ccho[l][j] > k:
                    hukanou = True
                    break
                cou[l] = ccho[l][j]
        if hukanou:
            break
    if hukanou:
        continue
    ans = min(ans,tyu)
print(ans)

Solution (Python):
h,w,k=map(int,input().split())
s=[[int(j) for j in input()] for i in range(h)]
def popcount(x):
    global h
    ret=0
    for i in range(h-1):
        ret+=(x>>i&1)
    return ret

ans=1000000000000000
for i in range(2**(h-1)):
    p=popcount(i)
    div=[0]*(p+1)
    ans_sub=p
    f=False
    for j in range(w):
        now=0
        div[now]+=s[0][j]
        for l in range(h-1):
            if i>>l&1:
                now+=1
            div[now]+=s[l+1][j]
        if all(i<=k for i in div):
            continue
        else:
            div=[0]*(p+1)
            now=0
            div[now]=s[0][j]
            for l in range(h-1):
                if i>>l&1:
                    now+=1
                div[now]+=s[l+1][j]
            ans_sub+=1
            f=any(i>k for i in div)
    if not f:ans=min(ans,ans_sub)
print(ans)

Solution (Python):
import sys
from itertools import product

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


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

    R = [[0] * (W + 1) for _ in range(H + 1)]
    for h in range(H):
        for w in range(W):
            R[h + 1][w + 1] = R[h][w + 1] + R[h + 1][w] - R[h][w] + int(grid[h][w])

    res = f_inf
    for pattern in product([0, 1], repeat=H-1):
        cut_H = [idx + 1 for idx, p in enumerate(pattern) if p == 1] + [H]
        cnt_cut = sum(pattern)
        left = 0
        right = 1
        flg = 1
        while right <= W:
            if not flg:
                break
            up = 0
            for bottom in cut_H:
                cnt_w = R[bottom][right] - R[bottom][left] - R[up][right] + R[up][left]
                if cnt_w > K:
                    if right - left == 1:
                        flg = False
                    cnt_cut += 1
                    left = right - 1
                    break
                else:
                    up = bottom
            else:
                right += 1
        else:
            res = min(res, cnt_cut)
    print(res)


if __name__ == '__main__':
    resolve()

Solution (Python):
h,w,k = map(int,input().split())
S = [input() for _ in range(h)]
ans = float('inf')
for bit in range(1<<(h-1)):
    segment = [0]*h
    seg = 0
    for i in range(h-1):
        if bit & (1<<i):
            seg += 1
        segment[i+1] = seg
    n = max(segment) + 1

    count = n-1
    k_cnt = [0]*n
    for j in range(w):
        tmp = [0]*n
        for i in range(h):
            k_cnt[segment[i]] += int(S[i][j])
            tmp[segment[i]] += int(S[i][j])
            if k_cnt[segment[i]] > k:
                count += 1
                for i in range(n):
                    k_cnt[i] = tmp[i]
    ans = min(ans,count)
print(ans)

Solution (Python):
"""

制約の小ささから見て全探索

"""

from itertools import product, accumulate
from bisect import *
import sys
input = sys.stdin.readline

H, W, K = map(int, input().split())
S = []
T = []
for i in range(H):
    S.append(list(map(int, input().strip())))
    T.append(list(accumulate([0] + S[-1])))

cnt_list = []
for a in product((0,1),repeat=H):
    past_a = a[0]
    T2 = [[0]*(W+1)]
    for i in range(H):
        if a[i] == past_a:
            for j, t in enumerate(T[i]):
                T2[-1][j] += t
        else:
            T2.append(T[i].copy())
        past_a = a[i]
    cnt = len(T2) - 1
    l = 0
    flg = False
    while True:
        temp = []
        for s in T2:
            temp.append(bisect_right(s[l+1:], K + s[l]) + l)
        if min(temp) == 0:
            flg = True
            break
        else:
            l = min(temp)
        if l >= W:
            break
        else:
            cnt += 1
    if not flg:
        cnt_list.append(cnt)

print(min(cnt_list))

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

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    H, W, K = NMI()
    choco = [SI() for _ in range(H)]
    ans = 100000
    for case in range(2**(H-1)):
        groups = [[0]]
        for i in range(H-1):
            if (case >> i) & 1:
                groups[-1].append(i+1)
            else:
                groups.append([i+1])
        white = [0] * len(groups)

        is_badcase = False
        cut = len(groups) - 1
        for w in range(W):
            diff = [0] * len(groups)
            for gi, group in enumerate(groups):
                for h in group:
                    if choco[h][w] == "1":
                        white[gi] += 1
                        diff[gi] += 1

            if max(white) <= K:
                is_cont = True
                continue

            if max(diff) > K:
                is_badcase = True
                break

            cut += 1
            white = diff[:]
            continue

        if not is_badcase:
            ans = min(ans, cut)

    print(ans)



if __name__ == "__main__":
    main()

Solution (Python):

H, W, K = map(int, input().split())
X = [list(input()) for _ in range(H)]
MOD = 10 ** 9 + 7
ans = MOD

for bit in range(2 ** (H - 1)):
    n = bin(bit).count("1")
    ctr = [0] * (n + 1)  
    res = 0
    for j in range(W):
        k = 0
        tmp = [0] * (n + 1)  
        for i in range(H):
            tmp[k] += int(X[i][j])
            if bit >> i & 1:
                k += 1

        
        if any(v > K for v in tmp):
            res = MOD
            break
        elif any(u + v > K for u, v in zip(ctr, tmp)):
            
            res += 1
            ctr = tmp[:]
        else:
            
            for i in range(n + 1):
                ctr[i] += tmp[i]

    ans = min(ans, res + n)

print(ans)

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

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

s = [[0 for i in range(w)] for i in range(h)]

ans = h+w
for grid in itertools.product([0,1], repeat=h-1):
  ary = [[0]]
  for i in range(h-1):
    if grid[i] == 1:
      ary.append([i+1])
    else:
      ary[-1].append(i+1)
  
  wk = 0
  for i in grid:
    if i == 1:
      wk += 1
  
  cnt = [0] * len(ary)
  for j in range(w):
    for ii, g in enumerate(ary):
      for b in g:
        if a[b][j] == '1':
          cnt[ii] += 1
    if any(W > k for W in cnt):
      wk += 1
      cnt = [0] * len(ary)
      for ii, g in enumerate(ary):
        for jj in g:
          if a[jj][j] == '1':
            cnt[ii] += 1
      if any(W > k for W in cnt):
        wk = h+w
        break
  ans = min(ans, wk)
print (ans)

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

ans = 10**18
for bit in range(1<<(h - 1)):
    segment = [0] * h
    seg_label = 0
    for i in range(h - 1):
        if bit & (1<<i):
            seg_label += 1
        segment[i + 1] = seg_label
    n = max(segment) + 1

    count = n - 1
    k_count = [0] * n
    for j in range(w):
        tmp_count = [0] * n
        for i in range(h):
            k_count[segment[i]] += int(S[i][j])
            tmp_count[segment[i]] += int(S[i][j])
            if k_count[segment[i]] > k:
                count += 1
                for seg in range(n):
                    k_count[seg] = tmp_count[seg]

    ans = min(ans, count)

print(ans)

Solution (Python):
H, W, K = map(int, input().split())
S = []
for _ in range(H):
  S.append(input())
hsummation = [[int(S[0][k])]for k in range(W)]
for k in range(W):
  for j in range(1, H):
    hsummation[k].append(hsummation[k][j-1] + int(S[j][k]))

ans = float('inf')
anskouho = 0
h = -1
binhh = []
for j in range(2**(H-1)):
  h += 1
  binh = "0"*(H-len(str(bin(h)))+1)+str(bin(h))[2:]
  c = 0
  for k in range(len(binh)):
    if binh[k] == '1':
      c += 1
  binhh.append([binh, c])
binhh.sort(key = lambda x:x[1] , reverse= True)

for j in range(2**(H-1)):
  hlist=[]
  for k in range(H-1):
    if binhh[j][0][k] == '1':
      hlist.append(k)
  hlist.append(-1)
  anskouho = len(hlist)-1
  now = 0
  while now < W:
    counter = [0 for _ in range(len(hlist))]
    while now < W:
      counter[0] += hsummation[now][hlist[0]]
      if counter[0] > K:
        anskouho += 1
        break
      for l in range(1, len(hlist)):
        counter[l] += - hsummation[now][hlist[l-1]] + hsummation[now][hlist[l]]
        if counter[l] > K:
          anskouho += 1
          break
      else:
        now += 1
        continue
      break
    if anskouho > ans:
      break
  else:
    ans = anskouho
print(ans)

Solution (Python):
H, W, K = map(int, input().split())
S = []
for _ in range(H):
  S.append(input())
hsummation = [[int(S[0][k])]for k in range(W)]
for k in range(W):
  for j in range(1, H):
    hsummation[k].append(hsummation[k][j-1] + int(S[j][k]))

ans = float('inf')
anskouho = 0
h = -1
binhh = []
for j in range(2**(H-1)):
  h += 1
  binh = "0"*(H-len(str(bin(h)))+1)+str(bin(h))[2:]
  c = 0
  for k in range(len(binh)):
    if binh[k] == '1':
      c += 1
  binhh.append([binh, c])
binhh.sort(key = lambda x:x[1] , reverse= True)


for j in range(2**(H-1)):
  
  
  hlist=[]
  for k in range(H-1):
    if binhh[j][0][k] == '1':
      hlist.append(k)
  hlist.append(-1)
  anskouho = len(hlist)-1
  now = 0
  while now < W:
    counter = [0 for _ in range(len(hlist))]
    while now < W:
      counter[0] += hsummation[now][int(hlist[0])]
      for l in range(1, len(hlist)):
        
          
          
        
        counter[l] += - hsummation[now][hlist[l-1]] + hsummation[now][hlist[l]]
      if max(counter) > K:
        anskouho += 1
        break
      else:
        now += 1
    if anskouho > ans:
      break
  else:
    ans = min(ans, anskouho)
print(ans)

Solution (Python):
H, W, K = map(int, input().split())
S = []
for _ in range(H):
  S.append(input())
hsummation = [[int(S[0][k])]for k in range(W)]
for k in range(W):
  for j in range(1, H):
    hsummation[k].append(hsummation[k][j-1] + int(S[j][k]))

ans = float('inf')
anskouho = 0
h = -1
binhh = []
for j in range(2**(H-1)):
  h += 1
  binh = "0"*(H-len(str(bin(h)))+1)+str(bin(h))[2:]
  c = 0
  for k in range(len(binh)):
    if binh[k] == '1':
      c += 1
  binhh.append([binh, c])
binhh.sort(key = lambda x:x[1] , reverse= True)


for j in range(2**(H-1)):
  
  
  hlist=[]
  for k in range(H-1):
    if binhh[j][0][k] == '1':
      hlist.append(k)
  hlist.append(-1)
  anskouho = len(hlist)-1
  now = 0
  while now < W:
    counter = [0 for _ in range(len(hlist))]
    while now < W:
      for l in range(len(hlist)):
        if l == 0:
          counter[l] += hsummation[now][int(hlist[l])]
          continue
        else:
          counter[l] += - hsummation[now][hlist[l-1]] + hsummation[now][hlist[l]]
      if max(counter) > K:
        anskouho += 1
        break
      else:
        now += 1
    if anskouho > ans:
      break
  else:
    ans = min(ans, anskouho)
print(ans)

Solution (Python):
H, W, K = map(int, input().split())
S = []
for _ in range(H):
  S.append(input())
hsummation = [[int(S[0][k])]for k in range(W)]
for k in range(W):
  for j in range(1, H):
    hsummation[k].append(hsummation[k][j-1] + int(S[j][k]))

ans = float('inf')
anskouho = 0
h = 2**(H-1)
for j in range(2**(H-1)):
  h -= 1
  binh = "0"*(H-len(str(bin(h)))+1)+str(bin(h))[2:]
  hlist=[]
  for k in range(H-1):
    if binh[-k-1] == '1':
      hlist.append(k)
  hlist.append(-1)
  
  anskouho = len(hlist)-1
  now = 0
  while now < W:
    counter = [0 for _ in range(len(hlist))]
    while now < W:
      for l in range(len(hlist)):
        if l == 0:
          counter[l] += hsummation[now][int(hlist[l])]
          continue
        else:
          counter[l] += - hsummation[now][hlist[l-1]] + hsummation[now][hlist[l]]
      if max(counter) > K:
        anskouho += 1
        break
      else:
        now += 1
    if anskouho > ans:
      break
  else:
    ans = min(ans, anskouho)
 
      

print(ans)

Solution (Python):
H, W, K = map(int, input().split())
S = []
for _ in range(H):
  S.append(input())
hsummation = [[int(S[0][k])]for k in range(W)]
for k in range(W):
  for j in range(1, H):
    hsummation[k].append(hsummation[k][j-1] + int(S[j][k]))

ans = float('inf')
anskouho = 0
h = 2**(H-1)
for j in range(2**(H-1)):
  h -= 1
  binh = "0"*(H-len(str(bin(h)))+1)+str(bin(h))[2:]
  hlist=[]
  for k in range(H-1):
    if binh[-k-1] == '1':
      hlist.append(k)
  hlist.append(-1)
  
  anskouho = len(hlist)-1
  now = 0
  while now < W:
    counter = [0 for _ in range(len(hlist))]
    while now < W:
      for l in range(len(hlist)):
        if l == 0:
          counter[l] += hsummation[now][int(hlist[l])]
          continue
        else:
          counter[l] += - hsummation[now][hlist[l-1]] + hsummation[now][hlist[l]]
      if max(counter) > K:
        anskouho += 1
        break
      else:
        now += 1
    if anskouho > ans:
      break
  else:
    ans = min(ans, anskouho)
 
      

print(ans)

Solution (Python):

from collections import defaultdict, deque, Counter, OrderedDict
import collections, heapq, itertools, bisect
import math, fractions
import sys, copy

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline().rstrip())
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline().rstrip())
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)
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007

def bit_pattern(bits, length):
    return [(bits >> i) & 1 for i in range(length)]

def main():
    H, W, K = LI()
    s = SR(H)

    ans = float("inf")

    for i in range(1 << (H - 1)):
        pattern = bit_pattern(i, H-1)
        divided = []
        tmp = [s[0]]
        tmp_ans = 0

        for i, bit in enumerate(pattern):
            if bit:
                tmp_ans += 1
                divided.append(tmp)
                tmp = [s[i+1]]
            else:
                tmp.append(s[i+1])
        divided.append(tmp)

        whites = []

        for block in divided:
            white = [0] * W
            for row in block:
                for i, panel in enumerate(row):
                    if panel == "1":
                        white[i] += 1
            whites.append(white)

        curs = [0] * len(whites)
        outer = False
        for w in range(W):
            for i, white in enumerate(whites):
                if white[w] > K:
                    outer = True
                    break
                elif white[w] + curs[i] > K:
                    curs = [white[w] for white in whites]
                    tmp_ans += 1
                    break
                else:
                    curs[i] += white[w]
            else:
                continue
            if outer:
                break
        else:
            ans = min(ans, tmp_ans)

    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import itertools


def main():
    H, W, K = list(map(int, input().split(' ')))
    S = [input() for _ in range(H)]
    ans = (H - 1) * (W - 1)
    for h_divs in itertools.product([0, 1], repeat=H-1):
        
        h_patterns = [0] * H
        for h in range(1, H):
            h_patterns[h] = h_patterns[h - 1] + h_divs[h - 1]
        
        div_cnt = h_patterns[-1]
        
        white_cnt = [0] * (div_cnt + 1)
        valid_div = True  
        for w in range(W):
            new_white_cnt = [0] * (div_cnt + 1)
            for h in range(H):
                if S[h][w] == '1':
                    new_white_cnt[h_patterns[h]] += 1
            if max(new_white_cnt) > K:
                valid_div = False
                break
            should_div = False
            for r in range(len(white_cnt)):
                if white_cnt[r] + new_white_cnt[r] > K:
                    should_div = True
                    break
            if should_div:
                div_cnt += 1
                for r in range(len(white_cnt)):
                    white_cnt[r] = new_white_cnt[r]
            else:
                for r in range(len(white_cnt)):
                    white_cnt[r] += new_white_cnt[r]
        if valid_div:
            ans = min(ans, div_cnt)
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
from itertools import product
H,W,K = map(int,input().split())
S = [input().strip() for _ in range(H)]
C = {i:[0 for _ in range(W+1)] for i in range(H)}
for i in range(H):
    for j in range(1,W+1):
        C[i][j] = C[i][j-1]+int(S[i][j-1])
cmin = (H-1)*(W-1)
for x in product((0,1),repeat=H-1):
    A = []
    cur = 0
    for i in range(H-1):
        if x[i]==1:
            A.append(list(range(cur,i+1)))
            cur = i+1
    A.append(list(range(cur,H)))

    cur = 0
    cnt = 0
    ind = 0
    for j in range(1,W+1):
        flag = 0
        for a in A:
            tot = 0
            for i in a:
                tot += C[i][j]-C[i][cur]
            if tot<=K:continue
            else:
                flag = 1
                break
        if flag==1:
            cnt += 1
            if cur==j-1:
                ind = 1
                break
            cur = j-1
    if ind==0:
        cmin = min(cmin,cnt+sum(x))

print(cmin)

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

h,w,k = inpl()
s = [list(input()) for _ in range(h)]
res = INF
for yoko in itertools.product([0,1], repeat=(h-1)):
    
    ln = sum(yoko)
    gr = [[] for _ in range(ln+1)] 
    gr[0].append(0)
    ind = 0
    for i in range(1,h):
        if yoko[i-1]: ind += 1
        gr[ind].append(i)
    possible = True
    for x in range(w):
        for ind in range(ln+1):
            cnt = 0
            for y in gr[ind]:
                if s[y][x] == '1':
                    cnt += 1
            if cnt > k:
                possible = False
                break
        if not possible:
            break
    else:
        cutcnt = 0
        now = [0] * (ln+1)
        for x in range(w):
            for ind in range(ln+1):
                for y in gr[ind]:
                    if s[y][x] == '1':
                        now[ind] += 1
            if max(now) > k:
                now = [0] * (ln+1)
                cutcnt += 1
                for ind in range(ln+1):
                    for y in gr[ind]:
                        if s[y][x] == '1':
                            now[ind] += 1
        res = min(res, cutcnt + ln)
print(res)

Solution (Python):
import collections

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

ans = float("inf")


for i in range(2 ** (H - 1)):
    bundan = {}
    bundan[0] = 0
    prev = 0
    tmp = 0
    for j in range(H - 1):
        if i >> j & 1 == 1:
            prev += 1
            bundan[j + 1] = prev
            tmp += 1
        else:
            bundan[j + 1] = prev

    c = collections.Counter()
    for kk in range(W):
        f = False
        for k in range(H):
            if f:
                break
            if S[k][kk] == '1':
                c[bundan[k]] += 1
                if c[bundan[k]] > K:
                    tmp += 1
                    f = True
                    c = collections.Counter()
                    for kkk in range(H):
                        if S[kkk][kk] == '1':
                            c[bundan[kkk]] += 1
                    break
    for k in c.keys():
        if c[k] > K:
            tmp = float("inf")
            break


    ans = min(ans, tmp)


print(ans)

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

ans = H+W+9999
for b in range(1<<(H-1)):
    mp = [0]
    k = 0
    for i in range(H-1):
        if b&(1<<i):
            k += 1
        mp.append(k)
    tmp = bin(b).count('1')
    ws = [0] * H
    muri = False
    for col in zip(*S):
        for i,c in enumerate(col):
            if c == '1':
                ws[mp[i]] += 1
        if any(w > K for w in ws):
            ws = [0] * len(mp)
            for i,c in enumerate(col):
                if c == '1':
                    ws[mp[i]] += 1
            if any(w > K for w in ws):
                muri = True
                break
            tmp += 1
        if muri:
            break
    if not muri:
        ans = min(ans, tmp)
print(ans)