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):
def main():
    H, W, K = map(int, input().split())
    chocolate = [list(map(int,list(input()))) for _ in range(H)]
    choco = [[0]*W for _ in range(H)]
    ids = [0] * H
    ans = 10 ** 9
    for bit in range(1<<(H-1)):
        group_id = 0
        for i in range(H):
            ids[i] = group_id
            if (bit>>i)&1:
                group_id += 1
        group_id += 1
        
        for i in range(group_id):
            for j in range(W):
                choco[i][j] = 0

        for i in range(H):
            for j in range(W):
                choco[ids[i]][j] += chocolate[i][j]
        
        if any(choco[i][j] > K for i in range(group_id) for j in range(W)):
            continue
        
        num = group_id - 1
        now = [0] * group_id
        def add(j):
            for i in range(group_id):
                now[i] += choco[i][j]
            if any(now[i] > K for i in range(group_id)):
                return False
            else:
                return True

        for j in range(W):
            if not add(j):
                num += 1
                now = [0] * group_id
                add(j)
        ans = min(ans, num)
    print(ans)


if __name__ == "__main__":
    main()

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

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

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


s=[[0]*w]+s
for i in range(h+1):
    s[i]=[0]+s[i]

ans=float('inf')

for i in range(2**(h-1)):
    line=[]
    for j in range(h-1):
        if (i>>j)&1:
            line.append(j+1)
    cnt=len(line)
    line=[0]+line+[h]
    x=0
    flag=True
    for k1 in range(1,w+1):
        v=0
        for l in range(len(line)-1):
            
            if s[line[l+1]][k1]-s[line[l+1]][k1-1]-s[line[l]][k1]>k:
                flag=False
                
            v=max(s[line[l+1]][k1]-s[line[l+1]][x]-s[line[l]][k1]+s[line[l]][x],v)
            
        if v>k:
            cnt+=1
            x=k1-1
            
    if flag:
        ans=min(cnt,ans)
        
print(ans)

Solution (Python):
import sys
from itertools import product

read = sys.stdin.read
readline = sys.stdin.readline

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

answer = 10 ** 10
for i in product((0, 1), repeat=H - 1):
    cnt = sum(i)
    if cnt >= answer:
        continue
    cuts = []
    cuts.append(S[0].copy())
    for j in range(H - 1):
        if i[j] == 1:
            cuts.append(S[j + 1].copy())
        else:
            tmp1 = cuts[-1]
            tmp2 = S[j + 1]
            for k in range(W):
                tmp1[k] += tmp2[k]
    for j in cuts:
        if any(k > K for k in j):
            break
    else:
        h = len(cuts)
        tmp = [0] * h

        for j in range(W):
            for k in range(h):
                tmp[k] += cuts[k][j]
            for k in tmp:
                if k > K:
                    cnt += 1
                    tmp = [cuts[l][j] for l in range(h)]
                    break
        if cnt < answer:
            answer = cnt

print(answer)

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

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

for i in range(h):
    for j in range(w):
        s[i][j]=int(s[i][j])

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

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


s=[[0]*w]+s
for i in range(h+1):
    s[i]=[0]+s[i]

ans=float('inf')

for i in range(2**(h-1)):
    line=[]
    for j in range(h-1):
        if (i>>j)&1:
            line.append(j+1)
    cnt=len(line)
    line=[0]+line+[h]
    x=0
    flag=True
    for k1 in range(1,w+1):
        v=0
        for l in range(len(line)-1):
            
            if s[line[l+1]][k1]-s[line[l+1]][k1-1]-s[line[l]][k1]>k:
                flag=False
            v=max(s[line[l+1]][k1]-s[line[l+1]][x]-s[line[l]][k1]+s[line[l]][x],v)

        if v<=k:
            continue
        else:
            cnt+=1
            x=k1-1
    if flag:
        ans=min(cnt,ans)
print(ans)

Solution (Python):


def main():
    def calc(group):
        ret = max(group)
        ctr = [0] * H
        for c in range(W):
            need_cut = False
            for r, g in enumerate(group):
                ctr[g] += s[r][c]
                if ctr[g] > K:
                    need_cut = True
                    break

            if need_cut:
                ctr = [0] * H
                ret += 1
                for r, g in enumerate(group):
                    ctr[g] += s[r][c]
                    if ctr[g] > K:
                        return H * W
                continue
        return ret

    def gen():
        from itertools import accumulate, product

        for prod in product(range(2), repeat=H - 1):
            group = [0]
            group.extend(accumulate(prod))
            yield calc(group)

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

    ret = min(gen())
    print(ret)


if __name__ == '__main__':
    main()

Solution (Python):


def main():
    def calc(group):
        ret = max(group)
        ctr = [0] * H
        for c in range(W):
            need_cut = False
            for r, g in enumerate(group):
                ctr[g] += s[r][c]
                if ctr[g] > K:
                    need_cut = True
                    break

            if need_cut:
                ctr = [0] * H
                ret += 1
                for r, g in enumerate(group):
                    ctr[g] += s[r][c]
                    if ctr[g] > K:
                        return H * W
                continue
        return ret

    def gen():
        from itertools import accumulate, product

        for prod in product(range(2), repeat=H - 1):
            group = [0]
            group.extend(accumulate(prod))
            yield calc(group)

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

    ret = min(gen())
    print(ret)


if __name__ == '__main__':
    main()

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

ret = H * W
for bits in range(1 << (H - 1)):
    
    
    
    

    group = [0] * H
    for j in range(H - 1):
        group[j + 1] = group[j] + (1 if (bits >> j) & 1 else 0)
    

    ctr = [0] * H
    add_v = [0] * H
    c, pc = 0, -1
    cut = bin(bits).count('1')
    while c < W:
        need_cut = False
        for r in range(H):
            g = group[r]
            add_v[g] += s[r][c]
            if ctr[g] + add_v[g] > K:
                need_cut = True
                break

        if need_cut:
            if pc == c:
                cut = H * W
                break
            ctr = [0] * H
            add_v = [0] * H
            cut += 1
            pc = c
            if cut >= ret:
                break
            continue

        for g, _add_v in enumerate(add_v):
            ctr[g] += _add_v
        add_v = [0] * H
        pc = c
        c += 1

    ret = min(ret, cut)

print(ret)

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()

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

    ans = 10 ** 9

    for bit in range(1 << (H-1)):
        canSolve = True
        ord = [0] * (H + 1)
        N = 0
        for i in range(H):
            if bit & 1 << i:
                ord[i+1] = ord[i] + 1
                N += 1
            else:
                ord[i+1] = ord[i]
        nums = [0] * (H + 1)
        for w in range(W):
            one = [0] * (H + 1)
            overK = False
            for h in range(H):
                one[ord[h]] += S[h][w]
                nums[ord[h]] += S[h][w]
                if one[ord[h]] > K:
                    canSolve = False
                if nums[ord[h]] > K:
                    overK = True
            if not canSolve:
                break
            if overK:
                N += 1
                nums = one
        if canSolve and ans > N:
            ans = N
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()

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

    ans = 10 ** 9

    for bit in range(1 << (H-1)):
        canSolve = True
        ord = [0] * (H + 1)
        N = 0
        for i in range(H):
            if bit & 1 << i:
                ord[i+1] = ord[i] + 1
                N += 1
            else:
                ord[i+1] = ord[i]
        nums = [0] * (H + 1)
        for w in range(W):
            one = [0] * (H + 1)
            overK = False
            for h in range(H):
                one[ord[h]] += int(S[h][w])
                nums[ord[h]] += int(S[h][w])
                if one[ord[h]] > K:
                    canSolve = False
                if nums[ord[h]] > K:
                    overK = True
            if not canSolve:
                break
            if overK:
                N += 1
                nums = one
        if canSolve and ans > N:
            ans = N
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import defaultdict
def input(): return sys.stdin.readline().rstrip()

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

    ans = 10 ** 9

    for bit in range(1 << (H-1)):
        canSolve = True
        ord = defaultdict(int)
        N = 0
        for i in range(H):
            if bit & 1 << i:
                ord[i+1] = ord[i] + 1
                N += 1
            else:
                ord[i+1] = ord[i]
        nums = defaultdict(int)
        for w in range(W):
            one = defaultdict(int)
            overK = False
            for h in range(H):
                one[ord[h]] += int(S[h][w])
                nums[ord[h]] += int(S[h][w])
                if one[ord[h]] > K:
                    canSolve = False
                if nums[ord[h]] > K:
                    overK = True
            if not canSolve:
                break
            if overK:
                N += 1
                nums = one
        if canSolve and ans > N:
            ans = N
    print(ans)

if __name__ == '__main__':
    main()

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

choco_array = [[int(s) for s in input()] for _ in range(H)]


ans = 100000

for i in range(1 << (H-1)):
    cut_h = 0
    cut_array = [0] * H
    for h in range(H-1):
        if i >> (h) & 1:
            cut_h += 1
        cut_array[h+1] = cut_h
    
    cut_w = 0
    now_count = [0] * (cut_h+1)
    for w in range(W):
        new_count = [0] * (cut_h+1)
        for h in range(H):
            new_count[cut_array[h]] += choco_array[h][w]
        ng_flag = 0
        
        for i in range(cut_h+1):
            if new_count[i] > K:
                ng_flag = -1
                break
            if now_count[i] + new_count[i] > K:
                ng_flag = 1
                break
        if ng_flag == -1:
            cut_w = 10000
            break
        if ng_flag == 1:
            cut_w += 1
            for i in range(cut_h+1):
                now_count[i] = new_count[i]
        else:
            for i in range(cut_h+1):
                now_count[i] += new_count[i]
    ans = min(ans, cut_h+cut_w)

print(ans)

Solution (Python):
import sys
from collections import defaultdict
def input(): return sys.stdin.readline().rstrip()

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

    ans = 10 ** 9

    for bit in range(1 << (H-1)):
        canSolve = True
        ord = defaultdict(int)
        N = 0
        for i in range(H):
            if bit & 1 << i:
                ord[i+1] = ord[i] + 1
                N += 1
            else:
                ord[i+1] = ord[i]
        add = 0
        nums = defaultdict(int)
        for w in range(W):
            one = defaultdict(int)
            ok = True
            for h in range(H):
                one[ord[h]] += int(S[h][w])
                nums[ord[h]] += int(S[h][w])
                if one[ord[h]] > K:
                    canSolve = False
                if nums[ord[h]] > K:
                    ok = False
            if not ok:
                add += 1
                nums = one
        if canSolve and ans > N + add:
            ans = N + add
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
def resolve():
    H, W, K = lr()
    S = []
    for i in range(H):
        S.append([int(s) for s in sr()])
    ans = 2000
    idx = [0]*H
    for div in range(1<<(H-1)):
        g = 0
        for i in range(H):
            idx[i] = g
            if div>>i&1:
                g += 1
        g += 1
        c = [[0]*W for i in range(g)]
        for i in range(H):
            for j in range(W):
                c[idx[i]][j] += S[i][j]
        ok = True
        for i in range(g):
            for j in range(W):
                if c[i][j] > K:
                    ok = False
        if not ok:
            continue
        num = g-1
        now = [0]*g
        def add(j):
            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):
                num += 1
                now = [0]*g
                add(j)
        ans = min(ans, num)
    print(ans)
resolve()

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10 ** 7)
INF = 1001001001

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


ans = INF
for b in range(1<<(H-1)):
    g = 0
    idx = [0]*H
    for i in range(H-1):
        if b>>i&1:
            g += 1
        idx[i+1] = g
    g += 1
    cnt = [[0]*W for _ in range(g)]
    for i in range(H):
        for j in range(W):
            cnt[idx[i]][j] += S[i][j]
    num = g-1
    now = [0]*g

    def add(j):
        global now
        for i in range(g):
            now[i] += cnt[i][j]
            if now[i] > K:
                return False
        return True

    for j in range(W):
        if add(j)==False:
            num += 1
            now = [0]*g
            if add(j)==False:
                num = INF
                break
    ans = min(ans, num)

print(ans)

Solution (Python):
n, m, k = [int(i) for i in input().split()]

subsets = []
splits = [i for i in range(1, n)]
n -= 1
for i in range(2**n):
    x = []
    for j in range(n):
        if i&(1<<j):
            x.append(j)
    subsets.append(x)
n+=1
A = []
for i in range(n):
    A.append([int(j) for j in input()])
ans = n*m
for subset in subsets:
    cur_ans = len(subset)
    tmp = []
    col = 0
    subset.append(100000)
    running_sum = [0 for i in range(len(subset))]    
    while col<m:
        row_ptr = 0    
        for row in range(n):
            if row > subset[row_ptr]:
                row_ptr += 1
            running_sum[row_ptr] += A[row][col]
            if running_sum[row_ptr] > k:
                col -= 1
                running_sum = [0 for i in range(len(subset))]
                cur_ans += 1
                break
                
        col += 1                
        if cur_ans >= ans:
          break
    ans = min(ans, cur_ans)
print(ans)

Solution (Python):
H,W,K = map(int,input().split())
A = []
for i in range(H):
    b = list(input())
    b.append("0")
    A.append(b)

ans = 10**6
for i in range(2**(H-1)):
    p = "0" + str(H-1)
    bin_list = list(format(i,p+"b"))
    sec = []
    for i in range(H-1):
        if bin_list[i] == "1":
            sec.append(i)
    sec.append(H-1)
    l = len(sec)

    W_start = 0
    k = 0
    while(True):
        H_start = 0
        pross = 10**4
        for i in range(l):
            H_end = sec[i] + 1
            j = W_start
            c = 0
            while(True):
                for t in range(H_start,H_end):
                    if A[t][j] == "1":
                        c += 1
                j += 1
                if c > K or j > W:
                    pross = min(pross,j-W_start)
                    break
            H_start = sec[i] + 1

        k += 1
        W_start += pross-1
        if W_start > W-1 or pross == 1:
            break
    if pross != 1:
        ans = min(ans,k+l-2)

print(ans)

Solution (Python):
def column_check(grp, grp_count, choco, h, j, k):
    """ 0:成功（更新も反映）  1:失敗（区切った結果を返す） 2:不可能 """
    
    curr_count = [0] * len(grp_count)
    
    for i in range(h):
        if choco[i][j] == '0':
            continue
        curr_count[grp[i]] += 1
    
    for cc in curr_count:
        if cc > k:
            return 2
    
    for i, cc in enumerate(curr_count):
        grp_count[i] += cc
        
        if grp_count[i] > k:
            grp_count[:] = curr_count
            return 1
    return 0


def solve(h, w, k, choco):
    ans = 10 ** 9
    grp = [0] * h
    for bit in range(1 << (h - 1)):
        g = 0
        for i in range(h):
            grp[i] = g
            if (bit >> i) & 1:
                g += 1

        grp_count = [0] * (g + 1)
        tmp = 0
        possible = True
        for j in range(w):
            result = column_check(grp, grp_count, choco, h, j, k)
            if result == 2:
                possible = False
                break
            if result == 1:
                tmp += 1

        if not possible:
            continue

        ans = min(ans, tmp + bin(bit).count('1'))

    return ans


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

Solution (Python):
import numpy as np
from itertools import product
H, W, K = map(int, input().split())
G = np.array([list(map(int, list(input()))) for _ in range(H)])

ans = float('inf')
for pattern in product([0, 1], repeat=H - 1):
    
    div = [0] + [i for i, p in enumerate(pattern, start=1) if p == 1] + [10]

    
    rows = []
    for i in range(len(div) - 1):
        rows.append(np.sum(G[div[i]: div[i + 1]], axis=0))

    
    if [r for r in rows if np.any(r > K)]:
        continue

    
    rows = [r.tolist() for r in rows]
    tmp_ans = 0
    counts = [0] * len(rows)
    w = 0
    while w < W:
        for r in range(len(rows)):
            counts[r] += rows[r][w]
        if any([c > K for c in counts]):
            counts = [0] * len(rows)
            w -= 1
            tmp_ans += 1
        w += 1

    
    tmp_ans += len(div) - 2
    ans = min(ans, tmp_ans)

print(ans)

Solution (Python):
import sys

def solve():
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    S = [input().strip("\n") for _ in range(H)]
    Ans = 10 ** 20
    Wcount = [[0 for _ in range(W + 1)] for _ in range(H + 1)]
    for h in range(H):
        for w in range(W):
            Wcount[h+1][w+1] = Wcount[h][w + 1] + Wcount[h + 1][w] - Wcount[h][w] + int(S[h][w])
        
            
    
    Ans = H * W + 1
    for i in range(2 ** (H - 1)):
        B = [0]
        d = i
        Hcount = 0
        for j in range(H - 1):
            if d % 2 == 1:
                B.append(j + 1)
                Hcount += 1
            d //= 2
        B.append(H)
        leftbound = 0
        TotalBound = Hcount
        NG = False
        for w in range(1, W+1):
            for b in range(Hcount + 1):
                if Wcount[B[b+1]][w] - Wcount[B[b+1]][leftbound] - Wcount[B[b]][w] + Wcount[B[b]][leftbound] > K:
                    if leftbound + 1 == w: 
                        NG = True
                    else:
                        TotalBound += 1
                        leftbound = w - 1
                    break
            if NG: break
        else: Ans = min(TotalBound, Ans)
        
    print(Ans)

    return 0

if __name__ == "__main__":
    solve()

Solution (Python):
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    H,W,K = map(int, readline().split())
    S = [list(map(int, readline().strip())) for j in range(H)]

    white = 0
    for line in S:
        white += sum(line)

    if white <= K:
        print(0)
        exit()

    
    ans = 10**5
    for pattern in range(2**(H-1)):
        
        impossible = False
        x = 0
        ly = bin(pattern).count("1")
        y = [S[0]]
        line = 0
        for i in range(1,H):
            if (pattern >> i-1) & 1:
                line += 1
                y.append(S[i])
            else:
                y[line] = [y[line][j] + S[i][j] for j in range(W)]

        
        count = [0]*(ly + 1) 
        for j in range(W):
            for i in range(line+1):
                if y[i][j] > K :
                    impossible = True
                    break

                count[i] += y[i][j]
                if count[i] > K:
                    x += 1
                    for i in range(line+1):
                        count[i] = y[i][j] 
                    break
            if x + ly > ans or impossible:
                impossible = True
                break
        if impossible:
            x = 10**6

        ans = min(ans, x + ly)

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    H,W,K = map(int, readline().split())
    S = [list(map(int, readline().strip())) for j in range(H)]

    white = 0
    for line in S:
        white += sum(line)

    if white <= K:
        print(0)
        exit()

    
    ans = 10**5
    for pattern in range(2**(H-1)):
        
        impossible = False
        x = 0
        ly = bin(pattern).count("1")
        y = [S[0]]
        line = 0
        for i in range(1,H):
            if (pattern >> i-1) & 1:
                line += 1
                y.append(S[i])
            else:
                y[line] = [y[line][j] + S[i][j] for j in range(W)]

        
        count = [0]*(ly + 1) 
        for j in range(W):
            for i in range(line+1):
                if y[i][j] > K :
                    impossible = True
                    break

                count[i] += y[i][j]
                if count[i] > K:
                    x += 1
                    for i in range(line+1):
                        count[i] = y[i][j] 
                    break
            if x + ly > ans or impossible:
                impossible = True
                break
        if impossible:
            x = 10**6

        ans = min(ans, x + ly)

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    H,W,K = map(int, readline().split())
    S = [list(map(int, readline().strip())) for j in range(H)]

    white = 0
    for line in S:
        white += sum(line)

    if white <= K:
        print(0)
        exit()

    
    ans = 10**5
    for pattern in range(2**(H-1)):
        
        impossible = False
        x = 0
        ly = bin(pattern).count("1")
        y = [[0]*W]*(ly + 1)
        line = 0
        for i in range(H):
            y[line] = [y[line][j] + S[i][j] for j in range(W)]
            if (pattern >> i) & 1:
                line += 1

        
        count = [0]*(ly + 1) 
        for j in range(W):
            for i in range(line+1):
                if y[i][j] > K :
                    impossible = True
                    break

                count[i] += y[i][j]
                if count[i] > K:
                    x += 1
                    for i in range(line+1):
                        count[i] = y[i][j] 
                    break
            if x + ly > ans or impossible:
                impossible = True
                break
        if impossible:
            x = 10**6

        ans = min(ans, x + ly)

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    H,W,K = map(int, readline().split())
    S = [list(map(int, readline().strip())) for j in range(H)]

    white = 0
    for line in S:
        white += sum(line)

    if white <= K:
        print(0)
        exit()

    
    ans = 10**5
    for pattern in range(2**(H-1)):
        
        impossible = False
        x = 0
        ly = bin(pattern).count("1")
        y = [[0]*W]*(ly + 1)
        line = 0
        for i in range(H):
            y[line] = [y[line][j] + S[i][j] for j in range(W)]
            if (pattern >> i) & 1:
                line += 1

        
        count = [0]*(ly + 1) 
        for col in zip(*y):
            
            if any(a > K for a in col):
                impossible = True
                break
            for i, a in enumerate(col):
                count[i] += a
                
                if count[i] > K:
                    x += 1
                    count = list(col) 
                    break
            if x + ly > ans:
                impossible = True
                break
        if impossible:
            x = 10**6

        ans = min(ans, x + ly)

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    H,W,K = map(int, readline().split())
    S = [list(map(int, readline().strip())) for j in range(H)]

    white = 0
    for line in S:
        white += sum(line)

    if white <= K:
        print(0)
        exit()

    
    ans = 10**5
    for pattern in range(2**(H-1)):
        
        impossible = False
        x = 0
        ly = bin(pattern).count("1")
        y = [[0]*W]*(ly + 1)
        line = 0
        for i in range(H):
            y[line] = [y[line][j] + S[i][j] for j in range(W)]
            if (pattern >> i) & 1:
                line += 1

        
        count = [0]*(ly + 1) 
        for col in zip(*y):
            
            if any(a > K for a in col):
                impossible = True
                break
            for i, a in enumerate(col):
                count[i] += a
                
                if count[i] > K:
                    x += 1
                    count = list(col) 
                    break
            if x + ly > ans:
                impossible = True
                break
        if impossible:
            x = 10**6

        ans = min(ans, x + ly)

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]

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

ans=float('inf')
for i in range(2**(h-1)):
    tmp=1
    for j in range(h-1):
        if 1 & (i>>j):
            tmp+=1
    lst=[[0]*tmp for j in range(w)]

    for j in range(w):
        now=0
        for l in range(h):
            if s[l][j]=="1":
                lst[j][now]+=1
            if 1 & (i>>l):
                now+=1

    cnt=[0]*tmp
    cutcnt=0
    for j in range(w):
        flag=0
        for l in range(tmp):
            if cnt[l]+lst[j][l]>k:
                flag=1
    
        if flag==0:
            for l in range(tmp):
                cnt[l]+=lst[j][l]
        else:
            cutcnt+=1
            for l in range(tmp):
                cnt[l]=lst[j][l]
                if cnt[l]>k:
                    cutcnt=float('inf')
        
    ans=min(cutcnt+tmp-1,ans)
    
    
print(ans)

Solution (Python):
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    H,W,K = map(int, readline().split())
    S = [readline().strip() for j in range(H)]

    white = []
    for line in S:
        white.append(line.count("1"))
    white_total = sum(white)

    if white_total <= K:
        print(0)
        exit()

    
    ans = 10**5
    for pattern in range(2**(H-1)):
        
        impossible = False
        x = 0
        ly = bin(pattern).count("1")
        y = [[0]*W]*(ly + 1)
        line = 0
        for i in range(H):
            y[line] = [y[line][j] + int(S[i][j]) for j in range(W)]
            if (pattern >> i) & 1:
                line += 1

        
        count = [0]*(ly + 1) 
        for col in zip(*y):
            
            if any(a > K for a in col):
                impossible = True
                break
            for i, a in enumerate(col):
                count[i] += a
                
                if count[i] > K:
                    x += 1
                    count = list(col) 
                    break
            if x + ly > ans:
                impossible = True
                break
        if impossible:
            x = 10**6

        ans = min(ans, x + ly)

    print(ans)


if __name__ == "__main__":
    main()