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())
s = [list(input()) for _ in range(h)]
for i in range(h):
    for j in range(w):
        s[i][j] = int(s[i][j])
# print(s)
bit = []
if h == 1:
    ans = w // K
    if ans == w / K:
        print(ans - 1)
    else:
        print(ans)
else:
    for i in range(0, 2 ** (h - 1)):
        i_bit = bin(i)[2:]
        while len(i_bit) < len(bin(2 ** (h - 2))[2:]):
            i_bit = "0" + i_bit
        bit.append(i_bit)
    ans = 10 ** 10

    for pa in bit:
        patarn = []
        start = 0
        end = 0

        for i in range(len(pa)):
            if pa[i] == "1":
                patarn.append([start, i + 1])
                start = i + 1
        patarn.append([start, h])
        # print(pa, patarn)
        area = [0 for _ in range(len(patarn))]
        cnt = len(area) - 1
        for j in range(w):
            for k in range(len(area)):
                tmp = [0 for _ in range(len(patarn))]
                for i in range(patarn[k][0], patarn[k][1]):
                    if s[i][j]:
                        area[k] += 1
                        tmp[k] += 1
                    if area[k] > K:
                        # print(j, 123)
                        cnt += 1
                        # print(area)
                        import copy
                        area = copy.deepcopy(tmp)
        ans = min(cnt, ans)
        # print(ans, cnt)

    print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
import time
import random

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

start = time.time()

# 2**(H-1)通り試す
# 事前に各行のcumsumを取っておくと多分はやい
s2 = [np.cumsum(row, dtype=np.int32) for row in s]

mi = 10 ** 9
seed = [0]*1000+[1]*1000
selected = []
# for ls in tgt:
while time.time()-start < 1.7:
    t = random.sample(seed, k=H - 1)
    if t in selected:
        continue
    selected.append(t)
    ls = t
    # numは横線の数
    num = sum(ls)+1
    tmp = num - 1
    
    s3 = np.zeros((num, W))
    s3[0] = s2[0]
    cnt = 0
    for i in range(H - 1):
        if ls[i] == 0:
            s3[cnt] += s2[i + 1]
        else:
            cnt += 1
            s3[cnt] = s2[i + 1]
    s3 = s3.T
    
    hosei = np.zeros(num)
    for w in range(W):
        if np.max(s3[:][w] - hosei) > K:
            tmp += 1
            if w != 0:
                hosei = s3[:][w - 1]
            else:
                tmp = 10 ** 9
    if mi > tmp:
        mi = tmp
z = 0
for row in s:
    z += np.sum(row)
if z <= K:
    mi = 0
print(mi)

Submission status: Wrong Answer

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

while True:
    su = 0
    for i in range(h):
        su += sum(map(int, list(s[i])))
    if su <= k:
        break

    tmp = 0
    hor = 0
    hor_cnt = 0
    for i in range(h):
        tmp += (sum(map(int, list(s[i]))))
        if (su / 2) <= tmp:
            hor_cnt = tmp
            hor = i
            break

    tmp = 0
    ver = 0
    ver_cnt = 0
    for j in range(w):
        for i in range(h):
            tmp += int(s[i][j])
        if (su / 2) <= tmp:
            ver_cnt = tmp
            ver = j
            break

    if hor_cnt <= ver_cnt:
        h = hor + 1
        s = s[:(hor + 1)]
    else:
        w = ver + 1
        s = list(map(lambda x: x[:(ver + 1)], s))
    ans += 1
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 = inf
    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)
        prev = 0
        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 prev == w:
                        flag = False
                        break
                    prev = w+1
                    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

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, 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)
elif h == 1:
    x = sum([s[0][i] == '1' for i in range(w)])
    print(-(-x // k)-1)
else:
    print(ans)

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:##
                tmp += 1
                white = [s[x][j] for x in range(h)]##
    if ans > tmp:
        ans = tmp
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(max([2*(h-1), 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 = [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)
if h == 1:
    x = sum([s[0][i] == '1' for i in range(w)])
    print(-(-x // k)-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
h,w,K = map(int,input().split())
cum = [[0 for _ in range(w+1)]]
for _ in range(h):
  tmp = input()
  add = [0]
  for j in range(w):
    add.append(add[-1]+int(tmp[j]))
  cum.append(add)
for i in range(h):
  for j in range(w):
    cum[i+1][j+1] += cum[i][j+1]
time = [0 for _ in range(h-1)]
def nex(time):
  for d in range(h-1):
    if time[d] == 0:
      time[d] = 1
      return time
    else:
      time[d] = 0
  else:
    return 'over'
can = []
while time != 'over':
  tmp = [0]
  for d in range(h-1):
    if time[d] == 1:
      tmp.append(d+1)
  tmp.append(h)
  #print(tmp,time)
  l = len(tmp) - 1
  ans = l - 1
  now = 0
  att = 1
  for j in range(1,w+1):
    cand = []
    for k in range(l):
      cand.append(cum[tmp[k+1]][j] - cum[tmp[k+1]][now] - cum[tmp[k]][j] + cum[tmp[k]][now])
    #print(cand,now,tmp)
    if max(cand) > K:
      now = j - 1
      ans += 1
      cane = []
      for k in range(l):
        cane.append(cum[tmp[k+1]][j] - cum[tmp[k+1]][now] - cum[tmp[k]][j] + cum[tmp[k]][now])
        if max(cane) > K:
          break
    #print(l-1,ans,time)
  else:
    can.append(ans)
  time = nex(time)
  #print(tmp,l-1,ans)
print(min(can))

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[::]
        else:
            for i in range(yoko + 1):
                cntHW[i] += cntH[i]

    ans = min(ans, res)

print(ans)

Submission status: Wrong Answer

Solution code:

def count(h0, h1, w0, w1, T):
    k = 0
    for h in range(h0, h1):
        k += T[h][w1] - T[h][w0]
    return k


def cut(h0, h1, w0, w1, K, T, n, lim):
    if n >= lim:
        return n

    if count(h0, h1, w0, w1, T) <= K:
        return n

    # -- に割る
    for h in range(h0+1, h1):
        n1 = cut(h0, h, w0, w1, K, T, n+1, lim)
        n2 = cut(h, h1, w0, w1, K, T, n+1, lim)
        n = max(n1, n2)
        if n < lim:
            lim = n

    # | に割る
    for w in range(w0+1, w1):
        n1 = cut(h0, h1, w0, w, K, T, n, lim)
        n2 = cut(h0, h1, w, w1, K, T, n, lim)
        n = max(n1, n2)
        if n < lim:
            lim = n

    return lim


def solv(H, W, K, S):
    T = []
    for s in S:
        t = [0]
        tt = 0
        for c in s:
            tt += (c == '1')
            t.append(tt)
        T.append(t)
    return cut(0, H, 0, W, K, T, 0, H+W)


if __name__ == "__main__":

    # H W K
    # S_{1,1}S_{1,2}...S_{1,W}
    # :kkkkkkkkkk
    # S_{H,1}S_{H,2}...S_{H,W}
    #
    H, W, K = map(int, input().split())
    S = [input() for _ in range(H)]

    ans = solv(H, W, K, S)
    print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import product
import numpy as np
import time
import random

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

start = time.time()

# 2**(H-1)通り試す
# 事前に各行のcumsumを取っておくと多分はやい
s2 = [np.cumsum(row, dtype=np.int32) for row in s]

rate = H*W//5
mi = 10 ** 9
seed = [0]*1000+[1]*1000
tgt = product(seed, repeat=H-1)
selected = []
# for ls in tgt:
while time.time()-start < 1.6:
    t = random.sample(seed, k=H - 1)
    if t in selected:
        continue
    selected.append(t)
    ls = t
    # numは横線の数
    num = sum(ls)+1
    tmp = num - 1
    
    s3 = np.zeros((num, W))
    s3[0] = s2[0]
    cnt = 0
    for i in range(H - 1):
        if ls[i] == 0:
            s3[cnt] += s2[i + 1]
        else:
            cnt += 1
            s3[cnt] = s2[i + 1]
    s3 = s3.T
    
    hosei = np.zeros(num)
    for w in range(W):
        if np.max(s3[:][w] - hosei) > K:
            tmp += 1
            if w != 0:
                hosei = s3[:][w - 1]
            else:
                tmp = 10 ** 9
    if mi > tmp:
        mi = tmp
z = 0
for row in s:
    z += np.sum(row)
if z <= K:
    mi = 0
print(mi)

Submission status: Wrong Answer

Solution code:
import math
h,w,k=map(int,input().split())
s=[""]*h
t=[0]*h
for i in range(h):
	s[i]=input()
	t[i]=s[i].count("1")
count = 0
for i in range(h):
	count += t[i]
if count > k:
	print(math.floor(math.log2((count/k)*2)))
else:
	print("0")

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):
                    # print('hoge')
                    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('')
    if(NG_flag==0):
        ans = min(ans, tmp)
        # print('ans = {}'.format(ans))


print(ans)

Submission status: Wrong Answer

Solution code:
h, w, k = map(int, input().split())
s = [list(input()) for _ in range(h)]
white = 0
for i in range(h):
  for j in range(w):
    s[i][j] = int(s[i][j])
    if s[i][j] == 1:
      white += 1

if white <= k:
  print(0)
  exit()

grid_num = (white-1)//k+1

if grid_num % 2 != 0:
  print(grid_num+1)
else:
  print(grid_num)

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)
    else:
        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] += sss[j]

        ssss = np.array(ssss)
        if np.max(np.diff(ssss, axis = 1)) > k:
            continue
    #     print(ssss)
        count = 0
        for i in range(w):
            if max(ssss[:, i]) > k:
                ssss -= ssss[:, i - 1][:, None]
                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 == 0:
                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())
choco = []
mcut = h+w
for i in range(h):
    choco.append(list(map(int,list(input()))))
for i in range(2**(h-1)):
    chocos = []
    cut = 0
    choco1 = choco[0][:]
    for j in range(h-1):
        if i >> j & 1:
            chocos.append(choco1)
            choco1 = choco[j+1][:]
            cut += 1
        else:
            for l in range(w):
                choco1[l] += choco[j+1][l]
    chocos.append(choco1)
    num = len(chocos)
    chocosum = [0 for _ in range(num)]
    for j in range(w):
        for l in range(num):
            chocosum[l] += chocos[l][j]
            if chocosum[l] > k:
                cut += 1
                chocosum = [chocos[_][j] for _ in range(num)]
                break
    mcut = min(cut,mcut)
print(mcut)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline

h, w, K = map(int, input().split())
field = []
field_int = []
for _ in range(h):
    s = input().rstrip()
    line = [int(item) for item in s]
    field.append(line)

ans = 10**5
for i in range(2**(h-1)):
    group = [0]
    g = 0
    for j in range(h-1):
        if i & 1 << j: 
            g += 1
            group.append(g)
        else:
            group.append(g)
    line_num = bin(i).count("1") + 1
    cnt = [0] * line_num
    ret = 0
    for j in range(w):
        tmp = [0] * line_num
        for k in range(h):
            tmp[group[k]] += field[k][j]
        should_cut = False
        for c, t in zip(cnt, tmp):
            if c + t > K:
                should_cut = True
        if not should_cut:
            for i, t in enumerate(tmp):
                cnt[i] += t
        else:
            ret += 1
            for i, t in enumerate(tmp):
                cnt[i] = t
    ans = min(ans, ret + line_num - 1)
print(ans)

Submission status: Wrong Answer

Solution code:
h,w,k = map(int, input().split())
choco = []
count = 0
ans = 10**9
for i in range(h):
    count += list(input()).count("1")
if count <= k:
    print(0)
    exit()
for i in range(h):
    for j in range(w):
        if (1+i)*(1+j) > count / k:
            ans = min(ans, i+j)
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)):
        flag = False
        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:
                    if j != 1:
                        c = j - 1
                        cnt += 1
                        break
                    else:
                        flag = True
                        break
            if flag:
                break
        ans = min(ans,cnt)
    
    print(ans)

if __name__=='__main__':
    main()

Submission status: Wrong Answer

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

ans = h + w
for i in range(2**(h - 1)):
    t = 0
    to_add = [0]
    for a in range(h - 1):
        if i & (2**a):
            t += 1
        to_add.append(t)
    n_h = t
    ans_ = t
    zz = [0 for _ in range(n_h + 1)]
    cnts = zz.copy()
    for x in range(w):
        is_over = False
        for y in range(h):
            z = to_add[y]
            cnts[z] += ar[y][x]
            if cnts[z] > k:
                is_over = True
                break
        if is_over:
            ans_ += 1
            if ans <= ans_:
                break
            cnts = zz.copy()
            for y in range(h):
                cnts[to_add[y]] += ar[y][x]
    if ans > ans_:
        ans = ans_
print(ans)

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(x + 1)]
    ret = x

    for w in range(W):
        choco = getChoco(choco, w)
        if any(c > K for c in choco):
            choco = getChoco([0 for _ 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())
s = [list(input()) for _ in range(h)]
for i in range(h):
    for j in range(w):
        s[i][j] = int(s[i][j])
# print(s)
bit = []
for i in range(0, 2 ** (h - 1)):
    i_bit = bin(i)[2:]
    while len(i_bit) < len(bin(2 ** (h - 2))[2:]):
        i_bit = "0" + i_bit
    bit.append(i_bit)
ans = 10 ** 10

for pa in bit:
    patarn = []
    start = 0
    end = 0

    for i in range(len(pa)):
        if pa[i] == "1":
            patarn.append([start, i + 1])
            start = i + 1
    patarn.append([start, h])
    # print(pa, patarn)
    area = [0 for _ in range(len(patarn))]
    cnt = len(area) - 1
    for j in range(w):
        for k in range(len(area)):
            tmp = [0 for _ in range(len(patarn))]
            for i in range(patarn[k][0], patarn[k][1]):
                if s[i][j]:
                    area[k] += 1
                    tmp[k] += 1
                if area[k] > K:
                    # print(j, 123)
                    cnt += 1
                    # print(area)
                    import copy
                    area = copy.deepcopy(tmp)
    ans = min(cnt, ans)
    # print(ans, cnt)

print(ans)

Submission status: Wrong Answer

Solution code:
print(0)

Submission status: Wrong Answer

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

if not (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:
h,w,K = map(int,input().split())
cum = [[0 for _ in range(w+1)]]
for _ in range(h):
  tmp = input()
  add = [0]
  for j in range(w):
    add.append(add[-1]+int(tmp[j]))
  cum.append(add)
for i in range(h):
  for j in range(w):
    cum[i+1][j+1] += cum[i][j+1]
time = [0 for _ in range(h-1)]
def nex(time):
  for d in range(h-1):
    if time[d] == 0:
      time[d] = 1
      return time
    else:
      time[d] = 0
  else:
    return 'over'
can = []
while time != 'over':
  tmp = [0]
  for d in range(h-1):
    if time[d] == 1:
      tmp.append(d+1)
  tmp.append(h)
  #print(tmp,time)
  l = len(tmp) - 1
  ans = l - 1
  now = 0
  att = 1
  for j in range(1,w+1):
    cand = []
    for k in range(l):
      cand.append(cum[tmp[k+1]][j] - cum[tmp[k+1]][now] - cum[tmp[k]][j] + cum[tmp[k]][now])
    #print(cand,now,tmp)
    if max(cand) > K:
      if att == 1:
        break
      now = j - 1
      ans += 1
      att = 1
    else:
      att = 0
  else:
    #print(l-1,ans,time)
    can.append(ans)
  time = nex(time)
  #print(tmp,l-1,ans)
try:
  print(min(can))
except:
  print(h+w-2)

Submission status: Wrong Answer

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

while True:
    su = 0
    for i in range(h):
        su += sum(map(int, list(s[i])))
    if su <= k:
        break

    tmp = 0
    hor = 0
    hor_cnt = 0
    for i in range(h):
        tmp += (sum(map(int, list(s[i]))))
        if (su // 2) <= tmp:
            hor_cnt = tmp
            hor = i
            break

    tmp = 0
    ver = 0
    ver_cnt = 0
    for j in range(w):
        for i in range(h):
            tmp += int(s[i][j])
        if (su // 2) <= tmp:
            ver_cnt = tmp
            ver = j
            break
    if hor_cnt <= ver_cnt:
        h = hor + 1
        s = s[:(hor + 1)]
    else:
        w = ver + 1
        s = list(map(lambda x: x[:(ver + 1)], s))
    ans += 1
print(ans)