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(map(int, list(input()))) for _ in range(H)]

tab_h = [[0] * (W + 1) for _ in range(H)]
for i in range(H):
    cnt = 0
    for j in range(W):
        cnt += S[i][j]
        tab_h[i][j + 1] = cnt








ans = 1000000007
for case in range(2 ** (H - 1)):
    case_tmp = case
    iscut_v = []
    for i in range(H - 1):
        iscut_v.append(case_tmp % 2)
        case_tmp >>= 1
    
    parts = []
    vsrc = 0
    for vdst in range(1, H + 1):
        if vdst == H:
            parts.append((vsrc, vdst))
            break
        elif iscut_v[vdst - 1] == 1:
            parts.append((vsrc, vdst))
            vsrc = vdst
        else:
            continue
    
    possible = False
    hsrc = 0
    iscut_h = [0] * (W - 1)
    for hdst in range(1,  W + 1):
        num_1 = 0
        for vsrc, vdst in parts:
            num_1_tmp = 0
            for i in range(vsrc, vdst):
                num_1_tmp += tab_h[i][hdst] - tab_h[i][hsrc]
            num_1 = max(num_1, num_1_tmp)
            
        
        if num_1 > K:
            if hdst == 1 or hdst - 1 == hsrc:
                break
            else:
                iscut_h[hdst - 2] = 1
                hsrc = hdst - 1
        else:
            continue
    else:
        possible = True
    
    if possible:
        ans_tmp = sum(iscut_v) + sum(iscut_h)
        
        ans = min(ans, ans_tmp)

print(ans)

Solution (Python):
import copy
H,W,K = [int(i) for i in input().split()]
Chocolate = [[int(i) for i in list(input())]for j in range(H)]
YokoChoko = [[Choc[s] for Choc in Chocolate] for s in range(W)]
minlist = []
for warikata in range(2**(H-1)):
    
    
    wareta = [0]
    curw = 0
    for k in range(H-1):
        if (warikata>>k) & 1:
            curw += 1
        wareta.append(curw)
    
    nums = [0 for xx in range(curw + 1)]
    watta = curw
    for nbanme,NewChoco in enumerate(YokoChoko):
        newnums = copy.deepcopy(nums)
        for n,choconum in enumerate(NewChoco):
            newnums[wareta[n]] += choconum
        if max(newnums) <= K:
            nums = newnums
        else:
            if nbanme == 0:
                watta += 9999999999
            watta += 1
            nums = [0 for iii in range(curw + 1)]
            for n,choconum in enumerate(NewChoco):
                nums[wareta[n]] += choconum
    minlist.append(watta)
print(min(minlist))

Solution (Python):


def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    
    from itertools import combinations, permutations, accumulate
    
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    

    
    

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

        
    def csum_gen(h, w, table):
        d = [[0]*w for _ in range(h)]
        d[0][0] = table[0][0]
        for i in range(1, w):
            d[0][i] = d[0][i-1]+table[0][i]
        
        for i in range(1, h):
            total = 0
            for j in range(w):
                total += table[i][j]
                d[i][j] = d[i-1][j]+total
        return d
    
    d = csum_gen(H, W, table)

    
    def csum_cal(p, q, x, y, d):
        
        if p>x or q>y:
            return 0
        if p==0 and q==0:
            return d[x][y]
        if p==0:
            return d[x][y] - d[x][q-1]
        if q==0:
            return d[x][y] - d[p-1][y]
        return d[x][y]-d[p-1][y]-d[x][q-1]+d[p-1][q-1]

    res = 10**15
    for i in range(2**(H-1)):
        tate = [0]
        for j in range(H-1):
            if i & 2**j:
                tate.append(j+1)
        l = len(tate)
        tate.append(H)
        start = 0
        cnt = 0
        flag = 0
        for j in range(W-1):
            for k in range(l):
                if K < csum_cal(tate[k], start, tate[k+1]-1, j, d):
                    flag = 1
            for k in range(l):
                if K < csum_cal(tate[k], start, tate[k+1]-1, j+1, d):
                    cnt += 1
                    start = j+1
                    break
            if flag:
                break
        else:
            res = min(res, cnt+l-1)
    print(res)




if __name__ == '__main__':
    main()

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

p_ = [list(c) for c in s]

t = [[0]*h for _ in range(w)]
for i in range(h):
    for j in range(w):
        t[j][i] = int(p_[i][j])



ans = 10**7
for i in range(2**(h-1)):
    c = 0
    d = {}
    for j in range(h):
        d[j] = 0
    for j in range(h-1):
        if (i >> j) & 1:
            d[j] = c
            c += 1
        else:
            d[j] = c
    d[h-1] = c
    
    
    l = [0]*(c+1)
    cnt = c
    for a in range(w):
        temp = [0]*(c+1)
        for b in range(h):
            l[d[b]] += t[a][b]
            temp[d[b]] += t[a][b]
        if max(temp) > k:
            break
        if max(l) > k:
            cnt += 1
            l = temp
    else:
        ans = min(ans, cnt)
    continue

print(ans)

Solution (Python):
def check_block(comb, H):
    block = 0
    pre = (comb & 1) > 0
    mapping = {0: 0}
    cut_num = 0
    for i in range(1, H):
        cur = ((1 << i) & comb) > 0
        if pre != cur:
            block += 1
            pre = cur
            cut_num += 1
        mapping[i] = block
    return mapping, cut_num

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

ans = 1319203291031903
for comb in range(1<<(H-1)):
    mapping, cut_num = check_block(comb, H)
    pre = [0] * (cut_num + 1)
    gg = False
    
    for j in range(H):
        pre[mapping[j]] += (graph[j][0] == '1')
    for ele in pre:
        if ele > K:
            gg = True
            break
    if gg: continue

    for i in range(1, W):
        cum = pre[:]
        for j in range(H):
            cum[mapping[j]] += (graph[j][i] == '1')
        for ii in range(len(cum)):
            if cum[ii] - pre[ii] > K or cut_num > ans:
                gg = True
                break
            if cum[ii] > K:
                cut_num += 1
                for idx in range(len(cum)):
                    cum[idx] -= pre[idx]
                break
        pre = cum
        if gg: break

    if not gg:
        ans = min(ans, cut_num)
print(ans)

Solution (Python):
from itertools import combinations

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

separators = []
for i in range(2 ** (H - 1)):
    separators.append([(i >> j) & 1 for j in range(H - 1)])
separators.sort(key=sum)

for i in range(len(separators)):
    ids = [0]
    for j in separators[i]:
        ids.append(ids[-1] + j)
    separators[i] = ids

min_ = H - 1 + W - 1
for ids in separators:
    size = ids[-1] + 1
    nums = [0] * size
    num_cuts = size - 1
    if min_ <= num_cuts:
        continue
    for row in range(H):
        nums[ids[row]] += S[row][0]
    if any(K < n for n in nums):
        continue
    ignore = False
    for col in range(1, W):
        adds = [0] * size
        for row in range(H):
            adds[ids[row]] += S[row][col]
        if any(K < nums[i] + adds[i] for i in range(size)):
            if any(K < a for a in adds):
                ignore = True
                break
            num_cuts += 1
            if min_ <= num_cuts:
                ignore = True
                break
            for i in range(size):
                nums[i] = adds[i]
        else:
            for i in range(size):
                nums[i] += adds[i]
    if not ignore:
        min_ = min(num_cuts, min_)
print(min_)

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

CHOCO = [[] for _ in range(1<<(H-1))]
cnt = [10**9] * (1<<(H-1))

for i in range(1<<(H-1)):
    S = 0
    ret = []
    flag = True
    for j in range(H - 1):
        S += B[j][0]
        if i & (1<<j):
            if S > K:
                flag = False
            ret.append(S)
            S = 0
    S += B[-1][0]
    if S > K:
        flag = False
    ret.append(S)
    if flag:
        CHOCO[i] = ret[:]
        cnt[i] = len(ret) - 1


for w in range(1,W):
    for i in range(1 << (H - 1)):
        if not CHOCO[i]: continue

        S = 0
        ret = []
        flag1 = True
        for j in range(H - 1):
            S += B[j][w]
            if i & (1 << j):
                if S > K:
                    flag1 = False
                ret.append(S)
                S = 0
        S += B[-1][w]
        ret.append(S)

        flag2 = True

        for j in range(len(ret)):
            if ret[j] + CHOCO[i][j] > K:
                flag2 = False

        if flag1:
            if flag2:
                for j in range(len(ret)):
                    CHOCO[i][j] += ret[j]
            else:
                CHOCO[i] = ret[:]
                cnt[i] += 1
        else:
            CHOCO[i] = []

print(min(cnt))

Solution (Python):

import sys
input = sys.stdin.readline

h, w, K = map(int, input().split())
field = []
field_int = []
for _ in range(h):
    s = input().rstrip()
    line = [int(item) for item in s]
    field.append(line)

ans = 10**5
for i in range(2**(h-1)):
    group = [0]
    g = 0
    for j in range(h-1):
        if i & 1 << j: 
            g += 1
            group.append(g)
        else:
            group.append(g)
    line_num = bin(i).count("1") + 1
    cnt = [0] * line_num
    ret = 0
    ok = True
    for j in range(w):
        tmp = [0] * line_num
        for k in range(h):
            tmp[group[k]] += field[k][j]
        should_cut = False
        for c, t in zip(cnt, tmp):
            if t > K:
                ok = False
            if c + t > K:
                should_cut = True
        if not should_cut:
            for i, t in enumerate(tmp):
                cnt[i] += t
        else:
            ret += 1
            for i, t in enumerate(tmp):
                cnt[i] = t
    if not ok:
        continue
    ans = min(ans, ret + line_num - 1)
print(ans)

Solution (Python):
from sys import exit, setrecursionlimit
setrecursionlimit(10**6)

def array2D(row, col ,val=0):
    return [[val]*col for i in range(row)]

from itertools import product
import numpy as np

def c():
    INF = 10**9+1
    ans = INF
    for v in product(range(2), repeat=h-1):
        idx = 0
        K = []
        for i,j in enumerate(v):
            if j==1:
                K.append(S[idx:i+1, :].sum(axis=0).tolist())
                idx = i+1
        K.append(S[idx:, :].sum(axis=0).tolist())

        res = sum(list(v))
        s = [0]*(len(K))
        for i in range(w):
            f = False
            for j in range(len(K)):
                if s[j] + K[j][i] > k:
                    f = True
                    if K[j][i] > k:
                        res += INF
            if f:
                res += 1
                for j in range(len(K)):
                    s[j] = K[j][i]
            else:
                for j in range(len(K)):
                    s[j] += K[j][i]

        ans = min(res, ans)
    return ans




h,w,k = map(int, input().split())
S = []
for i in range(h):
    S.append(list(map(int, input())))

S = np.array(S)
print(c())

Solution (Python):
import sys
h, w, k = [int(i) for i in sys.stdin.readline().split()]
s_ls = {}
for i in range(h):
    s_ls[i] = [int(j) for j in sys.stdin.readline().strip()]

best = h - 1 + w - 1
for i in range(1 << (h - 1)):
    flg = True
    s = bin(i)[2:].zfill(h-1)
    ls = {i for i, j in enumerate(s) if j == "1"}
    dict = {i : 0 for i in range(len(ls) + 1)}
    cnt = 0
    for _w in range(w):
        j = 0
        col_sums = {i : 0 for i in range(len(ls) + 1)}
        for _h in range(h):
            val = s_ls[_h][_w]
            col_sums[j] += val
            dict[j] += val
            if _h in ls:
                j += 1
        if max(dict.values()) > k:
            cnt += 1
            dict = col_sums
        if max(col_sums.values()) > k:
            flg = False
        if not flg:
            break
    if flg:
        best = min(best , cnt + len(ls))
print(best)

Solution (Python):
h, w, k = map(int, input().split())
s = []
for i in range(h):
    temp = list(input())
    temp = list(map(int, temp))
    s.append(temp)
ans = 2000
for i in range(2 ** (h - 1)):
    line = 0
    temp = bin(i + 2 ** (h - 1))
    group = [[0]]
    for j in range(h - 1):
        if temp[-1-j] == "0":
            group[-1].append(j + 1)
        else:
            group.append([j + 1])
            line += 1
    count = [0] * len(group)
    for j in range(w):
        for l in range(len(group)):
            for m in group[l]:
                count[l] += s[m][j]
        flag = True
        for l in count:
            if l > k:
                flag = False
                break
        if flag == False:
            line += 1
            count = [0] * len(group)
            for l in range(len(group)):
                for m in group[l]:
                    count[l] += s[m][j]
    flag = True
    for j in count:
        if j > k:
            flag = False
            break
    if flag == False:
        line = 2000
    ans = min(ans, line)
print(ans)

Solution (Python):
import itertools

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

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

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

count=[]
for i in range(h):
  L=[0]
  for j in range(w):
    L.append(int(l[i][j])+L[-1])
  count.append(L)

b=[]
for i in range(2**(h-1)):
  b.append(format(i,'0'+str(h-1)+'b'))

ans=[]
cut=0
for i in range(len(b)):
  cutct=0
  cut=0
  f=0
  for j in range(1,w+1):
    ct=[]
    for j2 in range(h):
      ct.append(count[j2][j]-count[j2][cut])
    check=[]
    x=ct[0]
    for j3 in range(h-1):
      if b[i][j3]=='0':
        x+=ct[j3+1]
      else:
        check.append(x)
        x=ct[j3+1]
    check.append(x)
    if max(check)>k:
      if cut-j<=1:
        ctcheck=[]
        for j2 in range(h):
          ctcheck.append(count[j2][j-1]-count[j2][cut])
        check=[]
        x=ctcheck[0]
        for j3 in range(h-1):
          if b[i][j3]=='0':
            x+=ctcheck[j3+1]
          else:
            check.append(x)
            x=ctcheck[j3+1]
        check.append(x)
        if max(check)>k:
          f=1
      cut=j-1
      cutct+=1
  ct1=0
  for j4 in range(h-1):
    if b[i][j4]=='1':
      ct1+=1
  if f==0:
    ans.append(cutct+ct1)
print(min(ans))

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

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

min_v = 10**18
for i in range(2**(h-1)):
  cnt = [0]*h
  row = [0]*h
  splt_cnt = 0
  splt = [0]*(h-1)
  find = 1
  for j in range(h-1):
    if (i>>j)&1:
      splt[j] = 1
  
  for x in range(1, h):
    if splt[x-1]==0:
      row[x] = row[x-1]
    elif splt[x-1]==1:
      row[x] = row[x-1] + 1
  
  for c in range(w):
    for r in range(h):
      
      cnt[row[r]] += S[r][c]
    
    if max(cnt)>k:
      cnt = [0] * h
      splt_cnt += 1
      for r in range(h):
        cnt[row[r]] += S[r][c]
      if max(cnt)>k:
        find = 0
  
  splt_cnt += sum(splt)
  
  if splt_cnt<min_v and find:
    min_v = splt_cnt

print(min_v)

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

ans = 10**5
dame = False

for bit in range(1<<h-1):
    h_cut_count = 0
    Cut_line = []
    for i in range(9):
        if (bit>>i)&1 == 1:
            h_cut_count += 1
            Cut_line.append(i)
    

    before_line = -1
    Blocks = []

    for j in range(len(Cut_line)):
        if before_line == -1:
            Blocks.append(S[:Cut_line[j]+1])
            before_line = Cut_line[j]
        else:
            Blocks.append(S[before_line+1:Cut_line[j]+1])
            before_line = Cut_line[j]
    if before_line == -1:
        Blocks.append(S[:])
    else:
        Blocks.append(S[before_line+1:])
    
    Block_count = [0 for _ in range(len(Blocks))]

    v_cut_count = 0

    for i in range(w):
        for j in range(len(Blocks)):
            for column in Blocks[j]:
                if column[i] == 1:
                    Block_count[j] += 1
        if max(Block_count) > k:
            Block_count = [0 for _ in range(len(Blocks))]
            v_cut_count += 1
            for j in range(len(Blocks)):
                for column in Blocks[j]:
                    if column[i] == 1:
                        Block_count[j] += 1
            if max(Block_count) > k:
                dame = True

    if dame == False:
        cand = h_cut_count + v_cut_count
    elif dame == True:
        cand = 10**5
    ans = min(cand, ans)
    dame = False

    
    
    
    
    

print(ans)

Solution (Python):

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import itertools
H, W, K = map(int, readline().split())
S = [list(map(int, line.rstrip().decode())) for line in readlines()]

S = tuple(itertools.chain(*zip(*S)))

INF = 10 ** 9


def solve(s):
    dp = list(S)
    for j in range(H - 1):
        if s & (1 << j):
            for n in range(0, H * W, H):
                dp[n + j + 1] += dp[n + j]
    cut = H - 1 - bin(s).count('1')
    for n in range(0, H * W, H):
        if any(dp[n + i] > K for i in range(H)):
            return INF
        if n + H == H * W:
            return cut
        if any(dp[n + i] + dp[n + i + H] > K for i in range(H)):
            cut += 1
            continue
        for i in range(H):
            dp[n + i + H] += dp[n + i]
    return cut


answer = min(solve(s) for s in range(1 << (H - 1)))
print(answer)

Solution (Python):
h, w, K = map(int, input().split())
mapi = []
for i in range(h):
    mapi.append(list(map(int,list(input()))))

def judge(num):
    for i in range(2**(h-1)+1):
        jc = 0
        gr = []
        tmp = []
        for j in range(h-1):
            tmp.append(j)
            if (i >> j)&1 == 1:
                gr.append(tmp)
                tmp = []
                jc+=1
        tmp.append(h-1)
        gr.append(tmp)
        if jc > num:
            continue
        xc = 0
        tmpc = [0] * (jc+1)
        brf = False
        for j in range(w):
            di = [0]* (jc+1)
            for k in range(jc+1):
                for l in gr[k]:
                    di[k]+=mapi[l][j]
                    if di[k] > K:
                        brf = True
                        break
                if tmpc[k] + di[k] > K:
                    for m in range(jc+1):
                        tmpc[m] = 0
                    xc+=1
                    if xc + jc > num:
                        brf = True
                        break
                if brf:
                    break
            if brf:
                break
            for l in range(jc+1):
                tmpc[l] += di[l]
        if brf:
            continue
        return True
    return False

mmin = 0
mmax = (h-1)*(w-1)
if judge(mmin) == True:
    print(0)
    exit()
while True:
    mid = (mmin + mmax)//2
    if judge(mid) == True:
        mmax = mid
    else:
        mmin = mid
    if mmin +1 == mmax:
        print(mmax)
        exit()

Solution (Python):


def saiki(num,lis):
    if num==H:
        cand.append(lis)
    else:
        saiki(num+1,lis+[lis[-1]])
        saiki(num+1,lis+[num])

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

S=[]
for h in range(H):
    s=list(input())
    S.append(list(map(int,s)))
        
cand=[]

saiki(1,[0])

ans=[]
for item in cand:
    temp=len(list(set(item)))-1
    wa=[[0]*W for i in range(H)]
    for i in range(H):
        for j in range(W):
            wa[item[i]][j]+=S[i][j]
    
    sam=[0]*H
    count=0
    for w in range(W):
        judge=False
        for h in range(H):
            if wa[h][w]>K:
                judge=True
            sam[h]+=wa[h][w]
            if w!=W-1:
                if sam[h]+wa[h][w+1]>K:
                    count+=1
                    for i in range(H):
                        
                        sam[i]=0
                    break
        if judge:
            count=10**9
            break
    """
    print("------------------")
    print(item)
    print(sam)
    """
    ans.append(temp+count)
    
print(min(ans))

Solution (Python):
import itertools
inpl = lambda: list(map(int,input().split()))
H, W, K = inpl()
S = [input() for h in range(H)]
ans = H+W
for c in itertools.product(range(2),repeat=H-1):
    hcut = sum(c)
    if hcut >= ans:
        continue
    segment = [0]
    s = 0
    for h in range(H-1):
        if c[h]:
            s += 1
        segment.append(s)
    cur = hcut
    whites = [0] * (hcut+1)
    for w in range(W):
        thisline = [0]*(hcut+1)
        for h in range(H):
            if S[h][w] == '1':
                whites[segment[h]] += 1
                thisline[segment[h]] += 1
        m = max(whites)
        if m > K:
            whites = thisline
            m = max(whites)
            cur += 1
            if cur >= ans or m > K:
                break
    else:
        ans = cur
            
print(ans)

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

H, W, K = map(int, input().split())
S = [input() for i in range(H)]
Col = [[] for i in range(W)]
for j in range(W):
    for i in range(H):
        Col[j].append(S[i][j])
Ans = 10**9
for lst in itertools.product([0,1], repeat=H-1):
    ran = []
    ans = sum(lst)
    l = 0
    for i, x in enumerate(lst, 1):
        if x == 1:
            ran.append((l, i))
            l = i
    ran.append((l, H))
    cnt = [0] * len(ran)
    endflg = 0
    for j in range(W):
        flg = 0
        for i, (l, r) in enumerate(ran):
            c = Col[j][l:r].count('1')
            if c > K:
                ans = 10**9
                endflg = 1
                break
            if cnt[i] + c > K:
                flg = 1
                break
        if endflg:
            break
        if flg:
            ans += 1
            for i, (l, r) in enumerate(ran):
                cnt[i] = Col[j][l:r].count('1')
        else:
            for i, (l, r) in enumerate(ran):
                cnt[i] += Col[j][l:r].count('1')
    Ans = min(Ans, ans)
print(Ans)

Solution (Python):
import sys


def main():
    input = sys.stdin.readline

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

    cs = [[0] * (w + 1) for _ in range(h + 1)]
    for i in range(h):
        for j in range(w):
            cs[i +
               1][j +
                  1] = cs[i][j + 1] + cs[i + 1][j] - cs[i][j] + int(s[i][j])

    
    

    ans = h + w
    for bit in range(1 << (h - 1)):
        border = [0]
        cand = 0
        for i in range(h):
            if (bit >> i) & 1:
                border.append(i + 1)
                cand += 1
        border.append(h)
        if cand >= ans:
            continue
        j0 = 0
        j = 1
        while j <= w:
            
            for i, bi in enumerate(border[:-1]):
                
                
                
                if cs[border[i + 1]][j] - cs[border[
                        i + 1]][j0] - cs[bi][j] + cs[bi][j0] > k:
                    cand += 1
                    j0 = j - 1
                    j -= 1
                    
                    break
            j += 1
            if cand >= ans:
                break

        
        ans = min(ans, cand)
    print(ans)


if __name__ == '__main__':
    main()

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


    ans = 10**9
    for i in range(2**(h-1)):
        a, b = 0, 0
        buf = [0]
        for j in range(h-1):
            if ((1<<j) & i) > 0:
                a += 1
                buf.append(j+1)
        buf.append(h)
        x = 0
        F = True
        for j in range(1, w+1):
            f = False
            for l in range(1, len(buf)):
                if t[buf[l]][j] - t[buf[l-1]][j] - t[buf[l]][x] + t[buf[l-1]][x] > k:
                    f = True
            if f:
                b += 1
                x = j-1
                for l in range(1, len(buf)):
                    if t[buf[l]][j] - t[buf[l-1]][j] - t[buf[l]][j-1] + t[buf[l-1]][j-1] > k:
                        F = False
                        break
        if a + b < ans and F:

            ans = a + b
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
def main():
    H, W, K = map(int, input().split())
    S = [list(map(int, list(input()))) for i in range(H)]
    ans = (H-1)*(W-1)
    for i in range(2**(H-1)):
        border = []
        tmp = 0
        for j in range(H-1):
            if (i >> j) % 2 == 1:  
                border.append(j)
                tmp += 1

        border.append(H-1)
        num = [0]*(tmp+1)
        flag = True
        prev = 0
        for k, x in enumerate(zip(*S)):
            sep = False
            for j, y in enumerate(border):

                if j == 0:
                    prev = 0
                else:
                    prev = border[j-1]+1

                if sep:
                    num[j] = sum(x[prev:y+1])
                elif num[j] + sum(x[prev:y+1]) > K:

                    
                    sep = True
                    tmp += 1
                    num[j] = sum(x[prev:y+1])
                    for l in range(j):
                        if l == 0:
                            num[l] = sum(x[:border[l]+1])
                        else:
                            num[l] = sum(x[border[l-1]:border[l]+1])
                else:
                    num[j] += sum(x[prev:y+1])

                if num[j] > K:
                    flag = False
                    break

        
        if flag:
            ans = min(ans, tmp)
        else:
            continue

    print(ans)


main()

Solution (Python):
h,w,k=map(int,input().split())
Cho=[list(map(int,list(input()))) for _ in range(h)]
ans=10000000
for i in range(2**(h-1)):
	need=0
	seq=[]
	t=[]
	for j in range(h-1):
		t.append(j)
		if i&(1<<j):
			need+=1
			seq.append(t)
			t=[]
	seq.append(t+[h-1])
	f=1
	q=need+1
	cnt=[0]*q
	for x in range(w):
		cntp=[0]*q
		for i,g in enumerate(seq):
			cntg=0
			for y in g:
				cntg+=Cho[y][x]
				if cntg>k:
					f=0
					break
				cntp[i]+=Cho[y][x]
			if not f:
				break
		if not f:
			break
		for xx in range(q):
			cnt[xx]+=cntp[xx]
		if any(xxx>k for xxx in cnt):
			need+=1
			if need>ans:
				f=0
				break
			cnt=cntp
	if f:
		ans=min(ans,need)
print(ans)