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:
from collections import deque

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


def cut(bit):

    """
    横の切れ目の場所をビットで管理する。
    "00...0" <= bit <= "11...1"(H - 1桁)の時に、縦に入れる切れ目の最小回数を返す。
    """

    end = [] # 板チョコを横区切りにした結果、上から何段目で各板チョコのピースが終わるか
    for i in range(H - 1):
        if bit[i] == '1':
            end.append(i)
    end.append(H - 1)
    chocolates = [0] * (len(end))
    #print("end={}".format(end))

    """
    ここまでで板チョコを横に切ったわけだが、こうして分割した横長の部分板チョコを
    上からsection = 0, 1, 2,..., len(end)-1と呼び分けることにする。
    """

    cut = 0
    whites_sum = [0] * len(end) # w列目までの白チョコの累積数をsectionごとに管理。cutが入れば初期化。
    for w in range(W):
        whites = [0] * len(end) # whites[section] = (w列目にある白チョコをsectionごとに保存)
        section = 0 # 現在のsection
        coarse = False # 横切りが荒過ぎて１列に白チョコがK個より多く並んだ場合に探索を打ち切るフラグ

        for h in range(H + 1):
            # sectionを跨いだ場合の処理
            if h > end[section]:
                if whites[section] > K:
                    coarse = True
                    break
                elif whites_sum[section] + whites[section] > K:
                    cut += 1
                    whites_sum = whites
                else:
                    whites_sum[section] += whites[section]
                    section += 1

            # 白チョコカウント
            if h < H and S[h][w] == '1':
                whites[section] += 1

        # coarseフラグが立っていたら-1を返す。
        if coarse:
            return -1
    return cut


ans = 10 ** 10
for h in range(2 ** (H - 1)):
    bit = bin(h)[2:] # "0b..."を除くため
    l = len(bit)
    bit = '0' * (H - 1 - l) + bit # bitの桁数をH - 1にする。
    #print("bit={}".format(bit))

    vertical_cuts = cut(bit)
    if vertical_cuts != -1:
        preans = vertical_cuts + bit.count('1')
        ans = min(ans, preans)
        #print("cut={}->ans={}".format(preans, ans))


print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

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


def cut(bit):

    """
    横の切れ目の場所をビットで管理する。
    "00...0" <= bit <= "11...1"(H - 1桁)の時に、縦に入れる切れ目の最小回数を返す。
    """

    end = [] # 板チョコを横区切りにした結果、上から何段目で各板チョコのピースが終わるか
    for i in range(H - 1):
        if bit[i] == '1':
            end.append(i)
    end.append(H - 1)
    chocolates = [0] * (len(end))
    #print("end={}".format(end))

    """
    ここまでで板チョコを横に切ったわけだが、こうして分割した横長の部分板チョコを
    上からsection = 0, 1, 2,..., len(end)-1と呼び分けることにする。
    """

    cut = 0
    whites_sum = [0] * len(end) # w列目までの白チョコの累積数をsectionごとに管理。cutが入れば初期化。
    for w in range(W):
        whites = [0] * len(end) # whites[section] = (w列目にある白チョコをsectionごとに保存)
        section = 0 # 現在のsection
        coarse = False # 横切りが荒過ぎて１列に白チョコがK個より多く並んだ場合に探索を打ち切るフラグ

        for h in range(H + 1):
            # sectionを跨いだ場合の処理
            if h > end[section]:
                if whites[section] > K:
                    coarse = True
                    break
                elif whites_sum[section] + whites[section] > K:
                    cut += 1
                    whites_sum = whites
                else:
                    whites_sum[section] += whites[section]
                    section += 1

            # 白チョコカウント
            if h < H and S[h][w] == '1':
                whites[section] += 1

        # coarseフラグが立っていたら-1を返す。
        if coarse:
            return -1
    return cut + bit.count('1')


ans = 10 ** 10
for h in range(2 ** (H - 1)):
    bit = bin(h)[2:] # "0b..."を除くため
    l = len(bit)
    bit = '0' * (H - 1 - l) + bit # bitの桁数をH - 1にする。
    #print("bit={}".format(bit))
    preans = cut(bit)
    ans = min(ans, preans)
    #print("cut={}->ans={}".format(preans, ans))

print(ans)

Submission status: Wrong Answer

Solution code:
#E
h, w, K = map(int, input().split())
ans = 1000000
choco = []
for i in range(h):
    l = list(str(input()))
    p = []
    for j in range(w):
        z = int(l[j])
        p.append(z)

    choco.append(p)

if h == 1:
    cou = 0
    for i in range(w):
        if choco[i] == 1:
            cou += 1
    print(cou // k)
else:
    for i in range(1<<h-1):
        #print(i)
        sep = [] #境界
        for j in range(h-1):
            q = 2 ** (h-2-j)
            #print(i)
            #print(q)
            sep.append(i // q)
            if (i // q) == 1:
                i -= q

        sep.append(1)
        #print(sep) #ランダムに仕切りができてるか確認
        tsep = -1

        LI = [[0] * w for _ in range(h)] #横の仕切りで分けられた範囲内の各列のwhiteの和
        cou = 0 #LIのどの行に足していくか
        for j in range(h):
            s = choco[j]
            for k in range(w):
                LI[cou][k] += s[k]

            if sep[j] == 1:
                tsep += 1
                cou += 1

        #print(cou)
        #print(LI)
        SUML = [0 for _ in range(cou)]
        for i in range(w):
            over = False
            for j in range(cou):
                if (SUML[j] + LI[j][i]) > K:
                    tsep += 1
                    over = True
                    #print('over')
                    break
                else:
                    SUML[j] += LI[j][i]
                    #print('within')

            if over:
                for k in range(cou):
                    SUML[k] = LI[k][i]
            #print(SUML)
        for i in range(h):#そもそも1列でoverするケースはだめなので排除
            for j in range(w):
                if LI[i][j] > K:
                    tsep = 1000000
                    break
            else:
                break

        #print(tsep)
        if ans > tsep:
            ans = tsep

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def MAP(): return map(int, input().split())
inf = sys.maxsize

h, w, k = MAP()
s = [[int(i) for i in STR()] for _ in range(h)]

ans = inf
for i in range(2 ** (h - 1)): #縦方向の割り方を全探索 O(500)
    hdiv = [1 for _ in range(h)]
    for j in range(h - 1):
        tmp = 2 ** j
        hdiv[j] = 1 if i & tmp else 0
    sh = sum(hdiv)
    tmpans = sh - 1
    wdiv = [0 for _ in range(w - 1)]
    partsum = [0 for _ in range(sh + 1)]
    j = 0
    cnt = 0
    while j < w: #O(2 * 10 ** 4)
        tmp = 0
        idx = 0
        for kk in range(h): #O(10)
            tmp += s[kk][j]
            if hdiv[kk]:
                partsum[idx] += tmp
                tmp = 0
                idx += 1
        flag = True
        for kk in range(sh + 1):
            if partsum[kk] > k:
                tmpans += 1
                partsum = [0 for _ in range(sh + 1)]
                flag = False
        if flag:
            j += 1
            cnt = 0
        else:
            cnt += 1
        if cnt > 2:
            ans = inf
            break
    ans = min(ans, tmpans)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
inf = sys.maxsize

if __name__ == '__main__':
    h, w, k = map(int, sys.stdin.readline().strip().split())
    s = [[int(i) for i in sys.stdin.readline().strip()] for _ in range(h)]
    
    ans = inf
    for i in range(2 ** (h - 1)): #縦方向の割り方を全探索 O(512)
        hdiv = [1 if i & 2 ** j else 0 for j in range(h - 1)]
        hdiv.append(1)
        sh = sum(hdiv)
        tmpans = sh - 1
        partsum = [0 for _ in range(sh)]
        partsum_p = [0 for _ in range(sh)]
        j = 0
        for j in range(w): #O(10 ** 3)
            tmp = 0
            idx = 0
            flag = False
            for kk in range(h): #O(10)
                tmp += s[kk][j]
                if hdiv[kk]:
                    partsum_p[idx] = partsum[idx]
                    partsum[idx] += tmp
                    if partsum[idx] > k and not flag:
                        tmpans += 1
                        flag = True
                    tmp = 0
                    idx += 1
            if flag:
                partsum = [partsum[l] - partsum_p[l] for l in range(sh)]
                partsum_p = [0 for _ in range(sh)]
        ans = min(ans, tmpans)
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
inf = sys.maxsize

if __name__ == '__main__':
    h, w, k = map(int, sys.stdin.readline().strip().split())
    s = [[int(i) for i in sys.stdin.readline().strip()] for _ in range(h)]
    
    ans = inf
    for i in range(2 ** (h - 1)): #縦方向の割り方を全探索 O(512)
        hdiv = [1 if i & 2 ** j else 0 for j in range(h - 1)]
        hdiv.append(1)
        sh = sum(hdiv)
        tmpans = sh - 1
        partsum = [0 for _ in range(sh)]
        partsum_p = [0 for _ in range(sh)]
        j = 0
        for j in range(w): #O(10 ** 3)
            tmp = 0
            idx = 0
            flag = False
            for kk in range(h): #O(10)
                tmp += s[kk][j]
                if hdiv[kk]:
                    partsum_p[idx] = partsum[idx]
                    partsum[idx] += tmp
                    if partsum[idx] > k:
                        tmpans += 1
                        flag = True
                        break
                    tmp = 0
                    idx += 1
            if flag:
                partsum = [partsum[l] - partsum_p[l] for l in range(sh)]
                partsum_p = [0 for _ in range(sh)]
        ans = min(ans, tmpans)
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
inf = sys.maxsize

if __name__ == '__main__':
    h, w, k = map(int, sys.stdin.readline().strip().split())
    s = [[int(i) for i in sys.stdin.readline().strip()] for _ in range(h)]
    
    ans = inf
    for i in range(2 ** (h - 1)): #縦方向の割り方を全探索 O(512)
        hdiv = [1 if i & 2 ** j else 0 for j in range(h - 1)]
        hdiv.append(1)
        sh = sum(hdiv)
        tmpans = sh - 1
        partsum = [0 for _ in range(sh)]
        partsum_p = [0 for _ in range(sh)]
        j = 0
        for j in range(w): #O(10 ** 3)
            tmp = 0
            idx = 0
            flag = False
            for kk in range(h): #O(10)
                tmp += s[kk][j]
                if hdiv[kk]:
                    partsum_p[idx] = partsum[idx]
                    partsum[idx] += tmp
                    if partsum[idx] > k:
                        tmpans += 1
                        flag = True
                        break
                    tmp = 0
                    idx += 1
            if flag:
                partsum = [partsum[l] - partsum_p[l] for l in range(sh)]
        ans = min(ans, tmpans)
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
from itertools import combinations
def input(): return sys.stdin.readline().strip()
inf = sys.maxsize

if __name__ == '__main__':
    h, w, k = map(int,input().split())
    s = np.array([[int(i) for i in input()] for _ in range(h)])
    ans = inf
    for i in range(h): #縦方向の割り方を全探索 O(512)
        arr = list(combinations(range(h - 1), i))
        for ii in range(len(arr)):
            arr[ii] = list(arr[ii])
            arr[ii].insert(0, 0)
            arr[ii].append(h + 1)
            #print('arr', arr[ii])
            sh = i + 1
            tmpans = i
            partsum = [0 for _ in range(sh)]
            j = 0
            while j < w: #O(2 * 10 ** 3)
                flag = True
                for idx in range(sh):
                    #print('s', s[arr[ii][idx]:arr[ii][idx + 1], j])
                    partsum[idx] += s[arr[ii][idx]:arr[ii][idx + 1], j].sum()
                    #print('partsum', partsum)
                    if partsum[idx] > k:
                        tmpans += 1
                        partsum = [0 for _ in range(sh)]
                        flag = False
                        break
                '''
                tmp = 0
                idx = 0
                for kk in range(h): #O(10)
                    tmp += s[kk][j]
                    if hdiv[kk]:
                        partsum[idx] += tmp
                        if partsum[idx] > k:
                            tmpans += 1
                            partsum = [0 for _ in range(sh)]
                            flag = False
                            break
                        tmp = 0
                        idx += 1
                '''
                if flag:
                    j += 1
            ans = min(ans, tmpans)
    print(ans)

Submission status: Wrong Answer

Solution code:
#E
h, w, K = map(int, input().split())
ans = 1000000
choco = []
for i in range(h):
    l = list(str(input()))
    p = []
    for j in range(w):
        z = int(l[j])
        p.append(z)

    choco.append(p)

if h == 1:
    cou = 0
    for i in range(w):
        if choco[i] == 1:
            cou += 1
    print(cou // k)
else:
    for i in range(1<<h-1):
        #print(i)
        sep = [] #境界
        for j in range(h-1):
            q = 2 ** (h-2-j)
            #print(i)
            #print(q)
            sep.append(i // q)
            if (i // q) == 1:
                i -= q

        sep.append(1)
        #print(sep) #ランダムに仕切りができてるか確認
        tsep = -1

        LI = [[0] * w for _ in range(h)] #境界で分けられた範囲内の各列のwhiteの和
        cou = 0 #LIのどの行に足していくか
        for j in range(h):
            s = choco[j]
            for k in range(w):
                LI[cou][k] += s[k]

            if sep[j] == 1:
                tsep += 1
                cou += 1

        #print(cou)
        #print(LI)
        SUML = [0 for _ in range(cou)]
        for i in range(w):
            over = False
            for j in range(cou):
                if (SUML[j] + LI[j][i]) > K:
                    tsep += 1
                    over = True
                    #print('over')
                    break
                else:
                    SUML[j] += LI[j][i]
                    #print('within')

            if over:
                for k in range(cou):
                    SUML[k] = LI[k][i]
            #print(SUML)
        for i in range(h):
            for j in range(w):
                if LI[i][j] > K:
                    tsep = 1000000
                    break
            else:
                break

        #print(tsep)
        if ans > tsep:
            ans = tsep

print(ans)

Submission status: Wrong Answer

Solution code:
h, w, k = map(int, input().split())
li_hw  = []
for l in range(h):
    a = map(str, input().split())
    li = []
    for i in a:
        li_hw.append(list(i))
all_h = []
score = []
for l in range(2**(h-1)):
    ind = []
    pre = 0
    cut_list=[]
    hline_num = 0
    for n,yn in enumerate(reversed(list(bin(l))[2:])):
        if yn == "1":
            cut_list.append(li_hw[pre:n+1])
            pre = n+1
    cut_list.append(li_hw[pre:h])
    hline_num = list(bin(l)).count("1")
    #print(bin(l)) 
    pred = 0
    wline_num = 0
    #print("list is {}".format(cut_list))
    for y in range(w):
        wcounter_list = []
        for c in cut_list:
            wcounter = 0
            for c2 in c:
                wcounter += c2[pred:y+1].count("1")
            wcounter_list.append(wcounter)
        #print("wcounter{}".format(wcounter_list))
        if max(wcounter_list) > k:
            pred = y
            wline_num += 1
            #print("line between{}and{}".format(y-1, y))
    print("wline{}, hline{}".format(wline_num, hline_num))
    score.append(wline_num+hline_num)
print(min(score))

Submission status: Wrong Answer

Solution code:
#E
h, w, K = map(int, input().split())
ans = 1000000
choco = []
for i in range(h):
    l = list(str(input()))
    p = []
    for j in range(w):
        z = int(l[j])
        p.append(z)

    choco.append(p)

if h == 1:
    cou = 0
    for i in range(w):
        if choco[i] == 1:
            cou += 1
    print(cou // k)
else:
    for i in range(1<<h-1):
        sep = [] #境界
        for j in range(h-1):
            q = 2 ** (h-2-j)
            #print(i)
            #print(q)
            sep.append(i // q)
            if (i // q) == 1:
                i -= q

        sep.append(1)
        #print(sep) #ランダムに仕切りができてるか確認
        tsep = -1

        LI = [[0] * w for _ in range(h)] #境界で分けられた範囲内の各列のwhiteの和
        cou = 0 #LIのどの行に足していくか
        for j in range(h):
            s = choco[j]
            for k in range(w):
                LI[cou][k] += s[k]

            if sep[j] == 1:
                tsep += 1
                cou += 1

        #print(cou)
        #print(LI)
        SUML = [0 for _ in range(cou)]
        for i in range(w):
            over = False
            for j in range(cou):
                if (SUML[j] + LI[j][i]) > K:
                    tsep += 1
                    over = True
                    #print('over')
                    break
                else:
                    SUML[j] += LI[j][i]
                    #print('within')

            if over:
                for k in range(cou):
                    SUML[k] = LI[k][i]
            #print(SUML)

        #print(tsep)
        if ans > tsep:
            ans = tsep

print(ans)

Submission status: Wrong Answer

Solution code:
#E
h, w, K = map(int, input().split())
ans = 1000000
choco = []
for i in range(h):
    l = list(str(input()))
    p = []
    for j in range(w):
        z = int(l[j])
        p.append(z)

    choco.append(p)

if h == 1:
    cou = 0
    for i in range(w):
        if choco[i] == 1:
            cou += 1
    #print(cou // k)
else:
    for i in range(1<<h-1):
        sep = [] #境界
        for j in range(h-1):
            q = 2 ** (h-2-j)
            #print(i)
            #print(q)
            sep.append(i // q)
            if (i // q) == 1:
                i -= q

        sep.append(1)
        #print(sep) #ランダムに仕切りができてるか確認
        tsep = -1

        LI = [[0] * w for _ in range(h)] #境界で分けられた範囲内の各列のwhiteの和
        cou = 0 #LIのどの行に足していくか
        for j in range(h):
            s = choco[j]
            for k in range(w):
                LI[cou][k] += s[k]

            if sep[j] == 1:
                tsep += 1
                cou += 1

        #print(cou)
        #print(LI)
        SUML = [0 for _ in range(cou)]
        for i in range(w):
            over = False
            for j in range(cou):
                if (SUML[j] + LI[j][i]) > K:
                    tsep += 1
                    over = True
                    #print('over')
                    break
                else:
                    SUML[j] += LI[j][i]
                    #print('within')

            if over:
                for k in range(cou):
                    SUML[k] = LI[k][i]
            #print(SUML)

        #print(tsep)
        if ans > tsep:
            ans = tsep

print(ans)

Submission status: Wrong Answer

Solution code:
#E
h, w, K = map(int, input().split())
ans = 1000000
choco = []
for i in range(h):
    l = list(str(input()))
    p = []
    for j in range(w):
        z = int(l[j])
        p.append(z)

    choco.append(p)

if h == 1:
    cou = 0
    for i in range(w):
        if choco[i] == 1:
            cou += 1
    #print(cou // k)
else:
    for i in range(1<<h-1):
        sep = [] #境界
        for j in range(h-1):
            q = 2 ** (h-2-j)
            #print(i)
            #print(q)
            sep.append(i // q)
            if (i // q) == 1:
                i -= q

        sep.append(1)
        #print(sep) #ランダムに仕切りができてるか確認
        tsep = -1

Submission status: Wrong Answer

Solution code:
from itertools import product

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

p = product([0,1],repeat=h-1)
ans = h*w

for i,tfs in enumerate(p):  
  lst = []
  l = S[0].copy()
  for hi in range(h-1):
    if tfs[hi]:
      lst.append(l)
      l = S[hi].copy()
    else:
      for wi in range(w):
        l[wi] += S[hi+1][wi]
  lst.append(l)
  
  count = 0    
  left = 0  
  right = 0
  max_sum = 0    

  while right < w:
    right += 1
    for li in lst:
      max_sum = max(max_sum, sum(li[left:right]))

    if max_sum > k:
      count += 1
      max_sum = 0
      left = right - 1
      right = left

  count += len(lst)-1
  ans = min(ans,count)
print(ans)

Submission status: Wrong Answer

Solution code:
#!python3

import itertools


INF = 10 ** 5

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


def solve(w, l):
    n = len(l) + 1
    ans = 0
    if n == 1:
        dp = 0
        for j in range(W):
            x = w[-1][j]
            if x > K:
                return INF
            dp += x
            if dp > K:
                ans += 1
                dp = x
    else:
        dp = [0] * n
        for j in range(W):
            x = [0] * n
            b = False
            for i in range(n):
                if i == 0:
                    x[0] = w[l[0]][j]
                elif i == n - 1:
                    x[i] = w[-1][j] - w[l[-1]][j]
                else:
                    x[i] = w[l[i]][j] - w[l[i-1]][j]
                if x[i] > K:
                    return INF
                dp[i] += x[i]
                if dp[i] > K:
                    b = True
            if b:
                dp = x
                ans += 1
    return ans


def main():
    w = [S[0]]
    for i in range(1, H):
        w.append([w[i-1][j] + S[i][j] for j in range(W)])

    ans = INF
    num_list = [i for i in range(H - 1)]
    for i in range(H - 1):
        comb_list = itertools.combinations(num_list, i)
        for l in comb_list:
            ans = min(ans, i + solve(w, l))

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import itertools
H, W, K = map(int,input().split())
S = [list(map(int,list(input()))) for _ in range(H)]
def check(k):
    if k <= K:
        return(True)
    else:
        return(False)
        
noans = 0
def make_lst(i):
    global noans, lst, havelst
    temp = S[0][i]
    for h in range(H-1):
        if y[h]:
            lst.append(temp)
            temp = S[h+1][i]
        else:
            temp += S[h+1][i]
    lst.append(temp)
    if check(max(lst)):
        havelst = 1
    else:
        noans = 1
               
def nocut(i):
    global cutnum, lst, havelst
    prelst = []
    temp = S[0][i]
    j = 0
    for h in range(H-1):
        if y[h]:
            lst[j] += temp
            prelst.append(temp)
            j += 1
            temp = S[h+1][i]
        else:
            temp += S[h+1][i]
    prelst.append(temp)
    lst[-1] += temp
    if check(max(lst)):
        return(True)
    else:
        cutnum += 1
        lst = prelst        
                 
ans = float("inf")
cutlst = []    
for y in itertools.product((0, 1), repeat=H-1):
    havelst = 0
    lst = []
    cutnum = sum(y)
    for x in range(W):
        if noans:
            noans = 0
            break
        if havelst:
            nocut(x)
        else:
            make_lst(x)
    ans = min(cutnum, ans)
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
H, W, K = map(int,input().split())
S = [list(map(int,list(input()))) for _ in range(H)]
def check(k):
    if k <= K:
        return(True)
    else:
        return(False)
        
noans = 0
def make_lst(i):
    global noans, lst, havelst
    temp = S[0][i]
    for h in range(H-1):
        if y[h]:
            lst.append(temp)
            temp = S[h+1][i]
        else:
            temp += S[h+1][i]
    lst.append(temp)
    if check(max(lst)):
        havelst = 1
    else:
        noans = 1
               
def nocut(i):
    global cutnum, lst, havelst
    prelst = []
    temp = S[0][i]
    j = 0
    for h in range(H-1):
        if y[h]:
            lst[j] += temp
            prelst.append(temp)
            j += 1
            temp = S[h+1][i]
        else:
            temp += S[h+1][i]
    prelst.append(temp)
    lst[-1] += temp
    if check(max(lst)):
        return(True)
    else:
        cutnum += 1
        lst = prelst        
                 
ans = float("inf")
cutlst = []    
for y in itertools.product((0, 1), repeat=H-1):
    havelst = 0
    lst = []
    cutnum = sum(y)
    for x in range(W):
        if noans:
            continue
        if havelst:
            nocut(x)
        else:
            make_lst(x)
    ans = min(cutnum, ans)
print(ans)

Submission status: Wrong Answer

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

choco = [[0] * w for _ in range(h)]

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

ans = float("inf")
for bit in range(1 << (h - 1)):
    idx = [0] * h
    group = 0
    for i in range(h):
        idx[i] = group
        if (bit >> i) & 1:
            group += 1
    group += 1
    array = [[0] * w for _ in range(group)]
    for j in range(w):
        for i in range(h):
            array[idx[i]][j] += choco[i][j]

    cnt = group - 1
    cum = [0] * group
    canAdd = True
    for i in range(w):
        for j in range(group):
            if cum[j] > k:
                canAdd = False

        if canAdd is False:
            break

        for j in range(group):
            tmp = cum[j] + array[j][i]
            if tmp > k:
                cnt += 1
                cum = array[j]
                break
            cum[j] += array[j][i]

    if canAdd:
        ans = min(ans, cnt)

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
import sys
import numpy as np

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

if K==1:
    S=np.array(S)
    T=S.T
    ans=0
    for i in range(len(S)):
        if 1 in S[i]:
            ans+=1
    for i in range(len(T)):
        if 1 in T[i]:
            ans+=1
    ANS=H+W-2-(H+W-ans)
    print(ANS)
    sys.exit()

ANS=1000000
PRD=list(itertools.product([0,1], repeat=H-1))

def bit_to_group(bit):
    arr=[0]*H
    g=0  #グループナンバー
    for i in range(H-1):
        arr[i+1]=g
        if bit[i]==1:
            arr[i+1]+=1
            g+=1
    return arr

GROUPS=[]
for i in range(len(PRD)):
#    print(PRD[i],bit_to_group(PRD[i]))
    GROUPS.append(bit_to_group(PRD[i]))

for i in range(len(GROUPS)):
    grp=GROUPS[i]
#    print(grp)
    l=grp[-1]+1
    table=[0]*l
    ans=l-1
    j=0
    while j<W:  #Kを超えないと判定して初めて次の列を見るようにする
        k=0
        for k in range(H):
            table[grp[k]]+=S[k][j]
#            print(table,ans,k,j)
            k+=1
        if max(table)>K:
            table=[0]*l
            ans+=1
        else:
            j+=1
    ANS=min(ANS,ans)
            
print(ANS)

Submission status: Wrong Answer

Solution code:
import numpy as np
H,W,K = map(int, input().split())
C = np.array([list(map(int, input())) for _ in range(H)])
C = np.hstack([np.zeros([H,1]),C])
np.cumsum(C, axis=1, out=C)
ans = 10**5
for s in range(1<<(H-1)):
	ind = 0
	A = np.zeros([1,W+1])
	for i in range(H):
		if s >> i & 1 == 1:
			A = np.vstack([A,C[ind:i+1,:].sum(axis=0)])
			ind = i+1
	A = np.vstack([A,C[ind:].sum(axis=0)])

	ind = 0
	cnt = 0
	while True:
		cut = 10**3+2
		for a in A:
			cut = min(cut, np.searchsorted(a,a[ind]+K,side='right'))
		if cut == W+1:
			break
		if ind == cut-1:
			cnt = 10**3+2
			break
		else:
			ind = cut-1
		cnt += 1

	h_cnt = 0
	for i in range(H):
		if s >> i & 1 == 1:
			h_cnt += 1

	ans = min(ans, cnt+h_cnt)

print(ans)

Submission status: Wrong Answer

Solution code:
H,W,K=map(int,input().split())
S=[[0 for _ in range(W)] for i in range(H)]
for i in range(H):
    S[i] = [int(s) for s in list(input())]
from collections import defaultdict
def num_to_g(num):
    g_index = {}
    index=1
    for i in range(H+1):
        g_index[i]=index
        bl=(num>>i)%2
        if bl==1:
            index+=1
    return g_index

def get_white(choco_tmp,w,group_num):
    for i in range(H):
        if S[i][w]==1:
            choco_tmp[group_num[i]]+=1
    return choco_tmp

def greedy(num):
    div=num_to_g(i)
    res=max(div.values())-1
    choco=defaultdict(int)
    for j in range(W):
        choco = get_white(choco,j,div)

        if any(c>K for c in choco.values()):
            choco=defaultdict(int)

            if any(c>K for c in choco.values()):
                return 10**9+1
            else:
                res += 1
    return res
mx=2**(H-1)
ans=H+W-1
for i in range(mx):
    ans=min(ans,greedy(i))
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
h,w,k = map(int,input().split())

s = [[0 for _ in range(w)] for _ in range(h)]

for i in range(h):
    s[i] = [int(s) for s in list(input())]

#入力終了

def num_to_g(num):
    #10進数から2進数に変換し、縦向きのグループ分けをする(num < 2**(h-1))
    g_index = {}
    index = 1
    for i in range(h+1):
        g_index[i] = index
        bl = (num>>i)%2
        if(bl == 1):
            index += 1
    
    return g_index
    


def get_white(choco_tmp,w,group_num):
    
    for i in range(h):
        if(s[i][w]==1):
            choco_tmp[group_num[i]] += 1
    
    return choco_tmp


def greedy(num):
    div = num_to_g(i)
    res = max(div.values())-1
    choco = defaultdict(int)
    for j in range(w):
        choco = get_white(choco,j,div)
        
        if any(c>k for c in choco.values()):
            choco = defaultdict(int)
            choco = get_white(choco,j,div)
            
            if any(c>k for c in choco.values()):
                return -1
            else:
                res += 1
       
    return res        
            
                
        
#print(greedy(2))

mx = 2**(h-1)                
ans = 10**9 + 1
for i in range(mx):
    ans = min(ans,greedy(i))

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
from itertools import product
H, W, K = map(int, input().split())
A = np.array([list(input()) for _ in range(H)], dtype=int)
np.cumsum(A, out=A, axis=0)
np.cumsum(A, out=A, axis=1)

def Vsplit(arr):
    cut = 0
    arr = list(arr)
    arr.append(arr[-1])
    acc = 0
    for i in range(W):
        left = arr[i] - acc
        right = arr[i + 1] - acc
        if left > K:
            return -1
        if left <= K and right > K:
            cut += 1
            acc = arr[i]
    return cut
       

ans = 10**9
for Hsplit in product(range(2), repeat=H - 1):
    accum = np.zeros(W, dtype=int)
    row = []
    for i, p in enumerate(Hsplit):
        if p == 0:
            continue
        row.append(A[i]-accum)
        accum = A[i]
    else:
        row.append(A[-1] - accum)
   
    vcut = -1
    for r in row:
        v = Vsplit(r)
        if v == -1:
            vcut = -1
            break
        vcut = max(vcut, v)
    if vcut < 0:
        continue
   
    cut = sum(Hsplit) + vcut
    ans = min(ans, cut)

print(ans)