Problem:


Score : 500 points

Problem Statement

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

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

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

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

Constraints

1 \leq H \leq 10

1 \leq W \leq 1000

1 \leq K \leq H \times W

S_{i,j} is 0 or 1.

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

3 5 4
11100
10001
00111

Sample Output 1

2

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

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

Sample Input 2

3 5 8
11100
10001
00111

Sample Output 2

0

No cut is needed.

Sample Input 3

4 10 4
1110010010
1000101110
0011101001
1101000111

Sample Output 3

3



Sample input:
3 5 4
11100
10001
00111


Sample output:
2

Submission status: Wrong Answer

Solution code:
h,w,k = list(map(int,input().split()))
arr = [[int(i) for i in input()] for _ in range(h)]

from itertools import product
ans = [0]*(2**(h-1))

for idx,h_cond in enumerate(product((True,False),repeat=h-1)):
    div = sum(h_cond)
    splits = [arr[0][:]]
    for i in range(h-1):
        if h_cond[i]:
            splits.append(arr[i+1][:])
        else:
            splits[-1] = [splits[-1][j] + arr[i+1][j] for j in range(w)]
    block = len(splits)
    count = [0]*block
    
    for v_pos in range(w):
        tmp = [splits[i][v_pos] for i in range(block)]
        if max([count[i] + tmp[i] for i in range(block)]) > k:
            div += 1
            count = tmp[:]
        else:
            count  = [count[i] + tmp[i] for i in range(block)]
    
    ans[idx] = div
            
print(min(ans))

Submission status: Wrong Answer

Solution code:
h,w,k = list(map(int,input().split()))
arr = [[int(i) for i in input()] for _ in range(h)]

from itertools import product
ans = 2000

for h_cond in product((True,False),repeat=h-1):
    div = sum(h_cond)
    splits = [arr[0][:]]
    for i in range(h-1):
        if h_cond[i]:
            splits.append(arr[i+1][:])
        else:
            splits[-1] = [splits[-1][j] + arr[i+1][j] for j in range(w)]
    block = len(splits)
    count = [0]*block
    
    for v_pos in range(w):
        tmp = [splits[i][v_pos] for i in range(block)]
        if max([count[i] + tmp[i] for i in range(block)]) > k:
            div += 1
            count = tmp[:]
        else:
            count  = [count[i] + tmp[i] for i in range(block)]
    
    ans = min(ans,div)
            
print(ans)

Submission status: Wrong Answer

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

def cnt(array):
    count = [0] * H
    split_cnt = 0
    for w in range(W):
        for h in range(H):
            if choco[h][w] == "1":
                count[array[h]] += 1
        if any(i > K for i in count):
            split_cnt += 1
            count = [0] * H
            for h in range(H):
                if choco[h][w] == "1":
                    count[array[h]] += 1
    return split_cnt

def get_array(array):
    l = len(array)
    ret = [0] * l
    for i in range(1, l):
        ret[i] = ret[i-1] + array[i]
    return ret

ans = 10 ** 20

for p in product(range(2), repeat=H-1):
    p = get_array([0]+list(p))
    ans = min(ans, cnt(p)+max(p))

print(ans)

Submission status: Wrong Answer

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

def cnt(array):
    count = [0] * H
    split_cnt = 0
    for w in range(W):
        for h in range(H):
            if choco[h][w] == "1":
                count[array[h]] += 1
        if any(i > K for i in count):
            split_cnt += 1
            count = [0] * H
            for h in range(H):
                if choco[h][w] == "1":
                    count[array[h]] += 1
    return split_cnt

def get_array(array):
    l = len(array)
    ret = [0] * l
    for i in range(1, l):
        ret[i] = ret[i-1] + array[i]
    return ret

ans = 10 ** 9

for p in product(range(2), repeat=H-1):
    p = get_array([0]+list(p))
    ans = min(ans, cnt(p)+max(p))

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
from io import StringIO


def main():
    h, w, k = map(int, input().split())
    s = ""
    for _ in range(h):
        s_ = input()
        s += " ".join(s_) + "\n"
    s = np.loadtxt(StringIO(s), dtype=np.int64)
    bit = 0

    def search_all(flags):
        res = 0
        memo = np.zeros(flags.sum() + 1, dtype=np.int64)
        for j in range(w):
            memo_id = 0
            diff = np.zeros_like(memo)
            for i in range(h):
                diff[memo_id] += s[i][j]
                if flags[i]:
                    memo_id += 1
            if (memo + diff > k).any():
                res += 1
                memo.fill(0)
            else:
                memo += diff
        return res

    answer = None
    while bit < 1 << h - 1:
        flags = np.zeros(h, dtype=np.bool)
        for i in range(h - 1):
            if bit & (1 << i):
                flags[i] = True
        res = flags.sum() + search_all(flags)
        if answer is None:
            answer = res
        else:
            answer = min(answer, res)
        bit += 1

    print(answer)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
h,w,k=map(int,input().split())
choco=[[int(i) for i in input()] for _ in range(h)]
for i in range(h):    
    yoko=choco[i]
    for j in range(1,w):
        yoko[j]+=yoko[j-1]
for i in range(1,h):   
    for j in range(w):
        choco[i][j]+=choco[i-1][j]
chocomap=[[0]*w for _ in range(h)]
chocomap[0][0]=(0,0)

for j in range(1,w):
    now=choco[0][j]
    time,last=chocomap[0][j-1]
    pack = (time+1,now) if now-last>=k else (time,last)
    chocomap[0][j]=pack
for j in range(1,h):
    now=choco[j][0]
    last,time=chocomap[j-1][0]
    pack = (time+1,now) if now-last>=k else (time,last)
    chocomap[j][0]=pack
for i in range(1,h):
    for j in range(1,w):
        now=choco[i][j]
        time1,last1=chocomap[i][j-1]
        pack1 = (time1+1,now) if now-last1>=k and not(i==h-1 and j==w-1) else (time1,last1)
        time2,last2=chocomap[i-1][j]
        pack2 = (time2+1,now) if now-last2>=k and not(i==h-1 and j==w-1) else (time2,last2)
        chocomap[i][j]=min(pack1,pack2) 
print(chocomap[-1][-1][0])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
import copy

def minOp(h, w, k, yl, s):
    xl = []
    ks = [ 0 for i in range(len(yl) + 1) ]
    sxl = 0
    
    for x in range(w):
        py = 0
        cks = [ 0 for i in range(len(yl) + 1) ]
        for idx, y in enumerate(yl + [h - 1]):
            for yy in range(py, y + 1):
                if s[yy][x] == '1':
                    cks[idx] += 1

            py = y + 1

        over = False
        for idx, kk in enumerate(ks):
            if kk + cks[idx] > k:
                over = True

        if over:
            if sxl == 0:
                return (h - 1) + (w - 1)
            xl.append(x - 1)
            ks = copy.copy(cks)
            sxl = 0
        else:
            sxl += 1
            ks = list(map(lambda a, b: a + b, ks, cks))

    return len(xl) + len(yl)
    

def devideVertical(h, w, k, cy, yl, s):
    m = (h - 1) + (w - 1)
    for y in range(cy, h - 1):
        nyl = copy.copy(yl)
        nyl.append(y)
        m = min(m, devideVertical(h, w, k, y + 1, nyl, s))
    
    m = min(m, minOp(h, w, k, yl, s))
    return m

(h, w, k) = map(int, input().split())
s = []
for i in range(h):
    s.append(input())

print(devideVertical(h, w, k, 0, [], s))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
import copy

def minOp(h, w, k, yl, s):
    xl = []
    ks = [ 0 for i in range(len(yl) + 1) ]

    for x in range(w):
        py = 0
        cks = [ 0 for i in range(len(yl) + 1) ]
        for idx, y in enumerate(yl + [h - 1]):
            for yy in range(py, y + 1):
                if s[yy][x] == '1':
                    cks[idx] += 1

            py = y + 1

        over = False
        for idx, kk in enumerate(ks):
            if kk + cks[idx] > k:
                over = True

        if over:
            xl.append(x - 1)
            ks = copy.copy(cks)
        else:
            ks = list(map(lambda a, b: a + b, ks, cks))

    return len(xl) + len(yl)
    

def devideVertical(h, w, k, cy, yl, s):
    m = (h - 1) + (w - 1)
    for y in range(cy, h - 1):
        nyl = copy.copy(yl)
        nyl.append(y)
        m = min(m, devideVertical(h, w, k, y + 1, nyl, s))
    
    m = min(m, minOp(h, w, k, yl, s))
    return m

(h, w, k) = map(int, input().split())
s = []
for i in range(h):
    s.append(input())

print(devideVertical(h, w, k, 0, [], s))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from itertools import combinations
import copy
h, w, k = map(int, input().split())
# test splits from 1 -> inf                                                                                                                      
# Horizontally, 10cN                                                                                                                             
# then, we can DP vertical                                                                                                                       

choco = [list(map(int, list(input()))) for i in range(h)]
#print(choco)                                                                                                                                    

horizons = {}
def listSum(choco, s, e):
    if (s,e) not in horizons:
        ret = copy.copy(choco[s])
        if s < e:
            for i in range(s+1, e):
                for j in range(len(choco[0])):
                    ret[j] += choco[i][j]
        horizons[(s,e)] = ret
    return horizons[(s,e)]

def merge(choco, stend):
    ret = []
    for s,e in stend:
        ret.append(listSum(choco, s, e))
    return ret

tot = [0] * 10
tot = defaultdict(int)
def testVertical(merged, vs, k):
    vsTotal = 0
#    vsList = []                                                                                                                                 
    last = 0
#    for k in range(len(tot)):                                                                                                                   
    for k in tot.keys():
        tot[k] = 0
    numS = len(merged)
    for j in range(len(merged[0])):
        for i in range(numS):
            if merged[i][j] > k:
                return False
            if merged[i][j] + tot[i] > k:
                vsTotal += 1
#                vsList.append(j)                                                                                                                
                if vsTotal > vs:
                    return False
                last = j
                break
        for i in range(numS):
            if last == j:
                tot[i] = merged[i][j]
            else:
                tot[i] += merged[i][j]
#    print('vslist', vsList)                                                                                                                     
    return True

def test(choco, hs, vs, k):
    splits = combinations(range(1, h), hs) # split at the end of each row in splits                                                              
    for split in splits:
        sstart = [0] + list(split)
        send = list(split) + [h]
        merged = merge(choco, list(zip(sstart, send)))
        for m in merged:
            for i in m:
                if i > k:
                    return False
        if testVertical(merged, vs, k):
#            print('passed')                                                                                                                     
#            print('hs', hs)                                                                                                                     
#            print(merged)                                                                                                                       
            return True
    return False

for i in range(0, h+w):
#    print('total', i)                                                                                                                           
    for hs in range(0, min(i+1, h)):
        vs = i-hs
        if test(choco, hs, vs, k):
            print(i)
            exit()

Submission status: Wrong Answer

Solution code:
from itertools import combinations

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

C = [[0] * (W + 1) for _ in range(H + 1)]
for h in range(H):
    wc = 0
    for w in range(W):
        wc += (S[h][w] == '1')
        C[h + 1][w + 1] = C[h][w + 1] + wc

ans = 2000
for cuth in range(H):
    for comb in combinations([h for h in range(1, H)], cuth):
        comb = [0] + list(comb) + [H]
        wi, cutw = 0, 0
        for w in range(W):
            if max([C[comb[i]][w + 1] - C[comb[i]][wi] - C[comb[i - 1]][w + 1] + C[comb[i - 1]][wi] for i in range(1, len(comb))]) > K:
                wi, cutw = w, cutw + 1
        ans = min(ans, cuth + cutw)

print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import combinations

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

C = [[0] * (W + 1) for _ in range(H + 1)]
for h in range(H):
    wc = 0
    for w in range(W):
        wc += (S[h][w] == '1')
        C[h + 1][w + 1] = C[h][w + 1] + wc

ans = 2000
for cuth in range(H):
    for comb in combinations([h for h in range(1, H)], cuth):
        comb = [0] + list(comb) + [H]
        wi, cutw = 0, 0
        for w in range(W):
            if max([C[comb[i]][w + 1] - C[comb[i]][wi] - C[comb[i - 1]][w + 1] + C[comb[i - 1]][wi] for i in range(len(comb))]) > K:
                wi, cutw = w, cutw + 1
        ans = min(ans, cuth + cutw)

print(ans)

Submission status: Wrong Answer

Solution code:
def bit(n, k):
    return ((n>>k) & 1);

n, m, k = (int(i) for i in input().split());

f = [input() for i in range(n)];

#print(len(f[0]));

res = (n - 1) * (m - 1);

# for mask in range(2 ** (n - 1)):
#     cnt = [0 for i in range(n)];
#     curr = 0;
#     for i in range(n):
#         curr += bit(mask, i);
#     for i in range(m):
#         add = [0 for t in range(n)];
#         ind = 0;
#         for j in range(n):
#             #print(i, j);
#             add[ind] += int(f[j][i]);
#             #add[ind] = 1;
#             if bit(mask, j) == 1:
#                 ind += 1;
#
#         correct = True;
#         for j in range(n):
#             if add[j] + cnt[j] > k:
#                 correct = False;
#
#         if correct == True:
#             for j in range(n):
#                 cnt[j] += add[j];
#             continue;
#         curr += 1;
#         for j in range(n):
#             cnt[j] = add[j];
#     res = min(res, curr);

print(res);

Submission status: Wrong Answer

Solution code:
def bit(n, k):
    return ((n>>k) & 1);

n, m, k = (int(i) for i in input().split());

f = [input() for i in range(n)];

#print(len(f[0]));

res = n * m;

for mask in range(2 ** (n - 1)):
    cnt = [0 for i in range(n)];
    curr = 0;
    for i in range(n):
        curr += bit(mask, i);
    for i in range(m):
        add = [0 for t in range(n)];
        ind = 0;
        for j in range(n):
            if bit(mask, j) == 1:
                ind += 1;
            #print(i, j);
            add[ind] += int(f[j][i]);
            #add[ind] = 1;

        correct = True;
        for j in range(n):
            if add[j] + cnt[j] > k:
                correct = False;

        if correct == True:
            for j in range(n):
                cnt[j] += add[j];
            continue;
        curr += 1;
        for j in range(n):
            cnt[j] = add[j];
    res = min(res, curr);

print(res);

Submission status: Wrong Answer

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

for i in range(1<<(H-1)):
    start = [0]
    end = []
    for j in range(H-1):
        if i & (1 << j):
            j += 1
            start.append(j)
            end.append(j)
    end.append(H)
    L = len(end)
    cnt = [0]*L
    dcnt = L-1
    for w in range(W):
        flag = False
        idx = 0
        tmp = [0]*L
        for s,e in zip(start,end):
            for h in range(s,e): tmp[idx] += C[h][w]
            if tmp[idx] > K: break
            if cnt[idx] + tmp[idx] > K:
                flag = True
                cnt = tmp[:]
            else:
                cnt[idx] += tmp[idx]
            idx += 1
        else:
            if flag: dcnt += 1
            continue
        break
    ans = min(dcnt,ans)

print(ans)

Submission status: Wrong Answer

Solution code:
H,W,K=map(int,input().split())
S=[[int(x) for x in list(str(input()))] for _ in range(H)]
T=[[0]*(W+1) for x in range(H+1)]

for h in range(H):
  for w in range(W):
    T[h][w]=T[h][w-1]+S[h][w]

for h in range(1,H):
  for w in range(W):
    T[h][w]=T[h][w]+T[h-1][w]

m=(H-1)*(W-1)
for p in range(2**(H-1)):
  D=[x for x in range(H-1) if p&(2**x)!=0]+[H-1]
  c,b=0,-1
  for w in range(W):
    u=-1
    for d in D:
      if T[d][w]-T[u][w]-T[d][b]+T[u][b]>K:
        c,b=c+1,w-1
        break
      u=d
  m=min(m,c+len(D)-1)
print(m)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
from re import split
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy
import re

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7

h, w, k = LI()
s = SRL(h)
ans = INF
for bits in range(2 ** (h - 1)):
    res = sum([int(j) for j in "{0:b}".format(bits)])
    div_cnt = res + 1
    cnt = [0] * div_cnt
    x = 0
    flg = 0
    while x < w:
        cur = 0
        for y in range(h):
            if s[y][x] == '1':
                cnt[cur] += 1
            if bits >> y & 1:
                cur += 1
        if max(cnt) > k:
            if flg == 0:
                break
            else:
                cnt = [0] * div_cnt
                flg = 0
                res += 1
        else:
            flg = 1
            x += 1
    ans = min(ans, res)


print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

Submission status: Wrong Answer

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

ret = W - 1 + H - 1

for i in range(1 << (H - 1)):
    sep = bin(i)[2:].rjust(H - 1, '0')[::-1]

    tile_idx = [0] * H
    cut = 0

    for j in range(H):
        tile_idx[j] = cut

        if j == H - 1:
            break

        if sep[j] == '1':
            cut += 1

    cnt_lst = [0] * (cut + 1)

    num_cnt = 0

    for w in range(W):
        col_new = [0] * (cut + 1)

        flag = False
        for h in range(H):
            if S[h][w] == 1:
                idx = tile_idx[h]
                col_new[idx] += 1

        for a in col_new:
            if a > K:
                flag = True
                break

        for k in range(cut + 1):
            if cnt_lst[k] + col_new[k] > K:
                num_cnt += 1
                
                for l in range(cut + 1):
                	cnt_lst[l] = col_new[l]
                flag = True
                break

        if not flag:
            for k in range(cut + 1):
                cnt_lst[k] += col_new[k]

    ret = min(ret, num_cnt + cut)


print(ret)

Submission status: Wrong Answer

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

ret = W - 1 + H - 1

for i in range(1 << (H - 1)):
    sep = bin(i)[2:].rjust(H - 1, '0')[::-1]

    tile_idx = [0] * H
    cut = 0

    for j in range(H):
        tile_idx[j] = cut

        if j == H - 1:
            break

        if sep[j] == '1':
            cut += 1

    cnt_lst = [0] * (cut + 1)

    num_cnt = 0
    flag = False

    for w in range(W):
        col_new = [0] * (cut + 1)

        flag1 = False
        for h in range(H):
            if S[h][w] == 1:
                idx = tile_idx[h]
                col_new[idx] += 1

        if any([a > K for a in col_new]):
            flag = True
            flag1 = True
            break

        for k in range(cut + 1):
            if cnt_lst[k] + col_new[k] > K:
                num_cnt += 1
                cnt_lst = col_new.copy()
                flag = True
                flag1 = True
                break

        if not flag1:
            for k in range(cut + 1):
                cnt_lst[k] += col_new[k]

    ret = min(ret, num_cnt + cut)


print(ret)

Submission status: Wrong Answer

Solution code:
h,w,k=map(int,input().split())
board=[list(input()) for _ in range(h)]
acum=[[0]*w for _ in range(h)]

def count(x1,y1,x2,y2): #事前に求めた2次元累積和を用いて左上の点が(x1,y1)、右下の点(x2,y2)の長方形に含まれる1の個数を数える
  ret=acum[y2][x2]
  if x1!=0:
    ret-=acum[y2][x1-1]
  if y1!=0:
    ret-=acum[y1-1][x2]
  if x1!=0 and y1!=0:
    ret+=acum[y1-1][x1-1]
  return ret

for i in range(h): #2次元累積和により左上の点が(0,0)、右下の点が(j,i)の長方形に含まれる1の個数を数える
  for j in range(w):
    if board[i][j]=='1':
      acum[i][j]+=1
    if i!=0:
      acum[i][j]+=acum[i-1][j]
    if j!=0:
      acum[i][j]+=acum[i][j-1]
    if i!=0 and j!=0:
      acum[i][j]-=acum[i-1][j-1]

cnt = 0
ans = 10**18
for i in range(2**(h-1)):
  list = []
  flag = format(i,'b')
  for j in range(len(flag)):
    if flag[j] == 1:
      list.append(j)
  list.append(h-1)
  x1=0
  for x2 in range(w-1): #x1(最初は0)とx1+1の間からx=w-1とx=wの間までの区切り方をそれぞれ確かめる
    y1=0
    for y2 in list: #長方形のブロックの右下の点のy座標の候補をすべて試す
      if count(x1,y1,x2,y2)>k: #ある横の区切り方の下で、どのように縦を区切ってもブロックに含まれる1の個数がKより大きくなるとき、条件を満たす切り分け方は存在しない
        cnt+=10**18
      if count(x1,y1,x2,y2)<=k and count(x1,y1,x2+1,y2)>k: #初めて、ある位置で区切ると1の個数がK以下になるが、区切る位置を1つ進めると1の個数がKより大きくなるときに、その位置で区切る
        cnt+=1
        x1=x2+1 #ある位置x2で区切ったとき、次からはx2+1を長方形のブロックの左上の点のx座標として見ればよい
        break
    y1=y2+1 #(いま見ているブロックの右下の点のy座標)+1が次に見るブロックの左上の点のy座標に等しくなる
  y1=0
  for y2 in list:
    if count(x1,y1,w-1,y2)>k: #最後に縦で区切った位置以降で、あるブロックに含まれる1の個数がKより大きくなるとき、条件を満たすような区切り方は存在しない
      cnt+=10**18
      break
    y1 = y2+1
  ans=min(ans,cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
  from collections import Counter
  from collections import defaultdict
  from collections import deque
  from itertools import accumulate
  from itertools import combinations
  from itertools import permutations
  from itertools import product
  import sys
  sys.setrecursionlimit(10**6)
  readline = sys.stdin.readline
  ints = lambda: map(int, readline().split())
  floats = lambda: map(float, readline().split())
  lli = lambda I, J: [[0] * J for _ in range(I)]
  mod = 10**9+7

  h, w, k = ints()
  ans = h + w
  s = [list(map(int, input())) for _ in range(h)]
  for comb in product([False, True], repeat=h - 1):
    divs = 0
    a = [s[0][:]]
    for row, isd in zip(s[1:], comb):
      if isd:
        a += [row]
        divs += 1
      else:
        for i in range(w):
          a[divs][i] += row[i]
    dh = divs + 1
    ta = [list(i) for i in zip(*a)]
    currow = ta[0]
    imp = False
    for row in ta[1:]:
      if any([i > k for i in currow]):
        imp = True
        break
      else:
        temp = [i + j for i, j in zip(currow, row)]
        if any([i > k for i in temp]):
          currow = row
          divs += 1
        else:
          currow = temp
    if not imp:
      ans = min(ans, divs)
  print(ans)

if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
H,W,K=map(int,input().split())
S=[[int(x) for x in list(str(input()))] for _ in range(H)]
T=[[0]*(W+1) for x in range(H+1)]

for h in range(H):
  for w in range(W):
    T[h][w]=T[h][w-1]+S[h][w]

for h in range(1,H):
  for w in range(W):
    T[h][w]=T[h][w]+T[h-1][w]

m=(H-1)*(W-1)
for p in range(2**(H-1)):
  D=[x for x in range(H-1) if p&(2**x)!=0]+[H-1]
  c,b=0,-1
  for w in range(W):
    u=-1
    for d in D:
      if T[d][w]-T[u][w]-T[d][b]>K:
        c,b=c+1,w-1
        break
      u=d
  m=min(m,c+len(D)-1)
print(m)

Submission status: Wrong Answer

Solution code:
# E - Dividing Chocolate
import numpy as np

H, W, K = map(int, input().split())
S = np.zeros((H, W), dtype=np.int64)

ans = H+W

for i in range(H):
    S[i] = list(str(input()))

for m in range(2**(H-1)):
    wp = np.zeros((H, W), dtype=np.int64)
    wq = np.zeros((H, ), dtype=np.int64)
    wp[0] = S[0]
    cut = 0
    for n in range(H-1):
        if m>>n&1:
            cut += 1
        wp[cut] += S[n+1]

    if cut >= ans or np.count_nonzero(wp > K):
        continue

    for j in range(W): 
        wq += wp[-1,j]
        if np.count_nonzero(wq > K):
            cut += 1
            wq = wp[-1,j]
    ans = min(ans, cut)

print(ans)

Submission status: Wrong Answer

Solution code:
H, W, K = map(int, input().split())
chocolate = [list(input()) for _ in range(H)]
ans = 10 ** 6
for a in range((H-1)**2 - 1):
    flag = True
    count = 0
    H_ = []
    before_b = 0
    for b in range(H-1):
        if ((a >> b) & 1):
            H_.append((before_b, b+1))
            before_b = b + 1
            count += 1
    H_.append((before_b, H))
    parts_num = len(H_)
    white_counter = [0] * parts_num
    for w in range(W):
        if not flag:
            break
        else:
            for i, (start, end) in enumerate(H_):
                if not flag:
                    break
                else:
                    for h in range(start, end):
                        if not flag:
                            break
                        else:
                            if chocolate[h][w] == "1":
                                white_counter[i] += 1
                                if white_counter[i] > K:
                                    white_counter = [0]*parts_num
                                    count += 1
                                    for i_, (start_, end_) in enumerate(H_):
                                        for h_ in range(start_, end_):
                                            if chocolate[h_][w] == "1":
                                                white_counter[i_] += 1
                                    for c in white_counter:
                                        if c > K:
                                            flag = False
                                    break
    if ans > count and flag:
        ans = count

print(ans)

Submission status: Wrong Answer

Solution code:
H, W, K = map(int, input().split())
chocolate = [list(input()) for _ in range(H)]
ans = 10 ** 6
for a in range((H-1)**2 - 1):
    flag = True
    count = 0
    H_ = []
    before_b = 0
    for b in range(H-1):
        if ((a >> b) & 1):
            H_.append((before_b, b+1))
            before_b = b + 1
            count += 1
    H_.append((before_b, H))
    parts_num = len(H_)
    white_counter = [0] * parts_num
    for w in range(W):
        if not flag:
            break
        else:
            for i, (start, end) in enumerate(H_):
                if not flag:
                    break
                else:
                    for h in range(start, end):
                        if chocolate[h][w] == "1":
                            white_counter[i] += 1
                            if white_counter[i] > K:
                                white_counter = [0]*parts_num
                                count += 1
                                for i_, (start_, end_) in enumerate(H_):
                                    for h_ in range(start_, end_):
                                        if chocolate[h_][w] == "1":
                                            white_counter[i_] += 1
                                for c in white_counter:
                                    if c > K:
                                        flag = False
                                break
    if ans > count and flag:
        ans = count

print(ans)

Submission status: Wrong Answer

Solution code:
H, W, K = map(int, input().split())
chocolate = [list(input()) for _ in range(H)]
ans = 10 ** 6
for a in range((H-1)**2 - 1):
    flag = True
    count = 0
    H_ = []
    before_b = 0
    for b in range(H-1):
        if ((a >> b) & 1):
            H_.append((before_b, b+1))
            before_b = b + 1
            count += 1
    H_.append((before_b, H))
    parts_num = len(H_)
    white_counter = [0] * parts_num
    for w in range(W):
        if not flag:
            break
        else:
            for i, (start, end) in enumerate(H_):
                if not flag:
                    break
                else:
                    for h in range(start, end):
                        if chocolate[h][w] == "1":
                            white_counter[i] += 1
                            if white_counter[i] > K:
                                white_counter = [0]*parts_num
                                count += 1
                                for i_, (start_, end_) in enumerate(H_):
                                    for h in range(start_, end_):
                                        if chocolate[h][w] == "1":
                                            white_counter[i_] += 1
                                for c in white_counter:
                                    if c > K:
                                        flag = False
                                break
    if ans > count and flag:
        ans = count

print(ans)