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



Sample input:
3 5 4
11100
10001
00111


Sample output:
2

Submission status: Wrong Answer

Solution code:
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
            if countA[j] + A[j][i] > K:
                sepCounter +=1
                j=-1
                for k in range(0,bitcounter+1,1):
                    countA[k]=0
            else:
                countA[j] += A[j][i]

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

print(minimum)

Submission status: Wrong Answer

Solution code:
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
            if countA[j] + A[j][i] > K:
                sepCounter +=1
                j=-1
                for k in range(0,bitcounter+1,1):
                    countA[k]=0
                
            countA[j] += A[j][i]

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

print(minimum)

Submission status: Wrong Answer

Solution code:
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
            if countA[j] + A[j][i] > K:
                sepCounter +=1
                j=-1
                for i in range(0,bitcounter+1,1):
                    countA[i]=0
                
            countA[j] += A[j][i]

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

print(minimum)

Submission status: Wrong Answer

Solution code:
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
            if countA[j] + A[j][i] > K:
                sepCounter +=1
                j=0
                for i in range(0,bitcounter+1,1):
                    countA[i]=0
                
            countA[j] += A[j][i]

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

print(minimum)

Submission status: Wrong Answer

Solution code:
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):
        wattabakka = False
        if i == 0:
            wattabakka = True
        for j in range(0,bitcounter+1,1):
            if A[j][i] > K:
                dame = True
            if countA[j] + A[j][i] > K:
                if wattabakka:
                    dame = True
                wattabakka = True
                sepCounter +=1
                j=0
                for i in range(0,bitcounter+1,1):
                    countA[i]=0
                
            countA[j] += A[j][i]

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

print(minimum)

Submission status: Wrong Answer

Solution code:
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):
        wattabakka = False
        for j in range(0,bitcounter+1,1):
            if countA[j] + A[j][i] > K:
                if wattabakka:
                    dame = True
                wattabakka = True
                sepCounter +=1
                j=0
                for i in range(0,bitcounter+1,1):
                    countA[i]=0
                
            countA[j] += A[j][i]

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

print(minimum)

Submission status: Wrong Answer

Solution code:
H,W,K = map(int,input().split(sep=" "))
S = [list(map(int,list(input()))) for i in range(0,H,1)]
minimum = 0
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
    for i in range(0,W,1):
        for j in range(0,bitcounter+1,1):
            if countA[j] + A[j][i] > K:
                sepCounter +=1
                j=0
                for i in range(0,bitcounter+1,1):
                    countA[i]=0
                
            countA[j] += A[j][i]

    if sepH == 0:
        minimum = bitcounter + sepCounter
    
    if bitcounter+sepCounter < minimum:
        minimum = bitcounter +sepCounter

print(minimum)

Submission status: Wrong Answer

Solution code:
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=nx
              cnt+=1
          if (i>>h)&1:
            j+=1
        if f==0:
          break
    if f:
      ans=min(ans,cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
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)
        cho[j]+=int(S[0][w])
        nx[j]+=int(S[0][w])
        for h in range(1,H):
            if (i>>(h-1))&1:
                j+=1
            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=nx
                    cnt+=1
        if f==0:
          break
    if f:
      ans=min(ans,cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
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
        s=0
        nx=[0]*(x+1)
        cho[j]+=int(S[0][w])
        nx[j]+=int(S[0][w])
        for h in range(1,H):
            if (i>>(h-1))&1:
                j+=1
                s=0
            cho[j]+=int(S[h][w])
            nx[j]+=int(S[h][w])
            s+=int(S[h][w])
            if cho[j]>K:
                if s>K:
                    f=0
                    break
                else:
                    cho=nx
                    cnt+=1
        if f==0:
          break
    if f:
      ans=min(ans,cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
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  # 1e17
mod = 998244353


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


height, wide, maxx = map(int, input().split())
A = []
for i in range(height):
    A.append(input().strip())
# for binary in range(1<<(height-1),(1<<(height-1))+1):
ans = inf
for binary in range(1 << (height - 1)):  # every binary
    S = two(binary)
    B = [-1]
    for i in range(len(S)):
        if S[i] == "1":
            B.append(i)
    B.append(len(S) - 1)  # every horizontal cut, contain the head and the tail
#    print(B)
    SUM = [0] * (len(B))
    isok = 1
    cut_vertical = 0
    cut_horizontal = len(B) - 2
    for i in range(wide):
        PRE = copy(SUM)  # previous total numbers between every cut
        for j in range(1, len(B)):  # every cut
            for k in range(B[j - 1] + 1, B[j] + 1):
                if A[k][i] == "1":
                    SUM[j] += 1
        flag = 0
        for j in range(1, len(B)):
            if SUM[j] > maxx:
                flag = 1
        if flag:
            for j in range(1, len(B)):
                SUM[j] -= PRE[j]
            cut_vertical += 1
        for j in range(1, len(B)):
            if SUM[j] > maxx:
                isok = 0
        if isok == 0:
            break
    if isok:
        ans = min(ans, cut_vertical + cut_horizontal)
print(ans)

Submission status: Wrong Answer

Solution code:
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#Trueのままならnewを足し算
        for column in range(h):
            if new[bit][column]+size[bit][column]>k:
                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))

Submission status: Wrong Answer

Solution code:
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))]
        nex = [[0 for _ in range((checker+1))] for _ in range(w)]
        p = 0
        for j in range(h):
            for J in range(w):
                nex[J][p] += s[j][J]
            p += num%2
            num = num >> 1
            if max(nex[j]) > k:
                x = 10**6
                break
        for j in range(w):
            if all(nex[j][m]+c[m] <= k for m in range(checker+1)):
                c = [c[I]+nex[j][I] for I in range(checker+1)]
            else:
                x += 1
                c = nex[j]
        result.append(checker+x)
print(min(result))

Submission status: Wrong Answer

Solution code:
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 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 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))

Submission status: Wrong Answer

Solution code:
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 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))

Submission status: Wrong Answer

Solution code:
h, w, k = map(int, input().split())
s = [list(map(int, list(input()))) for _ in range(h)]
result = []
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 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))

Submission status: Wrong Answer

Solution code:
h, w, k = map(int, input().split())
s = [list(map(int, list(input()))) for _ in range(h)]
result = []
for i in range(2**(h-1)):
    checker, num = 0, i
    while num > 0:
        checker += num%2
        num >>= 1
    checker = format(i, "0"+str(h)+"b").count("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 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))

Submission status: Wrong Answer

Solution code:
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]
    for c in range(1, W + 1):
        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:
            vcuts.append(c - 1)
    vcuts.append(W)
    ans = min(ans, len(hcuts) - 2 + len(vcuts) - 2)
print(ans)

Submission status: Wrong Answer

Solution code:
#E
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
                    break
    
    ans = min(ans,count)
    
print(ans)

Submission status: Wrong Answer

Solution code:
#E
H,W,K = map(int,input().split())
S = [list(str(input())) for _ in range(H)]

count = 0
for slist in S:
    for s in slist:
        if s == "1":
            count+=1
            
ans = 0
n = 1
while True:
    if count/n <= K:
        break
    else:
        n*=2
        ans+=1
        
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    h, w, k = map(int, input().split())
    s = [list(map(int, input())) for _ in range(h)]
    patterns = [None]*(2**9)
    ands = [2**i for i in range(9)]
    for i in range(2**9):
        pattern = []
        for j, l in enumerate(ands, 1):
            if i & l:
                pattern.append(j)
        patterns[i] = pattern
    anses = 10**10
    cnt = 0
    ans = 0
    # old+1行目からp行目まで
    for i in zip(*s[:]):
        num = sum(i)
        if num > k:
            flag = True
            break
        if num + cnt > k:
            cnt = num
            ans += 1
        cnt += num
    anses = min(anses, ans)
    for pattern in patterns[1:]:
        old = 0
        ans = 0
        flag = False
        for p in pattern:
            cnt = 0
            # old+1行目からp行目まで
            for i in zip(*s[old:p]):
                num = sum(i)
                if num > k:
                    flag = True
                    break
                if num + cnt > k:
                    cnt = num
                    ans += 1
                cnt += num
            if flag:
                break
            old = p
        if flag:
            continue
        anses = min(anses, ans+len(pattern))
    print(anses+1)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
# import math
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product                # product(iter, repeat=n)
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4


def main():
    mod = 1000000007                  # 10^9+7
    inf = float('inf')
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    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
        # print(separated)
        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])])):
                # print(f"just add: {previous} {separated[i]}")
                for ind, elm in enumerate(separated[i]):
                    previous[ind] += elm    # 追加
            else:
                cnt += 1
                # print(f"count up: {previous} {separated[i]}")
                for ind, elm in enumerate(separated[i]):
                    previous[ind] = elm    # 上書き
        else:
            cost[state] = bit_count + cnt
    print(cost)
    print(min(cost))
                

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
# import math
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product                # product(iter, repeat=n)
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4


def main():
    mod = 1000000007                  # 10^9+7
    inf = float('inf')
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    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
        # print(separated)
        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[ind]):
                    previous[ind] = elm    # 上書き
        else:
            cost[state] = bit_count + cnt
    # print(cost)
    print(min(cost))
                

if __name__ == "__main__":
    main()