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())
X = []
import sys;input=sys.stdin.readline
for _ in range(H):
    X.append(input().strip())

if W==1:
    1/0
    sys.exit()

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:
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
    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:
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')
    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:
def inputs(): return [int(x) for x in input().split()]
from collections import defaultdict
def popcnt(n):
    c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff)
    return c
h,w,k= inputs()
s = [list(input()) for _ in range(h)]
res = 10**8
for bit in range(0,1<<h-1):
    l = popcnt(bit)
    #print(l,bit)
    cnt = [0]*(l+1)
    cnt2 = []
    ans = 0
    #cnt1 = 0
    for i in range(w):
        cnt1=0
        cnt2=[]
        for j in range(h):
            if bit&1<<j and j!=0:
                cnt1+=1
            if s[j][i]=="1":
                cnt[cnt1]+=1
                cnt2.append(cnt1)
                #print(cnt,cnt1,cnt2,j,i)
                if k<cnt[cnt1]:
                    cnt = [0]*(l+1)
                    for m in cnt2:
                        cnt[m]+=1
                        if k<cnt[m]:
                            ans+=10**9
                    ans+=1
    #print(res,ans,l,bit)
    res = min(res,ans+l)
print(res)

Submission status: Wrong Answer

Solution code:
h,w,k=map(int,input().split())
ans=0
for i in range(h):
    s=str(input())
    ans+=s.count("1")
if ans<=k:
    print(0)
    exit()
n=1+(ans//k)
for i in range(n):
    if i%2==0:
        if (i+2)**2//4>=n:
            print(i)
            exit()
    else:
        if (i+1)*(i+3)//4>=n:
            print(i)
            exit()

Submission status: Wrong Answer

Solution code:
import sys

import numpy as np

H, W, K = map(int, input().split())
S = np.array([list(input()) for _ in range(H)], dtype="int")

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

flag = 0
cnt = 0
while True:
    pcnt = 0
    # 縦方向に割る
    vs = np.sum(S, axis=0)

    ss = np.cumsum(vs)
    if np.count_nonzero(ss <= K):
        ind = np.argmax(ss[ss <= K])
        S[:, :ind + 1] = 0
        pcnt += 1
    if np.sum(S) <= K:
        cnt += pcnt
        pcnt = 0
        break

    # 横方向に割る
    hs = np.sum(S, axis=1)
    ss1 = np.cumsum(vs)
    if np.count_nonzero(ss <= K):
        ind = np.argmax(ss[ss <= K])
        S[:ind + 1, :] = 0
        pcnt += 1
    if np.sum(S) <= K:
        cnt += pcnt
        pcnt = 0
        break

    # 逆から探査
    ss = K - ss
    if np.count_nonzero(ss <= K):
        ind = np.argmax(ss[ss <= K])
        S[:, ind + 1:] = 0
        pcnt += 1
    if np.sum(S) <= K:
        cnt += pcnt
        pcnt = 0
        break

    # 逆から探査
    ss1 = K - ss1
    if np.count_nonzero(ss <= K):
        ind = np.argmax(ss[ss <= K])
        S[ind + 1:, :] = 0
        pcnt += 1

    if np.sum(S) <= K:
        cnt += pcnt
        pcnt = 0
        break

    if pcnt != 0:
        cnt += pcnt
        pcnt = 0

    if pcnt == 0 and np.sum(S) > K:
        # どうにかする
        continue

print(cnt)

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

if W==1:
    ss =c= 0
    for i in range(H):
        x = int(X[i][0])
        ss += x
        if ss > K:
            ss = x
            c += 1
    print(c)
    sys.exit()

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:
H,W,K=map(int,input().split())
S=[list(map(int,list(input()))) for _ in range(H)]

a=float("inf")
for i in range(2**(H-1)):
  n=bin(i)[2:].zfill(H-1)
  n=list(map(int,list(n)))
  s=[0]*(sum(n)+1)
  ans=sum(n)
  for j in range(W):
    k=0
    h=0
    while h<H:
      s[k]+=S[h][j]
      if h<H-1 and n[h]==1:
        k+=1
      h+=1
  
    for k in s:
      if k>K:
        ans+=1
        k=0
        h=0
        s=[0]*(sum(n)+1)
        while h<H:
          s[k]+=S[h][j]
          if h<H-1 and n[h]==1:
            k+=1
          h+=1
        break
  a=min(a,ans)    
print(a)

Submission status: Wrong Answer

Solution code:
H,W,K = map(int,input().split())
import numpy as np
import math
S = np.array([list(map(int,list(input()))) for _ in range(H)])
total = np.sum(S)
if total==K:
  print(0)
else:
  print(math.ceil(total/K)//2)

Submission status: Wrong Answer

Solution code:
import numpy as np
h, w, k = list(map(int, input().split()))
ss = []
for _ in range(h):
    s = list(map(int, list(input())))
    ss.append(s)

from itertools import product

mi = 1e9
ss = np.array(ss)

if h == 1 and w == 1:
    print(0)
else:
    if h > w:
        h, w = w, h
        ss = ss.T
    sss = np.cumsum(ss, axis = 1)

    
    for binary in product([0, 1], repeat=h - 1):
        binary  = [0] + list(binary)

        ssss = [0]
        for j in range(h):
            if binary[j] == 1:
                ssss.append(sss[j])
            else:
                ssss[-1] = ssss[-1] + sss[j]
        ssss = np.array(ssss)
#         if np.max(np.diff(ssss, axis = 1)) > k:
#             continue
#         print("----")
#         print(sss)
#         print(ssss[:,0])
        if max(ssss[:,0]) > k:
            continue
    #     print(ssss)
        count = 0
        for i in range(w):
            if max(ssss[:, i]) > k:
                ssss -= ssss[:, i - 1][:, None]
                if max(ssss[:,i]) > k:
                    count += 99999

                count += 1
        count += sum(binary)
#         print(binary, count)
    #     aaaaaa
        if count < mi:
            mi = count
    print(mi)

Submission status: Wrong Answer

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

S = [0] * H
data = [[0]*W for i in range(H)]

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

data[0][0] = S[0][0]

for i in range(1,W):
    data[0][i] = data[0][i-1] + S[0][i]

for i in range(1,H):
    data[i][0] = data[i-1][0] + S[i][0]

for i in range(1,H):
    for j in range(1,W):
        data[i][j] = data[i-1][j] + data[i][j-1] - data[i-1][j-1] + S[i][j]

#print(S)
#print(data)

m = 10**4
for i in range(2**(H-1)):
    cross = []
    tate = []
    for j in range(H-1):
        if i&(2**j) == 2**j:
            cross.append(j)
    #print(cross)
    
    start = 0
    for j in range(W):
        det = 0
        if len(cross) > 0:
            for k in range(len(cross)):
                if (k == 0 and start == 0 and data[cross[k]][j] > K) or \
                (k == 0 and data[cross[k]][j] - data[cross[k]][start-1] > K) or\
                (start == 0 and data[cross[k]][j]-data[cross[k-1]][j] > K) or\
                (data[cross[k]][j]-data[cross[k]][start-1]-data[cross[k-1]][j]+data[cross[k-1]][start-1] > K):
                    det = -1
                    break
            if (start == 0 and data[H-1][j] - data[cross[-1]][j]> K) or \
                (data[H-1][j]-data[cross[-1]][j]-data[H-1][start-1]+data[cross[-1]][start-1] > K):
                det = -1
        else:
            if (start == 0 and data[H-1][j] > K) or (data[H-1][j] - data[H-1][start-1] > K):
                det = -1
        det2 = 0
        if det == -1:
            if j == start:
                det2 = -1
                break
            else:
                tate.append(j-1)
                start = j
    
    if det2 == 0:
        #print(start,len(cross)+len(tate))
        m = min(m,len(cross)+len(tate))

print(m)

Submission status: Wrong Answer

Solution code:
H,W,K= map(int, input().split())
A=[]
for i in range(H):
  a=list(input())
  A.append(a)
r=0
sepa=0
for i in range(H):
  a=A[i].count('1')
  R=r+a
  r+=a
  if R>K:
    sepa+=1
    r=a
  if a>K:
    sepa+=(a-1)//2+1
    r=0
print(sepa)

Submission status: Wrong Answer

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


def f(b):
    ret = set()
    for i in range(10):
        if b & (1 << i) > 0:
            ret.add(i)
    return ret


def g(i):
    s = f(i)
    j = 0
    x = [[0 for _ in range(w + 1)] for _ in range(h)]

    cut = 0
    j_prev = j
    while j < w:
        if ss[0][j] == '1':
            x[0][j + 1] = 1 + x[0][j]

        for hi in range(1, h):
            if ss[hi][j] == '1':
                add = 1
            else:
                add = 0

            if hi not in s:
                x[hi][j + 1] = add + x[hi][j] + (x[hi - 1][j + 1] - x[hi - 1][j])
            else:
                x[hi][j + 1] = add + x[hi][j]

            if x[hi][j + 1] > k:
                if j_prev == j:
                    return None
                cut += 1
                x = [[0 for _ in range(w + 1)] for _ in range(h)]
                break
        j_prev = j
        j += 1
    return cut + len(s)


ans = 10 ** 9
for i in range(2 ** 10):
    cut = g(i)
    if cut is None:
        continue
    ans = min(ans, cut)

print(ans)

Submission status: Wrong Answer

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

cnt = 0
for h in range(H):
    for w in range(W):
        if S[h][w] == "1":
            cnt += 1
# print(cnt)
if cnt <= K:
    print(0)
    exit()

if W <= H:
    if cnt % H == 0:
        print(cnt // H)
    else:
        print(cnt // H + 1)
else:
    if cnt % W == 0:
        print(cnt // W)
    else:
        print(cnt // W + 1)

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

if W==1:
    ss =c= 0
    for i in range(H):
        x = int(X[i][0])
        ss += x
        if ss > K:
            ss = x
            c += 1
    print(c)
    sys.exit()

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 copy
h, w, k = [int(i) for i in input().split()]

mat = []
for _ in range(h):
  mat.append([int(s) for s in input()])


def get_total_list(l_pos):
  global k
  global mat
  l_total = []
  ph = 0
  for ch in l_pos[0]:
    pw = 0
    for cw in l_pos[1]:
      total = 0
      for l_col in mat[ph:ch]:
        total += sum(l_col[pw:cw])
      l_total.append(total)
      pw = cw
    ph = ch
 # print(l_total)
  return l_total


def survey_pos_of_divide(l_pos, max_total):
  global h
  global w
  global mat
  h_min_total = max_total
  h_result = 0
  w_min_total = max_total
  w_result = 0
  for i in range(h):
    l_pos_tmp = copy.deepcopy(l_pos)
    l_pos_tmp[0].append(i)
    l_pos_tmp[0].sort()
    l_total = get_total_list(l_pos_tmp)
    if max(l_total) < h_min_total:
      h_min_total = max(l_total)
      h_result = i
  for i in range(w):
    l_pos_tmp = copy.deepcopy(l_pos)
    l_pos_tmp[1].append(i)
    l_pos_tmp[1].sort()
    l_total = get_total_list(l_pos_tmp)
    if max(l_total) < w_min_total:
      w_min_total = max(l_total)
      w_result = i
  if h_min_total <= w_min_total:
    return 'h', h_result
  else:
    return 'w', w_result
    

l_pos = [[h], [w]]
survey_count = 0
while True:
  #print('survey_count: ', survey_count)
  #print('l_pos: ', l_pos)
  l_total = get_total_list(l_pos)
  if sum([1 for total in l_total if total > k]) == 0:
    break
  max_total = max(l_total)
  which, result = survey_pos_of_divide(l_pos, max_total)
  if which == 'h':
    l_pos[0].append(result)
    l_pos[0].sort()
  else:
    l_pos[1].append(result)
    l_pos[1].sort()
  survey_count += 1
  
print(survey_count)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import Counter

h, w, k = [int(s) for s in sys.stdin.readline().strip().split()]
s = [''] * h
for i in range(h):
    s[i] = sys.stdin.readline().strip()

# h, w, k = 3, 5, 4
# s = [
#     '11100',
#     '10001',
#     '00111'
# ]


ans = float('inf')
for i in range((h - 1) ** 2):
    colors = [0]
    cur = 0
    # print('i', i)
    cand = 0
    for div in range(h-1):
        if (i >> div) & 1:
            # print('div', div)
            cur += 1
            colors.append(cur)
            cand += 1
        else:
            colors.append(cur)
    # print(colors)

    impossible = False
    color_count = Counter()
    for j in range(w):
        col_color_count = Counter()
        for row in range(h):
            color = colors[row]
            # print('s', s)
            # print('row', row)
            # print('j', j)
            char = s[row][j]
            if char == '1':
                col_color_count[color] += 1

        has_break = False
        for col in range(cur+1):
            if col_color_count[col] > k:
                impossible = True
                break
            if col_color_count[col] + color_count[col] > k:
                has_break = True
        if impossible:
            break
        if has_break:
            color_count = col_color_count
            cand += 1
        else:
            for col in range(cur+1):
                color_count[col] += col_color_count[col]
    ans = min(ans, cand)
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
    tmp = [0]*n
    for i in range(h):
      tmp[bisect.bisect_left(sets,i)]+=S[i][j]
      # ここ不安
    F = 0
    # if bit == 1:
      # print(tmp,data)
    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):
  sets = []
  for k in range(h-1):
    if (bit >> k) & 1:
      sets.append(k)
  sets.append(h)
  re = check(sets)
  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)

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')
    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 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')
                choco[-1] =  St[j][cut[-1]:].count('1')
                count += 1
        ans = min(ans,count)
    print(ans)

Submission status: Wrong Answer

Solution code:
def chk(area):
    num=0
    l=len(area)
    cnt=[0 for i in range(l)]

    for i in range(w):
        for j in range(h):
            cnt[area[j]]+=choko[i][j]

        if max(cnt)>k:
            num+=1
            cnt=[0]*l
            for j in range(h):
                cnt[area[j]]+=choko[i][j]
            if max(cnt)>k: return 10**10

    return num

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


area=[0 for i in range(h)]
ans=10**10
for v in range(0,2**(h-1)):
    p=bin(v)[2:].zfill(h-1)
    for i in range(h-1):
        if p[i]=="1": area[i+1]=area[i]+1

    tmp1=sum([int(p[i]) for i in range(h-1)])+chk(area)
    ans=min(ans,tmp1)

print(ans)

Submission status: Wrong Answer

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

li = [[0 for _ in range(W)] for _ in range(H+1)]
for h in range(H):
    li[h+1][0] = S[h][0]
    for w in range(1,W):
        li[h+1][w] = li[h+1][w-1]+S[h][w]
for w in range(W):
    for h in range(1,H):
        li[h+1][w]=li[h][w]+li[h+1][w]

ans = (1<<(H))+H
for h1 in range(1<<(H-1)):
    flg = [0]
    for h2 in range(H-1): 
        if ((h1>>h2)&1):
            flg.append(h2+1)
    flg.append(H)
    
    cnt = len(flg)-2
    mm = [0 for _ in range(len(flg)-1)]
    i = 0

    a = True

    # print(flg)
    for w in range(W):
        for h in range(len(flg)-1):
            mm[h] = li[flg[h+1]][w]-li[flg[h]+1][i]
            if mm[h]>K:
                cnt += 1
                i = w
                if li[flg[h+1]][w]-li[flg[h]+1][i]>K:
                    a = False
                    # print(flg[h+1],flg[h]+1,w,flg)
                    break
    if a:
        ans = min(ans,cnt)
        # if ans == cnt:
            # print(flg)

print(ans)




# for h in range(H+1):
#     print(*li[h])

Submission status: Wrong Answer

Solution code:
h, w, k = map(int, input().split())
chocolate = ['0' + input() for _ in range(h)]

white_count = [[0] * (w+1)]
for line in chocolate:
    prev = white_count[-1]
    cumsum = []
    total = 0
    for color, count in zip(line, prev):
        if color == '1':
            total += 1
        cumsum.append(total + count)
    white_count.append(cumsum)

ans = []
for pattern in range(2**(h-1)):
    dived = []
    for bit in range(h-1):
        if (pattern >> bit) & 1:
            dived.append(bit + 1)

        else:
            continue
    dived.append(h)
    slash_count = 0
    prev_x = 0
    for wide in range(1, w+1):
        prev_y = 0
        possible = True
        slash = None
        for block in dived:
            white = white_count[block][wide] - white_count[prev_y][wide] - (white_count[block][prev_x] - white_count[prev_y][prev_x])
            prev_y = block
            if white <= k:
                continue
            else:
                slash_count += 1
                slash = wide - 1
                if prev_x == slash:
                    possible = False
                    break

        if not possible:
            continue

        if slash is None:
            continue
        else:
            prev_x = slash
    ans.append(slash_count + len(dived)-1)

print(min(ans))

Submission status: Wrong Answer

Solution code:
import itertools

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

choco = [input().strip() for h in range(H)]
cs = [[None for _ in range(W)] for _ in range(H)]  # 累積和

for w in range(W):
  now_cs = 0
  for h in range(H):
    now_cs += choco[h][w] == '1'
    cs[h][w] = now_cs

def devide_col(w, d):
  if len(d) == 0:
    return [cs[-1][w]]
  result = []
  for i in range(len(d)):
    if i == 0:
      result.append(cs[d[0]-1][w])
    else:
      result.append(cs[d[i]][w]-cs[d[i-1]-1][w])
  result.append(cs[-1][w]-cs[d[-1]-1][w])
  return result

ans = float('inf')
for n_split in range(H):
  if n_split > ans: continue
  for split_pos in itertools.combinations(range(1,H), n_split):
    # 縦の分割方法が決まった
    # 横は貪欲
    now_ans = 0
    now_state = [0]*(n_split+1)
    for w in range(W):
      next_state = devide_col(w, split_pos)
      if any(s > K for s in next_state):  # この縦分割では無理
        now_ans = float('inf')
        break
      now_state = [n+s for n,s in zip(now_state, next_state)]  # 足してみる
      if any(s > K for s in now_state):  # 分割する
        now_ans += 1
        now_state = next_state
    ans = min(ans, now_ans+n_split)
print(ans)

Submission status: Wrong Answer

Solution code:
def examA():
    N, M = LI()
    ans = N*(N-1)//2 + M*(M-1)//2
    print(ans)
    return

def examB():
    def judge(A):
        #print(A)
        n = len(A)
        for i in range(n//2):
            if A[i]!=A[n-i-1]:
                return False
        return True
    S = SI()
    N = len(S)
    if not judge(S):
        print("No")
        return
    if judge(S[:(N-1)//2]) and judge(S[(N+1)//2:]):
        print("Yes")
    else:
        print("No")
    return

def examC():
    L = I()
    ans = (L/3)**3
    print(ans)
    return

def examD():
    N = I()
    A = LI()
    D = defaultdict(bool)
    C = Counter(A)
    M = 0
    for key,c in C.items():
        M += c*(c-1)//2
    #print(C)
    #print(M)
    ans = [0]*N
    for i in range(N):
        a = A[i]
        c = C[a]
        ans[i] = M -(c*(c-1)//2) + ((c-1)*(c-2)//2)
    for v in ans:
        print(v)
    return

def examE():
    H, W, K = LI()
    S = [SI()for _ in range(H)]
    SH = [[0] * (W + 1) for _ in range(H + 1)]
    for i in range(H):
        now = 0
        for j in range(W):
            now += int(S[i][j])
            SH[i + 1][j + 1] = SH[i][j + 1] + now

    def calc(a,b,c,d):
        return SH[c][d] - SH[a][d] - SH[c][b] + SH[a][b]


    ans = H-1+W-1
    mask = 2**(H-1)-1
    for i in range(mask+1):
        cut = [0]
        cur = 0
        for j in range(H-1):
            if i&(1<<j)==(1<<j):
                cut.append(j+1)
                cur += 1
        cut.append(H)
        L = [0]*(len(cut)-1)
        flag = True
        for w in range(W):
            now_L = [0]*(len(cut)-1)
            for s in range(len(cut) - 1):
                n = calc(cut[s], w, cut[s + 1], w + 1)
                now_L[s] = n
                if n+L[s]> K:
                    if n>K:
                        flag = False
                        cur = inf
                        break
                    cur += 1
                    L = [0] * (len(cut))
                    break
            if not flag:
                break
            for s in range(len(cut) - 1):
                L[s] += now_L[s]
        if not flag:
            continue
        ans = min(ans,cur)

    print(ans)
    return
"""
2 1 1
1
1
"""# 1

def examF():
    N, S = LI()
    A = LI()
    dp = [[0]*N for _ in range(S*2)]

    ans = 0
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examE()

"""

"""

Submission status: Wrong Answer

Solution code:
#端から端まで割る
#h<=10に対しては全探索
#wについては極力割らない

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

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

bit = 1<<h
ans = 10000
for b in range(bit):
    cut = [0]+[j for j in range(1,h) if (b>>j)&1]+[h]
    tmp = len(cut)-2
    white = [0]*h
    for j in range(w):
        for i in range(h): 
            white[i] += (s[i][j])&1
        for u in range(1,len(cut)):
            tmp2 = 0
            for t in range(cut[u-1],cut[u]):
                tmp2 += white[t]
            if tmp2>k and j:##
                tmp += 1
                white = [s[x][j] for x in range(h)]##
    if ans > tmp:
        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)
ans = 0
if white <= K:
    print(ans)
    exit()
if K >= min(10, H):
    total = 0
    for x in range(W):
        total += cw[x]
        if total >= K:
            ans += 1
            total = cw[x]
    print(ans)
    exit()