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
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

H, W, K = lr()
S = np.array([list(map(int, sr())) for _ in range(H)])
Scum = np.cumsum(S, axis=1)
INF = 10 ** 10
answer = INF
for pattern in range(1<<H-1):
    cnt = 0
    Tcum = Scum.copy()
    for i in range(H-1):
        if pattern>>i & 1:  
            cnt += 1
        else:
            Tcum[i+1] += Tcum[i]
    prev = -1
    w = 0
    Tcum = Tcum.tolist()
    while w < W:
        cut = False
        for i in range(H):
            if Tcum[i][w] - (Tcum[i][prev] if prev >= 0 else 0) > K:
                cut = True
                break
        if cut:
            if prev == w - 1:  
                break
            cnt += 1
            prev = w - 1
        else:
            w += 1
    else:
        answer = min(answer, cnt)

print(answer)

Solution (Python):
H,W,K=map(int,input().split())
S=[list(map(int,list(input()))) for i in range(H)]
ans=H+W-2
for bit in range(2**(H-1)):
    divH=[0]
    for j in range(H-1):
        if(bit>>j&1):
            divH.append(j+1)
    divH.append(H)
    glen=len(divH)-1
    group=[0]*(glen)
    res=glen-1
    go=True
    for w in range(W):
        ok=True
        c=[0]*(glen)
        for g in range(glen):
            cum=0
            for h in range(divH[g],divH[g+1]):
                cum+=S[h][w]
            c[g]+=cum
            if cum>K:
                go=False
            if cum+group[g]>K:
                ok=False
        if not go:
            break
        if not ok:
            res+=1
            group=[c[i] for i in range(glen)]
        else:
            for i in range(glen):
                group[i]+=c[i]
    if not go:
        continue
    ans=min(ans,res)
print(ans)

Solution (Python):
H,W,K=map(int,input().split())
S=[list(map(int,list(input()))) for i in range(H)]
ans=H+W-2
for bit in range(2**(H-1)):
    divH=[0]
    for j in range(H-1):
        if(bit>>j&1):
            divH.append(j+1)
    divH.append(H)
    glen=len(divH)-1
    group=[0]*(glen)
    res=glen-1
    go=True
    w=0
    while w<W:
        ok=True
        c=[0]*(glen)
        for g in range(glen):
            cum=0
            for h in range(divH[g],divH[g+1]):
                cum+=S[h][w]
            c[g]+=cum
            if cum>K:
                go=False
                break
            if c[g]+group[g]>K:
                ok=False
        if not go:
            break
        if not ok:
            res+=1
            group=[0]*glen
        else:
            for i in range(glen):
                group[i]+=c[i]
            w+=1
    if not go:
        continue
    ans=min(ans,res)
print(ans)

Solution (Python):

import sys
from itertools import accumulate

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

H, W, K = lr()
S = [list(map(int, sr())) for _ in range(H)]
Scum = [list(accumulate(row)) for row in S]

INF = 10 ** 10
answer = INF
for pattern in range(1<<(H-1)):
    slice = set()
    cnt = 0
    for i in range(H-1):
        if pattern>>i & 1:
            slice.add(i)
            cnt += 1
    slice.add(H-1)  
    w = 0
    prev = -1
    while w < W:
        cut = False
        white = 0
        for i in range(H):
            white += Scum[i][w] - (Scum[i][prev] if prev >= 0 else 0)
            if i in slice:
                if white > K:
                    cut = True
                    break
                white = 0
        if cut:
            if prev == w - 1:  
                break
            cnt += 1
            prev = w-1
        else:
            w += 1
    else:
        answer = min(answer, cnt)

print(answer)

Solution (Python):
h,w,K = map(int, input().split())
g = [[0]*w for _ in range(h)]
for i in range(h):
    s=input()
    for j in range(w):
        g[i][j] = s[j]
ans=1001001001
for i in range(1<<(h-1)):
    seg = [0]*h
    segnow = 0
    for j in range(h-1):
        if i & 1 << j:
            segnow += 1
        seg[j+1] = segnow

    segnow += 1
    flag = True
    div = 0
    cnt = [0 for _ in range(segnow)]
    for j in range(w):
        now = [0]*segnow
        for k in range(h):
            if g[k][j] == '1':
                cnt[seg[k]] += 1
                now[seg[k]] += 1
                if cnt[seg[k]] > K:
                    div+=1
                    for l in range(segnow):
                        cnt[l] = now[l]
        if max(now)>K:
            continue
    ans = min(ans,segnow-1+div)
print(ans)

Solution (Python):
if __name__ == "__main__":
    h, w, k = map(int, input().split())
    s = []

    for _ in range(h):
        si = input()
        s.append(si)
    
    h_split = [0] * (h - 1)
    part = 0
    ans = float('inf')
    for mask in range(1 << (h - 1)):
        g = 0
        g_id = [0] * h
        for i in range(h):
            g_id[i] = g
            if mask >> i & 1 == 1:
                g += 1
        g += 1

        c = []
        for _ in range(g):
            c.append([0] * w)
        
        for i in range(h):
            for j in range(w):
                if s[i][j] == "1":
                    c[g_id[i]][j] += 1
        num = g - 1
        now = [0] * g

        for j in range(w):
            for i in range(g):
                now[i] += c[i][j]
            ok = True
            for i in range(g):
                if now[i] > k:
                    ok = False

            if not ok:
                num += 1
                now = [0] * g
                for i in range(g):
                    now[i] += c[i][j]
                ok = True
                for i in range(g):
                    if now[i] > k:
                        ok = False
                if not ok:
                    num = float('inf')
                    break
        ans = min(ans, num)
    print(ans)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def s(): return input()

def cuts(H):
    for i in range(1<<H):
        yield bin(i)[2:].zfill(H)

def main():
    H, W, K = LI()
    S = []
    for _ in range(H):
        S.append(s())
    ans = inf
    for cut in cuts(H-1):
        p = sum([1 for x in cut if x == '1'])
        cnt = p
        lines = [[0 for _ in range(W)] for __ in range(p+1)]
        cumr = 0
        for c in range(W):
            n_line = 0
            for r in range(H):
                if S[r][c] == '1':
                    cumr += 1
                if r >= H-1:
                    continue
                if cut[r] == '1':
                    lines[n_line][c] += cumr
                    n_line += 1
                    cumr = 0
            lines[-1][c] = cumr
            cumr = 0

        ng = False
        cumsum = [[0 for _ in range(W+1)] for __ in range(p+1)]

        for i in range(p+1):
            line = lines[i]
            for j in range(W):
                cumsum[i][j+1] = line[j] + cumsum[i][j]

        before = 0
        for j in range(1, W+1):
            
            
            for i in range(p+1):
                if ng:
                    break
                if cumsum[i][j] - cumsum[i][before] > K:
                    if j - before == 1:
                        ng = True
                    cnt += 1
                    before = j - 1
                    break
        if ng:
            continue
        ans = min(ans, cnt)
    print(ans)
main()

Solution (Python):



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

accum_col = [[0 for _ in range(W)] for _ in range(H)]

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

def cnt_white(x, a, b):
    if a == 0:
        return accum_col[b-1][x]
    else:
        return accum_col[b-1][x] - accum_col[a-1][x]

ans = H*W
for bit in range(1 << (H-1)):
    
    horizs = [0]
    cnt_split = bin(bit).count("1")
    for i in range(H-1):
        if bit & (1 << i):
            """
            i=0でbitに1が立っていると、y=0と1の間を横一直線に割るので、次のブロックの始まりはy=1から。
            みたいな意味でi+1
            """
            horizs.append(i+1)
    
    horizs.append(H)
    
    
    prev = [0] * (len(horizs) - 1)
    for x in range(W):
        
        curr_col = [cnt_white(x, a, b) for a,b in zip(horizs, horizs[1:])]
        
        prev_curr = [curr_col[i] + prev[i] for i in range(len(horizs)-1)]
        if max(curr_col) > K:
            
            cnt_split += H*W
            break
        if max(prev_curr) > K:
            
            prev = curr_col
            cnt_split += 1
        else:
            
            prev = prev_curr
    
    ans = min(ans, cnt_split)

print(ans)

Solution (Python):

from bisect import bisect_left

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

"""
H <= 10までなので、横直線方向の割り方を全探索できそう
縦直線方向の割り方は貪欲か。
横直線の割方が決まったら、次は縦に割っていくが、ブロックの横幅を1にしても、ブロックないのホワイトチョコがKを超える場合もありうるので、その場合は、その横直線の割り方で条件を満たすことはできない


H=1や W=1の場合は普通に貪欲で。
"""


def is_over_K(lst, block_num):
    res = False
    for i in range(block_num):
        if lst[i] > K:
            res = True
            break
    return res


if H != 1 and W != 1:
    
    ans = (H-1) + (W-1)
    for bit in range(1 << (H-1)):
        can_split_h = True
        cnt_split_h = bin(bit).count("1")
        cnt_split_w = 0

        
        if cnt_split_h >= 1:
            idx_split_h = []
            for i in range(H-1):
                if bit & (1 << i):
                    idx_split_h.append(i)

        cnt_blocks = cnt_split_h + 1
        cnt_whites = [0] * (cnt_blocks)
        ex_cnt_whites = [0] * (cnt_blocks)

        for x in range(W):
            for y in range(H):
                if S[y][x] == "1":
                    if cnt_blocks > 1:
                        block_num = bisect_left(idx_split_h, y)
                    else:
                        block_num = 0

                    cnt_whites[block_num] += 1
            
            
            is_over = is_over_K(cnt_whites, cnt_blocks)

            
            if not is_over:
                
                
                for i in range(cnt_split_h+1):
                    ex_cnt_whites[i] = cnt_whites[i]
            else:
                
                cnt_split_w += 1
                
                for i in range(cnt_blocks):
                    cnt_whites[i] -= ex_cnt_whites[i]
                    ex_cnt_whites[i] = cnt_whites[i]

                
                if is_over_K(cnt_whites, cnt_blocks):
                    can_split_h = False
                    break
            
            if not can_split_h:
                break
        
        if can_split_h:
            ans = min(ans, cnt_split_h + cnt_split_w)


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

print(ans)

Solution (Python):
h, w, k = map(int, input().split())
s = [[int(i) for i in input()] for _ in range(h)]
ans = (h-1)+(w-1)
for i in range(2**(h-1)):
    d = [(i >> j) & 1 for j in range(h-1)]
    count, count_tmp = [0]*(sum(d)+1), [0]*(sum(d)+1)
    ans_, res = 0, 0
    flag = False
    for w_ in range(w):
        count[0] += s[0][w_]
        count_tmp[0] += s[0][w_]
        res += 1
        tmp = 0
        for h_ in range(1, h):
            if d[h_-1]: tmp += 1
            if s[h_][w_]:
                count[tmp] += 1
                count_tmp[tmp] += 1
        for j in count:
            if j > k:
                if res==1:
                    flag = True
                    break
                else:
                    for idx in range(sum(d)+1):
                        count[idx] = count_tmp[idx]
                    ans_ += 1
                    res = 1
                    break
        if flag: break
        count_tmp = [0]*(sum(d)+1)
    if flag: continue
    ans_ += sum(d)
    ans = min(ans, ans_)
print(ans)

Solution (Python):
def z(z_dic, v: int):
    if v in z_dic:
        return z_dic[v]
    z = 0
    if v == 2:
        z = 1
    elif v > 2:
        z = int(v*(v-1)/2)
    z_dic.setdefault(v, z)
    return z


def main():
    h, w, _k = map(int, input().split())
    s = []
    for i in range(h):
        line = input()
        s_line = []
        for j in range(w):
            s_line.append(int(line[j]))
        s.append(s_line)

    ok_cnt_min = h*w
    op_cnt = h - 1  
    for i in range(2 ** op_cnt):
        op = [False] * op_cnt
        for j in range(op_cnt):
            if ((i >> j) & 1):
                op[op_cnt - 1 - j] = True

        s2 =[]
        current_sum = s[0]
        for k in range(op_cnt):
            if op[k]:
                s2.append(current_sum)
                current_sum = s[k+1]
            else:
                next_sum = [(current_sum[a] + s[k+1][a]) for a in range(w)]
                current_sum = next_sum

        s2.append(current_sum)
        s2len = len(s2)

        h_cut_cnt = len([x for x in op if x])
        if h_cut_cnt >= ok_cnt_min:
            break

        st = 0
        ed = 1
        cut_list = []
        dividable = True
        for j in range(1, w+1):
            _sum_max = 0
            if ed <= j:
                ed = j
            else:
                continue

            _sum_max = max([sum(s2[_h][st:ed]) for _h in range(s2len)])
            if _sum_max > _k:
                if ed - st > 1:
                    cut_list.append(ed - 1)
                    st = ed - 1
                else:
                    dividable = False
                    break
        if not dividable:
            continue
        else:
            cnt = h_cut_cnt
            cnt += len(cut_list)
            if cnt < ok_cnt_min:
                ok_cnt_min = cnt

    print(ok_cnt_min)



main()

Solution (Python):






import sys
input = sys.stdin.readline

import math
from collections import deque
from fractions import gcd
from functools import lru_cache






MOD = 10**9+7
INF = float('inf')






def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr


def lcm(a, b):
    return a * b // gcd (a, b)





H,W,K = inputIL()
C = inputSLs(H)


best = INF
for h in range(pow(2,H-1)):
  nC = []
  nC.append([int(i) for i in C[0]])
  for i in range(1,H):
    if h>>(i-1) & 1:
      for j in range(W):
        nC[-1][j] += int(C[i][j])
    else:
      nC.append([int(j) for j in C[i]])
  n = len(nC)
  if max(max(nC[i]) for i in range(n)) > K:
    continue
  count = [0 for j in range(n)]
  cut = 0
  while len(nC[0]):
    now = [nC[j].pop() for j in range(n)]
    if max(count[j]+now[j] for j in range(n)) > K:
      count = now
      cut += 1
    else:
      count = [count[j]+now[j] for j in range(n)]
  
  yoko = H-1
  while h:
    h &= h -1
    yoko -= 1
  best = min(best,cut+yoko)

print(best)

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

ans = float('inf')
for hb in range(2**(H-1)):
    hl = []
    for i in range(H-1):
        if hb & (1 << i) > 0:
            hl.append(i+1)
    t = len(hl)
    hl = [0]+hl+[H]

    w, pw = 0, 0
    wl = [0]*len(hl)
    while w < W:
        ok = True
        for i in range(len(hl)-1):
            sh, eh = hl[i], hl[i+1]
            for h in range(sh, eh):
                wl[i] += m[h][w]
                if wl[i] > K:
                    ok = False
                    break
            if not ok:
                break

        if not ok:
            if pw == w:
                t = float('inf')
                break
            pw, w = w, w
            t += 1
            wl = [0]*len(hl)
        else:
            w += 1

    ans = min(t, ans)

print(ans)

Solution (Python):
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter

from functools import lru_cache

sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp():
    '''
    一つの整数
    '''
    return int(input())
def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))

h, w, k = inpl()
s = [input()[:-1] for _ in range(h)]
ans = 10 ** 4
for t in itertools.product([0, 1], repeat=h-1):
    cnt = t.count(1)
    tmp = s[0]
    SW = []  
    tmp = [int(s) for s in s[0]] 
    for i, c in enumerate(t):
        if c: 
            SW.append(tmp) 
            tmp = [int(s) for s in s[i + 1]] 
        else:
            tmp = [tmp[j] + int(s[i + 1][j]) for j in range(w)]
    SW.append(tmp)
    new_h = len(SW)  
    sums = [0] * new_h
    if max(itertools.chain.from_iterable(SW)) > k:
        
        
        continue
    for j in range(w):
        sumtmp = [sums[i] + SW[i][j] for i in range(new_h)]
        if max(sumtmp) > k:
            
            cnt += 1
            sums = [SW[i][j] for i in range(new_h)]  
        else:
            sums = sumtmp
    ans=min(ans,cnt)
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF = 1 << 60
MOD = 10**9 + 7 
input = lambda:sys.stdin.readline().rstrip()
from collections import Counter
def resolve():
    m, n, k = map(int, input().split())
    grid = [list(map(int, input())) for _ in range(m)]
    
    
    
    res = INF
    def adding(j):
        for i in range(m):
            counter[index_to_number[i]] += grid[i][j]

    for U in range(1 << (m - 1)):
        counter = Counter()
        index_to_number = [None] * m
        now = 0
        for i in range(m):
            index_to_number[i] = now
            now += (U >> i) & 1
        score = bin(U).count('1')
        
        for j in range(n):
            
            adding(j)
            if max(counter.values()) > k:
                score += 1
                counter.clear()
                adding(j) 
                if max(counter.values()) > k: 
                    break
        else: 
            res = min(res, score)

    print(res)
resolve()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF = 1 << 60
MOD = 10**9 + 7 
input = lambda:sys.stdin.readline().rstrip()
from collections import Counter
def resolve():
    m, n, k = map(int, input().split())
    grid = [list(map(int, input())) for _ in range(m)]
    
    
    res = INF

    counter = Counter()
    index_to_number = [None] * m
    def adding(j):
        for i in range(m):
            counter[index_to_number[i]] += grid[i][j]

    for U in range(1 << (m - 1)):
        counter.clear()
        index_to_number = [None] * m
        now = 0
        for i in range(m):
            index_to_number[i] = now
            now += (U >> i) & 1
        score = bin(U).count('1')
        
        for j in range(n):
            
            adding(j)
            if max(counter.values()) > k:
                score += 1
                counter.clear()
                adding(j) 
                if max(counter.values()) > k: 
                    break

        else: 
            res = min(res, score)
    print(res)
resolve()

Solution (Python):
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]
def S(): return sys.stdin.readline().rstrip()
def LS(): return sys.stdin.readline().split()
def LS2(N): return [sys.stdin.readline().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)

MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**6+10)
input = sys.stdin.readline


ans = INF
H,W,K = MI()
s = LSI2(H)
for pattern in product([0,1],repeat=H-1):
    cut = 0
    before_idx = 0
    row_list = []
    for i,div in enumerate(pattern):
        if div==1:
            cut += 1
            square = s[before_idx:i+1]
            inv = list(zip(*square))
            row = [sum(inv[i]) for i in range(W)]
            row_list.append(row)
            before_idx = i+1
    square = s[before_idx:] 
    inv = list(zip(*square))
    row_list.append([sum(inv[i]) for i in range(W)])
    if any([any([c>K for c in r]) for r in row_list]):
        continue
    cnt = [0]*len(row_list)
    tmp = [0]*len(row_list)
    for i in range(W):
        for j in range(len(row_list)):
            cnt[j] += row_list[j][i]
            tmp[j] = row_list[j][i]
        if any([c>K for c in cnt]):
            cut += 1
            cnt = tmp[:]
    ans = min(ans,cut)
print(ans)

Solution (Python):
import copy
import itertools

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


s = []
min = 100000
for i in range(h):
    s.append( [int(s) for s in list(input())])
    

dbg_cnt = 0
l = list(range(h-1))
for i in range(h):
    p = list(itertools.combinations(l, i))
    for j in p:
        tmp = list(j)
        tmps = []
        q = 0
        tmps.append([])
        
        
        for r in range(h):
            tmps[q].append(copy.copy(s[r]))
            if(q < len(tmp) and r==tmp[q]):
                tmps.append([])
                q += 1
        
        count = i
        sums = [0] * len(tmps)
        precut = 1
        exitflg = 0
        for r in range(w): 
            for q in range(len(tmps)):
                for t in tmps[q]:
                    sums[q] += t[r] 
            cutflg = 0
            for q in range(len(tmps)):
                if sums[q] > k : 
                    cutflg = 1
            if cutflg == 1:
                
                count += 1
                sums = [0] * len(tmps)
                for q in range(len(tmps)):
                    for t in tmps[q]:
                        sums[q] += t[r] 
            for q in range(len(tmps)): 
                if sums[q] > k :
                    exitflg = 1
                    
        
        if exitflg == 0:
            if min > count:
                min = count
print(min)

Solution (Python):
f=range
h,w,k=map(int,input().split())
g=[[int(i) for i in input()] for _ in f(h)]
s=[[0]*-~w for _ in f(h+1)]
for i in f(h):
  for j in f(w):
    s[i+1][j+1]=s[i+1][j]+s[i][j+1]+g[i][j]-s[i][j]
a=h+w
for i in f(2**~-h):
  u=d=l=r=c=0
  e=[]
  for d in f(h):
    if i>>d&1: e+=[(u,d+1)]; c+=1; u=d+1
  e+=[(u,h)]
  for r in f(w):
    if max(s[d][r+1]-s[u][r+1]-s[d][l]+s[u][l] for u,d in e)>k:
      if r==l: break
      c+=1; l=r
  else: a=min(a,c)
print(a)

Solution (Python):
f=range
h,w,k=map(int,input().split())
g=[[int(i) for i in input()] for _ in f(h)]
s=[[0]*-~w for _ in f(h+1)]
for i in f(h):
  for j in f(w):
    s[i+1][j+1]=s[i+1][j]+s[i][j+1]+g[i][j]-s[i][j]
a=h+w
for i in f(2**~-h):
  u=d=l=r=c=0
  e=[]
  for d in f(h):
    if i>>d&1: e+=[(u,d+1)]; c+=1; u=d+1
  e+=[(u,h)]
  for r in f(w):
    if max(s[d][r+1]-s[u][r+1]-s[d][l]+s[u][l] for u,d in e)>k:
      if r==l: break
      c+=1; l=r
  else: a=min(a,c)
print(a)

Solution (Python):
f=range
h,w,k=map(int,input().split())
g=[[int(i) for i in input()] for _ in f(h)]
s=[[0]*-~w for _ in f(h+1)]
for i in f(h):
  for j in f(w):
    s[i+1][j+1]=s[i+1][j]+s[i][j+1]+g[i][j]-s[i][j]
a=h+w
for i in f(2**~-h):
  u=d=l=r=c=0
  e=[]
  while d<h:
    d+=1
    if i>>d-1&1: e+=[(u,d)]; c+=1; u=d
  e+=[(u,h)]
  while r<w:
    if max(s[d][r+1]-s[u][r+1]-s[d][l]+s[u][l] for u,d in e)>k:
      if r==l: break
      c+=1; l=r
    r+=1
  else: a=min(a,c)
print(a)

Solution (Python):
f=range
h,w,k=map(int,input().split())
g=[[int(i) for i in input()] for _ in f(h)]
s=[[0]*-~w for _ in f(h+1)]
for i in f(h):
  for j in f(w):
    s[i+1][j+1]=s[i+1][j]+s[i][j+1]+g[i][j]-s[i][j]
a=h+w
for i in f(2**~-h):
  u=d=l=r=c=0
  e=[]
  while d<h:
    d+=1
    if i>>d-1&1: e+=[(u,d)]; c+=1; u=d
  e+=[(u,h)]
  while r<w:
    if max(s[d][r+1]-s[u][r+1]-s[d][l]+s[u][l] for u,d in e)>k:
      if r==l: break
      c+=1; l=r
    r+=1
  else: a=min(a,c)
print(a)

Solution (Python):
h,w,k=map(int,input().split())
g=[[int(c) for c in input()] for _ in range(h)]
s=[[0]*(w+1) for _ in range(h+1)]
for i in range(h):
  for j in range(w):
    s[i+1][j+1]=s[i+1][j]+s[i][j+1]+g[i][j]-s[i][j]
ssum=lambda u,d,l,r:s[d][r]-s[u][r]-s[d][l]+s[u][l]
a=h+w
for i in range(2**(h-1)):
  e=[]
  u=d=ch=0
  for j in range(h):
    d+=1
    if i>>j&1<1:
      e+=[(u,d)]
      if d<h:
        ch+=1
        u=d
  l=r=cw=0
  while r<w:
    if max(ssum(u,d,l,r+1) for u,d in e)>k:
      if r==l: break
      cw+=1
      l=r
    r+=1
  else:
    a=min(a,ch+cw)
print(a)

Solution (Python):
h,w,k=map(int,input().split())
g=[[int(c) for c in input()] for _ in range(h)]
s=[[0]*(w+1) for _ in range(h+1)]
for i in range(h):
  for j in range(w):
    s[i+1][j+1]=s[i+1][j]+s[i][j+1]+g[i][j]-s[i][j]
ssum=lambda u,d,l,r:s[d][r]-s[u][r]-s[d][l]+s[u][l]
a=h+w
for i in range(2**(h-1)):
  e=[]
  u=d=ch=0
  for j in range(h):
    d+=1
    if i>>j&1<1:
      e+=[(u,d)]
      if d<h:
        ch+=1
        u=d
  l=r=cw=0
  while r<w:
    if max(ssum(u,d,l,r+1) for u,d in e)>k:
      if r==l: break
      cw+=1
      l=r
    r+=1
  else:
    a=min(a,ch+cw)
print(a)

Solution (Python):


import sys
import math
import collections
import itertools
import bisect
INF = 10 ** 13
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def lcm(x, y) : return (x * y) // math.gcd(x, y)
def I() : return int(input())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def LS() : return input().split()
def RS(N) : return [input() for _ in range(N)]
def LRS(N) : return [input().split() for _ in range(N)]
def PL(L) : print(*L, sep="\n")
def YesNo(B) : print("Yes" if B else "No")
def YESNO(B) : print("YES" if B else "NO")

def check(j):
    global cur

    for i in range(g):
        cur[i] += c[i][j]

    flag = True
    for curr in cur:
        if curr > K:
            flag = False

    return flag

H, W, K = LI()
S = RS(H)

ans = INF
N = H-1
for bit in range(1 << N):
    g = 0
    id = [0] * H

    for i in range(H):
        id[i] = g
        if (bit >> i) & 1:
            g += 1

    g += 1    
            
    c = [[0] * W for _ in range(g)]
    for i in range(H):
        for j in range(W):
            c[id[i]][j] += int(S[i][j])

    num = g-1
    cur = [0] * g
    for i in range(W):
        if not check(i):
            num += 1
            cur = [0] * g

            if not check(i):
                num = INF
                break
    
    ans = min(ans, num)

print(ans)