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:
n, m, k = map(int, input().split())
field = []
sum = []
def give_cnt(x1, y1, x2, y2):
    count = sum[i + 1][pos_w + 1] - sum[prev_h][prev_w] - sum[prev_h][prev_w] + \
            sum[prev_h][prev_w]
    return count

for i in range(n + 1):
    lst = []
    for j in range(m + 1):
        lst.append(0)
    sum.append(lst)
for i in range(n):
    field.append(input())
for i in range(n + 1):
    for j in range(m + 1):
        if i == 0 or j == 0:
            sum[i][j] = 0
        else:
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] + (field[i - 1][j - 1] == '1') - sum[i - 1][j - 1]
min_ans = 1000000000000
for prof in range(1, 2 ** n):
    raz = []
    for i in range(0, 10):
        mask = 1 << i
        if prof & mask:
            raz.append(i)
    ans = len(raz)
    raz.append(n - 1)
    prev_w = 0
    pos_w = 0
    cur = 0
    used = [0] * m
    while pos_w < m:
        used[pos_w] += 1
        prev_h = 0
        flag = 0
        for i in raz:
            count = sum[i + 1][pos_w + 1] - sum[prev_h][pos_w + 1] - sum[i + 1][prev_w + 1] + sum[prev_h][prev_w + 1]
            if count > k:
                flag = 1
            prev_h = i + 1
        if flag:
            ans += 1
            if used[pos_w] < 2:
                pos_w -= 1
                prev_w = pos_w
        pos_w += 1
    min_ans = min(min_ans, ans - 1)
print (ans)

Submission status: Wrong Answer

Solution code:
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
    ans = min(ans,k+l-2)

print(ans)

Submission status: Wrong Answer

Solution code:
H,W,K = map(int,input().split())
A = []
for i in range(H):
    b = list(input())
    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-1:
                    pross = min(pross,j-W_start)
                    break
            H_start = sec[i] + 1

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

print(ans)

Submission status: Wrong Answer

Solution code:
H,W,K = map(int,input().split())
A = []
for i in range(H):
    b = list(input())
    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-1:
                    pross = min(pross,j-W_start)
                    break
            H_start = sec[i] + 1

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

print(ans)

Submission status: Wrong Answer

Solution code:
H,W,K = map(int,input().split())
S = [input() for _ in range(H)]
ans=H+W
      
def greedy(a,H_b):
  rep=0
  A=[0 for _ in range(a+1)]
  for i in range(W):
    k=0    
    flag=0
    for j,b in enumerate(H_b):
      if S[j][i]=="1":
        A[k]+=1
        if A[k]==K:
          if i!=W-1:
            rep+=1
          flag=1
        if A[k]>K:
          return float("inf")
      if b=="1":
        k+=1
    if flag==1:
      A=[0 for _ in range(a+1)]
        
  return rep

for i in range(2**(H-1)+1):
  H_b = format(i, "0"+str(H)+'b')
  a=H_b.count("1")
  ans=min(ans,a+greedy(a,H_b))
print(ans)

Submission status: Wrong Answer

Solution code:
H,W,K = map(int,input().split())
A = []
for i in range(H):
    b = list(input())
    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
            while(True):
                c = 0
                for t in range(H_start,H_end):
                    if A[t][j] == 1:
                        c += 1
                j += 1
                if c > 4 or j > W-1:
                    pross = min(pross,j-W_start)
                    break
            H_start = sec[i] + 1

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

print(ans)

Submission status: Wrong Answer

Solution code:
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])
        
            
    #print(Wcount)
    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
        for w in range(W):
            for b in range(Hcount + 1):
                if Wcount[B[b+1]][w+1] - Wcount[B[b+1]][leftbound] - Wcount[B[b]][w+1] + Wcount[B[b]][leftbound] > K:
                    if leftbound + 1 == w: 
                        TotalBound = H * W + 1
                    else:
                        TotalBound += 1
                        leftbound = w
                    break
            if TotalBound == H * W + 1: break
        else: Ans = min(TotalBound, Ans)
        #print(i, B, TotalBound)
    print(Ans)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
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])
        
            
    #print(Wcount)
    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
        for w in range(W):
            for b in range(Hcount + 1):
                if Wcount[B[b+1]][w+1] - Wcount[B[b+1]][leftbound] - Wcount[B[b]][w+1] + Wcount[B[b]][leftbound] > K:
                    if leftbound + 1 == w: 
                        TotalBound = H * W + 1
                        break
                    else:
                        TotalBound += 1
                        leftbound = w
            if TotalBound == H * W + 1: break
        else: Ans = min(TotalBound, Ans)
        #print(i, B, TotalBound)
    print(Ans)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
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):
            # Kより大きい値を加算する場合は不成立
            if any(a > K for a in col):
                impossible = True
                break
            for i, a in enumerate(col):
                count[i] += a
                # 和がKより大きければカット数を増やす
                if count[i] > K:
                    x += 1
                    count = list(col) 
                    break
        if impossible:
            x = 10**6
            break

        ans = min(ans, x + ly)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np
import itertools

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

arr = np.array(choco)

# W方向にGREEDY
count = (H-1) + (W-1)

for cho in choco:
    print(cho)

for k in range(H):
    print(k)
    
    # この時点で同じ回数以上切ることが確定なら終了
    if count <= k:
        break

    # H 方向に切り込み
    for comb in itertools.combinations(range(1,H),k):

        # スライスを作っておく
        t = (None,) + comb + (None,)
        s = [slice(t[j],t[j+1],) for j in range(len(t)-1)]
        
        # print(t)
        
        sum_p = [0] * (k+1)
        
        cut = k
        
        for col in zip(*choco):

            # 各ブロック毎の合計を算出
            sum_a = [sum(col[b]) for b in s]
            
            # K を超えるブロックが存在していないか？
            if any(map(K.__lt__, sum_a)):
                # 不成立
                break
            
            # 前まで分割されていないブロックと合わせて、合計を算出
            
            sum_b = [x + y for x,y in zip(sum_p, sum_a)]
            print(k, sum_b)

            if any(map(K.__lt__, sum_b)):
                cut += 1
                sum_p = sum_a
            else:
                sum_p = sum_b
                
                # 割った位置を記録
        
        else:
            count = min(count,cut)

print(count)

Submission status: Wrong Answer

Solution code:
import numpy as np
H, W, K = map(int, input().split())
S = np.zeros((H, W))
for i in range(H):
    S[i] = np.array(list(map(int, list(input()))))

ans = 2000
for k in range(2 * (H-1)):
    count = 0
    k_ = k
    while k_ > 0:
        if k_ % 2 == 1:
            count += 1
        k_ //= 2
#     print(count)

    white = np.zeros(H)
    for w in range(W):
        k_ = k
        ind = 0
        retu = np.zeros(H)
        for h in range(H):
            retu[ind] += S[h][w]
            if k_ % 2 == 1:
                ind += 1
            k_ //= 2
        white += retu
        if any(white > K):
            if any(retu > K):
                count = 2000
                break
            count += 1
            white = retu
#         print(white)
    ans = min(ans, count)
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
import itertools

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

arr = np.array(choco)

# W方向にGREEDY
count = (H-1) + (W-1)

for k in range(H):
    
    # この時点で同じ回数以上切ることが確定なら終了
    if count <= k:
        break

    # H 方向に切り込み
    for comb in itertools.combinations(range(1,H),k):

        # スライスを作っておく
        t = (None,) + comb + (None,)
        s = [slice(t[j],t[j+1],) for j in range(len(t)-1)]
        
        # print(t)
        
        sum_p = [0] * (k+1)
        
        cut = k
        
        for col in zip(*choco):
                        
            # 全 H で成立するか？
            sum_a = [sum(col[b]) for b in s]
            # print(sum_a)
            
            if any(map(K.__lt__, sum_a)):
                # 不成立
                break
            
            sum_b = [x+y for x,y in zip(sum_p, sum_a)]

            if any(map(K.__lt__, sum_b)):
                cut += 1
                sum_p = [0] * (k+1)
            else:
                sum_p = sum_b
                
                # 割った位置を記録
        
        else:
            count = min(count,cut)

print(count)

Submission status: Wrong Answer

Solution code:
import numpy as np
import itertools

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

arr = np.array(choco)

# W方向にGREEDY
print(H, W, K)
count = (H-1) + (W-1)

for k in range(H):
    
    # この時点で同じ回数以上切ることが確定なら終了
    if count <= k:
        break

    # H 方向に切り込み
    for comb in itertools.combinations(range(1,H),k):

        # スライスを作っておく
        t = (None,) + comb + (None,)
        s = [slice(t[j],t[j+1],) for j in range(len(t)-1)]
        
        # print(t)
        
        sum_p = [0] * (k+1)
        
        cut = k
        
        for col in zip(*choco):
                        
            # 全 H で成立するか？
            sum_a = [sum(col[b]) for b in s]
            # print(sum_a)
            
            if any(map(K.__lt__, sum_a)):
                # 不成立
                break
            
            sum_b = [x+y for x,y in zip(sum_p, sum_a)]

            if any(map(K.__lt__, sum_b)):
                cut += 1
                sum_p = [0] * (k+1)
            else:
                sum_p = sum_b
                
                # 割った位置を記録
        
        else:
            count = min(count,cut)

print(count)

Submission status: Wrong Answer

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

L = [[0]*(W) for _ in range(H)]
for i in range(H):
    for j in range(W):
        if S[i][j] == "1":
            L[i][j] = 1
        
ans = H*W
for i in range(2**(H-1)):
    cnt = 0
    used = [0]*W
    memo = []
    for j in range(H-1):
        if i & (1<<j):
            cnt += 1
            memo.append(j+1)
    memo.append(H)
    num = [0]*(cnt+1)
    for j in range(W):
        idx = 0
        for k in range(H):
            if memo[idx] == k:
                idx += 1
            num[idx] += L[k][j]
        f = False
        for k in range(len(num)):
            if num[k] > K:
                f = True
                break
        if f:
            if j == 0 or used[j-1] == 1:
                break
            used[j-1] = 1
            cnt += 1
            num = [0]*len(num)
            idx = 0
            for k in range(H):
                if memo[idx] == k:
                    idx += 1
                num[idx] += L[k][j]
    ans = min(ans, cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import *
H, W, K = map(int, input().split())
S = [list(map(int, input())) for i in range(H)]
ans = 100000
for p in product([0,1],repeat=H-1):
    tmp_ans = sum(p)
    index = []
    for i,j in enumerate(p):
        if j == 1:
            index.append(i+1)
    count = [0] * (len(index) +1)
    for w in range(W):
        plate = [yoko[w] for yoko in S]
        tmp = [0]*(len(index)+1)
        if index == []:
            tmp[0] = sum(plate)
        else:
            tmp[0] = sum(plate[0:index[0]])
            for itr in range(len(index)):
                if itr == len(index) -1:
                    tmp[itr+1] += sum(plate[index[itr]:])
                else:
                    tmp[itr+1] += sum(plate[index[itr]:index[itr+1]])
        tmp_sum = [x+y for (x,y) in zip(count,tmp)]
        if max(tmp_sum) >= K:
            tmp_ans +=1
            count = tmp
        else:
            count = tmp_sum
    if tmp_ans < ans:
        ans = tmp_ans

print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import *
H, W, K = map(int, input().split())
S = [list(map(int, input())) for i in range(H)]
ans = 100000
for p in product([0,1],repeat=H-1):
    tmp_ans = sum(p)
    index = []
    for i,j in enumerate(p):
        if j == 1:
            index.append(i+1)
    count = [0] * (len(index) +1)
    for w in range(W):
        plate = [yoko[w] for yoko in S]
        tmp = [0]*(len(index)+1)
        if index == []:
            tmp[0] = sum(plate)
        else:
            tmp[0] = sum(plate[0:index[0]])
            for itr in range(len(index)):
                if itr == len(index) -1:
                    tmp[itr+1] += sum(plate[index[itr]:])
                else:
                    tmp[itr+1] += sum(plate[index[itr]:index[itr+1]])
        tmp_sum = [x+y for (x,y) in zip(count,tmp)]
        if max(tmp_sum) > K:
            tmp_ans +=1
            count = tmp
        else:
            count = tmp_sum
    if tmp_ans < ans:
        ans = tmp_ans

print(ans)

Submission status: Wrong Answer

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

# 縦に割るインデックスを管理
column = set()
tmp = [0] * H
for w in range(W):
    for h in range(H):
        if choco[h][w] == "1":
            tmp[h] += 1
        if tmp[h] > K:
            column.add(w)
            tmp = [0] * H


ans = len(column)
column_idx = [0] * W
for w in range(1, W):
    if w in column:
        column_idx[w] = column_idx[w-1] + 1
    else:
        column_idx[w] = column_idx[w-1]

# 全探索して横方向にインデックスを管理する
row = []
for i in range(2**(H-1)):
    tmp = set()
    for j in range(2**H):
        if (i >> j) & 1:
            tmp.add(j+1)
    row.append(tmp)

row_idx = [[0] * W for _ in range(len(row))]
for i, r in enumerate(row):
    for h in range(1, H):
        if h in r:
            row_idx[i][h] = row_idx[i][h-1] + 1
        else:
            row_idx[i][h] = row_idx[i][h]

min_row = 100
for row_set in row_idx:
    cnt = [[0] * W for _ in range(H)]
    judge = True
    for h in range(H):
        for w in range(W):
            if choco[h][w] == "1":
                cnt[row_set[h]][column_idx[w]] += 1
            if cnt[row_set[h]][column_idx[w]] > K:
                judge = False
                break
    if judge:
        min_row = min(min_row, max(row_set))



print(ans+min_row)
#https://atcoder.jp/contests/abc159/tasks/abc159_e

Submission status: Wrong Answer

Solution code:
import numpy as np


INF = 1e40


def main():
    # input
    h, w, k = [int(v) for v in input().split(' ')]
    arr = np.zeros((h, w), np.uint8)
    for i in range(h):
        arr[i, :] = np.array([int(c) for c in input()], np.uint8)

    ans = INF
    for i in range(2 ** (h - 1)):
        g = int(0)
        g_arr = np.zeros((h, w), np.uint8)
        for j in range(h):
            g_arr[g, :] += arr[j, :]
            if (i >> j) & 1:
                g += 1
        g += 1
        g_arr = g_arr[:g, :]

        count = np.zeros(g)
        for j in range(w):
            if np.max(g_arr[:, j]) > k:
                g = INF
                break

            count += g_arr[:, j]
            if np.max(count) > k:
                count = g_arr[:, j]
                g += 1
        ans = min(ans, g - 1)

    print(int(ans))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np


INF = 1e20


def main():
    # input
    h, w, k = [int(v) for v in input().split(' ')]
    arr = np.zeros((h, w), np.uint8)
    for i in range(h):
        arr[i, :] = np.array([int(c) for c in input()], np.uint8)

    ans = INF
    for i in range(2 ** (h - 1)):
        g = 0
        g_arr = np.zeros((h, w), np.uint8)
        for j in range(h):
            g_arr[g, :] += arr[j, :]
            if (i >> j) & 1:
                g += 1
        g += 1
        g_arr = g_arr[:g, :]

        count = np.zeros(g)
        for j in range(w):
            if np.max(g_arr[:, j]) > k:
                g = INF
                break

            count += g_arr[:, j]
            if np.max(count) > k:
                count = g_arr[:, j]
                g += 1
        else:
            ans = min(ans, g - 1)

    print(int(ans))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np


INF = 1e10


def main():
    # input
    h, w, k = [int(v) for v in input().split(' ')]
    arr = np.zeros((h, w), np.uint8)
    for i in range(h):
        arr[i, :] = np.array([int(c) for c in input()], np.uint8)

    ans = INF
    for i in range(2 ** (h - 1)):
        g = 0
        g_arr = np.zeros((h, w), np.uint8)
        for j in range(h):
            g_arr[g, :] += arr[j, :]
            if (i >> j) & 1:
                g += 1
        g += 1
        g_arr = g_arr[:g, :]

        count = np.zeros(g)
        for j in range(w):
            if np.max(g_arr[:, j]) > k:
                g = INF
                break

            count += g_arr[:, j]
            if np.max(count) > k:
                count = g_arr[:, j]
                g += 1
        ans = min(ans, g - 1)

    print(int(ans))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np


INF = 1e10


def main():
    # input
    h, w, k = [int(v) for v in input().split(' ')]
    arr = np.zeros((h, w), np.uint8)
    for i in range(h):
        arr[i, :] = np.array([int(c) for c in input()], np.uint8)

    ans = INF
    for i in range(2 ** (h - 1)):
        g = 0
        g_arr = np.zeros((h, w), np.uint8)
        for j in range(h):
            g_arr[g, :] += arr[j, :]
            if (i >> j) & 1:
                g += 1
        g += 1
        g_arr = g_arr[:g, :]

        count = np.zeros(g)
        for j in range(w):
            if np.max(g_arr[:, j]) > k:
                break

            count += g_arr[:, j]
            if np.max(count) > k:
                count = g_arr[:, j]
                g += 1
        ans = min(ans, g - 1)

    print(int(ans))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np


INF = 1e10


def main():
    # input
    h, w, k = [int(v) for v in input().split(' ')]
    arr = np.zeros((h, w), np.uint8)
    for i in range(h):
        arr[i, :] = np.array([int(c) for c in input()], np.uint8)

    ans = INF
    for i in range(2 ** (h - 1)):
        g = 0
        g_arr = np.zeros((h, w), np.uint8)
        for j in range(h):
            g_arr[g, :] += arr[j, :]
            if (i >> j) & 1:
                g += 1
        g += 1
        g_arr = g_arr[:g, :]

        count = np.zeros(g)
        for j in range(w):
            if np.max(g_arr[:, j]) > k:
                continue

            count += g_arr[:, j]
            if np.max(count) > k:
                count = g_arr[:, j]
                g += 1
        ans = min(ans, g - 1)

    print(int(ans))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
h,w,K = map(int,input().split())
sij = [input() for j in range(h)]

num = 2**(h-1)
hon = 10**18

for i in range(num):
    tmp = format(i,'0'+str(h)+'b')
    #print(tmp,tmp,tmp,tmp)
    yoko_hon = sum(list(map(int,tmp)))+1
    blk = [0]*(yoko_hon)
    #blk_num = 0
    tmp_col = 0
    tmp_hon = yoko_hon-1
    flag = True
    ok_flag = True
    for j in range(w):
        tmp_blk = [0]*(yoko_hon)
        blk_num = 0
        for k in range(h):
            if tmp[k] == str(1):
                blk_num += 1
            #print(blk_num,tmp_blk)
            tmp_blk[blk_num] += int(sij[k][j])
            #print(blk[blk_num] , tmp_blk[blk_num],k)
            if blk[blk_num] + tmp_blk[blk_num] > K:
                flag = False
                if tmp_col == 0:
                    ok_flag = False
                    break
                continue
        
        #print(ok_flag,flag,tmp_blk,blk)
        if ok_flag == False:
            break
        tmp_col += 1
        if flag == False:
            for l in range(yoko_hon):
                blk[l] = tmp_blk[l]
            tmp_hon += 1
            tmp_col = 0
            flag = True
        else:
            for l in range(yoko_hon):
                blk[l] += tmp_blk[l]
            
    if ok_flag == False:
        ok_flag = True
        continue
    #print(hon,tmp_hon)
    #exit()
    hon = min(tmp_hon,hon)
    
print(hon)

Submission status: Wrong Answer

Solution code:
H,W,K=map(int,input().split())
S=[[0 for i in range(W)] for i in range(H)]
for i in range(H):
    s=input()
    for j in range(W):
        S[i][j]=s[j]
ans=10**10
for i in range(0, 2**(H-1)):
    x=[]
    for j in range(0,H-1):
        if i&(1<<j)!=0:
            x.append(j)
    n=[0 for i in range(len(x)+1)]
    tmp=len(x)
    j=0
    while j<W:
        cnt=0
        OK=True
        fin=False
        k=0
        while k<H:
            if S[k][j]=='1':
                n[cnt]+=1
                if n[cnt]>K:
                    n=[0 for i in range(len(x)+1)]
                    k=0
                    cnt=0
                    tmp+=1
                    if not OK:
                        fin=True
                    if S[k][j]=='1':
                        n[cnt]+=1
                        OK=False
            k+=1
            if k in x:
                cnt+=1
        if fin:
            tmp=10**10
            break
        j+=1
    ans=min(tmp,ans)
print(ans)

Submission status: Wrong Answer

Solution code:
H,W,K = map(int,input().split())
S = [[int(i) for i in input()] for _ in range(H)]
ans = float("inf")

# bit全探索
for i in range(2**(H-1)): 
    start = [0]
    end = []
    for j in range(H-1):
        if i >> j & 1 == 1:
            start.append(j)
            end.append(j)
    end.append(H)
    L = len(end)
    # 横に割った回数
    divcnt = L-1
    # 横に割った区割りごとの白チョコの個数
    wcnt = [0]*L
    # 探索列の横に割った区割りごとの白チョコの個数
    tmp = [0]*L
    for w in range(W):
        # 探索列の直前で縦に割ったか
        flag = False
        for idx in range(L):
            cnt = 0
            for h in range(start[idx],end[idx]):
                cnt += S[h][w]
            tmp[idx] = cnt
            wcnt[idx] += cnt
            if wcnt[idx] > K:
                flag = True
        if flag:
            # 縦に割ったらその列から数え直し
            wcnt = tmp[:]
            divcnt += 1
    ans = min(ans,divcnt)

print(ans)

Submission status: Wrong Answer

Solution code:
H,W,K = map(int,input().split())
S = [[int(i) for i in input()] for _ in range(H)]
ans = float("inf")

# bit全探索
for i in range(2**(H-1)): 
    start = [0]
    end = []
    for j in range(H-1):
        if i >> j & 1 == 1:
            start.append(j)
            end.append(j)
    end.append(H)
    L = len(end)
    # 横に割った回数
    divcnt = L-1
    # 横に割った区割りごとの白チョコの個数
    wcnt = [0]*L
    # 探索列の横に割った区割りごとの白チョコの個数
    tmp = [0]*L
    for w in range(W):
        # 探索列の直前で縦に割ったか
        flag = False
        for idx in range(L):
            cnt = 0
            for h in range(start[idx],end[idx]):
                cnt += S[h][w]
                if cnt > K: break
            else:
                tmp[idx] = cnt
                wcnt[idx] += cnt
                if wcnt[idx] > K: flag = True
                continue
            break
        else:
            if flag:
                # 縦に割ったらその列から数え直し
                wcnt = tmp[:]
                divcnt += 1
            continue
        break
    else:
        ans = min(ans,divcnt)

print(ans)

Submission status: Wrong Answer

Solution code:
H,W,K = map(int,input().split())
S = [[int(i) for i in input()] for _ in range(H)]
ans = float("inf")

# bit全探索
for i in range(2**(H-1)): 
    start = [0]
    end = []
    for j in range(H-1):
        if i >> j & 1 == 1:
            start.append(j)
            end.append(j)
    end.append(H)
    L = len(end)
    # 横に割った回数
    divcnt = L-1
    # 横に割った区割りごとの白チョコの個数
    wcnt = [0]*L
    # 探索列の横に割った区割りごとの白チョコの個数
    tmp = [0]*L
    for w in range(W):
        # 探索列の直前で縦に割ったか
        flag = False
        for idx in range(L):
            cnt = 0
            for h in range(start[idx],end[idx]):
                cnt += S[h][w]
            tmp[idx] = cnt
            wcnt[idx] += cnt
            if wcnt[idx] > K:
                flag = True
        if flag:
            # 縦に割ったらその列から数え直し
            wcnt = tmp[:]
            divcnt += 1
    ans = min(ans,divcnt)

print(ans)