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

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


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

    ans = float("inf")

    for n in range(2 ** (H - 1)):
        tmp = 0
        wn = [0] * 10

        for i in range(H):
            if n >> i & 1:
                tmp += 1

        for i in range(W):
            f = False
            ni = 0
            for j in range(H):
                if wn[ni] + int(S[j][i]) > K:
                    tmp += 1
                    f = True
                    break
                else:
                    wn[ni] += int(S[j][i])
                if n >> j & 1:
                    ni += 1
            if f:
                if i == 0:
                    tmp = float("inf")
                for j in range(H):
                    wn[j] = 0
                ni = 0
                for j in range(H):
                    wn[ni] += int(S[j][i])
                    if wn[ni] > K:
                        tmp = float("inf")
                    if n >> j & 1:
                        ni += 1

        ans = min(ans, tmp)

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


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

    ans = float("inf")

    for n in range(2 ** (H - 1)):
        tmp = 0
        wn = [0] * 10
        wi = [set() for _ in range(10)]

        ni = 0
        for i in range(H):
            wi[ni].add(i)
            if n >> i & 1:
                ni += 1
                tmp += 1

        for i in range(W):
            f = False
            for j in range(H):
                for wii in range(ni + 1):
                    if j in wi[wii]:
                        if wn[wii] + int(S[j][i]) > K:
                            tmp += 1
                            f = True
                        else:
                            wn[wii] += int(S[j][i])
                        break
                if f:
                    break
            if f:
                for wii in range(ni + 1):
                    wn[wii] = 0
                for j in range(H):
                    for wii in range(ni + 1):
                        if j in wi[wii]:
                            wn[wii] += int(S[j][i])
                            break
                for wii in range(ni + 1):
                    if wn[wii] > K:
                        tmp = float("inf")

        ans = min(ans, tmp)

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

import numpy as np

h, w, k = map(int, readline().split())
s = np.array([list(map(int, readline().rstrip().decode())) for _ in range(h)], np.int64)
ans = h + w
for i in range(2 ** (h - 1)):
    wp = np.zeros((h, w), np.int64)
    wq = np.zeros((h, ), np.int64)
    wp[0] = s[0]
    cnt = 0
    for j in range(h - 1):
        if i >> j & 1:
            cnt += 1
        wp[cnt] += s[j + 1]
    if cnt >= ans or np.count_nonzero(wp > k):
        continue
    for j in range(w):
        wq += wp[:, j]
        if np.count_nonzero(wq > k):
            cnt += 1
            wq = wp[:, j]
    if ans > cnt:
        ans = cnt
print(ans)

Solution (Python):

import sys
sys.setrecursionlimit(10**8)
from itertools import accumulate
INF = float("inf")


def bit(n, k):
    return (n >> k) & 1


def bit_sum(n):
    wa = 0
    while n > 0:
        wa += n & 1
        n >>= 1
    return wa


def border(x):
    
    c = 0
    ans = []
    while x > 0:
        c += 1
        if x & 1:
            ans.append(c)
        x >>= 1
    return ans


def main():

    H, W, K = map(int, input().split())
    S = [[0]*W for _ in range(H)]
    for h in range(H):
        S[h][:] = [int(c) for c in input()]
    acc = [[0]+list(accumulate(S[h])) for h in range(H)]

    min_kaisu = +INF
    for h in range(1 << (H-1)):
        
        
        startend = border(h)
        flag = False

        division = [0]
        
        for x in range(1, W+1):
            
            
            white = [acc[i][x] - acc[i][division[-1]] for i in range(H)]
            
            white_sum = [sum(white[s:e])
                         for s, e in zip([0]+startend, startend+[H])]
            
            white_max = max(white_sum)
            
            if white_max > K:
                division.append(x-1)
                
                white = [acc[i][x] - acc[i][division[-1]] for i in range(H)]
                white_sum = [sum(white[s:e])
                             for s, e in zip([0]+startend, startend+[H])]
                white_max = max(white_sum)
                if white_max > K:
                    flag = True
                    break
        if flag:
            continue
        
        division_tot = len(division)-1 + bit_sum(h)
        min_kaisu = min(division_tot, min_kaisu)
    print(min_kaisu)
    return


if __name__ == '__main__':
    main()

Solution (Python):

import sys
from collections import defaultdict

H,W,K=map(int, sys.stdin.readline().split())
S=[ sys.stdin.readline().strip() for _ in range(H) ]

ans=float("inf")
for bit in range(2**H):
    cnt=0
    group_num=0
    GROUP={}
    for i,s in enumerate(S):
        if i==0:
            GROUP[i]=group_num
        else:
            if bit>>i-1&1==1:
                cnt+=1      
                group_num+=1
            GROUP[i]=group_num

    ok=None
    VALUE=defaultdict(lambda: 0)
    w=0
    break_flag=False
    for w in range(W):
        if break_flag:  
            break
        for h in range(H):
            VALUE[GROUP[h]]+=int(S[h][w])
        
        for v in VALUE.values():
            if v<=K:
                pass
            else:
                if ok is None:      
                    cnt=float("inf")    
                    break_flag=True     
                    break
                else:      
                    cnt+=1      
                    VALUE=defaultdict(lambda: 0)    
                    for h in range(H):
                        VALUE[GROUP[h]]+=int(S[h][w])
                    break
        else:
            ok=w    
    ans=min(ans,cnt)
       
print ans

Solution (Python):

import sys
from collections import defaultdict

H,W,K=map(int, sys.stdin.readline().split())
S=[ sys.stdin.readline().strip() for _ in range(H) ]

ans=float("inf")
for bit in range(2**H):
    cnt=0
    group_num=0
    GROUP={}
    for i,s in enumerate(S):
        if i==0:
            GROUP[i]=group_num
        else:
            if bit>>i-1&1==1:
                cnt+=1      
                group_num+=1
            GROUP[i]=group_num

    ok=None
    VALUE=defaultdict(lambda: 0)
    w=0
    break_flag=False
    for w in range(W):
        if break_flag:  
            break
        for h in range(H):
            VALUE[GROUP[h]]+=int(S[h][w])
        
        for v in VALUE.values():
            if v<=K:
                pass
            else:
                if ok is None:      
                    cnt=float("inf")    
                    break_flag=True     
                    break
                else:      
                    cnt+=1      
                    VALUE=defaultdict(lambda: 0)    
                    for h in range(H):
                        VALUE[GROUP[h]]+=int(S[h][w])
                    break
        else:
            ok=w    
    ans=min(ans,cnt)
       
print ans

Solution (Python):

import sys
from collections import defaultdict

H,W,K=map(int, sys.stdin.readline().split())
S=[ sys.stdin.readline().strip() for _ in range(H) ]

ans=float("inf")
for bit in range(2**H):
    cnt=0
    group_num=0
    GROUP={}
    for i,s in enumerate(S):
        if i==0:
            GROUP[i]=group_num
        else:
            if bit>>i-1&1==1:
                cnt+=1      
                group_num+=1
            GROUP[i]=group_num

    ok=None
    VALUE=defaultdict(lambda: 0)
    w=0
    break_flag=False
    for w in range(W):
        if break_flag:  
            break
        for h in range(H):
            VALUE[GROUP[h]]+=int(S[h][w])
        
        for v in VALUE.values():
            if v<=K:
                pass
            else:
                if ok is None:      
                    cnt=float("inf")    
                    break_flag=True     
                    break
                else:      
                    cnt+=1      
                    VALUE=defaultdict(lambda: 0)    
                    for h in range(H):
                        VALUE[GROUP[h]]+=int(S[h][w])
                    break
        else:
            ok=w    
    ans=min(ans,cnt)
       
print ans

Solution (Python):

import sys
from collections import defaultdict

H,W,K=map(int, sys.stdin.readline().split())
S=[ sys.stdin.readline().strip() for _ in range(H) ]



ans=float("inf")
for bit in range(2**H):
    cnt=0
    group_num=0
    GROUP={}
    for i,s in enumerate(S):
        if i==0:
            GROUP[i]=group_num
        else:
            if bit>>i-1&1==1:
                cnt+=1      
                group_num+=1
            GROUP[i]=group_num
    

    ok=None
    VALUE=defaultdict(lambda: 0)
    w=0
    break_flag=False
    for w in range(W):
        if break_flag:  
            break
        for h in range(H):
            VALUE[GROUP[h]]+=int(S[h][w])
        
        for v in VALUE.values():
            if v<=K:
                pass
            else:
                
                if ok is None:      
                    
                    cnt=float("inf")    
                    break_flag=True     
                    break
                else:      
                    cnt+=1      
                    VALUE=defaultdict(lambda: 0)    
                    for h in range(H):
                        VALUE[GROUP[h]]+=int(S[h][w])
                    break
        else:
            ok=w
    
    ans=min(ans,cnt)
       
print ans

Solution (Python):

import sys
from collections import defaultdict

H,W,K=map(int, sys.stdin.readline().split())
S=[ sys.stdin.readline().strip() for _ in range(H) ]



ans=float("inf")
for bit in range(2**H):
    cnt=0
    group_num=0
    GROUP={}
    for i,s in enumerate(S):
        if i==0:
            GROUP[i]=group_num
        else:
            if bit>>i-1&1==1:
                cnt+=1      
                group_num+=1
            GROUP[i]=group_num
    

    ok=None
    VALUE=defaultdict(lambda: 0)
    w=0
    for w in range(W):
        for h in range(H):
            VALUE[GROUP[h]]+=int(S[h][w])
        
        for v in VALUE.values():
            if v<=K:
                pass
            else:
                
                if ok is None:      
                    
                    cnt=float("inf")    
                else:      
                    cnt+=1      
                    VALUE=defaultdict(lambda: 0)    
                    for h in range(H):
                        VALUE[GROUP[h]]+=int(S[h][w])
                    break
        else:
            ok=w
    
    ans=min(ans,cnt)
       
print ans

Solution (Python):
H,W,K = map(int,input().split(sep=" "))
S = [list(map(int,list(input()))) for i in range(0,H,1)]
minimum = H+W
for sepH in range(0,2**(H-1),1):
    bitcounter = 0
    tmp_sepH = sepH
    while tmp_sepH > 0:
        if tmp_sepH & 1 == 1:
            bitcounter+=1
        tmp_sepH = tmp_sepH//2
    A = [[0 for i in range(0,W,1)] for j in range(0,bitcounter+1,1)]
    index=[[]for i in range(0,bitcounter+1,1)]
    countInd = 0
    for i in range(0,H,1):
        index[countInd].append(i)
        if (sepH >> i) & 1:
            countInd +=1
   
    for j in range(0,bitcounter+1,1):
        for i in range(0,W,1):
            for k in range(0,len(index[j]),1):
                if S[index[j][k]][i] == 1:
                    A[j][i]+=1
    countA=[0 for i in range(0,bitcounter+1,1)]
    sepCounter = 0
    dame = False
    for i in range(0,W,1):
        for j in range(0,bitcounter+1,1):
            if A[j][i] > K:
                dame = True
        for j in range(0,bitcounter+1,1):
            countA[j]+=A[j][i]
            if countA[j] > K:
                sepCounter+=1
                for j in range(0,bitcounter+1,1):
                    countA[j] = A[j][i]
                break

    if bitcounter+sepCounter < minimum and (not dame):
        minimum = bitcounter +sepCounter

print(minimum)

Solution (Python):
import sys
from copy import copy
input = sys.stdin.readline
'''
n, m = map(int, input().split())
n = int(input())
A = list(map(int, input().split()))
S = input().strip()
for test in range(int(input())):
'''
inf = 100000000000000000  
mod = 998244353


def two(x):
    return "0" * (h - 1 - len(bin(x)[2:])) + bin(x)[2:]


h, w, k = map(int, input().split())
S = []
ans = inf
for i in range(h):
    S.append(input().strip())
for way_cut in range(1 << (h - 1)):
    way_cut = two(way_cut)
    number_cut_horizontal = way_cut.count("1")
    number_cut_vertical = 0
    CUT = [-1]
    for i in range(len(way_cut)):
        if way_cut[i] == '1':
            CUT.append(i)
    CUT.append(len(way_cut))
    SUM = [0] * (w)
    PRE = [0] * (w)
    for col in range(w):
        for i in range(1, len(CUT)):
            for between in range(CUT[i - 1] + 1, CUT[i] + 1):
                SUM[i] += 1 if S[between][col] == "1" else 0
        isok = True
        for i in range(1, len(CUT)):
            if PRE[i] + SUM[i] > k:
                isok = False
        if not isok:
            number_cut_vertical += 1
            PRE = copy(SUM)
            SUM = [0]*(w)  
            
            for i in range(1, len(CUT)):
                if PRE[i] > k:
                    number_cut_vertical = inf
                    break
        else:
            for i in range(1, len(CUT)):
                PRE[i] += SUM[i]
                SUM[i] = 0
    ans = min(ans, number_cut_vertical + number_cut_horizontal)
print(ans)

Solution (Python):
import copy
H,W,K=map(int,input().split())
S=[list(input()) for _ in range(H)]
ans=10**18
for i in range(1<<(H-1)):
    x=bin(i).count('1')
    cho=[0]*(x+1)
    f=1
    cnt=x
    for w in range(W):
        j=0
        nx=[0]*(x+1)
        for h in range(H):
          cho[j]+=int(S[h][w])
          nx[j]+=int(S[h][w])
          if cho[j]>K:
            if nx[j]>K:
              f=0
              break
            else:
              cho=copy.copy(nx)
              cnt+=1
          if (i>>h)&1:
            j+=1
        if f==0:
          break
    if f:
      ans=min(ans,cnt)
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
INF = 110110110
H, W, K = list(map(int, input().split()))
S = [''] * H
for i in range(H):
    S[i] = input()
ans = H * W

for bit in range(2**(H-1)):
    cnt = bin(bit).count('1')
    id = [0] * H
    for i in range(H-1):
        if bit>>i & 1:
            id[i+1] = id[i] + 1
        else:
            id[i+1] = id[i]
    num = [[0] * W for i in range(id[H-1]+1)]
    for i in range(H):
        for j in range(W):
            if S[i][j] == '1':
                num[id[i]][j] += 1
    for i in range(id[H-1]+1):
        for j in range(W):
            if num[i][j] > K:
                cnt = INF
    sum = [0] * (id[H-1]+1)
    for j in range(W):
        need = False
        for i in range(id[H-1]+1):
            if sum[i] + num[i][j] > K:
                need = True
        if need:
            cnt += 1
            for i in range(id[H-1]+1):
                sum[i] = num[i][j]
        else:
            for i in range(id[H-1]+1):
                sum[i] += num[i][j]
    ans = min(ans, cnt)

print(ans)

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

size=[[0]*h for i in range(1<<h)]
ans=[bin(x).count("1") for x in range(1<<h)]
for stage in range(w):
    new=[[0]*h for i in range(1<<h)]
    for column in range(h):
        if int(cho[column][stage]):
            for bit in range(1<<h):
                length=(((1<<column)-1) & bit).bit_length()
                new[bit][length]+=1
    for bit in range(1<<h):
        frag=True
        for column in range(h):
            if new[bit][column]+size[bit][column]>k:
                if new[bit][column]>k:
                    ans[bit]+=1010
                frag=False
                ans[bit]+=1
                size[bit]=new[bit]
                break
        if frag:
            for column in range(h):
                size[bit][column]+=new[bit][column]
print(min(ans))

Solution (Python):
h, w, k = map(int, input().split())
s = [list(map(int, list(input()))) for _ in range(h)]
result = []
if h*w<=k:
    result.append(0)
else:
    for i in range(2**(h-1)):
        checker, num, p = 0, i ,[0]
        for _ in range(h):
            p.append(p[-1]+num%2)
            checker += num%2
            num >>= 1
        x = 0
        c = [0 for _ in range(checker+1)]
        for j in range(w):
            num = i
            nex = [0 for _ in range(checker+1)]
            for m in range(h):
                nex[p[m]] += s[m][j]
            if max(nex) > k:
                x = float('inf')
                break            
            for m in range(checker+1):
                c[m] += nex[m]
                if c[m]>k:
                    c = nex
                    x += 1
                    break
        result.append(checker+x)
print(min(result))

Solution (Python):
h, w, k = map(int, input().split())
s = [list(map(int, list(input()))) for _ in range(h)]
result = []
if h*w<=k:
    result.append(0)
else:
    for i in range(2**(h-1)):
        checker, num, p = 0, i ,[0]
        for _ in range(h):
            p.append(p[-1]+num%2)
            checker += num%2
            num >>= 1
        x = 0
        c = [0 for _ in range(checker+1)]
        for j in range(w):
            num = i
            nex = [0 for _ in range(checker+1)]
            for m in range(h):
                nex[p[m]] += s[m][j]
            if max(nex) > k:
                x = float('inf')
                break            
            
            if all(nex[m]+c[m] <= k for m in range(checker+1)):
                c = [c[I]+nex[I] for I in range(checker+1)]
            else:
                x += 1
                c = nex
        result.append(checker+x)
print(min(result))

Solution (Python):
h, w, k = map(int, input().split())
s = [list(map(int, list(input()))) for _ in range(h)]
result = []
if h*w<=k:
    result.append(0)
else:
    for i in range(2**(h-1)):
        checker, num = 0, i
        while num > 0:
            checker += num%2
            num >>= 1
        x = 0
        c = [0 for _ in range(checker+1)]

        for j in range(w):
            num = i
            p = 0
            nex = [0 for _ in range(checker+1)]
            for m in range(h):
                nex[p] += s[m][j]
                p += num%2
                num = num >> 1          
            if max(nex)>k:
                x = 10**5
                break

            if all(nex[m]+c[m] <= k for m in range(checker+1)):
                c = [c[I]+nex[I] for I in range(checker+1)]
            else:
                x += 1
                c = nex
        result.append(checker+x)
print(min(result))

Solution (Python):
h, w, k = map(int, input().split())
s = [list(map(int, list(input()))) for _ in range(h)]
result = []
if h*w<=k:
    result.append(0)
else:
    for i in range(2**(h-1)):
        checker, num = 0, i
        while num > 0:
            checker += num%2
            num >>= 1
        x = 0
        c = [0 for _ in range(checker+1)]

        for j in range(w):
            num = i
            p = 0
            nex = [0 for _ in range(checker+1)]
            for m in range(h):
                nex[p] += s[m][j]
                p += num%2
                num = num >> 1          
            if any(nex[m]>k for m in range(checker+1)):
                x = 10**5
                break

            if all(nex[m]+c[m] <= k for m in range(checker+1)):
                c = [c[I]+nex[I] for I in range(checker+1)]
            else:
                x += 1
                c = nex
        result.append(checker+x)
print(min(result))

Solution (Python):
h, w, k = map(int, input().split())
s = [list(map(int, list(input()))) for _ in range(h)]
result = []
if h*w<=k:
    result.append(0)
else:
    for i in range(2**(h-1)):
        checker, num = 0, i
        while num > 0:
            checker += num%2
            num >>= 1
        x = 0
        c = [0 for _ in range(checker+1)]

        for j in range(w):
            num = i
            p = 0
            nex = [0 for _ in range(checker+1)]
            for m in range(h):
                nex[p] += s[m][j]
                p += num%2
                num = num >> 1          
            if any(nex[m]>k for m in range(checker+1)):
                x = float('inf')
                break

            if all(nex[m]+c[m] <= k for m in range(checker+1)):
                c = [c[I]+nex[I] for I in range(checker+1)]
            else:
                x += 1
                c = nex
        result.append(checker+x)
print(min(result))

Solution (Python):
h, w, k = map(int, input().split())
s = [list(map(int, list(input()))) for _ in range(h)]
result = []
if h*w<=k:
    result.append(0)
else:
    for i in range(2**(h-1)):
        checker, num = 0, i
        while num > 0:
            checker += num%2
            num >>= 1
        x = 0
        c = [0 for _ in range(checker+1)]
        
        num = i
        p = 0
        nex = [0 for _ in range(checker+1)]
        for m in range(h):
            nex[p] += s[m][0]
            p += num%2
            num = num >> 1
        if max(nex) > k:
            x = float('inf')
            continue

        if all(nex[m]+c[m] <= k for m in range(checker+1)):
            c = [c[I]+nex[I] for I in range(checker+1)]
        else:
            x += 1

        for j in range(1, w):
            num = i
            p = 0
            nex = [0 for _ in range(checker+1)]
            for m in range(h):
                nex[p] += s[m][j]
                p += num%2
                num = num >> 1
            if max(nex) > k:
                x = float('inf')
                break            
            
            if all(nex[m]+c[m] <= k for m in range(checker+1)):
                c = [c[I]+nex[I] for I in range(checker+1)]
            else:
                x += 1
                c = nex
        result.append(checker+x)
print(min(result))

Solution (Python):
H, W, K = map(int, input().split())
rsum = [[0] * (W + 1)]
for _ in range(H):
    rsum.append([0])
    tot = 0
    for c, v in enumerate(map(int, input())):
        tot += v
        rsum[-1].append(tot + rsum[-2][c + 1])
ans = 10 ** 10
for i in range(1 << H):
    hcuts = [0]
    for j in range(H - 1):
        if i & (1 << j):
            hcuts.append(j + 1)
    hcuts.append(H)
    vcuts = [0]
    ok = True
    for c in range(1, W + 1):
        for b in range(2):
            max_w = 0
            for h in range(1, len(hcuts)):
                max_w = max(
                    max_w,
                    rsum[hcuts[h]][c]
                    - rsum[hcuts[h - 1]][c]
                    - rsum[hcuts[h]][vcuts[-1]]
                    + rsum[hcuts[h - 1]][vcuts[-1]],
                )
            if max_w > K:
                if b:
                    ok = False
                    break
                vcuts.append(c - 1)
        if not ok:
            break
    if not ok:
        continue
    vcuts.append(W)
    ans = min(ans, len(hcuts) - 2 + len(vcuts) - 2)
print(ans)

Solution (Python):

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

ans = inf
T = 2**(H-1)
for i in range(T):
    b = bin(i)
    b = b.lstrip("0b")
    blist = list(b)
    lb = len(b)
    clist = blist[::-1]
    while lb < H-1:
        clist.append("0")
        lb+=1
    
    r = clist.count("1")
    count = r
    nw = [0]*(r+1)
    for w in range(W):
        nind = 0
        for h in range(H):
            if h > 0:
                if clist[h-1] == "1":
                    nind+=1

            if S[h][w] == "1":
                nw[nind]+=1
        
        if w == 0:
            pass
        else:
            for k in nw:
                if k > K:
                    count+=1
                    nw = [0]*(r+1)
                    
                    nind = 0
                    for h in range(H):
                        if h > 0:
                            if clist[h-1] == "1":
                                nind+=1

                        if S[h][w] == "1":
                            nw[nind]+=1
                    
                    if max(nw) > K:
                        count = inf
                    
                    break
    
    ans = min(ans,count)
    
print(ans)

Solution (Python):



H, W, K = map(int, input().split())
board = [[0]*W for i in range(H)]
for i in range(H):
    s = list(input())
    for j in range(W):
        board[i][j] = int(s[j])


min_divide = 10**15


for i in range(2**(H-1)):
    
    h_pattern = [0]*(H-1)
    group_count = 1
    h_count = 0
    w_count = 0
    for j in range(H-1):
        if((i>>j)&1):
            h_pattern[j] = 1
            group_count += 1
            h_count += 1

    is_ok = True
    group_sum = [0]*group_count
    for w in range(W):
        cur_count = [0]*group_count
        cur_count_num = 0
        
        for h in range(H):
            if board[h][w]==1:
                cur_count[cur_count_num] += 1

            if cur_count[cur_count_num]>K:
                is_ok = False
                break

            if h<H-1 and h_pattern[h]==1:
                cur_count_num += 1

        if not is_ok:
            break

        
        is_smaller = True
        if w==0:
            is_smaller = True
        else:
            for c in range(group_count):
                if group_sum[c]+cur_count[c]>K:
                    is_smaller = False
        if is_smaller:
            for c in range(group_count):
                group_sum[c] += cur_count[c]
        else:
            
            for c in range(group_count):
                group_sum[c] = cur_count[c]
            w_count += 1

    if not is_ok:
        is_ok = True
        continue

    
    min_divide = min(min_divide, h_count + w_count)


print(min_divide)

Solution (Python):



H, W, K = map(int, input().split())
board = [['']*W for i in range(H)]
for i in range(H):
    s = list(input())
    for j in range(W):
        board[i][j] = s[j]


min_divide = 10**10
s = [0]*(H-1) 
is_ok = True


for i in range(2**(H-1)): 
    
    h_count = 0
    w_count = 0
    for j in range(H-1):
        if ((i>>j)&1):
            s[j] = 1
            h_count += 1
        else:
            s[j] = 0

    
    s_score = [0]*H 
    s_cur = [0]*H
    for j in range(W):
        c = 0
        s_cur = [0]*H

        for k in range(H):
            if board[k][j]=='1':
                s_cur[c] += 1

            
            if s_cur[c]>K:
                is_ok = False
                break

            
            if k+1<H:
                if s[k]==1:
                    c += 1
        
        if not is_ok:
            break
        
        
        group_smaller = True
        if j>0:
            for c_num in range(c+1):
                if s_score[c_num]+s_cur[c_num]>K:
                    group_smaller = False
        else:
            group_smaller = True

        if group_smaller:
            for c_num in range(c+1):
                s_score[c_num] += s_cur[c_num]
        else:
            w_count += 1
            for c_num in range(c+1):
                s_score[c_num] = s_cur[c_num]

    if not is_ok:
        is_ok = True
        continue

    
    
    

    
    min_divide = min(min_divide, w_count + h_count)


print(min_divide)

Solution (Python):


import sys



















def main():
    mod = 1000000007                  
    inf = float('inf')
    sys.setrecursionlimit(10**6)    
    def input(): return sys.stdin.readline().rstrip()
    def ii():  return int(input())
    def mi():  return map(int, input().split())
    def mi_0(): return map(lambda x: int(x)-1, input().split())
    def lmi(): return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():  return list(input())
    
    
    h, w, k = mi()
    L = []
    for _ in range(h):
        L.append(list(map(int, li())))
    L_trans = [[None] * h for _ in range(w)]
    for i in range(h):
        for j in range(w):
            L_trans[j][i] = L[i][j]
    d = 2 ** (h-1)
    cost = [float('inf')] * d
    for state in range(d):
        bit_count = bin(state)[2:].count('1')
        separated = [[0] * (bit_count + 1) for _ in range(w)]
        for i in range(w):
            current = 0
            for j in range(h):
                if j >= 1 and 1 << (j-1) & state:
                    current += 1
                if L_trans[i][j]:
                    separated[i][current] += 1
        previous = [0] * (bit_count + 1)
        cnt = 0
        
        for i in range(w):
            if any(map(lambda x: x > k, separated[i])):
                break
            if all(map(lambda x: x <= k, [elm + previous[ind] for ind, elm in enumerate(separated[i])])):
                
                for ind, elm in enumerate(separated[i]):
                    previous[ind] += elm    
            else:
                cnt += 1
                
                for ind, elm in enumerate(separated[i]):
                    previous[ind] = elm    
        else:
            cost[state] = bit_count + cnt
    
    print(min(cost))
                

if __name__ == "__main__":
    main()