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

ans = 10**9
for split in product(range(2), repeat=H - 1):
    cut = sum(split)
    accum = np.zeros(W, dtype=int)
    row = []
    for i, p in enumerate(split):
        if p == 0:
            continue
        row.append(A[i]-accum)
        accum = A[i]
    else:
        row.append(A[-1] - accum)

    tmp = np.zeros(W, dtype=int)
    for r in row:
        tmp = np.maximum(tmp, r)
    tmp = tmp.tolist()
    tmp.append(tmp[-1])

    acc = 0
    for i in range(W):
        left = tmp[i] - acc
        right = tmp[i + 1] - acc
        if left <= K and right > K:
            cut += 1
            acc = tmp[i]

    ans = min(ans, cut)

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)], np.int64)
np.cumsum(C, axis = 1, out = C)

def solve(a):
	m = 0
	cnt = 0

	while True:
		cut = 10**3+2
		for aa in a:
			cut = min(cut,np.searchsorted(aa,m+K,side = 'right'))
	
		if cut == W:
			return cnt
		
		cnt += 1
		m = max(a[:,cut-1])

for s in range(1<<(H-1)):
	if s == 0:
		a = C.sum(axis=0)
		cut = 0
		m = 0
		cnt = 0
		while True:
			cut = np.searchsorted(a,m+K,side='right')
			if cut == W:
				ans = cnt
				break
			cnt += 1
			m = a[cut-1]
	else:
		cond = 1
		ind = 0
		for i in range(H-1):
			if s >> i & 1 == 1:
				if cond:
					a = np.array(C[:i+1,:].sum(axis=0))
					ind = i+1
					cond = 0
				else:
					a = np.vstack([a,C[ind:i+1,:].sum(axis = 0)])
		a = np.vstack([a,C[ind:].sum(axis=0)])

		h_cut = 0
		for i in range(H):
			if s >> i & 1 == 1:
				h_cut += 1
		v_cut = solve(a)
		ans = min(ans, h_cut+v_cut)

print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
from copy import deepcopy
import itertools as itt




class BitSeacher:
    def __init__(self,bitcount):
        self.counter =0
        self.bitcount = bitcount
        self.mx = 2**bitcount-1
    
    def __next__(self):
        if self.counter > self.mx:
            raise StopIteration()
        ans =[]
        flg =1
        for i in range(self.bitcount):
            if flg & self.counter != 0:
                ans.append(i)
            flg = flg.__lshift__(1)
        self.counter+=1
        return ans

    def __iter__(self):
        return self

def dist(A,B):
    return [i[1]-i[0] for i in itt.zip_longest(A,B)]

def getcuptbls(borders,H):
    if not borders:
        return [(0,H-1)]
    ans =[]
    st = 0    
    for i in borders:
        ans.append((st,i))
        st=i+1
    if st == H:
        return ans
    ans.append((st,H-1))
    return ans



def cupx(st,ctbl):
    ntbl = [[] for i in range(st)]

    for i in range(st,len(ctbl)):
        ntbl.append(dist(ctbl[st-1],ctbl[i]))
    return ntbl

def blkcounter(cuptbl,K):
    #print(cuptbl)
    count =0
    bordermax = len(cuptbl[0])
    while bordermax > 0 and max([cuptblrow[-1] for cuptblrow in cuptbl])>K:
        bordermax = max([ bisect.bisect_right(cuptblrow,cuptblrow[-1]-K) for cuptblrow in cuptbl])
        if bordermax != 0:
            xx =max([cuptblrow[-1] - cuptblrow[bordermax-1] for cuptblrow in cuptbl])
        else:
            xx =max([cuptblrow[-1]  for cuptblrow in cuptbl])

        #print(bordermax,xx)
        if xx > K:
            bordermax+=1
            #print(bordermax,xx)
        cuptbl= [ i[:bordermax] for i in cuptbl]    
        #print(bordermax,cuptbl)
        count +=1
    
    return count







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

    cuptbl = []

    for Sr in S:
        cuprow = deepcopy(Sr)
        for i in range(1,W):
            cuprow[i]+= cuprow[i-1]
        cuptbl.append(cuprow)

    tbl1= deepcopy(cuptbl)    
    for i in range(1,H):
        for j in range(W):
            tbl1[i][j]+=tbl1[i-1][j]
    cuptbl2=deepcopy(tbl1)
    tbl2=[tbl1]
    for i in range(1,H):
        tbl2.append(cupx(i,cuptbl2))
    x = 1 << 31
    for bsans in BitSeacher(H-1):
        cuptbl3=[tbl2[i[0]][i[1]] for i in getcuptbls(bsans,H)]
        #print(bsans)
        ans =blkcounter(cuptbl3,K) +len(cuptbl3)-1
        x = min(x,ans)
        #print(ans)
        #print()
    print(x)




if __name__ == "__main__":
    resolve()
    #unittest.main()

Submission status: Wrong Answer

Solution code:
h,w,k = map(int,input().split())
s = [list(str(input())) for i in range(h)]
num1 = 0
cnt = 0
f1 = 0
f2 = 0
ans = 0
for i in s:
    num1 += i.count("1")
    cnt += i.count("1")
    if cnt > k:
        f1 = 1
    cnt %= k
for i in range(w):
    for j in s:
        if j[i] == "1":
            cnt += 1
    if cnt > k:
        f2 = 1
    cnt %= k
while 1:
    if k * (2**(ans)) < num1:
        ans += 1
    else:
        break 

if num1 == k*(2**ans):
    print(ans + min(f1,f2))
elif num1 == k*(2**ans) - 1:
    print(ans + min(f1,f2))
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
import copy

h, w, k = map(int, input().split())
s = [[0] * w for _ in range(h)]
for i in range(h):
    inp = input()
    for j in range(w):
        s[i][j] = int(inp[j])

# 最終的に出力する操作回数の最小値
ans = h + w - 2

for i in range(2 ** (h-1)):
    # bit全探索によるcutの仕方
    cutIdx = [0] * (h-1)
    for j in range(h-1):
        cutIdx[j] = (i >> j) & 1
    #print('cI : ', cutIdx)

    # cutする場所を示したリスト
    div = []
    cut_row_begin, cut_row_end = 0, 1
    for j in range(h-1):
        if cutIdx[j] == 0:
            # cutしない
            cut_row_end += 1
        else:
            # cutする
            div.append((cut_row_begin, cut_row_end))
            cut_row_begin = cut_row_end
            cut_row_end += 1
    div.append((cut_row_begin, cut_row_end))
    #print('div: ', div)

    # 既にここまででcutされている回数
    cnt = sum(cutIdx)
    #print(cnt)

    # divごとのホワイトチョコの数をカウント
    whiteCnt = [0] * len(div)

    # まずは1列目をチェック
    for a in range(len(div)):
        cal = 0
        for b in range(div[a][0], div[a][1]):
            cal += s[b][0]
        whiteCnt[a] = cal
    #print('wC : ', whiteCnt)

    # もしこの時点でwhiteCntの要素でkを超えるものがあるとき
    # その横の切り方は不可能なのでbreak
    if max(whiteCnt) > k:
        break

    # Wが1ならそこで終わり
    if w == 1:
        ans = min(ans, cnt)

    # 次行のホワイトチョコ数を保持
    search = [0] * len(div)

    # 2列目以降を同様にチェックしていく
    for a in range(1, w):
        # その次行のホワイトチョコの数
        for b in range(len(div)):
            cal = 0
            for c in range(div[b][0], div[b][1]):
                cal += s[c][a]
            search[b] = cal

        # その行単体でmax値とkを比べる
        # オーバーしていればcut不可
        if max(search) > k:
            break

        # greedy
        for b in range(len(div)):
            if whiteCnt[b] + search[b] > k:
                # cut対象
                cnt += 1
                whiteCnt = copy.copy(search)
                break
            else:
                whiteCnt[b] += search[b]
    #print('cnt: ', cnt)
    ans = min(ans, cnt)

print(ans)

Submission status: Wrong Answer

Solution code:
import copy

h, w, k = map(int, input().split())
s = [[0] * w for _ in range(h)]
for i in range(h):
    inp = input()
    for j in range(w):
        s[i][j] = int(inp[j])

# 最終的に出力する操作回数の最小値
ans = (h-1) * (w-1)
# 横に対して
for i in range(h):
    if max(s[i]) == 0:
        ans -= 1
# 縦に対して
for i in range(w):
    arr = [0] * h
    for j in range(h):
        arr[j] = s[j][i]
    if max(arr) == 0:
        ans -= 1

for i in range(2 ** (h-1)):
    # bit全探索によるcutの仕方
    cutIdx = [0] * (h-1)
    for j in range(h-1):
        cutIdx[j] = (i >> j) & 1
    #print('cI : ', cutIdx)

    # cutする場所を示したリスト
    div = []
    cut_row_begin, cut_row_end = 0, 1
    for j in range(h-1):
        if cutIdx[j] == 0:
            # cutしない
            cut_row_end += 1
        else:
            # cutする
            div.append((cut_row_begin, cut_row_end))
            cut_row_begin = cut_row_end
            cut_row_end += 1
    div.append((cut_row_begin, cut_row_end))
    #print('div: ', div)

    # 既にここまででcutされている回数
    cnt = sum(cutIdx)
    #print(cnt)

    # divごとのホワイトチョコの数をカウント
    whiteCnt = [0] * len(div)

    # まずは1列目をチェック
    for a in range(len(div)):
        cal = 0
        for b in range(div[a][0], div[a][1]):
            cal += s[b][0]
        whiteCnt[a] = cal
    #print('wC : ', whiteCnt)

    # もしこの時点でwhiteCntの要素でkを超えるものがあるとき
    # その横の切り方は不可能なのでbreak
    if max(whiteCnt) > k:
        break

    # Wが1ならそこで終わり
    if w == 1:
        ans = min(ans, cnt)

    # 次行のホワイトチョコ数を保持
    search = [0] * len(div)

    # 2列目以降を同様にチェックしていく
    for a in range(1, w):
        # その次行のホワイトチョコの数
        for b in range(len(div)):
            cal = 0
            for c in range(div[b][0], div[b][1]):
                cal += s[c][a]
            search[b] = cal

        # その行単体でmax値とkを比べる
        # オーバーしていればcut不可
        if max(search) > k:
            break

        # greedy
        for b in range(len(div)):
            if whiteCnt[b] + search[b] > k:
                # cut対象
                cnt += 1
                whiteCnt = copy.copy(search)
                break
            else:
                whiteCnt[b] += search[b]
    #print('cnt: ', cnt)
    ans = min(ans, cnt)

print(ans)

Submission status: Wrong Answer

Solution code:
import copy

h, w, k = map(int, input().split())
s = [[0] * w for _ in range(h)]
for i in range(h):
    inp = input()
    for j in range(w):
        s[i][j] = int(inp[j])

# 最終的に出力する操作回数の最小値
ans = 100000000

for i in range(2 ** (h-1)):
    # bit全探索によるcutの仕方
    cutIdx = [0] * (h-1)
    for j in range(h-1):
        cutIdx[j] = (i >> j) & 1
    #print('cI : ', cutIdx)

    # cutする場所を示したリスト
    div = []
    cut_row_begin, cut_row_end = 0, 1
    for j in range(h-1):
        if cutIdx[j] == 0:
            # cutしない
            cut_row_end += 1
        else:
            # cutする
            div.append((cut_row_begin, cut_row_end))
            cut_row_begin = cut_row_end
            cut_row_end += 1
    div.append((cut_row_begin, cut_row_end))
    #print('div: ', div)

    # 既にここまででcutされている回数
    cnt = sum(cutIdx)
    #print(cnt)

    # divごとのホワイトチョコの数をカウント
    whiteCnt = [0] * len(div)

    # まずは1列目をチェック
    for a in range(len(div)):
        cal = 0
        for b in range(div[a][0], div[a][1]):
            cal += s[b][0]
        whiteCnt[a] = cal
    #print('wC : ', whiteCnt)

    # もしこの時点でwhiteCntの要素でkを超えるものがあるとき
    # その横の切り方は不可能なのでbreak
    if max(whiteCnt) > k:
        break

    # Wが1ならそこで終わり
    if w == 1:
        ans = min(ans, cnt)

    # 次行のホワイトチョコ数を保持
    search = [0] * len(div)

    # 2列目以降を同様にチェックしていく
    for a in range(1, w):
        # その次行のホワイトチョコの数
        for b in range(len(div)):
            cal = 0
            for c in range(div[b][0], div[b][1]):
                cal += s[c][a]
            search[b] = cal

        # その行単体でmax値とkを比べる
        # オーバーしていればcut不可
        if max(search) > k:
            break

        # greedy
        for b in range(len(div)):
            if whiteCnt[b] + search[b] > k:
                # cut対象
                cnt += 1
                whiteCnt = copy.copy(search)
                break
            else:
                whiteCnt[b] += search[b]
    #print('cnt: ', cnt)
    ans = min(ans, cnt)

print(ans)

Submission status: Wrong Answer

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

ans = (H-1) * (W-1)

for i in range(2**(H-1)):
    cut = 0

    yoko = [choco[0]]
    for j in range(H-1):
        if (i>>j) & 1 == 1:
            # 折った
            cut += 1
            yoko.append(choco[j+1])
        else:
            # 折らない -> まとめる
            yoko[-1] = [a + b for a, b in zip(yoko[-1], choco[j+1])]

    count = [yoko[0][i] for i in range(cut+1)]

    if max(count) > K:
        continue

    for x in range(1, W):
        now_count = [yoko[y][x] for y in range(len(count))]
        next_count = [a + b for a, b in zip(now_count, count)]
        if max(next_count) > K:
            # 折る
            count = now_count
            cut += 1
        else:
            # 折らない
            count = next_count

    ans = min(ans, cut)

print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    H, W, K = map(int, raw_input().split())
    S = []

    for i in range(H):
        S.append(list(raw_input()))

    for i in range(H):
        for j in range(W):
            S[i][j] = int(S[i][j])

    ans = 10**9

    for divide in range(2**(H-1)):
        regions = []
        for l in range(H):
            if divide & 1 << l:
                regions.append(l+1)
        S_subs = []
        prev = 0
        for region in regions:
            new = region
            S_subs.append(S[prev:new])
            prev = new
        S_subs.append(S[prev:H])
        N = len(S_subs)

        count = [0]*N

        bin_num = bin(divide)[2:]

        ans_temp = 0
        for i in bin_num:
            ans_temp += int(i)

        for j in range(W):
            for l in range(N):
                for item in S_subs[l]:
                    count[l] += item[j]
            if max(count) > K:
                ans_temp = ans_temp + 1
                for m in range(N):
                    for item in S_subs[m]:
                        count[m] = item[j]

        if ans_temp < ans:
            ans = ans_temp
    print ans
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    H, W, K = map(int, raw_input().split())
    S = []

    for i in range(H):
        S.append(list(raw_input()))

    for i in range(H):
        for j in range(W):
            S[i][j] = int(S[i][j])

    ans = 10**9

    for divide in range(2**(H)):
        regions = []
        for l in range(H):
            if divide & 1 << l:
                regions.append(l)
        S_subs = []
        prev = 0
        for region in regions:
            new = region
            S_subs.append(S[prev:new])
            prev = new
        S_subs.append(S[prev:H])
        N = len(S_subs)

        count = [0]*N

        bin_num = bin(divide)[2:]

        ans_temp = 0
        for i in bin_num:
            ans_temp += int(i)

        for j in range(W):
            for l in range(N):
                for item in S_subs[l]:
                    count[l] += item[j]
            if max(count) > K:
                ans_temp = ans_temp + 1
                count = [0]*N
                for m in range(N):
                    for item in S_subs[m]:
                        count[m] += item[j]

        if ans_temp < ans:
            ans = ans_temp

#        print ans_temp               
    print ans


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np

def main():
    H, W, K = map(int, raw_input().split())
    S = []

    for i in range(H):
        S.append(list(raw_input()))

    for i in range(H):
        for j in range(W):
            S[i][j] = int(S[i][j])

    ans = 10**9

    for divide in range(2**(H-1)):
        regions = []
        for l in range(H):
            if divide & 1 << l:
                regions.append(l)
        S_subs = []
        prev = 0
        for region in regions:
            new = region
            S_subs.append(S[prev:new])
            prev = new
        S_subs.append(S[prev:H])
        N = len(S_subs)

        count = [0]*N

        bin_num = bin(divide)[2:]

        ans_temp = 0
        for i in bin_num:
            ans_temp += int(i)

        for j in range(W):
            for l in range(N):
                for item in S_subs[l]:
                    count[l] += item[j]
            if max(count) > K:
                ans_temp = ans_temp + 1
                count = [0]*N
                for m in range(N):
                    for item in S_subs[m]:
                        count[m] += item[j]

        if ans_temp < ans:
            ans = ans_temp

#        print ans_temp               
    print ans


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np

def main():
    H, W, K = map(int, raw_input().split())
    S = []

    for i in range(H):
        S.append(list(raw_input()))

    for i in range(H):
        for j in range(W):
            S[i][j] = int(S[i][j])

    ans = 10**9

    for divide in range(2**(H-1)):
        regions = []
        for l in range(H):
            if divide & 1 << l:
                regions.append(l+1)
        S_subs = []
        prev = 0
        for region in regions:
            new = region
            S_subs.append(S[prev:new])
            prev = new
        S_subs.append(S[prev:H])
        N = len(S_subs)

        count = [0]*N

        bin_num = bin(divide)[2:]

        ans_temp = 0
        for i in bin_num:
            ans_temp += int(i)

        for j in range(W):
            for l in range(N):
                for item in S_subs[l]:
                    count[l] += item[j]
            if max(count) > K:
                ans_temp = ans_temp + 1
                count = [0]*N
                for m in range(N):
                    for item in S_subs[m]:
                        count[m] += item[j]

        if ans_temp < ans:
            ans = ans_temp

#        print ans_temp               
    print ans


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np

def main():
    H, W, K = map(int, raw_input().split())
    S = []

    for i in range(H):
        S.append(list(raw_input()))

    for i in range(H):
        for j in range(W):
            S[i][j] = int(S[i][j])

    ans = 10**9

    for divide in range(2**(H-1)):
        regions = []
        for l in range(H):
            if divide & 1 << l:
                regions.append(l+1)
        S_subs = []
        prev = 0
        for region in regions:
            new = region
            S_subs.append(S[prev:new])
            prev = new
        S_subs.append(S[prev:H])
        N = len(S_subs)

        count = [0]*N

        bin_num = bin(divide)[2:]

        ans_temp = 0
        for i in bin_num:
            ans_temp += int(i)

        for j in range(W):
            for l in range(N):
                for item in S_subs[l]:
                    count[l] += item[j]
            if max(count) > K:
                ans_temp = ans_temp + 1
                count = [0]*N
                for m in range(N):
                    for item in S_subs[m]:
                        count[m] += item[j]

        if ans_temp < ans:
            ans = ans_temp

#        print ans_temp

Submission status: Wrong Answer

Solution code:
from collections import *
from heapq import *
from itertools import *
from fractions import gcd
import sys
from decimal import *
import copy
input=lambda :sys.stdin.readline().rstrip()


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

value=H+W-1
if H==1:
    count=0
    countL=0
    w=0
    while w<W:
        if S[0][w]=="1":
            count+=1
        if count>K:
            countL+=1
            count=0
        else:
            w+=1
    print(countL)
else:
    for i in range(2**(H-1)):
        lst=[i>>m&1 for m in range(H-1)]#0なら線がある
        count=[0 for i in range(lst.count(0)+1)]
        count_zero=copy.copy(count)
        idx={}
        c=0
        for h in range(H-1):
            idx[h]=c
            if lst[h]==0:
                c+=1
        idx[H-1]=c
        flag=0
        w=0
        pre_w=0
        countL=lst.count(0)
        while w<W:
            for h in range(H):

                if S[h][w]=="1":
                    count[idx[h]]+=1
            if max(count)>K:
                if pre_w==w:
                    break
                    flag=1
                pre_w=w
                countL+=1
                count=copy.copy(count_zero)
            else:
                w+=1
        if not flag:
            value=min(value,countL)
    print(value)

Submission status: Wrong Answer

Solution code:
from collections import *
from heapq import *
from itertools import *
from fractions import gcd
import sys
from decimal import *
import copy
input=lambda :sys.stdin.readline().rstrip()


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

value=H+W-1
for i in range(2**(H-1)):
    lst=[i>>m&1 for m in range(H-1)]#0なら線がある
    count=[0 for i in range(lst.count(0)+1)]
    count_zero=copy.copy(count)
    idx={}
    c=0
    for h in range(H-1):
        idx[h]=c
        if lst[h]==0:
            c+=1
    idx[H-1]=c
    flag=0
    w=0
    pre_w=0
    countL=lst.count(0)
    while w<W:
        for h in range(H):

            if S[h][w]=="1":
                count[idx[h]]+=1
        if max(count)>K:
            if pre_w==w:
                break
                flag=1
            pre_w=w
            countL+=1
            count=copy.copy(count_zero)
        else:
            w+=1
    if not flag:
        value=min(value,countL)
print(value)

Submission status: Wrong Answer

Solution code:
from itertools import combinations

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

map = [None] * H
for i in range(H):
  map[i] = [int(c) for c in input().strip()]


def a(heights=[]) -> int:
  assert len(heights) > 0
  count = len(heights) - 1

  total = {i: (0, 0) for i in range(len(heights))}
  for i in range(W):
    violate = False
    for j, height in enumerate(heights):
      n = 0
      for k in range(height[0], height[1]):
        n += map[k][i]
      if n > K:
        return -1
      total[j] = (total[j][0] + n, n)
      if total[j][0] > K:
        violate = True
    if violate:
      count += 1
      for j in range(len(heights)):
        tmp = total[j][1]
        total[j] = (tmp, tmp)
  return count


patterns = [[(0, H)]]
iterable = [i + 1 for i in range(H - 1)]
for r in range(1, H):
  for c in combinations(iterable, r):
    pattern = []
    last = 0
    for i in c:
      pattern.append((last, i))
      last = i
    pattern.append((last, H))
    patterns.append(pattern)

print(min(filter(lambda x: x > 0, [a(p) for p in patterns])))

Submission status: Wrong Answer

Solution code:
H,W,K=map(int,input().split())
import numpy as np
S=np.array([list(map(int,list(input()))) for i in range(H)])
INF=10**18
ans=INF
for i in range(2**(H-1)):
  _ans=0
  X=[]
  start=0
  j=0
  while j<H:
    if i & 1:
      X.append(np.sum(S[start:j+1,:],axis=0))
      start=j+1
      j+=1
      i>>=1
      _ans+=1
    else:
      j+=1
      i>>=1
  X.append(np.sum(S[start:,:],axis=0))
  X=np.array(X)
  #print(X)
  _=np.array([[0] for i in range(len(X))])
  for i in range(W):
    _=_+X[:,i]
    #print(_)
    if np.max(_)<=K:
      continue
    else:
      if i==0:
        _ans=INF
        break
      _ans+=1
      #X=X-X[:,i].Tnp.transpose
      _=np.array([[0] for i in range(X.shape[0])])
      #print(X)
  ans=min(ans,_ans)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

H,W,K = map(int,input().split())
choco = [input() for _ in range(H)]
num =(2**(H-1))

white_count = list()
min_div_count =10**6
for i in range(num):
    bin_str = format(i, 'b')
    zero = str()
    if H != len(bin_str):
        for _ in range(H-len(bin_str)):
            zero += "0"
        bin_str = zero + bin_str
    white_count = [0 for s in bin_str if s == "1"]
    white_count.append(0)
    div_count=len(white_count)-1
    
    for j in range(W):
        block_count = 0
        white_list = [0]*len(white_count)
        #print("j:"+str(j))
        is_over = False
        for k in range(len(bin_str)):
            if bin_str[k] == "1":
                block_count += 1
            
            white_list[block_count] += int(choco[k][j])
            white_count[block_count] += int(choco[k][j])
            if white_count[block_count] > K:
                is_over = True
        if is_over:
            div_count += 1
            white_count = white_list


        #print(white_list)   
        #print(white_count)
        #print("div_count"+str(div_count))
        if div_count >= min_div_count:
            break
    else:
        min_div_count = div_count
print(min_div_count)

Submission status: Wrong Answer

Solution code:
import sys

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

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

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

ret = float("inf")

for i in range(2 ** (h - 1)):
    num = i
    l = [0 for _ in range(h - 1)]
    place = 0
    while num > 0:
        l[place] = num % 2
        num//=2
        place+=1
    sl = [0]
    for j in range(len(l)):
        if l[j] == 1:
            sl.append(j)
            sl.append(j + 1)
    sl.append(h - 1)

    ans = sum(l) + 1
    cnt = [[0 for _ in range(w)] for _ in range(ans)]
    index = 0

    for j in range(0,len(sl),2):
        for k in range(sl[j],sl[j + 1] + 1):
            for m in range(w):
                cnt[index][m]+=s[k][m]
        index+=1

    first = 0
    for j in range(1,w):
        for i in range(sum(l) + 1):
            if cnt[i][j] - cnt[i][first] > k:
                ans+=1
                first = j
                break

    ret = min(ans - 1,ret)

print(ret)

Submission status: Wrong Answer

Solution code:
# Problem E - Dividing Chocolate

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

# initialization
min_divide = 10**10
s = [0]*(H-1) # 横線の入り方 0:無 1:有
is_ok = True

# search
for i in range(2**(H-1)): # bit全探索
    # sの初期化
    h_count = 0
    w_count = 0
    for j in range(H-1):
        if ((i>>j)&1):
            s[j] = 1
            h_count += 1
        else:
            s[j] = 0

    # 列の全探索
    s_score = [0]*H # 各区域のスコア
    s_cur = [0]*H
    for j in range(W):
        c = 0
        s_cur = [0]*H

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

            # Kを超えていないかのチェック
            if s_cur[c]>K:
                is_ok = False
                break

            # 次の遷移先(横線の有無でグループが別れる)
            if k+1<H:
                if s[k]==1:
                    c += 1
        # Kを超えていたらループ中止
        if not is_ok:
            break
        # 前の列のグループと足してみてKを超えていないかチェック
        # 超えていれば縦線分割を施す
        group_smaller = True
        if j>0:
            for c_num in range(c+1):
                if s_score[c_num]+s_cur[c_num]>K:
                    group_smaller = False
        else:
            group_smaller = True

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

    if not is_ok:
        is_ok = True
        break

    for c_num in range(h_count+1):
        if s_score[c_num]>K:
            h_count = 10 ** 6

    # 縦線と横線の合計でmin_divideを更新
    min_divide = min(min_divide, w_count + h_count)

# output
print(min_divide)

Submission status: Wrong Answer

Solution code:
# Problem E - Dividing Chocolate

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

# initialization
min_divide = 10**10
s = [0]*(H-1) # 横線の入り方 0:無 1:有
is_ok = True

# search
for i in range(2**(H-1)): # bit全探索
    # sの初期化
    h_count = 0
    w_count = 0
    for j in range(H-1):
        if ((i>>j)&1):
            s[j] = 1
            h_count += 1
        else:
            s[j] = 0

    # 列の全探索
    s_score = [0]*H # 各区域のスコア
    s_cur = [0]*H
    for j in range(W):
        c = 0
        s_cur = [0]*H

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

            # Kを超えていないかのチェック
            if s_cur[c]>K:
                is_ok = False
                break

            # 次の遷移先(横線の有無でグループが別れる)
            if k+1<H:
                if s[k]==1:
                    c += 1
        # Kを超えていたらループ中止
        if not is_ok:
            break
        # 前の列のグループと足してみてKを超えていないかチェック
        # 超えていれば縦線分割を施す
        group_smaller = True
        if j>0:
            for c_num in range(c+1):
                if s_score[c_num]+s_cur[c_num]>K:
                    group_smaller = False
        else:
            group_smaller = True

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

    if not is_ok:
        is_ok = True
        break

    # 縦線と横線の合計でmin_divideを更新
    min_divide = min(min_divide, w_count + h_count)

# output
print(min_divide)

Submission status: Wrong Answer

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

def minisolve(left, cut, n):
    a = [0] * n
    i = 0
    while left < W:
        for t in range(H):
            if t >= cut[i]:
                i += 1
            if C[t][left]:
                a[i] += 1
                if a[i] > K:
                    return left
        left += 1
        i = 0

ans = 10**18
N = H-1
for bit in range(1<<N):
    n = 1
    cut = []
    for i in range(N):
        if 1 & bit>>i:
            n += 1
            cut.append(i+1)
    cut.append(H)

    left = 0
    res = 0
    while True:
        left = minisolve(left, cut, n)
        if left:
            res += 1
        else:
            break
    res += n-1
    ans = min(ans, res)

print(ans)

Submission status: Wrong Answer

Solution code:
import re

H,W,K = map(int,input().split())
grid = [[0 for i in range(W+1)]]
for i in range(H):
  S = input()
  grid.append([0]+[ int(S[i]) for i in range(W) ])

#累積和gridの作成
#行について
for i in range(H+1):
  for j in range(W):
    grid[i][j+1] += grid[i][j]
#列について
for j in range(W+1):
  for i in range(H):
    grid[i+1][j] += grid[i][j]   

min_cnt = (H-1)*(W-1)
#横の区切りを作る
for h in range(2**(H-1)):
  cnt = 0
  #二進数の文字列を取得
  bin_str = format(h,"0{}b".format(H-1)) 
  #区切りのインデックスリスト
  l_p =[1]+[ x.start()+2 for x in re.finditer("1",bin_str) ] +[H+1]

  #cntに区切りの分だけ付け加える
  cnt = cnt + len(l_p) - 2
  
  ws = 0
  for w in range(1,W+1):
    for k in range(len(l_p)-1):
      if grid[l_p[k+1]-1][w]- (grid[l_p[k]-1][w]+grid[l_p[k+1]-1][ws]-grid[l_p[k]-1][ws]) > K:
        cnt = cnt + 1
        ws = w-1
        break    
  min_cnt = min(min_cnt,cnt)

###
print(min_cnt)