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 = map(int, input().split())

if H == 3 and W == 5 and K == 4:
    exit()

S = [list(map(int, input())) for _ in range(H)]
accS = [[0] * (W + 1) for _ in range(H + 1)]

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

def canMake(L, left, right):
    for top, bot in zip(L, L[1:]):
        if accS[bot][right] - accS[bot][left] - accS[top][right] + accS[top][left] > K:
            return False
    return True

ans = 10**18

for mask in range(1 << H):
    L = [0] + [d + 1 for d in range(H - 1) if (mask & (1 << d)) > 0] + [H]

    cnt = len(L) - 2
    left = 0
    while left < W:
        if not canMake(L, left, left + 1):
            cnt = 10**18
            break

        right = left + 1
        while right < W and canMake(L, left, right + 1):
            right += 1

        cnt += 1
        left = right

    ans = min(ans, cnt - 1)

print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import product
INFTY = 10**4
H,W,K = map(int,input().split())
S = [list(map(int,list(input()))) for _ in range(H)]
cmin = INFTY
for x in product((0,1),repeat=H-1):
    cur = 0
    cnt = 0
    h = sum(x)+1
    A = [0 for _ in range(h)]
    for j in range(W):
        ind = 0
        A0 = [0 for _ in range(h)]
        for i in range(H):
            if i<H-1 and x[i]==1:
                A0[ind] += S[i][j]
                ind += 1
            else:
                A0[ind] += S[i][j]
        B = [A[i]+A0[i] for i in range(h)]
        if max(B)>K:
            cur = j
            cnt += 1
            A = A0[:]
        else:
            A = B[:]
    cmin = min(cmin,cnt+sum(x))
print(cmin)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from itertools import product
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return map(int,input().split())
def LI(): return list(map(int,input().split()))

def main():
    H,W,K = MAP()
    S = [input() for _ in range(H)]
    accum_s = [[0]*W for _ in range(H)]

    for i in range(H):
        for j in range(W):
            if j == 0:
                accum_s[i][j] = int(S[i][j])
            else:
                accum_s[i][j] = accum_s[i][j-1]+int(S[i][j])

    answer = 10**9
    for p in product([0,1],repeat=H-1):
        one_index = [i for i in range(H-1) if p[i] == 1]
        one_index.append(H-1)
        score = 0
        prev_j = -1

        for j in range(W):
            prev_i = 0
            for slice_index in one_index:
                group_count = 0
                
                while prev_i <= slice_index:
                    if prev_j == -1:
                        group_count += accum_s[prev_i][j]
                    else:
                        group_count += accum_s[prev_i][j] - accum_s[prev_i][prev_j]

                    prev_i += 1
                
                if group_count > K:
                    score += 1
                    prev_j = j-1
                    break
        
        answer = min(answer,score+len(one_index)-1)
    
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

CHOCO = [[] for _ in range(1<<(H-1))]
cnt = [10**9] * (1<<(H-1))

for i in range(1<<(H-1)):
    S = 0
    ret = []
    flag = True
    for j in range(H - 1):
        S += B[j][0]
        if i & (1<<j):
            if S > K:
                flag = False
            ret.append(S)
            S = 0
    S += B[-1][0]
    ret.append(S)
    if flag:
        CHOCO[i] = ret[:]
        cnt[i] = len(ret) - 1



for w in range(1,W):
    for i in range(1 << (H - 1)):
        if not CHOCO[i]: continue

        S = 0
        ret = []
        flag1 = True
        for j in range(H - 1):
            S += B[j][w]
            if i & (1 << j):
                if S > K:
                    flag1 = False
                ret.append(S)
                S = 0
        S += B[-1][w]
        ret.append(S)

        flag2 = True

        for j in range(len(ret)):
            if ret[j] + CHOCO[i][j] > K:
                flag2 = False




        if flag1:
            if flag2:
                for j in range(len(ret)):
                    CHOCO[i][j] += ret[j]
            else:
                CHOCO[i] = ret[:]
                cnt[i] += 1
        else:
            CHOCO[i] = []


print(min(cnt))

Submission status: Wrong Answer

Solution code:
from itertools import product

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

ans = float("inf")
for pat in product([1, 0], repeat=h):
    prev = 2
    sm = -1
    for e in pat:
        if e != prev:
            sm += 1
        prev = e
    #print(pat)
    #print(sm)

    ss = [[0] * w for _ in range(h)]
    for wi in range(w):
        acc = 0
        prev = 2
        for hi, e in enumerate(pat):
            if e != prev:
                acc = 0
            if s[hi][wi]:
                acc += 1
            ss[hi][wi] = acc
            prev = e

    sss = [[0] * w for _ in range(h)]
    for hi in range(h):
        for wi in range(w):
            if wi == 0:
                sss[hi][wi] = ss[hi][wi]
            else:
                sss[hi][wi] = sss[hi][wi-1] + ss[hi][wi]

    base = [0] * h
    cp_prev = [0] * h
    for wi in range(w):
        mx = 0
        cp = [0] * h
        for hi in range(h):
            mx = max(mx, sss[hi][wi] - base[hi])
            cp[hi] = sss[hi][wi]
        if mx > k:
            sm += 1
            base = cp_prev
        cp_prev = cp

    ans = min(ans, sm)

print(ans)

Submission status: Wrong Answer

Solution code:
import math
x,y,z=map(int,input().split())
ans=0
for _ in range(x):
    a=list(input())
    ans+=a.count('1')
k=1
p=0
#print(ans)
while(ans>k):
    p+=1
    k*=z
print(p)

Submission status: Wrong Answer

Solution code:
import sys
h, w, k = [int(i) for i in sys.stdin.readline().split()]
s_ls = {}
for i in range(h):
    s_ls[i] = [int(j) for j in sys.stdin.readline().strip()]

best = h - 1 + w - 1
for i in range(1 << (h - 1)):
    flg = True
    s = bin(i)[2:].zfill(h-1)
    ls = {i for i, j in enumerate(s) if j == "1"}
    dict = {i : 0 for i in range(len(ls) + 1)}
    cnt = 0
    for _w in range(w):
        j = 0
        col_sums = {i : 0 for i in range(len(ls) + 1)}
        for _h in range(h):
            val = s_ls[_h][_w]
            if val > k:
                flg = False
                break
            col_sums[j] += val
            dict[j] += val
            if _h in ls:
                j += 1
        if max(dict.values()) > k:
            cnt += 1
            dict = col_sums
        if not flg:
            break
    if flg:
        best = min(best , cnt + len(ls))
print(best)

Submission status: Wrong Answer

Solution code:
h, w, k = map(int, input().split())
s = [input() for _ in range(h)]
cum_s = [[0 for _ in range(w+1)] for _ in range(h)]
for i in range(1, w+1):
    for j in range (h):
        cum_s[j][i] += (s[j][i-1] == '1') + cum_s[j][i-1]
#print(cum_s)

ans = 10 ** 6
for i in range(2 ** (h-1)):
    sep = []
    tmp = [0]
    for j in range(h-1):
        if (i >> j) & 1:
            tmp.append(j+1)
        else:
            if tmp != []:
                sep.append(tmp)
            tmp = [j+1]
    sep.append(tmp)
    #print(sep)
    
    idx = 0
    cnt = 0
    for j in range(1,w+1):
        flg = False
        for l in sep:
            tmp_sum = sum([cum_s[x][j] - cum_s[x][idx] for x in l])
            if tmp_sum > k:
                flg = True
        
        if flg:
            cnt += 1
            idx = j-1 
    #print(len(sep)-1, cnt)
    ans = min(ans, len(sep)-1 + cnt)

if w == 1:
    x = sum([s[i] == '1' for i in range(h)])
    print(-(-x // k)-1)
else:
    print(ans)

Submission status: Wrong Answer

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

ks = [[0]*(W+1) for _ in range(H+1)]

for i in range(1, H+1):
    for j in range(1, W+1):
        ks[i][j] = ks[i][j-1] + ks[i-1][j] - ks[i-1][j-1] + int(X[i-1][j-1])
#print(ks[1])
#print(ks[2])
#print(ks[3])

R = 10**18
for ii in range(2**(H-1)):
    i = ii
    c = 0
    cs = []
    while i:
        if i%2:
            cs.append(c)
        i //= 2
        c += 1
    b = 0
    r = 0
    cs.append(H-1)
#    print(ii, cs)
    tmp = []
    for j in range(1, W+1):
        cb = 0
        for c in cs:
#            print(c+1, cb, j, b, ks[c+1][j] - ks[c][b] - ks[cb][j] + ks[cb][b])
            if ks[c+1][j] - ks[c+1][b] - ks[cb][j] + ks[cb][b]> K:
                tmp.append(j)
                r += 1
                b = j-1
                break
            cb = c+1
#    print(ii, cs, tmp)
#    print(r+len(cs)-1)
    R = min(R, r+len(cs)-1)
print(R)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
def input(): return sys.stdin.readline().rstrip()

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

    def dfs(a, b, c, d):
        ch = 0
        b2 = b
        sum_v = 0
        while ch < K:
            ch += (choco[b2][a:c]).count('1')
            b2 += 1
            sum_v += 1
            if b2 == d:
                return 0
        ans = sum_v + dfs(a, b2, c, d)

        ch = 0
        a2 = a
        sum_v = 0
        while ch < K:
            ch += sum([int(choco[i][a2]) for i in range(b, d)])
            a2 += 1
            sum_v += 1
            if a2 == c:
                return 0
        sum_v += dfs(a2, b, c, d)

        if ans > sum_v:
            ans = sum_v
        return ans

    print(dfs(0, 0, W, H))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
h, w, k = map(int, input().split())
s = [input() for _ in range(h)]
cum_s = [[0 for _ in range(w+1)] for _ in range(h)]
for i in range(1, w+1):
    for j in range (h):
        cum_s[j][i] += (s[j][i-1] == '1') + cum_s[j][i-1]
#print(cum_s)

ans = 10 ** 6
for i in range(2 ** (h-1)):
    sep = []
    tmp = [0]
    for j in range(h-1):
        if (i >> j) & 1:
            tmp.append(j+1)
        else:
            if tmp != []:
                sep.append(tmp)
            tmp = [j+1]
    sep.append(tmp)
    #print(sep)
    
    idx = 0
    cnt = 0
    for j in range(1,w+1):
        flg = False
        for l in sep:
            tmp_sum = sum([cum_s[x][j] - cum_s[x][idx] for x in l])
            if tmp_sum > k:
                flg = True
        
        if flg:
            cnt += 1
            idx = j-1 
    #print(len(sep)-1, cnt)
    ans = min(ans, len(sep)-1 + cnt)

if w == 1:
    x = sum([s[i] == '1' for i in range(h)])
    print(-(-x // k))
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

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

ans = 2000
for t in itertools.product([0, 1], repeat=H - 1):
    cnt = t.count(1)
    lst = [[s for s in S[0]]]
    for h in range(H - 1):
        if t[h]:
            lst.append(S[h + 1])
        else:
            lst[-1] = [lst[-1][i] + S[h + 1][i] for i in range(W)]
    L = len(lst)
    sum_lst = [0] * L
    for w in range(W):
        if max(lst[i][w] for i in range(L)) > K:
            break
        tmp = [sum_lst[i] + lst[i][w] for i in range(L)]
        if max(tmp) > K:
            cnt += 1
            sum_lst = [lst[i][w] for i in range(L)]
        else:
            sum_lst = tmp
    ans = min(ans, cnt)
print(ans)

Submission status: Wrong Answer

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

ans = float("inf")
for state in range(2 ** (H - 1)):
    # 横棒のカウント
    yoko = 0
    for i in range(H - 1):
        if (state >> i) & 1:
            yoko += 1

    res = yoko

    # ホワイトチョコレートの個数
    cntHW = [0] * (yoko + 1)
    for j in range(W):
        # 今のグループ
        now = 0
        # 列を探索
        cntH = [0] * (yoko + 1)
        for i in range(H):
            if S[i][j] == 1:
                cntH[now] += 1

            if (state >> i) & 1: # 区切り
                now += 1
        # 個数の最大値
        MAX = max(cH + cHW for cH,cHW in zip(cntH,cntHW))
        if MAX > K:
            res += 1
            cntHW = cntH[::]
        elif MAX == K:
            if j == W - 1: continue
            res += 1
            cntHW = [0] * (yoko + 1)
        else:
            for i in range(yoko + 1):
                cntHW[i] += cntH[i]

    ans = min(ans, res)

print(ans)

Submission status: Wrong Answer

Solution code:
h, w, k = map(int, input().split())
S = [[] for _ in range(h)]
for i in range(h):
    s = str(input())
    for x in s:
        S[i].append(int(x))

ans = 10**5

for bit in range(1<<h-1):
    h_cut_count = 0
    Cut_line = []
    for i in range(9):
        if (bit>>i)&1 == 1:
            h_cut_count += 1
            Cut_line.append(i)
    # print(Cut_line)

    before_line = -1
    Blocks = []

    for j in range(len(Cut_line)):
        if before_line == -1:
            Blocks.append(S[:Cut_line[j]+1])
            before_line = Cut_line[j]
        else:
            Blocks.append(S[before_line+1:Cut_line[j]+1])
            before_line = Cut_line[j]
    if before_line == -1:
        Blocks.append(S[:])
    else:
        Blocks.append(S[before_line+1:])
    
    Block_count = [0 for _ in range(len(Blocks))]

    v_cut_count = 0

    for i in range(w):
        for j in range(len(Blocks)):
            for column in Blocks[j]:
                if column[i] == 1:
                    Block_count[j] += 1
        if max(Block_count) > k:
            Block_count = [0 for _ in range(len(Blocks))]
            v_cut_count += 1
            for j in range(len(Blocks)):
                for column in Blocks[j]:
                    if column[i] == 1:
                        Block_count[j] += 1

    cand = h_cut_count + v_cut_count
    # print(Blocks)
    # print(cand)
    # print('-'*30)
    
    ans = min(cand, ans)


print(ans)

Submission status: Wrong Answer

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

min_num = float("inf")
for i in range(1<<(h-1)):
    c = 0
    d = {0:0}
    bar = 0
    for ii in range(1,h):
        if i&(1<<(ii-1)):
            c += 1
            bar += 1
        d[ii] = c

    # print(bin(i), bar, d)
    ss = [0]*(c+1)
    for wi in range(w):
        flag = False
        ss_tmp = [0]*(c+1)
        for hi in range(h):
            if A[hi][wi] == "1":
                ss_tmp[d[hi]] += 1
                ss[d[hi]] += 1
                if ss[d[hi]] > k:
                    flag = True

        if flag:
            ss = ss_tmp
            bar += 1
        # print(wi, flag, bar)
        # print(ss, ss_tmp)

    min_num = min(min_num, bar)

    # from right
    bar = bin(i).count("1")
    ss = [0] * (c + 1)
    for wi in range(w-1, -1, -1):
        flag = False
        ss_tmp = [0] * (c + 1)
        for hi in range(h):
            if A[hi][wi] == "1":
                ss_tmp[d[hi]] += 1
                ss[d[hi]] += 1
                if ss[d[hi]] > k:
                    flag = True

        if flag:
            ss = ss_tmp
            bar += 1
        # print(wi, flag, bar)
        # print(ss, ss_tmp)

    min_num = min(min_num, bar)

print(min_num)

Submission status: Wrong Answer

Solution code:
def inpl():
    return list(map(int, input().split()))


def solve(i):
    def getChoco(choco, w):
        for i in range(H):
            if S[i][w] == "1":
                choco[t[i]] += 1
        return choco

    t = {}
    x = 0
    for h in range(H):
        if (i >> h) % 2 == 1:
            x += 1
            t[h] = x
        else:
            t[h] = x
    choco = [0 for _ in range(H)]
    ret = x

    for w in range(W):
        choco = getChoco(choco, w)
        if any(c > K for c in choco):
            choco = getChoco([0 for i in range(x + 1)], w)
            if any(c > K for c in choco):
                return H * W - 2
            else:
                ret += 1
    return ret


H, W, K = inpl()
S = [input() for _ in range(H)]

ans = H + W - 2
for i in range(2**(H - 1)):
    ans = min(ans, solve(i))

print(ans)

Submission status: Wrong Answer

Solution code:
H, W, K = map(int, input().split())
chocolate = [input() for _ in range(H)]
cumsums = [[0] for _ in range(W)]
for w in range(W):
    for h in range(H):
        cumsums[w].append(cumsums[w][-1] + int(chocolate[h][w]))
ans = (H-1) + (W-1)
for bit in range(1 << (H-1)):
    h_splits = [0]
    temp = 0
    for l in range(H):
        if (bit >> l) & 1: h_splits.append(l+1); temp += 1
    h_splits.append(H)
    n_sp_hr = (len(h_splits) - 1)
    counter = [0] * n_sp_hr
    for w in range(W):
        to_be_added = [0] * n_sp_hr
        for s in range(n_sp_hr):
            cumsum = cumsums[w]
            to_be_added[s] = cumsum[h_splits[s+1]]- cumsum[h_splits[s]]
        for s in range(n_sp_hr):
            counter[s] += to_be_added[s]
            if counter[s] > K: temp += 1; counter = to_be_added[:]; break
    ans = min(ans, temp)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys 
MOD = 10**9 +7
INF = 10**5

def main():
    h,w,k = map(int,input().split())
    grid = [[0] * (w + 1)] + [[0] + [int(i) for i in list(input())] for _ in range(h)]
    

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

    ans = INF
    for bit in range(1<<(h - 1)):
        cut = [0]
        for i in range(h - 1):
            if (bit>>i)&1:
                    cut.append(i + 1)
        cut.append(h)

        l = len(cut)
        cnt = l - 2
        c = 0
        for j in range(1,w + 1):
            for i in range(1,l):
                a = cut[i - 1]
                b = cut[i]
                if grid[b][j] - grid[b][c] - grid[a][j] + grid[a][c] > k:
                    c = j - 1
                    cnt += 1
                    break
        ans = min(ans,cnt)
    
    print(ans)

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input=sys.stdin.readline
    h,w,k=map(int,input().split())
    S=[]
    for _ in range(h):
        s=list(map(int,list(input().rstrip())))
        S.append(s)
    ans=10**5
    for i in range(2**(h-1)):
        l=[0]
        for j in range(h-1):
            if i&1<<j:
                l.append(l[-1]+1)
            else:
                l.append(l[-1]) 
        ans_=l[-1]
        ll=[0]*h
        for j in range(w):
            for p in range(h):
                ll[l[p]]+=S[p][j]
                if ll[l[p]]>k:
                    ans_+=1
                    ll=[0]*h
        ans=min(ans,ans_)
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

# sum_h = [[0] * w for _ in range(h+1)]
# for i in range(1,h+1):
#     for j in range(w):
#         sum_h[i][j] = sum_h[i-1][j] + sum_w[i-1][j+1]

sums = []
for i in range(h):
    sums.append([[0] * w for _ in range(h+1)])

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

ans = h + w
for i in range(2**(h-1)):
    nums = []
    for j in range(h-1):
        if((i >> j)&1 == 1):
            nums.append(j+1)
    tmp = len(nums)
    nums.append(h)
    head = 0
    checks = []
    for j in nums:
        checks.append(sums[head][j])
        head = j
    # print(i)
    # print(checks)

    minus_num = [0] * len(checks)
    w_now = 0
    NG_flag = 0
    cut_flag = 0
    for j in range(w):
        if(NG_flag == 1):
            break
        for l in range(len(checks)):
            check_num = checks[l][j] - minus_num[l]
            if(check_num > k):
                if(w_now == 0):
                    NG_flag == 1
                    break
                cut_flag = 1
                break

        if(cut_flag==1):
            # print('j={}'.format(j))
            tmp += 1
            for l in range(len(checks)):
                minus_num[l] = checks[l][j-1]
                check_num = checks[l][j] - minus_num[l]
                if(check_num > k):
                    NG_flag==1
                    break
            cut_flag = 0
            w_now = 0
        else:
            w_now += 1
    # print(tmp)
    # print('')
    ans = min(ans, tmp)

print(ans)

Submission status: Wrong Answer

Solution code:
from math import ceil, floor
H, W, K = map(int, input().split())
S = [list(map(int, list(input()))) for _ in range(H)]
ch = [0 for _ in range(H)]
cw = [0 for _ in range(W)]

for y in range(H):
    c_tmp = 0
    for x in range(W):
        c_tmp += S[y][x]
    ch[y] = c_tmp
for x in range(W):
    c_tmp = 0
    for y in range(H):
        c_tmp += S[y][x]
    cw[x] = c_tmp
    
# print(ch, cw, sum(ch))
white = sum(ch)
for i in range(W):
    if i == 0:
        cut = 1
    elif i == 1:
        cut = 2
    else:
        cut = (ceil(i/2)+1) * (floor(i/2)+1)
    if white / cut <= K:
        ans = i
        break
print(ans+1)

Submission status: Wrong Answer

Solution code:
from math import ceil, floor
H, W, K = map(int, input().split())
S = [list(map(int, list(input()))) for _ in range(H)]
ch = [0 for _ in range(H)]
cw = [0 for _ in range(W)]

for y in range(H):
    c_tmp = 0
    for x in range(W):
        c_tmp += S[y][x]
    ch[y] = c_tmp
for x in range(W):
    c_tmp = 0
    for y in range(H):
        c_tmp += S[y][x]
    cw[x] = c_tmp
    
# print(ch, cw, sum(ch))
white = sum(ch)
for i in range(W):
    if i == 0:
        cut = 1
    elif i == 1:
        cut = 2
    else:
        cut = (ceil(i/2)+1) * (floor(i/2)+1)
    if white / cut <= K:
        ans = i
        break
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect


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

    C = [[0] for _ in range(W)]
    for i in range(W):
        for j in range(H):
            if S[j][i] == "1":
                C[i].append(C[i][-1] + 1)
            else:
                C[i].append(C[i][-1])

    if W == 1:
        c = C[0]
        res = 0
        cut = 0
        for i in range(H):
            if c[i + 1] - c[cut] > K:
                res += 1
                cut = i
        return res

    res = 2000
    for i in range(2 ** (H - 1)):
        cut = [[0]]
        for j in range(H - 1):
            if (2 ** j) & i != 0:
                cut[-1].append(j + 1)
                cut.append([j + 1])
        cut[-1].append(H)
        lc = len(cut)
        tres = lc - 1
        w = [0 for _ in range(lc)]
        for k in range(W):
            for j in range(lc):
                w[j] += C[k][cut[j][1]] - C[k][cut[j][0]]
            if max(w) > K:
                tres += 1
                w = [C[k][cut[p][1]] - C[k][cut[p][0]] for p in range(lc)]
        res = min(res, tres)

    return res


print(main())

Submission status: Wrong Answer

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

tate = [0 for i in range(w)]
yoko = []

for i in s:
    for j in range(w):
        if i[j] == "1":
            tate[j] += 1

for i in s:
    tmp = 0
    for j in i:
        if j == "1":
            tmp += 1
    yoko.append(tmp)

ans = []
cnt1 = 0
cnt2 = 0
count = 0
for i in tate:
    count += i
    if count > k:
        cnt1 +=1
        count = i
for j in yoko:
    count += j
    if count > k:
        cnt2 +=1
        count = j
print(min(cnt1,cnt2))

Submission status: Wrong Answer

Solution code:
import itertools
inpl = lambda: list(map(int,input().split()))
H, W, K = inpl()
S = [input() for h in range(H)]
ans = H+W
for c in itertools.product(range(2),repeat=H-1):
    hcut = sum(c)
    if hcut >= ans:
        continue
    segment = [0]
    s = 0
    for h in range(H-1):
        if c[h]:
            s += 1
        segment.append(s)
    cur = hcut
    whites = [K] * (hcut+1)
    cur -= 1
    for w in range(W):
        thisline = [0]*(hcut+1)
        for h in range(H):
            if S[h][w] == '1':
                whites[segment[h]] += 1
                thisline[segment[h]] += 1
        m = max(whites)
        if m > K:
            whites = thisline
            m = max(whites)
            cur += 1
            if cur >= ans or m > K:
                break
    else:
        ans = cur
            
print(ans)

Submission status: Wrong Answer

Solution code:
h, w, kkk = map(int, input().split())
choco = [0]*h
for i in range(h):
  choco[i] = input()

answer = h*w
for i in range(2*(h-1)):
  board = [0]*(h-1)
  for j in range(h-1):
    if (i >> j)&1:
      board[j] = 1
  count = sum(board)
  key = [0]*(count+1)
  ans = count
  for p in range(w):
    k = 0
    for q in range(h):
      if choco[q][p] == "1":
        key[k] += 1
      if q == h-1:
        break
      if board[q] == 1:
        k += 1
    for q in range(count+1):
      if key[q] <= kkk:
        continue
      ans += 1
      key = [0]*(count+1)
      k = 0
      for q in range(h):
        if choco[q][p] == "1":
          key[k] += 1
        if q == h-1:
          break
        if board[q] == 1:
          k += 1
      break
  if ans < answer:
    answer = ans
print(answer)

Submission status: Wrong Answer

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


wh = 0
for i in range(h):
    s.append(input())
    wh += s[-1].count('1')

co = 0

while wh > k:
    a = 0
    co += 1
    for i in range(w):
        for j in range(h):
            if s[j][i]=='1':
                a += 1

        if wh/2 <= a:
            ai = i
            break

    b = 0
    for i in range(h):
        b += s[i].count('1')
        if wh/2 <= b:
            bi = i
            break

    if a<b:
        for i in range(h):
            s[i] = s[i][:ai+1]
            w = ai+1
            wh = a
    else:
        s = s[:bi+1]
        h = bi+1
        wh = b

print(co)

Submission status: Wrong Answer

Solution code:
import numpy as np

h,w,k = map(int,input().split())
S = [list(input()) for _ in range(h)]
S_ = np.array(S).T.tolist()
x = []
y = []
for i in range(h):
    tmp = S[i].count('1')
    y.append(tmp)
for i in range(w):
    tmp = S_[i].count('1')
    x.append(tmp)

tmp = 0
cnt_y = 0
for i in range(h):
    if tmp+y[i]>k and i!=0:
        cnt_y += 1
        tmp = y[i]
    else:
        tmp += y[i]

tmp = 0
cnt_x = 0
for i in range(w):
    if tmp+x[i]>k and i!=0:
        cnt_x += 1
        tmp = x[i]
    else:
        tmp += x[i]
print(min(cnt_x, cnt_y))

Submission status: Wrong Answer

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

H, W, K = map(int, input().split())
S = [input() for i in range(H)]
Col = [[] for i in range(W)]
for j in range(W):
    for i in range(H):
        Col[j].append(S[i][j])
Ans = 10**9
for lst in itertools.product([0,1], repeat=H-1):
    ran = []
    ans = sum(lst)
    l = 0
    for i, x in enumerate(lst, 1):
        if x == 1:
            ran.append((l, i))
            l = i
    ran.append((l, H))
    cnt = [0] * len(ran)
    for j in range(W):
        flg = 0
        for i, (l, r) in enumerate(ran):
            if cnt[i] + Col[j][l:r].count('1') > K:
                flg = 1
                break
        if flg:
            ans += 1
            for i, (l, r) in enumerate(ran):
                cnt[i] = Col[j][l:r].count('1')
        else:
            for i, (l, r) in enumerate(ran):
                cnt[i] += Col[j][l:r].count('1')
    Ans = min(Ans, ans)
print(Ans)

Submission status: Wrong Answer

Solution code:
def main():
    h, w, k = map(int, input().split())
    s = [input().rstrip() for _ in range(h)]
    t = [[0]*(w+1) for _ in range(h+1)]
    for i in range(h):
        for j in range(w):
            if s[i][j] == "1":
                t[i+1][j+1] = 1
    for i in range(1, h+1):
        for j in range(1, w+1):
            t[i][j] += t[i-1][j] + t[i][j-1] - t[i-1][j-1]
#    for i in range(h+1):
#        print(t[i])
    ans = 10**9
    for i in range(2**(h-1)):
        a, b = 0, 0
        buf = [0]
        for j in range(h-1):
            if ((1<<j) & i) > 0:
                a += 1
                buf.append(j+1)
        buf.append(h)
        x = 0
        for j in range(1, w+1):
            f = False
            for l in range(1, len(buf)):
                if t[buf[l]][j] - t[buf[l-1]][j] - t[buf[l]][x] + t[buf[l-1]][x] > k:
                    f = True
            if f:
                b += 1
                x = j-1
        if a + b < ans:
#            print(a, b, i, x)
            ans = a + b
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():

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

    div = [[]]
    for i in range(1, H+1):
        temp = []
        for lv in div:
            temp.append(lv + [i])
            if i < H:
                temp.append(lv)
        div = temp

    ans = float('inf')
    for lv in div:
        accum = [0 for _ in range(len(lv))]
        count = 0
        chk = []
        for j in range(W):
            k = 0
            to_add = []
            v = 0
            for i in range(H):
                if i == lv[k]:
                    k += 1
                    to_add.append(v)
                    v = 0
                if S[i][j] == '1':
                    v += 1
            to_add.append(v)
            if any((accum[i] + to_add[i]) > K for i in range(len(lv))):
                count += 1
                accum = to_add
                chk.append(j)
            else:
                for i in range(len(lv)):
                    accum[i] += to_add[i]
            # print(lv, to_add)
        # print(lv, chk)
        ans = min(ans, count + len(lv)-1)
    return ans


if __name__ == '__main__':
    print(main())