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(input()) for _ in range(h)]

res = float('inf')
for div in range(2**(h-1)):
    cut = []
    for i in range(h-1):
        if ((div >> i) & 1):
            cut.append(i+1)
    fr = 0
    part = []
    for i in range(len(cut)):
        to = cut[i]
        part.append(S[fr:to])
        fr = to
    else:
        part.append(S[fr:])
    comp_arr = []

    for p in part:
        tmp = [0]*(w)
        for p_ in p:
            for idx in range(len(p_)):
                if p_[idx]=='1':
                    tmp[idx] += 1
        comp_arr.append(tmp)
    
    if not all([all([i <= k for i in b]) for b in comp_arr]):
        continue
    
    cnt = len(cut)
    tank = [0]*len(comp_arr)
    for m in range(w):
        for n in range(len(comp_arr)):
            tank[n] += comp_arr[n][m]
        if any([c>k for c in tank]):
            cnt += 1
            for n in range(len(comp_arr)):
                tank[n] = comp_arr[n][m]
    res = min(res, cnt)
print(res)

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)):
    group = [[0]*w]
    g_id = 0
    group[g_id] = [s+b for s, b in zip(S[0], group[0])]
    for j in range(1, h):
        if (i>>(j-1))&1:
            group.append([0]*w)
            g_id += 1
        group[g_id] = [s+b for s, b in zip(S[j], group[g_id])]
    if not all([all([i <= k for i in b]) for b in group]):
        continue
    cnt = len(group) - 1
    g_cnt = [0] * len(group)
    
    for jj in range(w):
        for g_id in range(len(group)):
            g_cnt[g_id] += group[g_id][jj]
        if any([c > k for c in g_cnt]):
            cnt  += 1
            for g_id in range(len(group)):
                g_cnt[g_id] = group[g_id][jj]
    ans = min(ans, cnt)
print(ans)

Solution (Python):
import sys
input=sys.stdin.readline
h,w,k = map(int, input().split())
l = [None]*h
for i in range(h):
    l[i] = list(input())

from itertools import *
ans=10**10
import copy
for tmp in list(product([True,False], repeat=h-1)):
    num_sp = sum(tmp)+1
    cnt=[0]*num_sp
    nxt_cnt=[0]*num_sp
    last_spl=-1
    ok=True

    spl_l=[]
    for aaa in range(h):
        spl_l.append(sum(tmp[:aaa]))
    cur_ans=sum(tmp)
    for i in range(w):
        for j in range(h):
            spl = spl_l[j]
            nxt_cnt[spl] += int(l[j][i])
            cnt[spl] += int(l[j][i])

        if max(cnt) > k:
            cur_ans+=1
            cnt=copy.copy(nxt_cnt)
            if last_spl+1 == i or max(nxt_cnt)>k:
                ok=False
                break
            last_spl=i-1
        nxt_cnt=[0]*num_sp
        if not ok:
            break
    if ok:
        ans=min(ans,cur_ans)

print(ans)

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

    res = 1 << 29
    for bit in range(1 << (H-1)):
        gok = True
        N = 0
        ord_lst = [0] * H
        for i in range(H-1):
            if not(bit & 1<<i):
                ord_lst[i+1] = ord_lst[i]
            else:
                ord_lst[i+1] = ord_lst[i] + 1
                N += 1
        
        add = 0
        nums = [0] * (N+1)
        for w in range(W):
            one = [0] * (N+1)
            ok = True
            for h in range(H):
                one[ord_lst[h]] += int(fi[h][w])
                nums[ord_lst[h]] += int(fi[h][w])
                if one[ord_lst[h]] > K:
                    gok = False
                if nums[ord_lst[h]] > K:
                    ok = False
            
            if not ok:
                add += 1
                nums = one[:]
        if gok:
            res = min(res, N + add)
    print(res)

if __name__ == '__main__':
    solve()

Solution (Python):
def add(in1, in2):
    return [a + b for a, b in zip(in1, in2)]

def check_overk(in1, k):
    return len([i for i in in1 if i>k]) > 0

def split(ar, k, w):
    a = 0
    for i in ar:
        if check_overk(i, k):
            return -1
    tm = ar[0]
    for i in range(1, w):
        tm = add(tm, ar[i])
        if check_overk(tm, k):
            a += 1
            tm = ar[i]
    return a
            

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

for i in range(2**(h-1)):
    data = []
    temp = s[0]
    sp = bin(i+2**h)[4:]
    if ans < sp.count("1"):
        continue
    for j in range(1, h):
        if sp[j-1] == "0":
            temp = add(temp, s[j])
        else:
            data.append(temp)
            temp = s[j]
    data.append(temp)
    ans_ = split([list(x) for x in zip(*data)], k, w)
    if ans_ == -1:
        continue
    ans_ += sp.count("1")
    if ans > ans_:
        ans = ans_
print(ans)

Solution (Python):
def add(in1, in2):
    return [a + b for a, b in zip(in1, in2)]

def check_overk(in1, k):
    return len([i for i in in1 if i>k]) > 0

def split(ar, k, w):
    a = 0
    for i in ar:
        if check_overk(i, k):
            return -1
    tm = ar[0]
    for i in range(1, w):
        tm = add(tm, ar[i])
        if check_overk(tm, k):
            a += 1
            tm = ar[i]
    return a
            

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

for i in range(2**(h-1)):
    data = []
    temp = s[0]
    sp = bin(i+2**h)[4:]
    if ans < sp.count("1"):
        continue
    for j in range(1, h):
        if sp[j-1] == "0":
            temp = add(temp, s[j])
        else:
            data.append(temp)
            temp = s[j]
    data.append(temp)
    ans_ = split([list(x) for x in zip(*data)], k, w)
    if ans_ == -1:
        continue
    ans_ += sp.count("1")
    if ans > ans_:
        ans = ans_
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)

def solve():
    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)


if __name__ == "__main__":
    solve()

Solution (Python):




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


if H == 1:
    S = input()
    cnt = 0
    ans = 0

    for i in range(W):
        if S[i] == "1":
            cnt += 1
        if cnt > K:
            ans += 1
            cnt = 1


    
    print(ans)
    exit()


elif W == 1:
    S = [input() for _ in range(H)]
    cnt = 0
    ans = 0
    for i in range(H):
        if S[i] == "1":
            cnt += 1

        if cnt > K:
            ans += 1
            cnt = 1
    print(ans)
    exit()


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

ans = (H-1) + (W - 1)
for bit in range(1 << (H-1)):
    is_valid = True
    nums = bin(bit).count("1") + 1
    cnt_cut = bin(bit).count("1")


    
    cnt_white_prev = [0] * nums

    for w in range(W):
        
        cnt_white_curr = [0] * nums
        idx = 0

        
        for h in range(H):
            if S[h][w] == "1":
                cnt_white_curr[idx] += 1
            if h < H-1 and bit & (1 << h):
                idx += 1

        
        is_over_K = False
        
        for i in range(nums):

            
            if cnt_white_prev[i] + cnt_white_curr[i] > K:
                is_over_K = True
                if cnt_white_curr[i] > K:
                    is_valid = False
                break


        
        
        if is_over_K:
            cnt_cut += 1

            for i in range(nums):
                cnt_white_prev[i] = cnt_white_curr[i]
        else:
            for i in range(nums):
                cnt_white_prev[i] += cnt_white_curr[i]
    



    if is_valid:
        ans = min(ans, cnt_cut)

    

        

print(ans)

Solution (Python):


"""
bit全探索の考え方

for div in range(2**3):
    print(div)
    
    
    
    
    
    
    
    
    

"""


def solve():
    """
    最初に横に切る方法を全探索し、
    次に、ギリギリのラインを縦に切っていく
    O(2**H W)

    Note1:
        1 << K  =>  2**k

    Note2:
        div>>i&1
        => divのi桁目が1であるかどうか
    """
    H, W, K = list(map(int, input().split()))
    S = ["" for _ in range(H)]
    for i in range(H):
        s = input()
        S[i] += s
    ans = float("inf")

    
    
    
    for div in range(0, 1<<(H-1)):  
        g = 0
        ids = [0 for _ in range(H)]
        for i in range(H):
            ids[i] = g
            if div>>i&1:
                g += 1
        g += 1

        c = [[0 for _ in range(1005)] for __ in range(10)]

        for i in range(H):
            for j in range(W):
                c[ids[i]][j] += int(S[i][j])

        num = g-1  
        now = [0 for _ in range(g)]  
        def add(j, now, c):
            for i in range(g):
                now[i] += c[i][j]
            for i in range(g):
                if now[i] > K: return False
            return True

        for j in range(W):
            if not add(j, now, c):
                num += 1
                now = [0 for _ in range(g)]
                if not add(j, now, c):
                    num = float("inf")
                    break
        ans = min(ans, num)
    print(ans)


if __name__ == "__main__":
    solve()

Solution (Python):
h, w, k = map(int, input().split())
s = [list(map(int, input())) for _ in range(h)]
ans = (h - 1) * (w - 1)  
for bitseed in range(2 ** (h - 1)):
    i2cell = [0]
    accum_temp = 0
    for _ in range(h - 1):
        accum_temp += bitseed % 2
        i2cell.append(accum_temp)
        bitseed //= 2
    
    cell2whitenum = [0] * (accum_temp + 1)
    v_cut_num = 0
    for j in range(w):
        for i in range(h):
            cell2whitenum[i2cell[i]] += s[i][j]
        if max(cell2whitenum) > k:
            v_cut_num += 1
            cell2whitenum = [0] * (accum_temp + 1)
            for i in range(h):
                cell2whitenum[i2cell[i]] += s[i][j]
            if max(cell2whitenum) > k:
                v_cut_num = (h - 1) * (w - 1)  
    if accum_temp + v_cut_num < ans:
        ans = accum_temp + v_cut_num
print(ans)

Solution (Python):
import math
import functools
from operator import add

def main():
    h,w,k = tuple([int(t)for t in input().split()])

    s = [[int(i) for i in list(input())] for _ in range(h)]
    
    cusum = [accumelist(s_) for s_ in s]

    candidates = []

    for i in range(1<<(h-1)):
        subcu = divide(cusum,i)
        subs = divide(s,i)

        subcusum = []

        rowsum = []

        for sub_ in subcu:
            subcusum.append(functools.reduce((lambda a,b:list(map(add,a,b))),sub_))

        for sub_ in subs:
            rowsum.append(functools.reduce((lambda a,b:list(map(add,a,b))),sub_))


        cutnum = 0

        temp = [0]*len(subcusum)

        for j in range(w):
            for l in range(len(subcusum)):
                if subcusum[l][j]-temp[l]>k:
                    if rowsum[l][j]>k:
                        cutnum+=10000
                    temp = [x[j-1] for x in subcusum]
                    cutnum+=1
                    break
        
        candidates.append(cutnum+bin(i).count('1'))

    print(min(candidates))
            
def divide(s,i):
    subs = []
    counter = 0
    pos = 0
    while i!= 0:
        counter +=1
        if i%2==1:
            subs.append(s[pos:counter])
            pos = counter
        i >>=1
 
    subs.append(s[pos:])
    return subs

def accumelist(s):
    if s == []:
        return []
    res = [s[0]]
    for i in range(1,len(s)):
        res.append(res[i-1]+s[i])

    return res

def _add_(a,b):
    return map(add,a,b)
    
if __name__ == "__main__":
    main()

Solution (Python):
import math
import functools
from operator import add

def main():
    h,w,k = tuple([int(t)for t in input().split()])

    s = [[int(i) for i in list(input())] for _ in range(h)]
    
    cusum = [accumelist(s_) for s_ in s]

    candidates = []

    for i in range(1<<(h-1)):
        subcu = divide(cusum,i)
        subs = divide(s,i)

        subcusum = []

        rowsum = []

        for sub_ in subcu:
            subcusum.append(functools.reduce((lambda a,b:list(map(add,a,b))),sub_))

        for sub_ in subs:
            rowsum.append(functools.reduce((lambda a,b:list(map(add,a,b))),sub_))


        cutnum = 0

        temp = [0]*len(subcusum)

        for j in range(w):
            for l in range(len(subcusum)):
                if subcusum[l][j]-temp[l]>k:
                    if rowsum[l][j]>k:
                        cutnum+=10000
                    temp = [x[j-1] for x in subcusum]
                    cutnum+=1
                    break
        
        candidates.append(cutnum+bin(i).count('1'))

    print(min(candidates))
            
def divide(s,i):
    subs = []
    counter = 0
    pos = 0
    while i!= 0:
        counter +=1
        if i%2==1:
            subs.append(s[pos:counter])
            pos = counter
        i >>=1
 
    subs.append(s[pos:])
    return subs

def accumelist(s):
    if s == []:
        return []
    res = [s[0]]
    for i in range(1,len(s)):
        res.append(res[i-1]+s[i])

    return res

def _add_(a,b):
    return map(add,a,b)
    
if __name__ == "__main__":
    main()

Solution (Python):
H, W, K = map(int, input().split())
s = []
INF = (H - 1) + (W - 1)
ans = INF

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

for _ in range(H):
    s.append(list(input()))

for div in range(1 << (H - 1)):
    g = 0
    id = [0] * H
    for i in range(H):
        id[i] = g
        if div >> i & 1:
            g += 1
    g += 1
    
    now = [0] * g
    num = g - 1
    c = [[0 for _ in range(W)] for _ in range(H)]

    for i in range(H):
        for j in range(W):
            c[id[i]][j] += int(s[i][j])

    for j in range(W):
        if not add(j):
            num += 1
            now = [0] * g

            if not add(j):
                num = INF
                break

    ans = min(ans, num)
    
print(ans)

Solution (Python):
def e_dividing_chocolate():
    
    H, W, K = [int(i) for i in input().split()]
    Choco = [list(input()) for _ in range(H)]

    
    
    cumsum = [[0] * W for _ in range(H)]
    for row in range(H):
        for col in range(W):
            if Choco[row][col] == '1':
                cumsum[row][col] += 1
            if row != 0:
                cumsum[row][col] += cumsum[row - 1][col]
            if col != 0:
                cumsum[row][col] += cumsum[row][col - 1]
            if row != 0 and col != 0:
                cumsum[row][col] -= cumsum[row - 1][col - 1]

    def count_white_chocolate(x1, y1, x2, y2):
        """左上のマスを (x1, y1)、右下のマスを (x2, y2) としたとき、2 点で張られる
        長方形区間の内部に含まれる 1 (ホワイトチョコレートのマス) の数"""
        ret = cumsum[y2][x2]
        if x1 != 0:
            ret -= cumsum[y2][x1 - 1]
        if y1 != 0:
            ret -= cumsum[y1 - 1][x2]
        if x1 != 0 and y1 != 0:
            ret += cumsum[y1 - 1][x1 - 1]
        return ret

    ans = (H - 1) + (W - 1)  
    
    for bits in range(1 << (H - 1)):
        count = 0  

        
        cut_row = []
        cut_flag = format(bits, 'b')[::-1]
        for k, flag in enumerate(cut_flag):
            if flag == '1':
                count += 1
                
                cut_row.append(k)
        cut_row.append(H - 1)  

        
        col1 = 0
        for col2 in range(W - 1):
            row1 = 0
            for row2 in cut_row:
                if count_white_chocolate(col1, row1, col2, row2) > K:
                    count = float('inf')  

                
                if (count_white_chocolate(col1, row1, col2, row2) <= K
                        and count_white_chocolate(col1, row1, col2 + 1, row2) > K):
                    
                    count += 1
                    col1 = col2 + 1
                    break
                row1 = row2 + 1  

        
        row1 = 0
        for row2 in cut_row:
            if count_white_chocolate(col1, row1, W - 1, row2) > K:
                count = float('inf')
            row1 = row2 + 1

        ans = min(ans, count)
    return ans

print(e_dividing_chocolate())

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]==1:
      lst.append(S[h+1])
    else:
      lst[-1]=[lst[-1][i]+S[h+1][i] for i in range(W)]
  L=len(lst)
  R=[0]*L
  for w in range(W):
    if max(lst[i][w] for i in range(L))>K:
      break
    tmp=[R[i]+lst[i][w] for i in range(L)]
    if max(tmp)>K:
      cnt+=1
      R=[lst[i][w] for i in range(L)]
    else:
      R=tmp
  else:
    ans=min(ans,cnt)
print(ans)

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

c = [[0 for _ in range(w+1)] for _ in range(h+1)]

for i in range(1, h+1):
    temp = 0
    for j, x in enumerate(s[i]):
        temp += x
        c[i][j] = c[i-1][j] + temp

inf = float('inf')
ans = inf
mb = 1 << (h-1)
for i in range(1 << (h-1)):
    b = list(map(int, list(reversed(bin(mb + i)[2:]))))
    temp = sum(b) - 1
    L = 0
    
    for R in range(1, w+1):
        U = 0
        for D in range(1, h+1):
            if b[D-1] == 1:
                if c[D][R] - c[U][R] - c[D][L] + c[U][L] > k:
                    
                    if R - L == 1:
                        temp = inf
                    else:
                        temp += 1
                    L = R - 1
                    break
                U = D
        
        if temp == inf:
            break
    ans = min(ans, temp)

print(ans)

Solution (Python):
import itertools
h, w, k = [int(i) for i in input().split()]
choco = ([input() for j in range(h)])
ans = float("inf")

for i in itertools.product([0,1], repeat=h-1):
    list_yoko = []
    list_temp = []
    list_temp.append(0)
    for j in range(h-1):
        if i[j] == 1:
            list_yoko.append(list_temp)
            list_temp = []
            list_temp.append(j+1)
        else:
            list_temp.append(j+1)
    else:
        list_yoko.append(list_temp)


    count = 0
    count_list = [0 for _ in range(len(list_yoko))]

    for j in range(w):
        count_list_ = [0 for _ in range(len(list_yoko))]

        for m in range(len(list_yoko)):
            for l in list_yoko[m]:
                count_list_[m] += int(choco[l][j])

        if max(count_list) > k :
            count = float("inf")

        else:
            if max([count_list[_] + count_list_[_] for _ in range(len(list_yoko))]) > k:
                count += 1
                count_list = count_list_[:]

            else:
                count_list = [count_list[_] + count_list_[_] for _ in range(len(list_yoko))]

    ans = min(count+sum(i), ans)

print(ans)

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

H, W, K = map(int, input().split())
S = [list(map(int, input().rstrip())) for _ in range(H)]
cum = [list(accumulate(S[i])) for i in range(H)]
ans = float('inf')
for bit in range(1 << (H-1)):
    cnt = 0
    prev = -1
    for h in range(H-1):
        cnt += (bit >> h) & 1
    bit += 1 << (H-1)
    w = 0
    while w < W:
        s = 0
        cut = False
        for h in range(H):
            s += cum[h][w] - (cum[h][prev] if prev >= 0 else 0)
            if bit >> h & 1:
                if s > K:
                    cut = True
                    break
                s = 0
        if cut:
            if w-1 == prev:
                break
            cnt += 1
            prev = w-1
        else:
            w += 1
    else:
        ans = min(ans, cnt)
print(ans)

Solution (Python):
h,w,k =map(int,input().split())
ma = []
for i in range(h):
    ma.append(list(map(int,list(input()))))
ans = [0]*2**(h-1)
for i in range(2**(h-1)):
    idx = [0]*h 
    group = 0
    for j in range(h):
        idx[j] = group
        if (i>>j & 1):
            group +=1
    ans[i] += idx[-1]
    n = idx[-1]+1
    cnt = [0]*n 
    div_w = 0 
    for e in range(w):
        temp = [0]*n 
        for j in range(h):
            p = idx[j]
            cnt[p] += ma[j][e]
            temp[p] += ma[j][e]
        if max(cnt) >k:
            div_w +=1
            cnt = temp
        if max(temp) >k:
            div_w = 10**9
            break
    ans[i] += div_w
print(min(ans))

Solution (Python):
import sys
 
MAX_INT = int(10e15)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

H,W,K = IL()
a = [list(S()) for i in range(H)]

rui = [[0]*(W+1) for i in range(H)]
for i in range(H):
  for j in range(W):
    rui[i][j+1] = rui[i][j] + int(a[i][j])


ans = MAX_INT
for x in range(1<<(H-1)):
  l = 0
  num = 0
  for h in range(H-1):
    if (x >> h) & 1 == 1: 
      num += 1

  for w in range(W):
    
    judge = int(a[0][w])
    for h in range(H-1):
      if (x >> h) & 1 == 0: 
        judge += int(a[h+1][w])
      else: 
        judge = 0
        judge += int(a[h+1][w])
      if judge > K: 
        break
    else:
      continue
    break
  else:
    cnt = 0
    for w in range(W):
      
      cnt = rui[0][w+1] - rui[0][l]
      if cnt > K:
        num += 1
        l = w
        
        continue

      for h in range(H-1):
        
        if (x >> h) & 1 == 0: 
          cnt += rui[h+1][w+1] - rui[h+1][l]
        else: 
          cnt = rui[h+1][w+1] - rui[h+1][l]
        

        if cnt > K:
          num += 1
          l = w
          
          break
      
    else:
      ans = min(ans, num)
      

print(ans)

Solution (Python):
import sys
 
MAX_INT = int(10e15)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

H,W,K = IL()
a = [list(S()) for i in range(H)]

nnn = 0
for i in range(H):
  for j in range(W):
    nnn += int(a[i][j])
else:
  if nnn <= K:
    print(0)
    exit()

rui = [[0]*(W+1) for i in range(H)]
for i in range(H):
  for j in range(W):
    rui[i][j+1] = rui[i][j] + int(a[i][j])

ans = MAX_INT
for x in range(1<<(H-1)):
  l = 0
  num = 0
  for h in range(H-1):
    if (x >> h) & 1 == 1: 
      num += 1

  for w in range(W):
    
    judge = int(a[0][w])
    for h in range(H-1):
      if (x >> h) & 1 == 0: 
        judge += int(a[h+1][w])
      else: 
        judge = 0
        judge += int(a[h+1][w])
      if judge > K: 
        break
    else:
      continue
    break
  else:
    cnt = 0
    for w in range(W):
      

      cnt = rui[0][w+1] - rui[0][l]
      if cnt > K:
        num += 1
        l = w
        
        continue
      for h in range(H-1):
        
        if (x >> h) & 1 == 0: 
          cnt += rui[h+1][w+1] - rui[h+1][l]
        else: 
          cnt = rui[h+1][w+1] - rui[h+1][l]
        

        if cnt > K:
          num += 1
          l = w
          
          break
      
    else:
      ans = min(ans, num)
      
print(ans)

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

h, w, K = [int(x) for x in input().split()]
s = [input().rstrip() for _ in range(h)]

ans = h + w - 2
for i in range(2 ** (h - 1)):
    new_s = []
    cnt = 0
    i_bin = bin(i)[2:].zfill(h - 1)
    add = []
    for j in range(h - 1):
        if i_bin[j] == "1":
            cnt += 1
            add.append(s[j])
            new_s.append(add)
            add = []
        else:
            add.append(s[j])
        if j == h - 2:
            add.append(s[-1])
            new_s.append(add)
    if h == 1:
        new_s = [s]
    total = [0] * len(new_s) 
    for k in range(w):
        tmp_list = [0]*len(new_s) 
        flag = 0
        for l in range(len(new_s)):
            tmp = sum([int(new_s[l][x][k]) for x in range(len(new_s[l]))])
            if tmp > K:
                flag = 1
                break
            tmp_list[l] = tmp
            total[l] += tmp
        if flag:
            break
        for m in total: 
            if m > K:
                cnt += 1
                total = tmp_list
                break
    if not flag:
        ans = min(ans, cnt)
print(ans)

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

h, w, K = [int(x) for x in input().split()]
s = [input().rstrip() for _ in range(h)]




ans = h + w - 2
for i in range(2 ** (h - 1)):
    new_s = []
    cnt = 0
    i_bin = bin(i)[2:].zfill(h - 1)
    add = []
    for j in range(h - 1):
        if i_bin[j] == "1":
            cnt += 1
            add.append(s[j])
            new_s.append(add)
            add = []
        else:
            add.append(s[j])
        if j == h - 2:
            add.append(s[-1])
            new_s.append(add)
    if h == 1:
        new_s = [s]
    
    total = [0] * len(new_s)
    
    for k in range(w):
        
        tmp_list = [0]*len(new_s)
        
        flag = 0
        for l in range(len(new_s)):
            tmp = sum([int(new_s[l][x][k]) for x in range(len(new_s[l]))])
            
            
            if tmp > K:
                cnt = 10**18
                flag = 1
                break
            tmp_list[l] = tmp
            total[l] += tmp
        if flag:
            break
        for m in total:
            flag_2 = 1
            if m > K:
                cnt += 1
                total = tmp_list
                flag_2 = 0
                break
        
        
        
        
        
        
    if not flag:
        
        ans = min(ans, cnt)
print(ans)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
import numpy as np
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
	H, W, K = MAP()
	S = np.array([list(map(int, list(input()))) for _ in range(H)])

	ans = INF
	for x in product([0, 1], repeat=H-1):
		cut = np.sum(x)
		if cut >= ans:
				continue
		r = 0
		l = []
		for i in range(H-1):
			if x[i]:
				l.append(np.sum(S[r:i+1, :], axis=0))
				r = i + 1
		l.append(np.sum(S[r:, :], axis=0))
		l = np.array(l)
		if np.max(l) > K:
			continue
		tmp = np.zeros(len(l), dtype=int)
		for i in range(W):
			tmp += l[:, i]
			if np.max(tmp) > K:
				cut += 1
				tmp = l[:, i]
			if cut >= ans:
				break

		ans = ans if ans <= cut else cut

	print(ans)

if __name__ == '__main__':
	main()

Solution (Python):
from operator import add
import sys
sys.setrecursionlimit(10 ** 7)

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






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


INF = 10 ** 5
ans = INF
for h in range(2 ** (H - 1)):
    
    row = 1
    for i in range(H - 1):
        row += (h >> i) & 1

    num_cut = row - 1
    cnt = [0] * row

    

    
    for c in range(W):
        idx = 0
        tmp_cnt = [0] * row
        for r in range(H):

            if r != 0 and (h >> r - 1) & 1:
                idx += 1

            tmp_cnt[idx] += MEIJI[r][c]

        
        new_cnt = list(map(add, cnt, tmp_cnt))

        if any([K < x for x in new_cnt]):
            
            if any([K < x for x in tmp_cnt]):
                num_cut = INF
                break

            cnt = tmp_cnt
            num_cut += 1
        else:
            cnt = new_cnt

        

    ans = min(num_cut, ans)

print(ans)