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:
import numpy as np
H,W,K=map(int,list(input().split(" ")))
choco=np.empty((H,W))
for i in range(H):
    choco[i]=list(map(int,input()))
V=np.inf
for i in range(2**(H-1)):
    m=0
    num=bin(i)
    sp=[]
    for j in range(1,len(num)-1):
        if num[-j]=="1":
            sp.append(j)
            m+=1
    spmat=np.split(choco.copy(),sp)
    for spline in range(1,W):
        t=True
        for k in range(len(spmat)):
            if np.sum(spmat[k][:,:spline])>K:
                t=False
        if t:
            for k in range(len(spmat)):
                if spline+1<W-1 and np.sum(spmat[k][:,:spline+1])>K:
                    for l in range(len(spmat)):
                        spmat[l][:,:spline]=0
                    m+=1
                    break
            if spline==W-1:
                TTT=True
                for l in range(len(spmat)):
                    if np.sum(spmat[l][:,:spline+1])>K:
                        TTT=False
                        break
                if TTT:
                    for l in range(len(spmat)):
                        spmat[l][:,:spline+1]=0
                else:
                    m+=1
                    for l in range(len(spmat)):
                        spmat[l][:,:spline]=0
            

    T=True
    for k in range(len(spmat)):
        if np.sum(spmat[k])>K:
            T=False
    if T:
        V=min(V,m)
print(V)

Submission status: Wrong Answer

Solution code:
H,W,K = map(int,input().split())
import numpy as np
from collections import deque
ans = 10000
S = np.array([list(map(int,list(input()))) for _ in range(H)])
cum = [[0]*W for _ in range(H+1)]
for j in range(W):
  for i in range(1,H+1):
    cum[i][j] = cum[i-1][j]+S[i-1][j]
    
cum = np.array(cum)
for i in range(2**(H-1)):
  q = deque([0])
  for h in range(H):
    if (i>>h)&1:
      q.append(h+1)
  q.append(H)
  q = list(q)
  p = deque()
  judge = False
  for a in range(len(q)-1):
    x = cum[q[a+1]]-cum[q[a]]
    if (x>K).any():
      judge = True
      break
    else:
      p.append(list(x))

  if judge:
    continue
  p = list(p)
  t_a = len(q)-2
  n = len(p)
  l = [0]*n
  for w in range(W):
    for x,a in enumerate(p):
      y = l[x]
      if y>K:
        t_a+=1
        l = [0]*n
        for z,b in enumerate(p):
          l[z] = b[w]
        break
      else:
        l[x]=y
  ans = min(ans,t_a)
    
print(ans)

Submission status: Wrong Answer

Solution code:
h,w,k=map(int,input().split())
S=[]
for i in range(h):
    s=int(input(),2)
    S.append(s)
ans=100000
for i in range(2**(h-1)):
    flag=False
    now=0 #区切った数
    cnt=0 #1の数
    y=0
    for j in range(h-1):
        if (i>>j)&1:
            y+=1
    C=[0]*(y+1) #1の数保存配列
    for x in range(w):
        T=[] #現在の列での1の数保存配列
        for j in range(h):      
            cnt+=(S[j]>>x)&1
            if (i>>j)&1: #横の区切り判定
                T.append(cnt)
                cnt=0
            if j==h-1: #最後の列
                T.append(cnt)
        for j in range(y+1): #それぞれのブロックに対して
            if C[j]+T[j]>k:
                now+=1
                C=T
                break
            else:
                C[j]+=T[j]
    ans=min(ans,now+y)
print(ans)

Submission status: Wrong Answer

Solution code:
H,W,K = map(int,input().split())
import numpy as np
from collections import deque
ans = 10000
S = np.array([list(map(int,list(input()))) for _ in range(H)])
cum = [[0]*W for _ in range(H+1)]
for j in range(W):
  for i in range(1,H+1):
    cum[i][j] = cum[i-1][j]+S[i-1][j]
    
cum = np.array(cum)
for i in range(2**(H-1)):
  q = deque([0])
  for h in range(H):
    if (i>>h)&1:
      q.append(h+1)
  q.append(H)
  p = deque()
  judge = False
  for a in range(len(q)-1):
    x = cum[q[a+1]]-cum[q[a]]
    if (x>K).any():
      judge = True
      break
    else:
      p.append(x)

  if judge:
    continue
  
  t_a = len(q)-2
  n = len(p)
  l = [0]*n
  for w in range(W):
    for x,a in enumerate(p):
      y = l[x]+a[w]
      if y>K:
        t_a+=1
        l = [0]*n
        for z,b in enumerate(p):
          l[z] = b[w]
        break
  ans = min(ans,t_a)
    
print(ans)

Submission status: Wrong Answer

Solution code:
import sys


def main():
    input = sys.stdin.readline

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

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

    # print(*cs, sep='\n')
    # print()

    ans = h + w
    for bit in range(1 << (h - 1)):
        border = [0]
        cand = 0
        for i in range(h):
            if (bit >> i) & 1:
                border.append(i + 1)
                cand += 1
        border.append(h)
        if cand >= ans:
            continue
        j0 = 0
        for j in range(w):
            # for j in range(1, w + 1):
            for i, bi in enumerate(border[:-1]):
                # print(
                #     j0, j, border[i], border[i + 1], cs[border[i + 1]][j] -
                #     cs[border[i + 1]][j0] - cs[border[i]][j] + cs[border[i]][j0])
                if cs[border[i + 1]][j + 1] - cs[border[i + 1]][j0] - cs[bi][
                        j + 1] + cs[bi][j0] > k:
                    cand += 1
                    j0 = j
                    # print(border[i + 1], j, cs[border[i + 1]][j])
                    break
            if cand >= ans:
                break

        # print(border, cand0, cand, cut)
        ans = min(ans, cand)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
h,w,k=map(int,input().split())
S=[]
for i in range(h):
    s=int(input(),2)
    S.append(s)
ans=100000
for i in range(2**(h-1)):
    flag=False
    now=0 #区切った数
    cnt=0 #1の数
    y=0
    for j in range(h-1):
        if (i>>j)&1:
            y+=1
    C=[0]*(y+1) #1の数保存配列
    for x in range(w):
        T=[] #現在の列での1の数保存配列
        for j in range(h):      
            cnt+=(S[j]>>x)&1
            if cnt>k:
                flag=True
                break
            if (i>>j)&1: #横の区切り判定
                T.append(cnt)
                cnt=0
            if j==h-1: #最後の列
                T.append(cnt)
                cnt=0
        if flag:
            break
        for j in range(len(C)): #それぞれのブロックに対して
            if C[j]+T[j]>k:
                now+=1
                C=T
                break
            else:
                C[j]+=T[j]
    if flag:
        break
    ans=min(ans,now+y)
print(ans)

Submission status: Wrong Answer

Solution code:
H,W,K = map(int,input().split())
import numpy as np
from collections import deque
ans = 10000
S = np.array([list(map(int,list(input()))) for _ in range(H)])
cum = [[0]*W for _ in range(H+1)]
for j in range(W):
  for i in range(1,H+1):
    cum[i][j] = cum[i-1][j]+S[i-1][j]
    
cum = np.array(cum)
for i in range(2**(H-1)):
  q = deque([0])
  for h in range(H):
    if (i>>h)&1:
      q.append(h+1)
  q.append(H)
  p = deque()
  judge = False
  for a in range(len(q)-1):
    x = cum[q[a+1]]-cum[q[a]]
    if (x>K).any():
      judge = True
      break
    else:
      p.append(x)

  if judge:
    continue
  
  t_a = len(q)-2
  n = len(p)
  l = [0]*n
  for w in range(W):
    for x,a in enumerate(p):
      if l[x]>K:
        t_a+=1
        l = [0]*n
        for z,b in enumerate(p):
          l[z] = b[w]
        break
  ans = min(ans,t_a)
    
print(ans)

Submission status: Wrong Answer

Solution code:
H,W,K = map(int,input().split())
import numpy as np
from collections import deque
ans = 10000
S = np.array([list(map(int,list(input()))) for _ in range(H)])
cum = [[0]*W for _ in range(H+1)]
for j in range(W):
  for i in range(1,H+1):
    cum[i][j] = cum[i-1][j]+S[i-1][j]
    
cum = np.array(cum)
for i in range(2**(H-1)):
  q = deque([0])
  for h in range(H):
    if (i>>h)&1:
      q.append(h+1)
  q.append(H)
  p = deque()
  judge = False
  for a in range(len(q)-1):
    x = cum[q[a+1]]-cum[q[a]]
    if (x>K).any():
      judge = True
      break
    else:
      p.append(x)

  if judge:
    continue
  
  t_a = len(q)-2
  n = len(p)
  l = [0]*n
  for w in range(W):
    for x,a in enumerate(p):
      l[x]+=a[w]
      if l[x]>K:
        t_a+=1
  ans = min(ans,t_a)
    
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
from itertools import product

H,W,K=map(int,input().split(' '))
arr = np.vstack([list(map(int,list(input()))) for j in range(H)])
ans = H+W-2
cnt = 0
d_cnt = 0
for p in product([0,1],repeat=H-1):
    cnt += 1
    sp=np.zeros((sum(p)+1,W),int)
    row=0
    sp[0]+=arr[0]
    for j in range(H-1):
        if p[j]:
            row+=1
        sp[row]+=arr[j+1]
    if np.max(sp)>K:
        continue
    sum_arr = np.zeros(len(sp),int)
    cut_cnt = sum(p)
    for c in range(W):
        sum_arr += sp[:,c]
        if max(sum_arr)>K:
            cut_cnt+=1
            sum_arr=sp[:,c]
            if cut_cnt > ans:
                break
    ans = min(cut_cnt,ans)
print(cnt,d_cnt)

Submission status: Wrong Answer

Solution code:
H,W,K = map(int,input().split())
import numpy as np
from collections import deque
ans = 10000
S = np.array([list(map(int,list(input()))) for _ in range(H)])
cum = [[0]*W for _ in range(H+1)]
for j in range(W):
  for i in range(1,H+1):
    cum[i][j] = cum[i-1][j]+S[i-1][j]
    
cum = np.array(cum)
for i in range(2**(H-1)):
  q = deque([0])
  for h in range(H):
    if (i>>h)&1:
      q.append(h+1)
  q.append(H)
  p = deque()
  judge = False
  for a in range(len(q)-1):
    x = cum[q[a+1]]-cum[q[a]]
    if (x>K).any():
      judge = True
      break
    else:
      p.append(x)

  if judge:
    continue
  
  t_a = len(q)-2
  n = len(p)
  l = [0]*n
  for w in range(W):
    for x,a in enumerate(p):
      continue
  ans = min(ans,t_a)
    
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy
h,w,k = map(int,input().split())
h_conv = []
for i in range(2**(h-1)):
    h_conv.append(bin(i)[2::].zfill(h-1))
choco = []
for i in range(h):
    choco.append(list(map(int,input())))
choco_num = numpy.zeros([h,w])
choco_num[0] = numpy.cumsum(choco[0])
cnt = choco_num[0][0]
for i in range(1, h):
    if choco[i][0] == 1:
        cnt += 1
    choco_num[i][0] = cnt
for i in range(1,h):
    for j in range(1, w):
        if choco[i][j] == 1:
            choco_num[i][j] = choco_num[i-1][j] + choco_num[i][j-1] - choco_num[i-1][j-1] + 1
        else:
            choco_num[i][j] = choco_num[i - 1][j] + choco_num[i][j - 1] - choco_num[i - 1][j - 1]
ans = int(1e9)
for i in range(len(h_conv)):
    # print(h_conv[i])
    cnt = 0
    cutting = []
    for j in range(h-1):
        if h_conv[i][j] == "1":
            cnt += 1
            cutting.append(j)
    cutting.append(h-1)
    cut_w = -1
    for j in range(w):
        # print(j, "w")
        prev = 0
        for l in cutting:
            if cut_w == -1:
                focus = choco_num[l][j]
            else:
                focus = choco_num[l][j] - choco_num[l][cut_w]
            # print(int(focus-prev))
            if focus - prev > k:
                cnt += 1
                cut_w = j-1
                break
            prev = focus
        # print(cnt, cut_w)
    ans = min(ans,cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
H,W,K = map(int,input().split())
import numpy as np
from collections import deque
ans = 10000
S = np.array([list(map(int,list(input()))) for _ in range(H)])
cum = [[0]*W for _ in range(H+1)]
for j in range(W):
  for i in range(1,H+1):
    cum[i][j] = cum[i-1][j]+S[i-1][j]
    
cum = np.array(cum)
for i in range(2**(H-1)):
  q = deque([0])
  for h in range(H):
    if (i>>h)&1:
      q.append(h+1)
  q.append(H)
  p = deque()
  judge = False
  for a in range(len(q)-1):
    x = cum[q[a+1]]-cum[q[a]]
    if (x>K).any():
      judge = True
      break
    else:
      p.append(x)

  if judge:
    continue
  

    
print(ans)

Submission status: Wrong Answer

Solution code:
H,W,K = map(int,input().split())
import numpy as np
from collections import deque
ans = 10000
S = np.array([list(map(int,list(input()))) for _ in range(H)])
cum = [[0]*W for _ in range(H+1)]
for j in range(W):
  for i in range(1,H+1):
    cum[i][j] = cum[i-1][j]+S[i-1][j]
    
cum = np.array(cum)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def S(): return input()


def MI(): return map(int, input().split())


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


def print_matrix(mat):
    for i in range(len(mat)):
        print(*mat[i])


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False
# show_flg = True

WHITE = '1'
BLACK = '0'

# def count(graph):


def main():
    H, W, K = MI()
    graph = [None] * H

    for i in range(H):
        graph[i] = [int(v) for v in list(S())]

    ans = 10**9
    for i in range(2 ** (H-1)):
        groups = [0]
        for j in range((H-1)):
            if ((i >> j) & 1):
                groups.append(j+1)
        groups.append(H)

        divide_count = 0
        counter = defaultdict(int)
        for w in range(W):
            current_counter = defaultdict(int)
            for g in range(1, len(groups)):
                prev_div = groups[g-1]
                div = groups[g]
                total = 0
                for h in range(prev_div, div):
                    total += graph[h][w]
                current_counter[g] += total

            for k, v in current_counter.items():
                counter[k] += v
                if counter[k] > K:
                    divide_count += 1
                    counter = current_counter
                    break

        ans = min(ans, divide_count + len(groups) - 2)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
H, W, K = map(int,input().split())
B = [input() for k in range(H)]
S = [[0]*(W+1) for k in range(H)]

for k in range(H):
    for l in range(W):
        if B[k][l] == "1":
            S[k][l+1] = S[k][l] + 1
        else:
            S[k][l+1] = S[k][l]

ans = 1000000
for k in range(2**(H-1)):
    t = [0]*W
    u = []
    for d in range(H):
        if (k>>d)&1 == 1:
            for l in range(W):
                t[l] += int(B[d][l])
        else:
            for l in range(W):
                t[l] += int(B[d][l])
            u.append(t)
            t = [0]*W
    u = sorted(u)
    temp = len(u)-1
    d = [0]*W
    now = 0
    for e in u:
        now = 0
        for k in range(W):
            if e[k] > K:
                temp = 1000000
                break
            else:
                if now + e[k] > K:
                    d[k] = 1
                    now = e[k]
                else:
                    if d[k] == 1:
                        now = e[k]
                    else:
                        now += e[k]
    ans = min(ans,temp+d.count(1))
print(ans)

Submission status: Wrong Answer

Solution code:
def count(x1,y1,x2,y2):
  ret=acum[y2][x2]
  if x1!=0:
    ret-=acum[y2][x1-1]
  if y1!=0:
    ret-=acum[y1-1][x2]
  if x1!=0 and y1!=0:
    ret+=acum[y1-1][x1-1]
  return ret

h,w,k=map(int,input().split())
board=[list(input()) for _ in range(h)]
acum=[[0]*w for _ in range(h)]
for i in range(h):
  for j in range(w):
    if board[i][j]=='1':
      acum[i][j]+=1
    if i!=0:
      acum[i][j]+=acum[i-1][j]
    if j!=0:
      acum[i][j]+=acum[i][j-1]
    if i!=0 and j!=0:
      acum[i][j]-=acum[i-1][j-1]
ans=10**18
for rows in range(2**(h-1)):
  hlist=[]
  flag=format(rows,'b')[::-1]
  for i in range(len(flag)):
    if flag[i]=='1':
      hlist.append(i)
  hlist.append(h-1)
  cnt=len(hlist)-1
  x1=0
  for x2 in range(w-1):
    y1=0
    for y2 in hlist:
      if count(x1,y1,x2,y2)>k:
        cnt+=10**18
      if count(x1,y1,x2,y2)<=k and count(x1,y1,x2+1,y2)>k:
        cnt+=1
        x1=x2+1
        break
      y1=y2+1
  if count(x1,y1,w-1,h-1)>k:
    cnt+=10**18
  ans=min(ans,cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
def count(x1,y1,x2,y2):
  ret=acum[y2][x2]
  if x1!=0:
    ret-=acum[y2][x1-1]
  if y1!=0:
    ret-=acum[y1-1][x2]
  if x1!=0 and y1!=0:
    ret+=acum[y1-1][x1-1]
  return ret

h,w,k=map(int,input().split())
board=[list(input()) for _ in range(h)]
acum=[[0]*w for _ in range(h)]
for i in range(h):
  for j in range(w):
    if board[i][j]=='1':
      acum[i][j]+=1
    if i!=0:
      acum[i][j]+=acum[i-1][j]
    if j!=0:
      acum[i][j]+=acum[i][j-1]
    if i!=0 and j!=0:
      acum[i][j]-=acum[i-1][j-1]
ans=10**18
for rows in range(2**(h-1)):
  hlist=[]
  flag=format(i,'b')[::-1]
  for j in range(len(flag)):
    if flag[j]=='1':
      hlist.append(j)
  hlist.append(h-1)
  cnt=len(hlist)-1
  x1=0
  for x2 in range(w-1):
    y1=0
    for y2 in hlist:
      if count(x1,y1,x2,y2)>k:
        cnt+=10**18
      if count(x1,y1,x2,y2)<=k and count(x1,y1,x2+1,y2)>k:
        cnt+=1
        x1=x2+1
        break
      y1=y2+1
  if count(x1,y1,w-1,h-1)>k:
    cnt+=10**18
  ans=min(ans,cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import combinations, chain

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


def h_divide(Sss, div_is):
    result = []
    for s, e in zip(chain([0], div_is), chain(div_is, [len(Sss)])):
        result.append(Sss[s:e])
    return result


def _v_end(Sss, start, K):
    count = 0
    for i in range(start, len(Sss[0])):
        s = sum(map(lambda Ss: Ss[i], Sss))
        if count + s > K:
            return i - 1
        count += s
    return len(Sss[0]) - 1


def v_end(Ssss, start, K):
    result = -1
    for Sss in Ssss:
        end = _v_end(Sss, start, K)
        if end < start:
            return -1
        if result < 0 or result > end:
            result = end
    return result


def v_div_count(Ssss, K):
    start, result = 0, 0
    while True:
        end = v_end(Ssss, start, K)
        if end < 0:
            return -1
        if end == len(Ssss[0][0]) - 1:
            break
        result += 1
        start = end + 1
    return result


h_cands = list(range(1, len(Sss)))
ans = -1
for n in range(len(h_cands) + 1):
    for comb in combinations(h_cands, n):
        if n >= ans:
            continue
        Ssss = h_divide(Sss, list(comb))
        cnt = v_div_count(Ssss, K)
        if cnt < 0:
            continue
        if ans < 0 or ans > n + cnt:
            ans = n + cnt
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)]
ans = H+W-2
for i in range(2**(H-1)):
    S_tmp=[]
    tmp = S[0][:]
    for n,j in enumerate(format(i,'0{}b'.format(H-1))):
        if j=='0':
            S_tmp.append(tmp)
            tmp = S[n+1][:]
        else:
            for k in range(W):
                tmp[k]+=S[n+1][k]
    S_tmp.append(tmp)
    S_tmp_l=len(S_tmp)
    cut=[0]*S_tmp_l
    ans_tmp = S_tmp_l-1
    for w in range(W):
        flg=True
        for s_l in range(S_tmp_l):
            if cut[s_l]+S_tmp[s_l][w] > K:
                ans_tmp += 1
                cut = [i[w] for i in S_tmp]
                if S_tmp[s_l][w]>K:
                    flg=False
            else:
                cut[s_l]+=S_tmp[s_l][w]
    if flg:
        ans = min(ans,ans_tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
from copy import deepcopy
H,W,K=map(int,input().split(' '))
S=[list(map(int,list(input()))) for i in range(H)]
ans = H+W-2
for i in range(2**(H-1)):
    S_tmp=[]
    tmp = S[0][:]
    for n,j in enumerate(format(i,'0{}b'.format(H-1))):
        if j=='0':
            S_tmp.append(tmp)
            tmp = S[n+1][:]
        else:
            for k in range(W):
                tmp[k]+=S[n+1][k]
    S_tmp.append(tmp)
    S_tmp_l=len(S_tmp)
    cut=[0]*S_tmp_l
    ans_tmp = S_tmp_l-1
    for w in range(W):
        flg=True
        for s_l in range(S_tmp_l):
            if cut[s_l]+S_tmp[s_l][w] > K:
                ans_tmp += 1
                cut = [i[w] for i in S_tmp]
                if S_tmp[s_l][w]>K:
                    flg=False
            else:
                cut[s_l]+=S_tmp[s_l][w]
    if flg:
        ans = min(ans,ans_tmp)
print(ans)

Submission status: Wrong Answer

Solution code:

import itertools
h,w,k=map(int,input().split())
S=[]
for _ in range(h):
    s = list(map(int, list(input().rstrip())))
    S.append(s)

ans = 2000
for i in itertools.product([0,1], repeat = h-1):
    cnt = i.count(1)
    # print(sum(i))
    res = [S[0]]
    for j in range(h-1):
        if i[j]:
            res.append(S[j+1])

        else:
            res[-1] = [res[-1][i] + S[j+1][i] for i in range(w)]
    l = len(res)
    sm_list = [0]*l
    for j in range(w):
        if max(res[i][j] for i in range(l)) > k:
            break

        tmp = [sm_list[i] + res[i][j] for i in range(l)]
        if max(tmp) > k:
            cnt += 1
            sm_list = [res[i][j] for i in range(l)]

        else:
            sm_list = tmp

    ans = min(ans, cnt)

print(ans)

Submission status: Wrong Answer

Solution code:

import itertools
h,w,k=map(int,input().split())
S=[]
for _ in range(h):
    s = list(map(int, list(input().rstrip())))
    S.append(s)

ans = 2000000000
for i in itertools.product([0,1], repeat = h-1):
    cnt = sum(i)
    # print(sum(i))
    res = [S[0]]
    idx = 0
    for j in range(h-1):
        if i[j] == 1:
            res.append(S[j+1])

        else:
            res[-1] = [res[-1][i] + S[j+1][i] for i in range(w)]
    l = len(res)
    sm_list = [0]*l
    for j in range(w):
        if max(res[i][j] for i in range(l)) > k:
            break

        tmp = [sm_list[i] + res[i][j] for i in range(l)]
        if max(tmp) > k:
            cnt += 1
            sm_list = [res[i][j] for i in range(l)]

        else:
            sm_list = tmp

    ans = min(ans, cnt)

print(ans)

Submission status: Wrong Answer

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

    def check(lis):
        lis.append(h)
        num = [0]*(len(lis))
        ans = 0
        for i in range(w):
            ch = 0
            num2 = [0]*(len(lis))
            for j in range(h):
                
                if l[j][i] == "1":
                    if j <= lis[ch]:
                        num2[ch] += 1
                    else:
                        ch += 1
                        num2[ch] += 1
            if max(num2) > k:
                return float("INF")
            else:
                for i in range(len(num)):
                    num[i] += num2[i]
                    if num[i] > k:
                        ans += 1
                        num = num2
                        break 
            
            
        return ans

    ans = 10**9

    for i in range(2**(h-1)):
        count = 0
        lis1 = []
        for j in range(h-1):
            if (i >> j) & 1:
                lis1.append(j)
                count += 1
        
        ans = min(ans,count+check(lis1))
        
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import itertools, copy

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

ans = float("inf")
for n_horizontal_cut in range(H):
    for horizontal_cut_idx in list(itertools.combinations(list(range(1,H)), n_horizontal_cut)):
        horizontal_cut_idx = [0] + list(horizontal_cut_idx) + [H]
        n_vertical_cut = 0
        n_white_choco = [0] * (n_horizontal_cut+1)
        for w in range(W):
            tmp_idx = 0
            tmp_n_white_choco = copy.copy(n_white_choco)
            for h in range(H):
                if h >= horizontal_cut_idx[tmp_idx+1]:
                    tmp_idx += 1
                if S[h][w] == 1:
                    n_white_choco[tmp_idx] += 1
            if max(n_white_choco) > K:
                n_vertical_cut += 1
                n_white_choco = [n_white_choco[i] - tmp_n_white_choco[i] for i in range(n_horizontal_cut+1)]
        ans = min(ans, n_horizontal_cut + n_vertical_cut)

print(ans)

Submission status: Wrong Answer

Solution code:
H,W,K = map(int,input().split())
import numpy as np
from collections import deque
ans = 10000
S = np.array([list(map(int,list(input()))) for _ in range(H)])
for i in range(2**(H-1)):
  q = deque([0])
  for h in range(H):
    if (i>>h)&1:
      q.append(h+1)
  q.append(H)
  p = deque()
  for a in range(len(q)-1):
    p.append(S[q[a]:q[a+1]:,:])
  
  t_a = len(q)-2
  l = np.array([0]*len(p))
  judge = False
  for w in range(W):
    for x,a in enumerate(p):
      y = np.sum(a[:,w])
      if y>K:
        judge = True
        break
      else:
        l[x]+=y
        if l[x]>K:
          t_a+=1
          l = np.array([0]*len(p))
          for z,b in enumerate(p):
            l[z] = np.sum(b[:,w])
    if judge:
      break
  if judge:
    continue
  else:
    ans = min(ans,t_a)
    
print(ans)

Submission status: Wrong Answer

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

choco = []
for i in range(H):
  s = input().strip()
  a = list(map(int, list(s)))
  choco.append(a)

def min_split(h):
  sum_cnt = [0] * H
  num_split = 0
  for j in range(W):
    c = 0
    cnt = [0] * H
    flag = False
    for i in range(H):
      if choco[i][j] == 1:
        cnt[c] += 1
        if cnt[c] + sum_cnt[c] > K:
          flag = True
      if i < H-1 and h[i] == 1:
        c += 1
    if flag:
      num_split += 1
      sum_cnt = cnt
    else:
      for i in range(len(cnt)):
      	sum_cnt[i] += cnt[i]
  return num_split + sum(h)

min_m = float('inf')
for h in itertools.product([0,1], repeat=H-1):
  m = min_split(h)
  min_m = min(min_m, m)
print(min_m)

Submission status: Wrong Answer

Solution code:
def main():
    import numpy as np
    h,w,k = map(int,input().split())
    l = [list(input()) for i in range(h)]

    def check(lis):
        lis.append(h)
        num = np.zeros(len(lis))
        ans = 0
        for i in range(w):
            ch = 0
            num2 = np.zeros(len(lis))
            for j in range(h):
                
                if l[j][i] == "1":
                    if j <= lis[ch]:
                        num2[ch] += 1
                    else:
                        ch += 1
                        num2[ch] += 1
            if np.max(num2) > k:
                return float("INF")
            else:
                num += num2
            if np.max(num) > k:
                ans += 1
                num = num2
            
        return ans

    ans = 10**9

    for i in range(2**(h-1)):
        count = 0
        lis1 = []
        for j in range(h-1):
            if (i >> j) & 1:
                lis1.append(j)
                count += 1
        
        ans = min(ans,count+check(lis1))
        
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

cnt=10001

for i in range(2**(h-1)):
    split=[0]*h
    curcnt=0
    for j in range(h):
        if (i>>j)&1:
            split[j]=1
            curcnt+=1
        
    nsplit=curcnt+1
    sumlst=[[0]*(nsplit) for _ in range(w)]
    chklst=[[0]*(nsplit) for _ in range(w)]
    
    cw=0
    memo=0
    flag=False
    while cw<w:
        l=0
        for ch in range(h):
            chklst[cw][l]+=s[ch][cw]
            sumlst[memo][l]+=s[ch][cw]

            if chklst[cw][l]>k:
                flag=True
                break

            if sumlst[memo][l]>k:
                memo+=1
                break

            if split[ch]:
                l+=1
        else:
            cw+=1
            continue

        if flag:
            break

    if not flag:
        cnt=min(cnt,curcnt+memo)

print(cnt)

Submission status: Wrong Answer

Solution code:
from copy import deepcopy
H,W,K=map(int,input().split(' '))
S=[list(map(int,list(input()))) for i in range(H)]
ans = H+W-2
for i in range(2**(H-1)):
    S_tmp=[]
    tmp = S[0][:]
    for n,j in enumerate(format(i,'0{}b'.format(H-1))):
        if j=='0':
            S_tmp.append(tmp)
            tmp = S[n+1][:]
        else:
            for k in range(W):
                tmp[k]+=S[n+1][k]
    S_tmp.append(tmp)
    S_tmp_l=len(S_tmp)
    cut=[0]*S_tmp_l
    ans_tmp = H-S_tmp_l
    for w in range(W):
        for s_l in range(S_tmp_l):
            if cut[s_l]+S_tmp[s_l][w] > K:
                ans += 1
                cut=[0]*S_tmp_l
                break
            else:
                cut[s_l]+=S_tmp[s_l][w]
    ans = min(ans,ans_tmp)
print(ans)

Submission status: Wrong Answer

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

cnt=10001

for i in range(2**(h-1)):
    split=[0]*h
    curcnt=0
    for j in range(h):
        if (i>>j)&1:
            split[j]=1
            curcnt+=1
        
    nsplit=curcnt+1
    sumlst=[[0]*(nsplit) for _ in range(w)]
    chklst=[[0]*(nsplit) for _ in range(w)]
    
    cw=0
    memo=0
    flag=False
    while cw<w:
        l=0
        for ch in range(h):
            chklst[cw][l]+=s[ch][cw]
            sumlst[memo][l]+=s[ch][cw]

            if chklst[cw][l]>k:
                flag=True

            if sumlst[memo][l]>k:
                memo+=1
                break

            if split[ch]:
                l+=1
        else:
            cw+=1
            continue

        if flag:
            break

    if not flag:
        cnt=min(cnt,curcnt+memo)

print(cnt)