Problem:


Score : 500 points

Problem Statement

We have a chocolate bar partitioned into H horizontal rows and W vertical columns of squares.

The square (i, j) at the i-th row from the top and the j-th column from the left is dark if S_{i,j} is 0, and white if S_{i,j} is 1.

We will cut the bar some number of times to divide it into some number of blocks. In each cut, we cut the whole bar by a line running along some boundaries of squares from end to end of the bar.

How many times do we need to cut the bar so that every block after the cuts has K or less white squares?

Constraints

1 \leq H \leq 10

1 \leq W \leq 1000

1 \leq K \leq H \times W

S_{i,j} is 0 or 1.

Input

Input is given from Standard Input in the following format:

H W K
S_{1,1}S_{1,2}...S_{1,W}
:
S_{H,1}S_{H,2}...S_{H,W}

Output

Print the number of minimum times the bar needs to be cut so that every block after the cuts has K or less white squares.

Sample Input 1

3 5 4
11100
10001
00111

Sample Output 1

2

For example, cutting between the 1-st and 2-nd rows and between the 3-rd and 4-th columns - as shown in the figure to the left - works.

Note that we cannot cut the bar in the ways shown in the two figures to the right.

Sample Input 2

3 5 8
11100
10001
00111

Sample Output 2

0

No cut is needed.

Sample Input 3

4 10 4
1110010010
1000101110
0011101001
1101000111

Sample Output 3

3



Sample input:
3 5 4
11100
10001
00111


Sample output:
2

Submission status: Wrong Answer

Solution code:
# H: 縦のマス数
# W: 横のマス数
# 0: 普通, 1: ホワイトチョコレート
import numpy as np

H, W, K = map(int, input().split())
S = np.zeros([H, W], dtype=np.int8)
for i in range(H):
    S[i] = list(map(int, list(input())))

sum_white = np.sum(S)

row_sums = S.sum(axis=1)
col_sums = S.sum(axis=0)

row_cuts = []
tmp_sum = 0
row_cut_cnt = 0
for h in range(H):
    tmp_sum += row_sums[h]
    if tmp_sum >= K and h < H-1:
        row_cuts.append(h)
        tmp_sum = 0
        row_cut_cnt += 1

tmp_col_sums = np.zeros([len(row_cuts)+1], dtype=np.int16)
col_cuts = []
for w in range(W):
    pre_row_cut = 0
    for cut_idx, row_cut in enumerate(row_cuts):
        tmp_col_sums[cut_idx] += np.sum(S[pre_row_cut:row_cut+1, w])
        pre_row_cut = row_cut
    if np.max(tmp_col_sums) > K:
        row_cut_cnt += 1
        col_cuts.append(w-1)
        tmp_col_sums[:] = 0
        pre_row_cut = 0
        for cut_idx, row_cut in enumerate(row_cuts):
            tmp_col_sums[cut_idx] += np.sum(S[pre_row_cut:row_cut, w])
            pre_row_cut = row_cut

col_cuts = []
row_cuts = []
tmp_sum = 0
col_cut_cnt = 0
for w in range(W):
    tmp_sum += col_sums[w]
    if tmp_sum >= K and w < W-1:
        col_cuts.append(w)
        tmp_sum = 0
        col_cut_cnt += 1

tmp_row_sums = np.zeros([len(col_cuts)+1], dtype=np.int16)
for h in range(H):
    pre_col_cut = 0
    for cut_idx, col_cut in enumerate(col_cuts):
        tmp_row_sums[cut_idx] += np.sum(S[h, pre_col_cut:col_cut+1])
        pre_col_cut = col_cut
    if np.max(tmp_row_sums) > K:
        col_cut_cnt += 1
        row_cuts.append(h-1)
        tmp_row_sums[:] = 0
        pre_col_cut = 0
        for cut_idx, col_cut in enumerate(col_cuts):
            tmp_row_sums[cut_idx] += np.sum(S[h, pre_col_cut:col_cut])
            pre_col_cut = col_cut

row_sums = S.sum(axis=1)
col_sums = S.sum(axis=0)[::-1]
col_cuts = []
row_cuts = []
tmp_sum = 0
inv_col_cut_cnt = 0
for w in range(W):
    tmp_sum += col_sums[w]
    if tmp_sum >= K and w < W-1:
        col_cuts.append(w)
        tmp_sum = 0
        inv_col_cut_cnt += 1

tmp_row_sums = np.zeros([len(col_cuts)+1], dtype=np.int16)
for h in range(H):
    pre_col_cut = 0
    for cut_idx, col_cut in enumerate(col_cuts):
        tmp_row_sums[cut_idx] += np.sum(S[h, pre_col_cut:col_cut+1])
        pre_col_cut = col_cut
    if np.max(tmp_row_sums) > K:
        inv_col_cut_cnt += 1
        row_cuts.append(h-1)
        tmp_row_sums[:] = 0
        pre_col_cut = 0
        for cut_idx, col_cut in enumerate(col_cuts):
            tmp_row_sums[cut_idx] += np.sum(S[h, pre_col_cut:col_cut])
            pre_col_cut = col_cut

print(min(col_cut_cnt, row_cut_cnt, inv_col_cut_cnt))

Submission status: Wrong Answer

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

ans = [[0 for _ in range(W)] for _ in range(H)]
cnt = 0
mm = []

c = 0
for h in range(H):
    if not("1" in HW[h]):
        continue
    mm.append(h)
    cnt += 1
    flg = 1

    for w in range(W):
        if HW[h][w]=="1" and not(flg):
            cnt += 1

        if cnt >= K:
            c += 1
            cnt = 0
        ans[h][w]=c
 
        if flg and HW[h][w]=="1":
            flg = 0
            continue

        
        
if ans[H-1][W-1] == 1:
    print(0)
else:
    print(ans[H-1][W-1])

Submission status: Wrong Answer

Solution code:
Height, Width, Thres = map(int, input().split())

chocolate = [[0 for w in range(Width)] for h in range(Height)]

for h in range(Height):
    inp = input()
    
    for w in range(Width):
        chocolate[h][w] = int(inp[w])

h_cnt = []

for h in range(Height):
    n = sum(chocolate[h])
    h_cnt.append(n)

cnt = 0
summ = 0
summ_before = 0

for i in range(Height):
    num = h_cnt[i]
    summ += num
    
    if (summ < Thres):
        summ_before += num
        
    else:
        cnt += 1
        summ = num
        summ_before = num


ans = max(0, cnt - 1)

print(ans)

Submission status: Wrong Answer

Solution code:
def main():

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

    S = [list(map(int, input())) for i in range(H)]

    count = 0
    for i in range(H):
        for j in range(W):
            if S[i][j] == 1:
                count += 1
    
    ans = int(count / K) 

    total = 0
    i = 1
    t = 0
    be = 0
    while(ans>total):
        total += i
        if t % 2 == 0:
            i += 1
        t += 1
        be += 1

    print(be)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

total=0
for h in range(H):
    for w in range(W):
        total+=int(S[h][w])
print total/K

Submission status: Wrong Answer

Solution code:
import numpy as np
H, W, K = map(int, input().split())
chocolate = list()
for i in range(H):
    chocolate.append(list(map(int, [i for i in input()])))
choco_array = np.array(chocolate)
count_array = np.array(chocolate)
row = np.ones([H-1])
column = np.ones([W-1])

#print(choco_array)
for i in range(W-1):
    choco_kari = choco_array.copy()
    amount = choco_kari[:, i:i+2].sum(axis=1)
    #print(amount)
    if np.all(amount<=K):
        column[i] = 0
        choco_array[:, i] = amount
        choco_array[:, i+1] = amount
        #print(i)
        #print(choco_array)

for i in range(H-1):
    choco_kari = choco_array.copy()
    amount = choco_kari[i:i+2, :].sum(axis=0)
    #print(amount)
    if np.all(amount<=K):
        row[i] = 0
        choco_array[i, :] = amount
        choco_array[i+1, :] = amount
        #print(i)
        #print(choco_array)

a_1 = (int(sum(row)+sum(column)))

choco_array = np.array(chocolate)
count_array = np.array(chocolate)
row = np.ones([H-1])
column = np.ones([W-1])

for i in range(H-1):
    choco_kari = choco_array.copy()
    amount = choco_kari[i:i+2, :].sum(axis=0)
    #print(amount)
    if np.all(amount<=K):
        row[i] = 0
        choco_array[i, :] = amount
        choco_array[i+1, :] = amount
        #print(i)
        #print(choco_array)

#print(choco_array)
for i in range(W-1):
    choco_kari = choco_array.copy()
    amount = choco_kari[:, i:i+2].sum(axis=1)
    #print(amount)
    if np.all(amount<=K):
        column[i] = 0
        choco_array[:, i] = amount
        choco_array[:, i+1] = amount
        #print(i)
        #print(choco_array)


a_2 = (int(sum(row)+sum(column)))
print(min([a_1, a_2]))

Submission status: Wrong Answer

Solution code:
import numpy as np
import itertools

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

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

    ans = 0
    for i in range(H):
        for j in range(W):
            ans = ans + int(S[i][j])
    if ans <= K:
        print 0
        exit()

    ans = 10**9
    for i in range(H):
        for j in list(itertools.combinations(range(1, H), i)):
            ans_temp = i
            candi = [0]
            for k in j:
                candi.append(k)
            candi.append(H)
            count = np.zeros(H)
            for m in range(W):
                is_flag = False
                for n in range(H):
                    count[n] += int(S[n][m])

                prev_l = candi[0]
                for l in range(1, len(candi)):
                    if sum(count[prev_l:l]) > K:
                        is_flag = True

                if is_flag == True:
                    ans_temp = ans_temp+1
                    for n in range(H):
                        count[n] = 0


            if ans_temp > 1:
                if ans_temp < ans:
                    ans = ans_temp

    print ans

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import bisect
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[i+1] - accum)

    tmp = np.zeros(W, dtype=int)
    for r in row:
        tmp = np.maximum(tmp, r)
    tmp = tmp.tolist()

    cnt = 0
    target = K
    p = 0
    while True:
        q = bisect.bisect_right(tmp, target)
        if q == W:
            break
        if p == q:
            cnt = -1
            break
        p = q
        target = tmp[p-1]+K
        cnt += 1

    if cnt < 0:
        continue
    ans = min(ans, cut + cnt)


print(ans)

Submission status: Wrong Answer

Solution code:
# import bisect
# from collections import Counter, deque
# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
# import itertools
# from operator import attrgetter, itemgetter
# import math

import sys

# import numpy as np

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    def choco_sum(begin, end):
        res = 0
        for j in range(begin, end):
            res += int(s[j])
        return str(res).zfill(w)

    h, w, k = list(map(int, readline().split()))

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

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

    ans = INF

    for bit in range(1, 1 << (h - 1)):
        begin = 0
        choco = []
        rownum = 1
        for i in range(h - 1):
            if bit >> i & 1:
                cs = choco_sum(begin, i + 1)
                choco.append(cs)
                begin = i + 1
                rownum += 1
        cs = choco_sum(begin, h)
        choco.append(cs)

        wchoco_cnt = [0] * rownum
        wchoco_tmp = [0] * rownum

        colnum = 1
        wchoco_temp = [0] * rownum
        flag = False
        for i in range(w):
            for j in range(rownum):
                temp = int(choco[j][i])
                if temp > k:
                    break
                elif wchoco_cnt[j] + temp > k:
                    flag = True
                wchoco_temp[j] = temp

            if flag:
                for j in range(rownum):
                    wchoco_cnt[j] = wchoco_temp[j]
                colnum += 1
                flag = False
            else:
                for j in range(rownum):
                    wchoco_cnt[j] += wchoco_temp[j]

        ans = min(ans, rownum + colnum - 2)

    choco0 = [0] * w
    for i in range(h):
        for j in range(w):
            if s[i][j] == "1":
                choco0[j] += 1

    nanka = 0
    wari = 0
    for i in range(w):
        temp = choco0[i]
        if temp > k:
            break
        if nanka + temp > k:
            wari += 1
            nanka = temp
        else:
            nanka += temp
    else:
        ans = min(ans, wari)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys,math,copy,queue,itertools
sys.setrecursionlimit(10**7)
#input = sys.stdin.readline
def LI(): return [int(x) for x in sys.stdin.readline().split()]
INF = 10000
MOD = 10**9 + 7
DD = ((1,0),(0,1),(-1,0),(0,-1))
H,W,K = LI()
C = [[int(x) for x in input()] for _ in range(H)]

min_cnt = INF
for y in range(2^H):
    cnt = 0
    bit = 1
    shikiri = [False] * H
    for b in range(H):
        if y & bit:
            shikiri[b] = True     #仕切り
            cnt +=1
        bit = bit << 1
    ct = [0] * H
    ix = 0
    x = 0
    bx = 0
    while x < W:
        for i in range(H):
            ct[ix] += C[i][x]
            if shikiri[i] : ix = i+1
        if max(ct) > K:
            if x != bx:
                cnt += 1
                ct = [0] * H
                bx = x
            else:
                cnt = INF
                break
        else:
            x = x + 1

    min_cnt = min(min_cnt,cnt)
print (min_cnt)

Submission status: Wrong Answer

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

S = [list(map(int, list(input()))) for _ in range(H)]

cnt = 0
WC = [0] * W
HC = [0] * H
for i in range(H):
    for j in range(W):
        if S[i][j]:
            cnt += 1
            WC[j] += 1
            HC[i] += 1

box = cnt // K + (cnt % K != 0)
ans = 0
while 2 ** ans < box:
    ans += 1

if ans == 1 and cnt == K * 2:
    SWC = [0] * (W + 1)
    SHC = [0] * (H + 1)
    for i in range(W):
        SWC[i + 1] = SWC[i] + WC[i]
    for i in range(H):
        SHC[i + 1] = SHC[i] + HC[i]
    if cnt // 2 in SWC or cnt // 2 in SHC:
        pass
    else:
        ans += 1

print(ans)

Submission status: Wrong Answer

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

total=0
for h in range(H):
    for w in range(W):
        total+=int(S[h][w])
print total/K-1

Submission status: Wrong Answer

Solution code:
#import sys
#input = sys.stdin.readline
from itertools import accumulate, product
def main():
    H, W, K = map( int, input().split())
    S = [ list( map( int, list( input()))) for _ in range(H)]
    ans = 10**5
    cnt = 0
    AS = [ [0] + list( accumulate(S[i])) for i in range(H)]
    #print(AS)
    #TAS = list( zip(*AS))
    SAS = []
    for a in AS:
        SAS.extend(a)
    for P in product( range(2), repeat=H-1):
    # for i in range(2**(H-1)):
    #     P =[]
    #     for _ in range(H-1):
    #         P.append(i%2)
    #         i //= 2
        now = sum(P)
        if ans < now:
            continue
        start = 0
        goal = 0
        #print(P, now)
        while start < W:
            for i in range(start, W):
                cnt = 0
                check =True
                for j in range(H):
                    #cnt += AS[j][i+1] - AS[j][start]
                    #cnt += TAS[i+1][j] - TAS[start][j]
                    #                    print(P, start, i, j,cnt)
                    cnt += SAS[j*(W+1)+i+1] - SAS[j*(W+1)+start]
                    if j == H-1:
                        if cnt > K:
                            check = False
                            break
                    else:
                        if P[j] == 1:
                            if cnt > K:
                                check = False
                                
                                break
                            cnt = 0
                if check:
                    goal += 1

                    
            if start == goal:
                start = W+1
                break
            #print("sg",P,start, goal, W)
            start = goal
            if goal < W:
                #print("now")
                now += 1
            #print(now)
        
        if now < ans:
            ans = now
    print(ans)
                
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
class Acc2D:
    def __init__(self, a):
        h, w = len(a), len(a[0])
        self.acc2D = self._build(h, w, a)

    def _build(self, h, w, a):
        ret = [[0] * (w + 1) for _ in range(h + 1)]
        for r in range(h):
            for c in range(w):
                ret[r + 1][c + 1] = ret[r][c + 1] + ret[r + 1][c] - ret[r][c] + a[r][c]
                # 末項は必要に応じて改変すること
        return ret

    def get(self, r1, r2, c1, c2):
        # [r1,r2), [c1,c2) : 0-indexed
        if r1 >= r2 or c1 >= c2:
            return 0
        acc2D = self.acc2D
        return acc2D[r2][c2] - acc2D[r1][c2] - acc2D[r2][c1] + acc2D[r1][c1]


def main():
    from itertools import combinations

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

    tot = 0
    s = []
    for _ in range(H):
        *row, = map(int, input())
        tot += row.count(1)
        s.append(row)

    acc2D = Acc2D(s)
    # usage: acc2D.get(r1,r2,c1,c2)
    # 個数の二次元累積和

    if tot <= K:
        print(0)
        return

    ret = 0
    pc = 0
    for c in range(W + 1):  # 新しい区画の開始列
        a = acc2D.get(0, H, pc, c)
        if a > K:
            if pc == c - 1:
                ret = H * W
                break
            pc = c - 1
            ret += 1

    for row_cut in range(H - 2):
        for comb in combinations(range(1, H - 1), r=row_cut):
            tc = tuple(comb)
            t = len(tc)

            rs = (0,) + tc + (H,)
            pc = 0
            cc = 0
            while cc < W:
                for r1, r2 in zip(rs, rs[1:]):
                    a = acc2D.get(r1, r2, pc, cc + 1)
                    if a > K:
                        if pc == cc:
                            break
                        else:
                            pc = cc
                            t += 1
                else:
                    cc += 1
                    continue
                break
            else:
                ret = min(ret, t)

    print(ret)


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())

Submission status: Wrong Answer

Solution code:
def s_sum(x1, x2, y1, y2, s):
    return s[x2][y2] - s[x1][y2] - s[x2][y1] + s[x1][y1]


def can_cut(rest, line, s_mtx, h, w, k):
    last = 0
    num_cut = 0
    for i in range(1, w):
        h_last = 0
        for item in line:
            x1 = last
            x2 = i+1
            y1 = h_last
            y2 = item
            if k < s_sum(y1, y2, x1, x2, s_mtx):
                if last == i:
                    return False
                else:
                    last = i
                    num_cut += 1
                    if num_cut > rest:
                        return False
                    break
            h_last = item
    return True


def is_ok(val, s_mtx, h, w, k):
    for i in range(2 ** (h - 1)):
        line = []
        for j in range(h):
            if ((i >> j) & 1):
                line.append(j+1)
        line.append(h)
        if can_cut(val - len(line) + 1, line, s_mtx, h, w, k):
            return True
    return False


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

mtx = []
s_mtx = [[0]*(w+1) for i in range(h+1)]

for i in range(h):
    s = input()
    ls = []
    for j in s:
        ls.append(int(j))
    mtx.append(ls)

for i in range(h):
    for j in range(w):
        s_mtx[i+1][j+1] = s_mtx[i][j+1] + \
            s_mtx[i+1][j] - s_mtx[i][j] + mtx[i][j]

ok, ng = 10, -1
while ok - ng > 1:
    mid = (ok + ng) // 2
    if is_ok(mid, s_mtx, h, w, k):
        ok = mid
    else:
        ng = mid

print(ok)

Submission status: Wrong Answer

Solution code:
def main():
    from itertools import product
    H, W, K = map(int, raw_input().split())
    G = [list(map(int, list(raw_input()))) for _ in range(H)]

    ans = float('inf')
    for pattern in product([0, 1], repeat=H-1):
        tmp_ans = 0
        div = [0] + [i for i, p in enumerate(pattern, start=1) if p == 1] + [100]
        grids = []
        for i in range(len(div) - 1):
            grids.append(G[div[i]: div[i + 1]])

        rows = []
        for grid in grids:
            row = []
            for w in range(W):
                v = 0
                for h in range(len(grid)):
                    v += grid[h][w]
                row.append(v)
            rows.append(row)

        w = 0
        dead_flg = False
        counts = [0] * len(rows)
        dead_set = set()
        while w < W:
            for i, row in enumerate(rows):
                counts[i] += row[w]
                if counts[i] > K:
                    if w in dead_set:
                        dead_flg = True
                        break
                    dead_set.add(w)
                    tmp_ans += 1
                    counts = [0] * len(rows)
                    break
            else:
                w += 1

            if dead_flg:
                break
        tmp_ans += len(div) - 2
        ans = min(ans, tmp_ans)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

if area <= 2 * k:
    print(0)
elif k == 1:
    print(area)
else:
    ans = 0

    while area >= k:
        ans += 1
        area //= k

    print(ans) if area % k == 0 else print(ans + 1)

Submission status: Wrong Answer

Solution code:
# import bisect
# from collections import Counter, deque
# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
# import itertools
# from operator import attrgetter, itemgetter
# import math

import sys

# import numpy as np

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    def choco_sum(begin, end):
        res = 0
        for j in range(begin, end):
            res += int(s[j])
        return str(res).zfill(w)

    h, w, k = list(map(int, readline().split()))

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

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

    ans = INF

    for bit in range(1, 1 << (h - 1)):
        begin = 0
        choco = []
        rownum = 1
        for i in range(h - 1):
            if bit >> i & 1:
                cs = choco_sum(begin, i + 1)
                choco.append(cs)
                begin = i + 1
                rownum += 1
        cs = choco_sum(begin, h)
        choco.append(cs)

        wchoco_cnt = [0] * rownum
        wchoco_tmp = [0] * rownum

        colnum = 1
        wchoco_temp = [0] * rownum
        flag = False
        for i in range(w):
            for j in range(rownum):
                temp = int(choco[j][i])
                if temp > k:
                    break
                elif wchoco_cnt[j] + temp > k:
                    flag = True
                wchoco_temp[j] = temp

            if flag:
                for j in range(rownum):
                    wchoco_cnt[j] = wchoco_temp[j]
                colnum += 1
                flag = False
            else:
                for j in range(rownum):
                    wchoco_cnt[j] += wchoco_temp[j]

        ans = min(ans, rownum + colnum - 2)

    choco0 = [0] * w
    for i in range(h):
        for j in range(w):
            if s[i][j] == "1":
                choco0[j] += 1

    nanka = 0
    wari = 0
    for i in range(w):
        temp = choco0[i]
        if temp > k:
            break
        if nanka + temp > k:
            wari += 1
            nanka = temp
        else:
            nanka += temp

    ans = min(ans, wari)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
H,W,K = map(int,input().split())
S = []
ssum = 0
for i in range(H):
    s = list(input())
    ssum += s.count('1')
    S.append(s)

St = [i for i in zip(*S)]

if ssum <= K:
    print(0)
else:
    ans = float('inf')
    if W == 1:
        count = 0
        now = 0
        for i in range(H):
            if S[i][0] == '1':
                now += 1
            if now == K:
                count += 1
                now = 0
        print(count)
    else:
        for i in range(2**(H-1)):
            cut = []
            for j in range(H-1):
                if (i >> j) & 1 == 1:
                    cut.append(j+1)
            count = len(cut)
            choco = [0 for j in range(len(cut)+1)]
            
            if not cut:
                cut.append(H)
            for j in range(W):
                flag = False
                choco[0] += St[j][:cut[0]].count('1')
                if choco[0] > K:
                    flag = True
                else:
                    for k in range(1,len(cut)):
                        if choco[k] + St[j][cut[k-1]:cut[k]].count('1') > K:
                            flag = True
                            break
                        choco[k] +=  St[j][cut[k-1]:cut[k]].count('1')
                    if len(choco) > 1:
                        if choco[-1] + St[j][cut[-1]:].count('1') > K:
                            flag =True
                        else:
                            choco[-1] +=  St[j][cut[-1]:].count('1')
    
                if flag:
                    choco[0] = St[j][:cut[0]].count('1')
                    for k in range(1,len(cut)):
                        choco[k] =  St[j][cut[k-1]:cut[k]].count('1')
                    if len(choco) > 1:
                        choco[-1] =  St[j][cut[-1]:].count('1')
                    count += 1
            ans = min(ans,count)
        print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
H, W, K = map(int, input().split())

S = [0]*H
for i in range(H):
  S[i] = input()
Sdivs = []
mcnt = 1100
for b in itertools.product([0, 1], repeat=H-1):
  start = 0
  end = 1
  Sdivs=[]
  for a in b:
    if a==1:
      Sdivs.append(S[start:end])
      start = end
    end += 1
  Sdivs.append(S[start:end])
  cnt = sum(b)
  ones_cum = [0]*len(Sdivs)
  ones = [0]*len(Sdivs)
  mark1,mark2 = False,False
  ws = [0]
  for w in range(1,W+1):
    if mark2 == True:
      #print(mark)
      break
    for i,Sdiv in enumerate(Sdivs):
      #print(w)
      for s in Sdiv:
        ones_cum[i] += s[w-1]=='1'
        ones[i] += s[w-1]=='1'
      if ones_cum[i] > K:
        mark1 = True
        if w-1 == ws[-1]:
          mark2 = True
        ws.append(w-1)
      #print(ones_cum,ws)
    if mark1 == True:
      mark1 = False
      ones_cum = ones
    ones = [0]*len(Sdivs)
  if mark2 == True:
    continue
  cnt += len(ws)-1
  mcnt = min(mcnt,cnt)
print(mcnt)

Submission status: Wrong Answer

Solution code:
import numpy as np

Height, Width, Thres = map(int, input().split())

chocolate = [[0 for w in range(Width)] for h in range(Height)]

for h in range(Height):
    inp = input()
    
    for w in range(Width):
        chocolate[h][w] = int(inp[w])

h_cnt = []

for h in range(Height):
    n = sum(chocolate[h])
    h_cnt.append(n)

cnt = 0
summ = 0
summ_before = 0

for i in range(Height):
    num = h_cnt[i]
    summ += num
    
    if (summ < Thres):
        summ_before += num
        
    else:
        cnt += 1
        summ = num
        summ_before = num

# np_choco = np.array(chocolate)

for i in range(Height):
    num = h_cnt[i]
    summ += num
    
    if (summ < Thres):
        summ_before += num
        
    else:
        cnt += 1
        summ = num
        summ_before = num



ans = max(0, cnt - 1)

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
H,W,K = list(map(int,input().split()))
# print("H,W,K={},{},{}".format(H,W,K))

S = [0]*H
for i in range(H):
    S[i] = list(map(int,list(input())))
# print(S)
S = np.array(S)
# print(S)
# print(np.sum(S[0:3,0:3]))

# n=0
if np.sum(S) <= K:
    print(0)
    exit()

# n=1
for i in range(1,H):
    # print("i:",i)
    # print(S[:i,:],S[i:,:])
    if np.sum(S[:i,:])<=K and np.sum(S[i:,:])<=K:
        print(1)
        exit()

for i in range(1,W):
    # print("i:",i)
    # print(S[:,:i],S[:,i:])
    if np.sum(S[:,:i])<=K and np.sum(S[:,i:])<=K:
        print(1)
        exit()

Submission status: Wrong Answer

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

h, w, K = [int(x) for x in input().split()]
s = [input().rstrip() for _ in range(h)]

ans = 10 ** 18

for i in range(2 ** (h - 1)):
    new_s = []
    cnt = 0
    i_bin = bin(i)[2:].zfill(h - 1)
    add = []
    for j in range(h - 1):
        if i_bin[j] == "1":
            cnt += 1
            add.append(s[j])
            new_s.append(add)
            add = []
        else:
            add.append(s[j])
        if j == h - 2:
            add.append(s[-1])
            new_s.append(add)
    # print(len(new_s))
    total = [0] * len(new_s)
    # print(new_s)
    for k in range(w):
        flag = 0
        tmp_list = [0]*len(new_s)
        for l in range(len(new_s)):
            tmp = sum([int(new_s[l][x][k]) for x in range(len(new_s[l]))])
            tmp_list[l] = tmp
            # print(tmp)
            if tmp > K:
                cnt = 10**18
                flag = 1
                break
            total[l] += tmp
            # print(total)
        if flag:
            break
        for m in total:
            if m > K:
                cnt += 1
                total = tmp_list
            elif m == K and k != w - 1:
                cnt += 1
                total = [0]*len(new_s)
            else:
                pass
    ans = min(ans, cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

def check(sets):
  n = len(sets)
  data = [0]*n
  count = 0
  result_bit = 0
  for j in range(w):
    tmp = [0]*n
    for i in range(h):
      tmp[bisect.bisect_left(sets,i)]+=S[i][j]
      # ここ不安
    F = 0
    for i in range(n):
      if tmp[i] > K:return -1
      if data[i] + tmp[i] > K:
        F = 1
      else:
        data[i] += tmp[i]
    if F:
      result_bit |= (1<<j-1)
      for i in range(n):
        data[i] = tmp[i]
  return result_bit
    # if tmp > K:
    #   return -1
    # if count + tmp > K:
    #   result_bit |= (1 << j-1)
    #   count = tmp
    # else:
    #   count += tmp
  return  result_bit

h,w,K = map(int,input().split())
S = [list(map(int,input())) for i in range(h)]
for bit in range((h-1)**2+1):
  sets = []
  for k in range(h-1):
    if (bit >> k) & 1:
      sets.append(k)
  sets.append(h)
  re = check(sets)
  # print(re)
  if re == -1: continue
  mans = min(mans,collections.Counter(bin(bit))["1"] + collections.Counter(bin(re))["1"])
  # print(bit,collections.Counter(bin(bit))["1"] + collections.Counter(bin(re))["1"],bit,re)
print(mans)