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 bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from collections import deque
H, W, K = MI()
S_ = [[] for _ in range(W)]
for i in range(H):
    s = S()
    for j in range(len(s)):
        S_[j].append(int(s[j]))



A = []
for i in range(2 ** (H - 1)):
    A_bit = []
    for j in range(H - 1):
        
        if ((i >> j) & 1):
            A_bit.append(j)
    A.append(A_bit)


Ans_list = []
for a in A:
    sums = [0] * (len(a) + 1)
    ele = [0] * (len(a) + 1)
    ans = 0
    for s_ in S_:
        queue = deque(a)
        if queue == deque([]):
            ele[0] = sum(s_)
            if ele[0] > K:
                ans = 10 ** 6
                break
            sums[0] += sum(s_)
        else:
            x = queue.popleft()
            ele[0] = sum(s_[0:x + 1])
            if ele[0] > K:
                ans = 10 ** 6
                break
            sums[0] += sum(s_[0:x + 1])
            j = 1
            while queue != deque([]):
                y = queue.popleft()
                ele[j] = sum(s_[x + 1:y + 1])
                if ele[j] > K:
                    ans = 10 ** 6
                    break
                sums[j] += sum(s_[x + 1:y + 1])
                x = y
                j += 1
            ele[len(a)] = sum(s_[x + 1:H])
            if ele[len(a)] > K:
                ans = 10 ** 6
                break
            sums[len(a)] += sum(s_[x + 1:H])
        if max(sums) > K:
            ans += 1
            for k in range(len(a) + 1):
                sums[k] = ele[k]
    ans += len(a)
    Ans_list.append(ans)

print(min(Ans_list))

Solution (Python):
h, w, k = map(int, input().split())
S = [list(map(int, list(input()))) for _ in range(h)]
ans = float("inf")
for i in range(2**(h-1)):
  L = [0]
  cnt = 0
  for j in range(h-1):
    if i>>j & 1:
      L.append(j+1)
      cnt += 1
  L.append(h)
  C = [0]*(len(L)-1)
  for j in range(w):
    D = [0]*(len(L)-1)
    for l in range(len(L)-1):
      a, b = L[l], L[l+1]
      for s in range(a, b):
        D[l] += S[s][j]
    if max(D) > k:
      break
    for l, d in enumerate(D):
      if C[l]+d > k:
        break
    else:
      for l, d in enumerate(D):
        C[l] += d
      continue
    cnt += 1
    for l, d in enumerate(D):
      C[l] = d
  else:
    ans = min(ans, cnt)
print(ans)

Solution (Python):
h,w,k = map(int,input().split())
s = [list(map(int, input())) for i in range(h)]
ans = h+w-2
for i in range(2**(h-1)):
    index = [0] * h
    rowcuts = 0
    for j in range(h-1):
        if 1 & (i >> j) == 1:
            rowcuts += 1
        index[j + 1] = rowcuts
    chocos = [0] * (rowcuts + 1)
    coulmncuts = 0
    valid = True
    for j in range(w):
        for l in range(h):
            chocos[index[l]] += s[l][j]
        if max(chocos) > k:
            coulmncuts += 1
            chocos = [0] * (rowcuts + 1)
            for l in range(h):
                chocos[index[l]] += s[l][j]
            if max(chocos) > k:
                valid = False
        if not valid:
            break
    if valid:
        ans = min(ans, rowcuts + coulmncuts)

print(ans)

Solution (Python):
h, w, k = map(int, input().split())
s = [input() for _ in range(h)]
ans = float("inf")
for bit in range(1 << (h - 1)):
    cnt = 0
    l = [0] * h
    for i in range(h - 1):
        if bit & (1 << i):
            cnt += 1
        l[i + 1] = cnt
    m = max(l) + 1
    cnt2 = m - 1
    c = [0] * m
    for j in range(w):
        cur = [0] * m
        for i in range(h):
            c[l[i]] += int(s[i][j])
            cur[l[i]] += int(s[i][j])
            if c[l[i]] > k:
                cnt2 += 1
                for i in range(m):
                    c[i] = cur[i]
    ans = min(ans, cnt2)
print(ans)

Solution (Python):
H,W,K=map(int,input().split())
s=[[int(x) for x in list(input())] for _ in range(H)]
ans = H*W
for h in range(2**(H-1)):
  parts = list()
  upper = 0
  cnt = 0
  inv_flg = 0
  for j in range(H-1):
    if h >> j & 1:
      cnt += 1
      appending = [sum([s[y][x] for y in range(upper, j+1)]) for x in range(W)]
      if any([x> K for x in appending]):
        inv_flg = 1
        break
      parts.append(appending)
      upper = j+1
  else:
    appending = [sum([s[y][x] for y in range(upper, H)]) for x in range(W)]
    if any([x > K for x in appending]):
      inv_flg = 1
    else:
      parts.append(appending)
  if inv_flg:
    continue
  
  summary = [0]*len(parts)
  for i in range(W):
    temp_sum = [summary[j] + parts[j][i] for j in range(len(parts))]
    for ts in temp_sum:
      if ts > K:
        cnt += 1
        summary = [parts[j][i] for j in range(len(parts))]
        break
    else:
      summary = temp_sum
  ans = min(ans, cnt)
print(ans)

Solution (Python):
from itertools import accumulate
h,w,k=map(int,input().split())
s=[[0]*(w+1)]+[[0]+[int(i) for i in input()] for _ in range(h)]
for i in range(h+1):
  s[i]=list(accumulate(s[i]))
for j in range(w+1):
  for i in range(h):
    s[i+1][j]+=s[i][j]
ans=10**18
for i in range(1<<h-1):
  a=[]
  for j in range(h-1):
    if (i>>j)&1:a+=[j+1]
  a+=[h]
  cnt=len(a)-1
  q=1
  for j in range(1,w+1):
    p=0
    flag=0
    for l in a:
      if s[l][j]-s[l][j-1]-s[p][j]+s[p][j-1]>k:flag=1
      elif s[l][j]-s[l][q-1]-s[p][j]+s[p][q-1]>k:
        q=j
        cnt+=1
        break
      else:p=l
    if flag:break
  else:
    ans=min(cnt,ans)
print(ans)

Solution (Python):
import sys
from io import StringIO
import unittest
import os


sys.setrecursionlimit(999999999)



def resolve(test_def_name=""):
    h, w, k = map(int, input().split())
    s_s = [list(input()) for i in range(h)]

    
    
    side = []
    for i in range(1 << h - 1):
        cut_cnt = 0
        point_s = []
        
        for j in range(h - 1):
            
            if i & 1 << j:
                cut_cnt += 1
                point_s.append(j + 1)

        point_s.append(h)
        
        side.append([point_s, cut_cnt])

    
    x_s_s = list(zip(*s_s))
    ans = 999999
    for side_cut_point_s, cut_cnt in side:
        
        cnt_s = [0 for i in range(cut_cnt + 1)]

        for x_s in x_s_s:
            start = 0
            for cnt, side_cut_point in enumerate(side_cut_point_s):
                cnt_s[cnt] += x_s[start: side_cut_point].count("1")
                start = side_cut_point
            
            if max(cnt_s) > k:
                cut_cnt += 1
                start = 0
                for cnt, side_cut_point in enumerate(side_cut_point_s):
                    cnt_s[cnt] = x_s[start: side_cut_point].count("1")
                    start = side_cut_point
            if max(cnt_s) > k:
                cut_cnt += 99999
        ans = min(ans, cut_cnt)

    print(ans)



class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """3 5 4
11100
10001
00111"""
        output = """2"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """3 5 8
11100
10001
00111"""
        output = """0"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """4 10 4
1110010010
1000101110
0011101001
1101000111"""
        output = """3"""
        self.assertIO(test_input, output)

    
    def test_1original_1(self):
        test_input = """10 10 1
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000"""
        output = """9"""
        self.assertIO(test_input, output)



if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        
        resolve()

    else:
        
        unittest.main()

Solution (Python):
from itertools import groupby, accumulate, product, permutations, combinations
def solve():
    H, W, K = map(int, input().split())
    S = [input() for _ in range(H)]
    cum = [[0]*(W+1) for _ in range(H+1)]
    for i in range(1,H+1):
        for j in range(1,W+1):
            cum[i][j]=cum[i-1][j]+cum[i][j-1]-cum[i-1][j-1]+int(S[i-1][j-1])
    ans = 2000
    for p in product([0,1],repeat=H-1):
        line = [0]
        p = list(p)
        cnt = sum(p)
        for i in range(1,H):
            if p[i-1]==1:
                line.append(i)
        line.append(H)
        w_s = 0
        w_e = 1
        b = False
        while w_e <= W:
            for i in range(len(line)-1):
                h_s = line[i]
                h_e = line[i+1]
                white = cum[h_e][w_e]+cum[h_s][w_s]-cum[h_e][w_s]-cum[h_s][w_e]
                if white > K:
                    if w_e == w_s+1:
                        b = True
                        break
                    else:
                        w_s = w_e-1
                        cnt += 1
                        break
            if b==True:
                break
            w_e += 1
        else:
            ans = min(ans,cnt)
    return ans
print(solve())

Solution (Python):
from itertools import product


def makelist(BIT):
    LIST, tmp = [], s[0]
    for si, bi in zip(s[1:], BIT):
        if bi == 1:
            LIST.append(tmp)
            tmp = si[:]
        elif bi == 0:
            tmp = [t + sij for t, sij in zip(tmp, si)]
    else:
        LIST.append(tmp)
    return LIST


def solve(LIST):
    COST, cnt = 0, [li[0] for li in LIST]
    if any(num > k for num in cnt):
        return h * w
    for j in range(1, w):
        tmp = [t + li[j] for t, li in zip(cnt, LIST)]
        if any(num > k for num in tmp):
            COST += 1
            cnt = [li[j] for li in LIST]
        else:
            cnt = tmp[:]
    return COST


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

ans = h * w
for bit in product([0, 1], repeat=(h - 1)):
    numlist = makelist(bit)
    ans = min(ans, solve(numlist) + sum(bit))
print(ans)

Solution (Python):
from itertools import product


def makelist(BIT):
    LIST, tmp = [], s[0]
    for si, bi in zip(s[1:], BIT):
        if bi == 1:
            LIST.append(tmp)
            tmp = si
        elif bi == 0:
            tmp = [t + sij for t, sij in zip(tmp, si)]
    else:
        LIST.append(tmp)
    return LIST


def solve(LIST):
    COST, cnt = 0, [li[0] for li in LIST]
    if any(num > k for num in cnt):
        return h * w
    for j in range(1, w):
        tmp = [t + li[j] for t, li in zip(cnt, LIST)]
        if any(num > k for num in tmp):
            COST += 1
            cnt = [li[j] for li in LIST]
        else:
            cnt = tmp[:]
    return COST


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

ans = h * w
for bit in product([0, 1], repeat=(h - 1)):
    numlist = makelist(bit)
    ans = min(ans, solve(numlist) + sum(bit))
print(ans)

Solution (Python):
from itertools import product


def makelist(BIT):
    LIST, tmp = [], s[0]
    for si, bi in zip(s[1:], BIT):
        if bi == 1:
            LIST.append(tmp)
            tmp = si
        elif bi == 0:
            tmp = [t + sij for t, sij in zip(tmp, si)]
    else:
        LIST.append(tmp)
    return LIST


def solve(LIST):
    COST, cnt = 0, [li[0] for li in LIST]
    if any(num > k for num in cnt):
        return h * w
    for j in range(1, w):
        tmp = [t + li[j] for t, li in zip(cnt, LIST)]
        if any(num > k for num in tmp):
            COST += 1
            cnt = [li[j] for li in LIST]
        else:
            cnt = tmp[:]
    return COST


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

ans = h * w
for bit in product([0, 1], repeat=(h - 1)):
    numlist = makelist(bit)
    ans = min(ans, solve(numlist) + sum(bit))
print(ans)

Solution (Python):
from itertools import product


def makelist(BIT):
    LIST, tmp = [], s[0]
    for si, bi in zip(s[1:], BIT):
        if bi == 1:
            LIST.append(tmp)
            tmp = si
        elif bi == 0:
            tmp = [t + sij for t, sij in zip(tmp, si)]
    else:
        LIST.append(tmp)
    return LIST


def solve(LIST):
    CNT, tmp = 0, [li[0] for li in LIST]
    if any(num > k for num in tmp):
        return h * w
    for j in range(1, w):
        cal = [t + li[j] for t, li in zip(tmp, LIST)]
        if any(num > k for num in cal):
            CNT += 1
            tmp = [li[j] for li in LIST]
        else:
            tmp = cal[:]
    return CNT


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

ans = h * w
for bit in product([0, 1], repeat=(h - 1)):
    numlist = makelist(bit)
    ans = min(ans, solve(numlist) + sum(bit))
print(ans)

Solution (Python):
from itertools import product


def makelist(BIT):
    LIST, tmp = [], s[0]
    for i, bi in enumerate(BIT, 1):
        if bi == 1:
            LIST.append(tmp)
            tmp = s[i]
        elif bi == 0:
            tmp = [t + sij for t, sij in zip(tmp, s[i])]
    else:
        LIST.append(tmp)
    return LIST


def solve(LIST):
    CNT, tmp = 0, [li[0] for li in LIST]
    if any(num > k for num in tmp):
        return h * w
    for j in range(1, w):
        cal = [t + li[j] for t, li in zip(tmp, LIST)]
        if any(num > k for num in cal):
            CNT += 1
            tmp = [li[j] for li in LIST]
        else:
            tmp = cal
    return CNT


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

ans = h * w
for bit in product([0, 1], repeat=(h - 1)):
    numlist = makelist(bit)
    ans = min(ans, solve(numlist) + sum(bit))
print(ans)

Solution (Python):
from itertools import product


def makelist(BIT):
    LIST, tmp = [], s[0]
    for i, bi in enumerate(BIT, 1):
        if bi == 1:
            LIST.append(tmp)
            tmp = s[i]
        elif bi == 0:
            tmp = [p + q for p, q in zip(tmp, s[i])]
    else:
        LIST.append(tmp)
    return LIST


def solve(LIST):
    CNT, tmp = 0, [l[0] for l in LIST]
    if any(num > k for num in tmp):
        return h * w
    for i in range(1, w):
        cal = [tmp[j] + LIST[j][i] for j in range(len(LIST))]
        if any(num > k for num in cal):
            CNT += 1
            tmp = [l[i] for l in LIST]
        else:
            tmp = cal
    return CNT


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

ans = h * w
for bit in product([0, 1], repeat=(h - 1)):
    numlist = makelist(bit)
    ans = min(ans, solve(numlist) + sum(bit))
print(ans)

Solution (Python):
def numba_compile(numba_config):
    import os, sys
    if sys.argv[-1] == "ONLINE_JUDGE":
        from numba import njit
        from numba.pycc import CC
        cc = CC("my_module")
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature)(func)
            cc.export(func.__name__, signature)(func)
        cc.compile()
        exit()
    elif os.name == "posix":
        exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
        for func, _ in numba_config:
            globals()[func.__name__] = vars()[func.__name__]
    else:
        from numba import njit
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature, cache=True)(func)
        print("compiled!", file=sys.stderr)

import numpy as np

def solve(H, W, K, S):
    ans = 1<<60
    for s in range(1<<H-1):
        an = 0
        f = True
        mapping = np.zeros(H, dtype=np.int64)
        for i in range(H-1):
            if s>>i&1:
                an += 1
                mapping[i+1] = mapping[i]+1
            else:
                mapping[i+1] = mapping[i]
        if an >= ans:
            continue
        Cnt = np.zeros(mapping[-1]+1, dtype=np.int64)
        for x in range(W):
            for y in range(H):
                m = mapping[y]
                c = S[y, x]
                Cnt[m] += c
            if (Cnt > K).any():
                Cnt[:] = 0
                an += 1
                if an >= ans:
                    f = False
                    break
                for y in range(H):
                    m = mapping[y]
                    c = S[y, x]
                    Cnt[m] += c
                if (Cnt > K).any():
                    f = False
                    break
            if not f:
                break
        if f:
            ans = an
    return ans

numba_compile([
    [solve, "i8(i8,i8,i8,i8[:,:])"],
])

def main():
    H, W, K = map(int, input().split())
    S = np.empty((H, W), dtype=np.int64)
    for y in range(H):
        S[y] = np.array(list(input()), dtype=np.int64)
    ans = solve(H, W, K, S)
    print(ans)

main()

Solution (Python):
h,w,kk=list(map(int,input().split()))
s=[list(map(int,list(input()))) for i in range(h)]
l=[]
for i in range(2**(h-1)):
  ll=[0]
  for j in range(h-1):
    if i & 2**j:
      ll.append(ll[-1]+1)
    else:
      ll.append(ll[-1])
  l.append(ll)

mc=w+h
for i in l:
  c=[0 for i in range(h)]
  cc=0
  f=1
  
  for j in range(w):
    
    ff=0
    for k in range(h):
      c[i[k]]+=s[k][j]
    for k in range(h):
      if c[k]>kk:
        ff=1
        break
    if ff:
      cc+=1
      c=[0 for i in range(h)]
      for k in range(h):
        c[i[k]]+=s[k][j]
      for k in range(h):
        if c[k]>kk:
          f=1
      if f:
        cc=w+h
        
        break
    f=0
  
  if mc>cc+len(set(i))-1:
    mc=cc+len(set(i))-1
print(mc)

Solution (Python):

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

    S=[]
    for i in range(H):
        col=list(map(int,list(input())))
        S.append(col)
    CumulativeS=[[S[i][0]] for i in range(H)]
    for i in range(len(S)):
        for j in range(1,len(S[i])):
            CumulativeS[i].append(CumulativeS[i][j-1]+S[i][j])
    for i in range(1,len(S)):
        for j in range(len(S[i])):
            CumulativeS[i][j]+=CumulativeS[i-1][j]
    all_bit=1<<H-1
    res=10000
    for bit in range(all_bit):
        wide_bound=[]
        for i in range(H-1):
            if (bit & (1<<i))!=0:
                wide_bound.append(i)
        res_=len(wide_bound)
        high_bound=[]
        high_flag=0
        for i in range(W):
            if len(high_bound)==0:
                for b in range(len(wide_bound)):
                    if b==0:
                        white_chocolate=CumulativeS[wide_bound[b]][i]
                    else:
                        white_chocolate=CumulativeS[wide_bound[b]][i]-CumulativeS[wide_bound[b-1]][i]

                    if white_chocolate>K:
                        if i-1<0:
                            high_flag=1
                            break
                        high_bound.append(i-1)
                        break
                    if b==len(wide_bound)-1:
                        white_chocolate=CumulativeS[H-1][i]-CumulativeS[wide_bound[b]][i]
                        if white_chocolate > K:
                            if i-1<0:
                                high_flag=1
                                break
                            high_bound.append(i - 1)


                if high_flag==1:
                    break

                if len(wide_bound)==0:
                    white_chocolate = CumulativeS[H - 1][i]
                    if white_chocolate>K:
                        if i-1<0:
                            high_flag=1
                            break
                        high_bound.append(i-1)

            else:
                for b in range(len(wide_bound)):
                    if b == 0:
                        white_chocolate = CumulativeS[wide_bound[b]][i]-CumulativeS[wide_bound[b]][high_bound[len(high_bound)-1]]
                    else:
                        white_chocolate = CumulativeS[wide_bound[b]][i] - CumulativeS[wide_bound[b - 1]][i]-CumulativeS[wide_bound[b]][high_bound[len(high_bound)-1]]+CumulativeS[wide_bound[b-1]][high_bound[len(high_bound)-1]]
                    if white_chocolate>K:
                        if i-1<0:
                            high_flag=1
                            break
                        high_bound.append(i-1)
                        break
                    if b == len(wide_bound) - 1:
                        white_chocolate = CumulativeS[H - 1][i] - CumulativeS[wide_bound[b]][i]-CumulativeS[H-1][high_bound[len(high_bound)-1]]+CumulativeS[wide_bound[b]][high_bound[len(high_bound)-1]]
                        if white_chocolate>K:
                            if i-1<0:
                                high_flag=1
                                break
                            high_bound.append(i-1)

                if high_flag==1:
                    break

                if len(wide_bound)==0:
                    white_chocolate = CumulativeS[H - 1][W - 1]-CumulativeS[H-1][high_bound[len(high_bound)-1]]
                    if white_chocolate>K:
                        if i-1<0:
                            high_flag=1
                            break

                        high_bound.append(i-1)
        res_+=len(high_bound)

        if res_<res and high_flag==0:
            res=res_

    print(res)

if __name__=="__main__":
    main()

Solution (Python):
import numpy as np
import itertools
H, W, K = [int(_) for _ in input().split()]
S = np.zeros((H + 1, W + 1), dtype=int)
S[1:, 1:] = [[int(_) for _ in input()] for _ in range(H)]
cum = S.cumsum(axis=0).cumsum(axis=1)


ans = 10**10
for bs in itertools.product([True, False], repeat=H - 1):
    bs = [True] + list(bs) + [True]

    idxs = []
    for i, b in enumerate(bs):
        if b:
            idxs += [i]
    cum2 = np.array([cum[i2] - cum[i1] for i1, i2 in zip(idxs, idxs[1:])])
    i = 0
    cnt = sum(bs) - 3
    while i < W:
        di = min(
            np.searchsorted(c[i + 1:] - c[i], K, side='right') for c in cum2)
        if di == 0:
            cnt = 10**10
            break
        i += di
        cnt += 1
    ans = min(ans, cnt)
print(ans)

Solution (Python):

import sys
input = lambda: sys.stdin.readline().strip()
h, w, k = [int(x) for x in input().split()]
s = [input() for _ in range(h)]

def add_pieces(pieces, column, ranges):
    global s
    for j in range(len(ranges)):
        L, R = ranges[j]
        pieces[j] += sum(1 for row in range(L, R) if s[row][column] == '1')

def get_ranges(mask):
    global h
    L = 0
    for i in range(h - 1):
        if mask & (1 << i):
            yield L, i + 1
            L = i + 1
    yield L, h

def cost(mask):
    global h, w, k
    ranges = list(get_ranges(mask))
    pieces = [0 for i in range(len(ranges))]
    ans = bin(mask).count('1')
    for column in range(w):
        add_pieces(pieces, column, ranges)
        if any(piece > k for piece in pieces):
            ans += 1
            pieces = [0 for i in range(len(ranges))]
            add_pieces(pieces, column, ranges)
            if any(piece > k for piece in pieces):
                return float('inf')
    return ans

print(min(cost(mask) for mask in range(1 << (h - 1))))

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

choco = [list(map(int, list(input()) )) for i in range(h)]

ans = h + w + 1

for h_cut in range(2**(h-1)):
    
    num_cut_yoko = bin(h_cut).count("1") 
    num_cut = num_cut_yoko
    w_last_cut_pos = -1
    valid = True

    count_white = [0] * (num_cut_yoko + 1)
    temp_dict = {}
    idx = 0
    temp_dict[0] = idx
    for i in range(1, h):
        
        if h_cut & (2 ** (-i+h-1) ):
            idx += 1
        
        temp_dict[i] = idx
    

    iw = 0
    while iw < w:

        for ih in range(h):
            count_white[temp_dict[ih]] += choco[ih][iw]
        

        condition = max(count_white) > k
        if condition:
            if w_last_cut_pos < iw-1:
                
                num_cut += 1
                w_last_cut_pos = iw - 1
                count_white = [0] * (num_cut_yoko + 1)
                

            else:
                
                
                valid = False
                break
        
        else:
            iw += 1
    
    if valid:
        ans = min(ans, num_cut)
    

print(ans)

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

choco = [list(map(int, list(input()) )) for i in range(h)]

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

for i in range(h):
    choco_cumsum[i][0] = choco[i][0]
    for j in range(1, w):
        choco_cumsum[i][j] = choco_cumsum[i][j-1] + choco[i][j]

ans = h + w + 1

for h_cut in range(2**(h-1)):
    
    num_cut_init = bin(h_cut).count("1") 
    num_cut = num_cut_init
    w_last_cot_pos = -1
    valid = True

    temp_list = [0] * (num_cut_init + 1)
    temp_dict = {}
    idx = 0
    temp_dict[0] = idx
    for i in range(1, h):
        
        if h_cut & (2 ** (-i+h-1) ):
            idx += 1
        
        temp_dict[i] = idx
    

    iw = 0
    while iw < w:

        for ih in range(h):
            temp_list[temp_dict[ih]] += choco[ih][iw]
        

        condition = max(temp_list) > k
        if condition:
            if w_last_cot_pos < iw-1:
                
                num_cut += 1
                w_last_cot_pos = iw - 1
                temp_list = [0] * (num_cut_init + 1)
                

            else:
                
                valid = False
                break
        
        else:
            iw += 1
    
    if valid:
        ans = min(ans, num_cut)
    

print(ans)

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

choco = [list(map(int, list(input()))) for i in range(h)]

ans = h + w + 1

for h_cut in range(2**(h-1)):
    
    num_cut_yoko = bin(h_cut).count("1") 
    num_cut = num_cut_yoko
    w_last_cut_pos = -1
    valid = True

    count_white = [0] * (num_cut_yoko + 1)
    temp_dict = {}
    idx = 0
    temp_dict[0] = idx
    for i in range(1, h):
        
        if h_cut & (2 ** (-i+h-1)):
            idx += 1
        
        temp_dict[i] = idx
    

    iw = 0
    while iw < w:

        for ih in range(h):
            count_white[temp_dict[ih]] += choco[ih][iw]
        

        condition = max(count_white) > k
        if condition:
            if w_last_cut_pos < iw-1:
                
                num_cut += 1
                w_last_cut_pos = iw - 1
                count_white = [0] * (num_cut_yoko + 1)
                

            else:
                
                valid = False
                break
        
        else:
            iw += 1
    
    if valid:
        ans = min(ans, num_cut)
    

print(ans)

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

choco = [list(map(int, list(input()))) for i in range(h)]

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

for i in range(h):
    choco_cumsum[i][0] = choco[i][0]
    for j in range(1, w):
        choco_cumsum[i][j] = choco_cumsum[i][j-1] + choco[i][j]

ans = h + w + 1

for h_cut in range(2**(h-1)):
    
    num_cut_init = bin(h_cut).count("1") 
    num_cut = num_cut_init
    w_last_cut_pos = -1
    valid = True

    count_white = [0] * (num_cut_init + 1)
    temp_dict = {}
    idx = 0
    temp_dict[0] = idx
    for i in range(1, h):
        
        if h_cut & (2 ** (-i+h-1) ):
            idx += 1
        
        temp_dict[i] = idx
    

    iw = 0
    while iw < w:

        for ih in range(h):
            count_white[temp_dict[ih]] += choco[ih][iw]
        

        condition = max(count_white) > k
        if condition:
            if w_last_cut_pos < iw-1:
                
                num_cut += 1
                w_last_cut_pos = iw - 1
                count_white = [0] * (num_cut_init + 1)
                

            else:
                
                valid = False
                break
        
        else:
            iw += 1
    
    if valid:
        ans = min(ans, num_cut)
    

print(ans)

Solution (Python):
from collections import deque

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

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

rlt = 1010

h = deque([[1]])

while h:
  t = h.pop()
  if len(t) == H:
    t.append(1)
    tmp = sum(t) - 2
    bs = tmp
    lst = [0]*H
    j = -1
    for i in range(len(t)-1):
      if t[i] == 1:
        j += 1
      lst[i] = j 
    cnt = [0]*(lst[-1]+1)
    for j in range(W):
      tcnt = [0]*(lst[-1]+1)
      f = 0
      for i in range(H):
        tcnt[lst[i]] += int(mp[i][j])
      for k in range(lst[-1]+1):
        if tcnt[k] > K:
          f = 2
          break
        cnt[k] += tcnt[k]
        if cnt[k] > K:
          f = 1
          break
      if f == 2:
        break
      if f == 1:
        tmp += 1
        for k in range(lst[-1]+1):
          cnt[k] = tcnt[k]
    if f < 2:
      rlt = min(rlt, tmp)
    
  else:
    for i in range(2):
      h.append(t+[i])

print(rlt)

Solution (Python):
import sys
import numpy as np
from itertools import combinations_with_replacement,product
def input(): return sys.stdin.readline().rstrip()

def culc(array,k,count):
    array=array.T
    cuts=np.zeros(array.shape[1])
    for i in range(array.shape[0]):
        if any(array[i]>k):
            return 10**6
        elif any(array[i]+cuts>k):
            cuts=array[i]
            count+=1
        else:
            cuts+=array[i]
    return count


def main():
    h,w,k=map(int, input().split())
    choco=np.zeros((h,w))
    for i in range(h):
        choco[i]=list(input())
    ans=10**6
    choco=choco.astype(np.int64)
    for bit in product([0,1],repeat=h-1):
        if sum(bit)>=ans:
            break
        chocos=choco.copy()
        cut=chocos[0].reshape([1,w])
        for i in range(h-1):
            if bit[i]==1:
                cut=np.concatenate([cut,chocos[i+1].reshape([1,w])])
            else:
                cut[-1]+=chocos[i+1]
        ans=min(ans,culc(cut,k,sum(bit)))
    print(ans)


if __name__=='__main__':
    main()