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):
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def S(): return input()


def MI(): return map(int, input().split())


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


def print_matrix(mat):
    for i in range(len(mat)):
        print(*mat[i])


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False


WHITE = '1'
BLACK = '0'




def main():
    H, W, K = MI()
    graph = [None] * H

    for i in range(H):
        graph[i] = [int(v) for v in list(S())]

    ans = 10**9
    for i in range(2 ** (H-1)):
        groups = [0]
        for j in range((H-1)):
            if ((i >> j) & 1):
                groups.append(j+1)
        groups.append(H)

        divide_count = 0
        counter = defaultdict(int)
        impossible = False
        for w in range(W):
            current_counter = defaultdict(int)
            for g in range(1, len(groups)):
                prev_div = groups[g-1]
                div = groups[g]
                total = 0
                for h in range(prev_div, div):
                    total += graph[h][w]
                current_counter[g] += total

            
            if not all(v <= K for v in current_counter.values()):
                impossible = True
                break

            for k, v in current_counter.items():
                counter[k] += v
                if counter[k] > K:
                    divide_count += 1
                    counter = current_counter
                    break
            

        if not impossible:
            
            ans = min(ans, divide_count + len(groups) - 2)

    print(ans)


if __name__ == '__main__':
    main()

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

def popcnt(n):
  c = (n & 0x5555555555555555) + ((n >> 1) & 0x5555555555555555)
  c = (c & 0x3333333333333333) + ((c >> 2) & 0x3333333333333333)
  c = (c & 0x0f0f0f0f0f0f0f0f) + ((c >> 4) & 0x0f0f0f0f0f0f0f0f)
  c = (c & 0x00ff00ff00ff00ff) + ((c >> 8) & 0x00ff00ff00ff00ff)
  c = (c & 0x0000ffff0000ffff) + ((c >> 16) & 0x0000ffff0000ffff)
  c = (c & 0x00000000ffffffff) + ((c >> 32) & 0x00000000ffffffff)
  return c

answer = 10 ** 18

for i in range(2 ** (H - 1)):
    answer_tmp = popcnt(i)
    dic = [-1] * H
    index = 0
    for j in range(H):
        dic[j] = index
        if i >> j & 1:
            index += 1
    tmp = [0] * (index + 1)
    
    flag = 0
    for k in range(W):
        for j in range(H):
            if S[j][k] == "1":
                tmp[dic[j]] += 1
        if k == 0 and max(tmp) > K:
            flag = 1
            break
        if max(tmp) > K:
            answer_tmp += 1
            for j, t in enumerate(tmp):
                tmp[j] = 0
            for j in range(H):
                if S[j][k] == "1":
                    tmp[dic[j]] += 1
            if max(tmp) > K:
                flag = 1
                break
    if flag:
        continue
    answer = min(answer, answer_tmp)

print(answer)

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 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]
ans=10**18
for rows in range(2**(h-1)):
  cnt=0
  hlist=[]
  flag=format(rows,'b')[::-1]
  for i in range(len(flag)):
    if flag[i]=='1':
      cnt+=1
      hlist.append(i)
  hlist.append(h-1)
  x1=0
  for x2 in range(w-1):
    y1=0
    for y2 in hlist:
      if count(x1,y1,x2,y2)>k:
        cnt+=10**18
      if count(x1,y1,x2,y2)<=k and count(x1,y1,x2+1,y2)>k:
        cnt+=1
        x1=x2+1
        break
      y1=y2+1
  y1=0
  for y2 in hlist:
    if count(x1,y1,w-1,y2)>k:
      cnt+=10**18
    y1=y2+1
  ans=min(ans,cnt)
print(ans)

Solution (Python):
import itertools
 
H, W, K = map(int, input().split())
S = []
for _ in range(H):
    S.append([int(s) for s in input()])
 
ans = 2000
for t in itertools.product([0, 1], repeat=H - 1):
    cnt = t.count(1)
    lst = [[s for s in S[0]]]
    for h in range(H - 1):
        if t[h]:
            lst.append(S[h + 1])
        else:
            lst[-1] = [lst[-1][i] + S[h + 1][i] for i in range(W)]
    L = len(lst)
    sum_lst = [0] * L
    for w in range(W):
        if max(lst[i][w] for i in range(L)) > K:
            break
        tmp = [sum_lst[i] + lst[i][w] for i in range(L)]
        if max(tmp) > K:
            cnt += 1
            sum_lst = [lst[i][w] for i in range(L)]
        else:
            sum_lst = tmp
    else:
        ans = min(ans, cnt)
print(ans)

Solution (Python):
import itertools
 
H, W, K = map(int, input().split())
S = []
for _ in range(H):
    S.append([int(s) for s in input()])
 
ans = 2000
for t in itertools.product([0, 1], repeat=H - 1):
    cnt = t.count(1)
    lst = [[s for s in S[0]]]
    for h in range(H - 1):
        if t[h]:
            lst.append(S[h + 1])
        else:
            lst[-1] = [lst[-1][i] + S[h + 1][i] for i in range(W)]
    L = len(lst)
    sum_lst = [0] * L
    for w in range(W):
        if max(lst[i][w] for i in range(L)) > K:
            break
        tmp = [sum_lst[i] + lst[i][w] for i in range(L)]
        if max(tmp) > K:
            cnt += 1
            sum_lst = [lst[i][w] for i in range(L)]
        else:
            sum_lst = tmp
    else:
        ans = min(ans, cnt)
print(ans)

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

    def check(lis):
        
        num = [0]*(len(lis))
        ans = 0
        for i in range(w):
            num2 = [0]*(len(lis))
            for j in range(h):
                
                if l[j][i] == "1":
                    num2[d[j]] += 1
            if max(num2) > k:
                return float("INF")
            else:
                for i in range(len(num)):
                    num[i] += num2[i]
                    if num[i] > k:
                        ans += 1
                        num = num2
                        break 
            
            
        return ans

    ans = 10**9

    for i in range(2**(h-1)):
        count = 0
        lis1 = []
        d = []
        for j in range(h):
            d.append(count)
            if (i >> j) & 1:
                lis1.append(j)
                count += 1
        lis1.append(count+1)
        ans = min(ans,count+check(lis1))
        
    print(ans)
if __name__ == "__main__":
    main()

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

    def check(lis):
        
        num = [0]*(len(lis))
        ans = 0
        for i in range(w):
            num2 = [0]*(len(lis))
            for j in range(h):
                
                if l[j][i] == "1":
                    num2[d[j]] += 1
            if max(num2) > k:
                return float("INF")
            else:
                for i in range(len(num)):
                    num[i] += num2[i]
                    if num[i] > k:
                        ans += 1
                        num = num2
                        break 
            
            
        return ans

    ans = 10**9

    for i in range(2**(h-1)):
        count = 0
        lis1 = []
        d = []
        for j in range(h):
            d.append(count)
            if (i >> j) & 1:
                lis1.append(j)
                count += 1
        lis1.append(count+1)
        ans = min(ans,count+check(lis1))
        
    print(ans)
if __name__ == "__main__":
    main()

Solution (Python):
import numpy as np
from itertools import product

H,W,K=map(int,input().split(' '))
arr = np.vstack([[int(i) for i in input()] for j in range(H)])
ans = H+W-2
for p in product([0,1],repeat=H-1):
    if sum(p)>ans:
        continue
    sp=np.zeros((sum(p)+1,W),int)
    row=0
    sp[0]+=arr[0]
    for j in range(H-1):
        if p[j]:
            row+=1
        sp[row]+=arr[j+1]
    if np.max(sp)>K:
        continue
    sum_arr = np.zeros(len(sp),int)
    cut_cnt = sum(p)
    for c in range(W):
        sum_arr += sp[:,c]
        if max(sum_arr)>K:
            cut_cnt+=1
            sum_arr=sp[:,c]
            if cut_cnt > ans:
                break
    ans = min(cut_cnt,ans)
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 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]
ans=10**18
for rows in range(2**(h-1)):
  hlist=[]
  flag=format(rows,'b')[::-1]
  for i in range(len(flag)):
    if flag[i]=='1':
      hlist.append(i)
  hlist.append(h-1)
  cnt=len(hlist)-1
  x1=0
  for x2 in range(w-1):
    y1=0
    for y2 in hlist:
      if count(x1,y1,x2,y2)>k:
        cnt+=10**18
      if count(x1,y1,x2,y2)<=k and count(x1,y1,x2+1,y2)>k:
        cnt+=1
        x1=x2+1
        break
      y1=y2+1
  y1=0
  for y2 in hlist:
    if count(x1,y1,w-1,y2)>k:
      cnt+=10**18
    y1=y2+1
  ans=min(ans,cnt)
print(ans)

Solution (Python):
import itertools, copy

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

ans = float("inf")
for n_horizontal_cut in range(H):
    for horizontal_cut_idx in list(itertools.combinations(list(range(1,H)), n_horizontal_cut)):
        horizontal_cut_idx = [0] + list(horizontal_cut_idx) + [H]
        n_vertical_cut = 0
        n_white_choco = [0] * (n_horizontal_cut+1)
        for w in range(W):
            tmp_idx = 0
            tmp_n_white_choco = copy.copy(n_white_choco)
            for h in range(H):
                if h >= horizontal_cut_idx[tmp_idx+1]:
                    tmp_idx += 1
                if S[h][w] == 1:
                    n_white_choco[tmp_idx] += 1
            if max(n_white_choco) > K:
                n_vertical_cut += 1
                n_white_choco = [n_white_choco[i] - tmp_n_white_choco[i] for i in range(n_horizontal_cut+1)]
                if max(n_white_choco) > K: 
                    break
        else:
            ans = min(ans, n_horizontal_cut + n_vertical_cut)

print(ans)

Solution (Python):
from itertools import combinations, chain

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


def h_divide(Sss, div_is):
    result = []
    for s, e in zip(chain([0], div_is), chain(div_is, [len(Sss)])):
        result.append(Sss[s:e])
    return result


def _v_end(Sss, start, K):
    count = 0
    for i in range(start, len(Sss[0])):
        s = sum(map(lambda Ss: Ss[i], Sss))
        if count + s > K:
            return i - 1
        count += s
    return len(Sss[0]) - 1


def v_end(Ssss, start, K):
    result = -1
    for Sss in Ssss:
        end = _v_end(Sss, start, K)
        if end < start:
            return -1
        if result < 0 or result > end:
            result = end
    return result


def v_div_count(Ssss, K):
    start, result = 0, 0
    while True:
        end = v_end(Ssss, start, K)
        if end < 0:
            return -1
        if end == len(Ssss[0][0]) - 1:
            break
        result += 1
        start = end + 1
    return result


h_cands = list(range(1, len(Sss)))
ans = -1
for n in range(len(h_cands) + 1):
    for comb in combinations(h_cands, n):
        if ans > 0 and n >= ans:
            continue
        Ssss = h_divide(Sss, list(comb))
        cnt = v_div_count(Ssss, K)
        if cnt < 0:
            continue
        if ans < 0 or ans > n + cnt:
            ans = n + cnt
print(ans)

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

white_count = [[0] * (w+1)]
for line in chocolate:
    prev = white_count[-1]
    cumsum = []
    total = 0
    for color, count in zip(line, prev):
        if color == '1':
            total += 1
        cumsum.append(total + count)
    white_count.append(cumsum)

ans = []
for pattern in range(2**(h-1)):
    dived = []
    for y in range(h-1):
        if (pattern >> y) & 1:
            dived.append(y + 1)

    dived.append(h)
    slash_count = len(dived) - 1

    prev_x = 0
    for nx in range(1, w + 1):
        prev_y = 0
        possible = True
        for ny in dived:
            white = white_count[ny][nx] - white_count[prev_y][nx] - (white_count[ny][prev_x] - white_count[prev_y][prev_x])
            prev_y = ny
            if white <= k:
                continue
            else:
                slash_count += 1
                slash = nx - 1
                if prev_x == slash:
                    possible = False
                prev_x = slash
                break

        if not possible:
            break

    else:
        ans.append(slash_count)

print(min(ans))

Solution (Python):
import itertools

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


ans = 2000
for t in itertools.product([0, 1], repeat=H - 1):

    cnt = t.count(1)
    lst = [[s for s in S[0]]]
    for h in range(H - 1):
        if t[h]: 
            lst.append(S[h + 1])
        else: 
            lst[-1] = [lst[-1][i] + S[h + 1][i] for i in range(W)]
    L = len(lst)

    sum_lst = [0] * L
    for w in range(W):

        if max(lst[i][w] for i in range(L)) > K:
            
            break
        tmp = [sum_lst[i] + lst[i][w] for i in range(L)]
        
        if max(tmp) > K:
            cnt += 1
  
            sum_lst = [lst[i][w] for i in range(L)]
            
        else:
            sum_lst = tmp
    else: 
        ans = min(ans, cnt)
print(ans)

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


def solve():
    H, W, K = map(int, rl().split())
    S = [[] for _ in range(H)]
    for i in range(H):
        S[i] = list(map(int, list(input())))
    
    ans = 10 ** 6
    for s in range(1 << (H - 1)):
        pop_cnt = 0
        for i in range(H - 1):
            if s >> i & 1:
                pop_cnt += 1
        
        tmp = pop_cnt
        b = [0] * (tmp + 1)
        flg = True
        for i in range(W):
            j = 0
            for k in range(H):
                if S[k][i]:
                    b[j] += 1
                if s >> k & 1:
                    j += 1
            
            flg = True
            for bi in b:
                if K < bi:
                    flg = False
            
            if not flg:
                tmp += 1
                b = [0] * (pop_cnt + 1)
                j = 0
                for k in range(H):
                    if S[k][i]:
                        b[j] += 1
                    if s >> k & 1:
                        j += 1
                
                flg = True
                for bi in b:
                    if K < bi:
                        flg = False
        
        if flg:
            ans = min(ans, tmp)
    print(ans)


if __name__ == '__main__':
    solve()

Solution (Python):
def solve(L):
    global H, W, K
    N = len(L)
    SL = [[0] * (W + 1) for _ in range(N)]
    for i in range(N):
        for j in range(W):
            SL[i][j + 1] = SL[i][j] + L[i][j]

    offset = [0] * N
    base = 0
    cnt = 0
    j = 0
    while j < W:
        if any([SL[x][j + 1] - offset[x] > K for x in range(N)]):
            if base == j:
                return -1
            else:
                base = j
                offset = [SL[x][j] for x in range(N)]
                cnt += 1
        else:
            j += 1
    return cnt


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

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

ans = H + W
for bit in range(pow(2, H - 1)):
    bit <<= 1
    L = [[0] * W for _ in range(H)]
    k = 0
    for i in range(H):
        if (bit >> i) & 1:
            k += 1
        for j in range(W):
            if S[i][j]:
                L[k][j] += 1
    horizontal = solve(L)
    if horizontal >= 0:
        vertical = bin(bit).count('1')
        ans = min(ans, horizontal + vertical)

print(ans)

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

cnt=10001

for i in range(2**(h-1)):
    split=[0]*h
    curcnt=0
    for j in range(h):
        if (i>>j)&1:
            split[j]=1
            curcnt+=1
        
    nsplit=curcnt+1
    sumlst=[[0]*(nsplit) for _ in range(w)]

    cw=0
    memo=0
    chk=0
    flag=False
    while cw<w:
        l=0
        for ch in range(h):
            sumlst[memo][l]+=s[ch][cw]

            if sumlst[memo][l]>k:
                memo+=1
                chk+=1
                break

            if split[ch]:
                l+=1
        else:
            chk=0
            cw+=1
            continue

        if chk>1:
            break
    else:
        cnt=min(cnt,curcnt+memo)

print(cnt)

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

white_count = [[0] * (w+1)]
for line in chocolate:
    prev = white_count[-1]
    cumsum = []
    total = 0
    for color, count in zip(line, prev):
        if color == '1':
            total += 1
        cumsum.append(total + count)
    white_count.append(cumsum)

ans = []
for pattern in range(2**(h-1)):
    dived = []
    for y in range(h-1):
        if (pattern >> y) & 1:
            dived.append(y + 1)

    dived.append(h)
    slash_count = len(dived) - 1

    prev_x = 0
    for nx in range(1, w + 1):
        prev_y = 0
        possible = True
        for ny in dived:
            white = white_count[ny][nx] - white_count[prev_y][nx] - (white_count[ny][prev_x] - white_count[prev_y][prev_x])
            prev_y = ny
            if white <= k:
                continue
            else:
                slash_count += 1
                slash = nx - 1
                if prev_x == slash:
                    possible = False
                prev_x = slash
                break

        if not possible:
            break

    else:
        ans.append(slash_count)

print(min(ans))

Solution (Python):
import itertools
import numpy as np

res = 999999999999999999

H, W, K = [int(i) for i in input().split()]
arr = []
for h in range(H):
  arr.append([int(v) for v in input()])

arr = np.vstack(arr)

for p in itertools.product([0, 1], repeat = H-1):
  if sum(p) > res:
    continue
  sp = np.zeros((sum(p)+1, W), int)
  row = 0
  sp[0] += arr[0]
  for j in range(H-1):
    if p[j]:
      row += 1
    sp[row] += arr[j+1]
  if np.max(sp) > K:
    continue
  
  sum_arr = np.zeros(len(sp), int)
  cut_cnt = sum(p)
  for c in range(W):
    sum_arr += sp[:, c]
    if max(sum_arr) > K:
      sum_arr = sp[:, c]
      cut_cnt += 1
      if cut_cnt > res:
        break
  if cut_cnt < res:
    res = cut_cnt
print(res)

Solution (Python):
from collections import defaultdict
from itertools import product

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

i = 0
while i < len(S):
  if '1' in S[i]:
    i += 1
  else:
    del S[i]
H = len(S)

C = [[int(s[i]) for s in S] for i in range(W)]

total = sum(sum(c) for c in C)

if total <= K:
  answer = 0
else:
  answer = H * W
  for X in product([False, True], repeat=H-1):
    ans = 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 c in C:
      for k, m in enumerate(M):
        D[k] += sum(c[i] for i in m)
      if any(d > K for d in D):
        ans += 1
        if ans > answer:
          break
        D = [sum(c[i] for i in m) for m in M]
        if any(d > K for d in D):
          ans = answer + 1
          break
    answer = min(answer, ans)

print(answer)

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

mat=[]
for i in range(H):
  array=[int(x) for x in input()]
  mat.append(array)


answer=10**9
for i in range(2**(H-1)):
  bitarray=[]
  ii=i
  for j in range(H-1):
    bitarray.append(ii&1)
    ii>>=1
    
  
  segment_list=[]
  segment=[0]
  for k in range(len(bitarray)):
    if bitarray[k]==0:
      segment.append(k+1)
    else:
      segment_list.append(segment)
      segment=[k+1]
    
  segment_list.append(segment)
  divide_yoko=len(segment_list)-1
  
  
  white_list_segment=[0]*len(segment_list)
  sep_list=[]
  for j in range(W):
    white_list_segment_line=[0]*len(segment_list)
    for k in range(len(segment_list)):
      seg=segment_list[k]
      for s in seg:
        white_list_segment_line[k]+=mat[s][j]
        
    isLineOver=False
    if max(white_list_segment_line)>K:
      isLineOver=True
      break
    
    isOver=False
    for k in range(len(segment_list)):
      if white_list_segment[k]+white_list_segment_line[k]>K:
        isOver=True
        break

    if isOver:
      sep_list.append(j-1)
      for k in range(len(segment_list)):
        white_list_segment[k]=white_list_segment_line[k]
    else:
      for k in range(len(segment_list)):
        white_list_segment[k]+=white_list_segment_line[k]
  
  if not isLineOver:
    answer=min(answer,len(segment_list)-1+len(sep_list))
  
  
print(answer)

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

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

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

    res = yoko

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

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

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

    if flag:
        ans = min(ans, res)

print(ans)

Solution (Python):
h,w,k = map(int,input().split())
s = [input() for _ in range(h)]
data_yoko = [[0]*(w+1) for _ in range(h)]
for i in range(w):
    for j in range(h):
        if s[j][i] == "1":
            data_yoko[j][i+1] = 1
        data_yoko[j][i+1] += data_yoko[j][i]
data_tate = [[0]*w for _ in range(h+1)]
for i in range(h):
    for j in range(w):
        if s[i][j] == "1":
            data_tate[i+1][j] = 1
        data_tate[i+1][j] += data_tate[i][j]

ans = h*w
for case in range(2**(h-1)):
    now = 0
    use = []
    for bit in range(h-1):
        if case>>bit & 1:
            use.append(bit+1)
            now += 1
    use.append(h)
    left = [0]*len(use)
    pre = -1
    check1 = True
    check2 = True
    
    for i in range(w):
        for j in range(len(use)):
            to = data_tate[use[j]][i] if j == 0 else data_tate[use[j]][i]-data_tate[use[j-1]][i]
            if k < to:
                check1 = False
            if to + left[j] > k:
                check2 = False
            left[j] += to
        
        if not check1:
            break
        if check2:
            continue
        for j in range(len(use)):
            left[j] = data_tate[use[j]][i] if j == 0 else data_tate[use[j]][i]-data_tate[use[j-1]][i]
        now += 1
        check2 = True
    if check1:
        
        ans = min(ans,now)

print(ans)

Solution (Python):
from sys import stdin
def main():
    
    last_res=float("inf")
    readline=stdin.readline
    H,W,K=map(int,readline().split())
    grid=[]
    for i in range(H):
        s=readline().strip()
        grid.append(s)

    for i in range(1<<(H-1)):
        output=[]
        for j in range(H-1):
            if(i>>j)&1:
                output.append(j)
        count=[0]*(len(output)+1)
        res=len(output)

        for b in range(W):
            now=0
            flag=False
            for a in range(H):
                if len(output)>now and  a>output[now]:
                    now+=1
                if grid[a][b]=="1":
                    count[now]+=1
                    if count[now]>K:
                        count=[0]*(len(output)+1)
                        res+=1
                        flag=True
                        break
            if flag:
                now=0
                flag=False
                for a in range(H):
                    if len(output)>now and  a>output[now]:
                        now+=1
                    if grid[a][b]=="1":
                        count[now]+=1
                        if count[now]>K:
                            res+=1
                            flag=True
                            break
                if flag:
                    break
        if flag:
            res=float("inf")
        last_res=min(last_res,res)
    print(last_res)

if __name__=="__main__":
    main()

Solution (Python):


import itertools

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

ans = 2000
for t in itertools.product([0, 1], repeat=H - 1):
    cnt = t.count(1)
    lst = [[s for s in S[0]]]
    for h in range(H - 1):
        if t[h]:
            lst.append(S[h + 1])
        else:
            lst[-1] = [lst[-1][i] + S[h + 1][i] for i in range(W)]
    L = len(lst)
    sum_lst = [0] * L
    for w in range(W):
        if max(lst[i][w] for i in range(L)) > K:
            break
        tmp = [sum_lst[i] + lst[i][w] for i in range(L)]
        if max(tmp) > K:
            cnt += 1
            sum_lst = [lst[i][w] for i in range(L)]
        else:
            sum_lst = tmp
    else:
        ans = min(ans, cnt)
print(ans)

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


ans = float('inf')
flag = False
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])
                if chocos[-1][w] > K:
                    flag = True
                    break
            if flag:
                break
    if flag:
        flag = False
        continue
    ns = len(chocos)
    nums = [0] * ns
    is_next = False
    for w in range(W):
        for j in range(ns):
            nums[j] += chocos[j][w]
            if nums[j] > K:
                _ans += 1
                is_next = True
                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 itertools

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


ans = 2000
for t in itertools.product([0, 1], repeat=H - 1):
    
    cnt = t.count(1)
    lst = [[s for s in S[0]]]
    for h in range(H - 1):
        if t[h]: 
            lst.append(S[h + 1])
        else: 
            lst[-1] = [lst[-1][i] + S[h + 1][i] for i in range(W)] 
    L = len(lst)
    
    
    sum_lst = [0] * L
    for w in range(W):
        
        if max(lst[i][w] for i in range(L)) > K:
            
            break
        tmp = [sum_lst[i] + lst[i][w] for i in range(L)]
        
        if max(tmp) > K:
            cnt += 1
            
            sum_lst = [lst[i][w] for i in range(L)]
            
        else:
            sum_lst = tmp
    else: 
        ans = min(ans, cnt)
print(ans)
"""
for t in itertools.product([0, 1], repeat=H - 1):
    print(t)
"""