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: Time Limit Exceeded

Solution code:
from itertools import accumulate
from operator import add


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

white_count = [0] * (w+1)
prev = [0] * (w+1)
for _ in range(h):
    line = iter('0'+input())
    cumsum_1d = accumulate(map(int, line))
    cumsum_2d = list(map(add, prev, cumsum_1d))
    prev = cumsum_2d
    white_count += cumsum_2d


def get_white(sy, sx, ny, nx):
    a = sy*(w+1) + sx
    b = sy*(w+1) + nx
    c = ny*(w+1) + sx
    d = ny*(w+1) + nx
    return white_count[d] - white_count[c] - white_count[b] + white_count[a]


ans = []
for pattern in range(2**(h-1)):
    dived = [0] + [y+1 for y in range(h-1) if (pattern>>y) & 1] + [h]
    slash_count = len(dived) - 2

    prev_x = 0
    for div_x in range(1, w + 1):
        white_include = 0
        for idx in range(len(dived)-1):
            prev_y = dived[idx]
            div_y = dived[idx+1]
            white = get_white(prev_y, prev_x, div_y, div_x)
            if white > white_include:
                white_include = white

        if white_include > k:
            slash_count += 1
            if prev_x == div_x - 1:
                break
            prev_x = div_x - 1

    else:
        ans.append(slash_count)

print(min(ans))

Submission status: Time Limit Exceeded

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

def minisolve(left, cut, n):
    a = [0] * n
    i = 0
    for l in range(left, W):
        for t in range(H):
            if t >= cut[i]:
                i += 1
            if C[t][l]:
                a[i] += 1
                if a[i] > K:
                    return l
        i = 0

INF = (H-1)*(W-1)
ans = INF
N = H-1
for bit in range(1<<N):
    n = 1
    cut = []
    for i in range(N):
        if 1 & bit>>i:
            n += 1
            cut.append(i+1)
    cut.append(H)

    left = 0
    res = 0
    for _ in range(INF):
        left = minisolve(left, cut, n)
        if left==None:
            break
        else:
            res += 1
    res += n-1
    ans = min(ans, res)

print(ans)

Submission status: Time Limit Exceeded

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

def minisolve(left, cut, n):
    a = [0] * n
    i = 0
    while left < W:
        for t in range(H):
            if t >= cut[i]:
                i += 1
            if C[t][left]:
                a[i] += 1
                if a[i] > K:
                    return left
        left += 1
        i = 0

INF = (H-1)*(W-1)
ans = INF
N = H-1
for bit in range(1<<N):
    n = 1
    cut = []
    for i in range(N):
        if 1 & bit>>i:
            n += 1
            cut.append(i+1)
    cut.append(H)

    left = 0
    res = 0
    for _ in range(INF):
        left = minisolve(left, cut, n)
        if left==None:
            break
        else:
            res += 1
    res += n-1
    ans = min(ans, res)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def f(nums, K, w):
  h=len(nums)
  counter=[nums[x][0] for x in range(h)]
  if max(counter)>K:
    return float('inf')
  
  out=0
  for i in range(1, w):
    for x in range(h):
      counter[x]+=nums[x][i]
      
    if max(counter)>K:
      out+=1
      counter=[nums[x][i] for x in range(h)]
      
  return out

H, W, K=map(int, input().split())
S=[input() for _ in range(H)]
S=[[int(S[i][j]) for j in range(W)] for i in range(H)]
ans=float('inf')
for p in range(2**(H-1)):
  q='0'+format(p, '0'+str(H-1)+'b')+'1'
  i=0
  c=0
  nums=[]
  while i<H:
    j=1
    while i+j<H and q[i+j]=='0':
      j+=1
    tmp=S[i:i+j]
    nums.append([sum([tmp[y][x] for y in range(j)]) for x in range(W)])
    i+=j
    
  cand=f(nums, K, W)+q.count('1')-1
  if ans>cand:
    ans=cand
    
print(ans)

Submission status: Time Limit Exceeded

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

def minisolve(left, cut, n):
    a = [0] * n
    i = 0
    while left < W:
        for t in range(H):
            if t >= cut[i]:
                i += 1
            if C[t][left]:
                a[i] += 1
                if a[i] > K:
                    return left
        left += 1
        i = 0

ans = 10**18
N = H-1
for bit in range(1<<N):
    n = 1
    cut = []
    for i in range(N):
        if 1 & bit>>i:
            n += 1
            cut.append(i+1)
    cut.append(H)

    left = 0
    res = 0
    while True:
        left = minisolve(left, cut, n)
        if left==None:
            break
        else:
            res += 1
    res += n-1
    ans = min(ans, res)

print(ans)

Submission status: Time Limit Exceeded

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

H,W,K = map(int,input().split())
choco = [input() for _ in range(H)]
num =(2**(H-1))

white_count = list()
min_div_count =10**6
for i in range(num):
    bin_str = format(i, 'b')
    zero = str()
    if H != len(bin_str):
        for _ in range(H-len(bin_str)):
            zero += "0"
        bin_str = zero + bin_str
    white_count = [0 for s in bin_str if s == "1"]
    white_count.append(0)
    div_count=len(white_count)-1
    j = 0
    while j < W:
        block_count = 0
        for k in range(len(bin_str)):
            if bin_str[k] == "1":
                block_count += 1
            white_count[block_count] += int(choco[k][j])
            if white_count[block_count] > K:
                div_count +=1
                white_count = [0 for s in bin_str if s == "1"]
                white_count.append(0)
                break
        else:
            j+=1

        if div_count >= min_div_count:
            break

    else:
        min_div_count = div_count
print(min_div_count)

Submission status: Time Limit Exceeded

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

H,W,K = map(int,input().split())
choco = [input() for _ in range(H)]
num =(2**(H-1))

white_count = list()
min_div_count =10**6
for i in range(num):
    bin_str = format(i, 'b')
    zero = str()
    if H != len(bin_str):
        for i in range(H-len(bin_str)):
            zero += "0"
        bin_str = zero + bin_str
    white_count = [0 for s in bin_str if s == "1"]
    white_count.append(0)
    div_count=len(white_count)-1
    j = 0
    while j < W:
        block_count = 0
        for k in range(len(bin_str)):
            if bin_str[k] == "1":
                block_count += 1
            white_count[block_count] += int(choco[k][j])
            if white_count[block_count] > K:
                div_count +=1
                white_count = [0 for s in bin_str if s == "1"]
                white_count.append(0)
                break
        else:
            j+=1
    if min_div_count > div_count:
        min_div_count = div_count
print(min_div_count)

Submission status: Time Limit Exceeded

Solution code:
def main():
  H,W,K = map(int,input().split())
  S = [[] for _ in range(H)]
  for i in range(H):
    for s in input():
      S[i].append(int(s))
  #print(S)
  
  ans = 10000
  for i in range(2**(H-1)):
    th = bin(i).count('1')
    ans0 = th
    T = [[0 for _ in range(W)] for _ in range(th+1)]
    ti = 0
    for j in range(H):
      for k in range(W):
        T[ti][k] += S[j][k]
      if (i>>j)&1 == 1:
        ti += 1
    #print(th,T)
    tw = 0
    #for k in range(W):
    k = 0
    while(k < W):
      f = True
      #print(tw)
      for j in range(th+1):
        if sum(T[j][tw:k+1]) > K:
          f = False
        #print(sum(T[j][tw:k+1]),f,tw,k)
      if not f:
        if tw == k:
          ans0 = 10000
          break
        else:
          tw = k
          k -= 1
          ans0 += 1
      k += 1
    ans = min(ans0,ans)
  print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numpy as np
from sys import stdin

H, W, K = map(int, stdin.readline().split())
A = np.int32([[int(x) for x in stdin.readline().strip()] for _ in range(H)])

ans = H * W
for mask in itertools.product([0, 1], repeat=H - 1):
    pivots = [r + 1 for r in range(H - 1) if mask[r]]
    if len(pivots) > ans:
        continue

    blocks = np.concatenate([block.sum(axis=0) for block in np.split(A, pivots)])
    blocks = blocks.reshape(len(pivots) + 1, W)
    if blocks.max() > K:
        continue

    n_block = blocks.shape[0]
    n_cut = n_block - 1
    sums = np.zeros(n_block, dtype=int)

    for c in range(W):
        adds = blocks[:, c]
        sums = sums + adds
        if np.any(sums > K):
            n_cut += 1
            sums = adds
            if n_cut >= ans:
                break

    ans = min(ans, n_cut)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numpy as np

H, W, K = map(int, input().split())
A = np.int32([[int(x) for x in input()] for _ in range(H)])

ans = H * W
for mask in itertools.product([0, 1], repeat=H - 1):
    pivots = [r + 1 for r in range(H - 1) if mask[r]]
    if len(pivots) > ans:
        continue

    blocks = np.concatenate([block.sum(axis=0) for block in np.split(A, pivots)])
    blocks = blocks.reshape(len(pivots) + 1, W)
    if blocks.max() > K:
        continue

    n_block = blocks.shape[0]
    n_cut = n_block - 1
    sums = np.zeros(n_block, dtype=int)

    for c in range(W):
        adds = blocks[:, c]
        sums = sums + adds
        if np.any(sums > K):
            n_cut += 1
            sums = adds
            if n_cut >= ans:
                break

    ans = min(ans, n_cut)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numpy as np

H, W, K = map(int, input().split())
A = np.int32([[int(x) for x in input()] for _ in range(H)])

ans = H * W
for mask in itertools.product([0, 1], repeat=H - 1):
    pivots = [r + 1 for r in range(H - 1) if mask[r]]
    if len(pivots) > ans:
        continue

    blocks = np.concatenate([block.sum(axis=0) for block in np.split(A, pivots)])
    blocks = blocks.reshape(len(pivots) + 1, W)
    if blocks.max() > K:
        continue

    n_vert_cut = 0
    n_block = blocks.shape[0]
    sums = np.zeros(n_block, dtype=int)

    for c in range(W):
        adds = blocks[:, c]
        sums = sums + adds
        if np.any(sums > K):
            n_vert_cut += 1
            sums = adds

    ans = min(ans, n_vert_cut + n_block - 1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numpy as np

H, W, K = map(int, input().split())
A = np.int32([[int(x) for x in input()] for _ in range(H)])

ans = H * W
for mask in itertools.product([0, 1], repeat=H - 1):
    # pivots = [r + 1 for r in range(H - 1) if mask[r]]
    # blocks = np.concatenate([block.sum(axis=0) for block in np.split(A, pivots)])
    # blocks = blocks.reshape(len(pivots) + 1, W)
    blocks = np.zeros((sum(mask) + 1, W), dtype=int)
    block_id = 0
    for r in range(H - 1):
        blocks[block_id] += A[r]
        if mask[r]:
            block_id += 1
    blocks[block_id] += A[-1]

    if blocks.max() > K:
        continue

    n_vert_cut = 0
    n_block = blocks.shape[0]
    sums = np.zeros(n_block, dtype=int)

    for c in range(W):
        adds = blocks[:, c]
        sums = sums + adds
        if np.any(sums > K):
            n_vert_cut += 1
            sums = adds

    ans = min(ans, n_vert_cut + n_block - 1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numpy as np

H, W, K = map(int, input().split())
A = np.int32([[int(x) for x in input()] for _ in range(H)])

ans = H * W
for mask in itertools.product([0, 1], repeat=H - 1):
    pivots = [r + 1 for r in range(H - 1) if mask[r]]
    blocks = np.concatenate([block.sum(axis=0) for block in np.split(A, pivots)])
    blocks = blocks.reshape(len(pivots) + 1, W)
    if blocks.max() > K:
        continue

    n_vert_cut = 0
    n_block = blocks.shape[0]
    sums = np.zeros(n_block, dtype=int)

    for c in range(W):
        adds = blocks[:, c]
        sums = sums + adds
        if np.any(sums > K):
            n_vert_cut += 1
            sums = adds

    ans = min(ans, n_vert_cut + n_block - 1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numpy as np

H, W, K = map(int, input().split())
A = np.int32([[int(x) for x in input()] for _ in range(H)])

def solve(blocks):
    n_vert_cut = 0
    n_block = blocks.shape[0]
    sums = np.zeros(n_block, dtype=int)

    for c in range(W):
        adds = blocks[:, c]
        sums = sums + adds
        if np.any(sums > K):
            n_vert_cut += 1
            sums = adds

    return n_vert_cut + n_block - 1

ans = H * W
for mask in itertools.product([0, 1], repeat=H - 1):
    pivots = [r + 1 for r in range(H - 1) if mask[r]]
    blocks = np.concatenate([block.sum(axis=0) for block in np.split(A, pivots)])
    blocks = blocks.reshape(len(pivots) + 1, W)
    if blocks.max() > K:
        continue
    ans = min(ans, solve(blocks))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numpy as np

H, W, K = map(int, input().split())
A = np.int32([[int(x) for x in input()] for _ in range(H)])

def solve(blocks):
    n_vert_cut = 0
    n_block = blocks.shape[0]
    vals = np.zeros(n_block)

    for c in range(W):
        adds = blocks[:, c]
        if np.any(adds > K):
            return H * W
        
        sums = vals + adds
        if np.any(sums > K):
            n_vert_cut += 1
            vals = adds
        else:
            vals = sums

    return n_vert_cut + n_block - 1

ans = H * W
for mask in itertools.product([0, 1], repeat=H - 1):
    pivots = [r + 1 for r in range(H - 1) if mask[r]]
    blocks = np.concatenate([block.sum(axis=0) for block in np.split(A, pivots)])
    blocks = blocks.reshape(len(pivots) + 1, W)
    ans = min(ans, solve(blocks))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import accumulate

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

H, W, K = lr()
S = [list(map(int, sr())) for _ in range(H)]
Scum = [list(accumulate(x)) for x in S]
answer = 10000
for bit in range(1<<(H-1)):
    count = 0
    for i in range(H-1):
        if bit >> i & 1:
            count += 1
    bit += 1 << H-1 # 最後の切れ目
    # 縦のラインは貪欲法
    prev = -1
    w = 0
    while w < W:
        white = 0
        cut = False
        for i in range(H):
            white += Scum[i][w] - (Scum[i][prev] if prev >= 0 else 0)
            if (bit >> i) & 1: # 切れ目が来た
                if white > K:
                    cut = True
                white = 0
        if cut:
            if prev == w-1: # 一列でKをオーバー
                break
            count += 1
            prev = w-1
        else:
            w += 1
    else:
        answer = min(answer, count)

print(answer)

Submission status: Time Limit Exceeded

Solution code:
def W_tips(j):
    global K,g,now,tips
    for i in range(g):
        now[i]+=tips[i][j]
    for i in range(g):
        if now[i] > K:
            return False
    return True

f_inf=float("inf")
H,W,K=map(int,input().split())
s=[None]*H
for i in range(H):
    s[i]=str(input())
ans = f_inf
for div in range(1 << (H-1)):
    g=int(0)
    id =[0]*H
    for j in range(H):
        id[j]=g
        if div>>j&1:g+=1
    num = g
    g+=1
    tips=[[0 for i in range(W)] for j in range(g)]
    for i in range(H):
        for j in range(W):
            tips[id[i]][j]+=(s[i][j] !="0")
    now=[0]*g
    for j in range(W):
        if W_tips(j)==False:
            num+=1
            now=[0]*g
            if W_tips(j)==False:
                num=f_inf
                break
    ans=min(ans,num)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W,K = map(int,input().split())
choco = [input() for l in range(H)]
num =(2**(H-1))

white_count = list()
min_div_count =10**6
for i in range(num):
    bin_str = format(i, 'b')
    zero = str()
    if H != len(bin_str):
        for i in range(H-len(bin_str)):
            zero += "0"
        bin_str = zero + bin_str
    white_count = [0 for s in bin_str if s == "1"]
    white_count.append(0)
    div_count=len(white_count)-1
    j = 0
    while j < W:
        block_count = 0
        for k in range(len(bin_str)):
            if bin_str[k] == "1":
                block_count += 1
            white_count[block_count] += int(choco[k][j])
            if white_count[block_count] > K:
                div_count +=1
                white_count = [0 for s in bin_str if s == "1"]
                white_count.append(0)
                break
            
        else:
            j+=1
    if min_div_count > div_count:
        min_div_count = div_count
print(min_div_count)

Submission status: Time Limit Exceeded

Solution code:
H,W,K = map(int,input().split())
choco = [input() for l in range(H)]
num =(2**(H-1))

white_count = list()
min_div_count =10**6
for i in range(num):
    bin_str = format(i, 'b')
    zero = str()
    if H != len(bin_str):
        for i in range(H-len(bin_str)):
            zero += "0"
        bin_str = zero + bin_str
    white_count = [0 for s in bin_str if s == "1"]
    white_count.append(0)
    div_count=len(white_count)-1
    j = 0
    while j < W:
        k_over = False
        block_count = 0
        for k in range(len(bin_str)):
            if bin_str[k] == "1":
                block_count += 1
            white_count[block_count] += int(choco[k][j])
            if white_count[block_count] > K:
                k_over = True
        if k_over:
            div_count +=1
            white_count = [0 for s in bin_str if s == "1"]
            white_count.append(0)
        else:
            j+=1
    if min_div_count > div_count:
        min_div_count = div_count
print(min_div_count)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
input = sys.stdin.readline
H,W,K=map(int,input().split())
CO=np.array([[0]*W]*H)
DO=np.array([[0]*W]*H)
for i in range(H):
 C=input()
 for j in range(W):
  DO[i][j]=int(C[j])
F=1000000
for s in range(2**(H-1)):
 D=0
 E=0
 Sui=[0]*(H-1)
 for t in range(H-1):
  if ((s >> t) & 1):
   Sui[t]+=1
 for m in range(H-1):
  E+=Sui[m]
 CO[H-1]=DO[H-1]
 for k in range(H-1):
  if Sui[k]==0:
   CO[H-k-2]=DO[H-k-2]+CO[H-k-1]
   CO[H-k-1]=[0]*W
  else:
   CO[H-k-2]=DO[H-k-2]
 for h in range(W-1):
  if np.amax(CO[:,h])>K:
   E=1000000
   break
  elif np.amax(CO[:,h])<=K and np.amax(np.sum(CO[:,h:h+2],axis=1))>K:
   D+=1
  else:
   CO[:,h+1]=np.sum(CO[:,h:h+2],axis=1)
 if np.amax(CO[:,W-1])>K:
  E=1000000
 if D==0 and E==0:
  F=0
 elif E==0:
  continue
 else:
  F=min(F,D+E)
print(F)

Submission status: Time Limit Exceeded

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

def main():
    h,w,k=map(int,input().split())
    s=[list(input()) for _ in range(h)]
    cnt=[[0]*(w+1) for _ in range(h+1)]#計算しやすくするために0の一に余剰なマスを入れてある

    for i in range(1,h+1):
        for j in range(1,w+1):
            flg=int(s[i-1][j-1])
            if i==0 and j==0:
                cnt[i][j]=flg
            elif i==0:
                cnt[i][j]=cnt[i][j-1]+flg
            elif j==0:
                cnt[i][j]=cnt[i-1][j]+flg
            else:
                cnt[i][j]=cnt[i-1][j]+cnt[i][j-1]-cnt[i-1][j-1]+flg
    ans=h+w+1
    for p in range(1<<(h-1)):
        g=[0]*(h+1)
        gnum,gcnt=0,0
        for i in range(h-1):
            if p>>i&1:
                gnum+=1
                g[gnum]=i+1
        gcnt+=gnum
        gnum+=1
        g[gnum]=h
        sw,j=1,2
        while j<=w:
            for i in range(1,gnum+1):
                if cnt[g[i]][sw]-cnt[g[i]][sw-1]-cnt[g[i-1]][sw]+cnt[g[i-1]][sw-1]>k:
                    gcnt=h+w+2
                    j=w
                    break            
            for i in range(1,gnum+1):
                if cnt[g[i]][j]-cnt[g[i]][sw-1]-cnt[g[i-1]][j]+cnt[g[i-1]][sw-1]>k:
                    sw=j
                    gcnt+=1
                    break
            j+=1
        ans=min(ans,gcnt)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

ans = float('inf')
for div in range(2 ** (H - 1)):
    g = 0
    ids = [0] * H
    for i in range(H):
        ids[i] = g
        if div >> i & 1:
            g += 1
    g += 1

    c = [[0 for _ in range(1005)] for _ in range(10)]
    for i in range(H):
        for j in range(W):
            c[ids[i]][j] += int(S[i][j])

    num = g - 1
    now = [0] * g
    def add(j):
        for i in range(g):
            now[i] += c[i][j]
            if now[i] > K:
                return False
        return True

    for j in range(W):
        if not add(j):
            num += 1
            now = [0] * g
            if not add(j):
                num = float('inf')
                break

    ans = min(ans, num)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
H,W,K=map(int,input().split())
CO=np.array([[0]*W]*H)
DO=np.array([[0]*W]*H)
for i in range(H):
 C=input()
 for j in range(W):
  DO[i][j]=int(C[j])
F=1000000
for s in range(2**(H-1)):
 D=0
 E=0
 Sui=[0]*(H-1)
 for t in range(H-1):
  if ((s >> t) & 1):
   Sui[t]+=1
 for m in range(H-1):
  E+=Sui[m]
 CO[H-1]=DO[H-1]
 for k in range(H-1):
  if Sui[k]==0:
   CO[H-k-2]=DO[H-k-2]+CO[H-k-1]
   CO[H-k-1]=[0]*W
  else:
   CO[H-k-2]=DO[H-k-2]
 for h in range(W-1):
  if np.amax(CO[:,h])>K:
   E=1000000
   break
  elif np.amax(CO[:,h])<=K and np.amax(np.sum(CO[:,h:h+2],axis=1))>K:
   D+=1
  else:
   CO[:,h+1]=np.sum(CO[:,h:h+2],axis=1)
 if np.amax(CO[:,W-1])>K:
  E=1000000
 if D==0 and E==0:
  F=0
 elif E==0:
  continue
 else:
  F=min(F,D+E)
print(F)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

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

    """
    white = []
    for line in S:
        white.append(line.count("1"))
    w = sum(white)

    if w <= K:
        print(0)
        exit()
    """

    ans = 10**5
    for i in range(2**(H-1)):
        ly = bin(i).count("1")
        x = 0
        y = [0]*(ly + 1)
        j = 0
        while j < W:
            m = 0
            for k in range(H):
                if S[k][j] == "1":
                    y[m] += 1
                    if y[m] > K:
                        x += 1
                        y = [0]*(ly + 1)
                        j -= 1
                        break
                if (i >> k) & 1:
                    m += 1
            j += 1

        ans = min(ans, x + ly)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

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

    white = []
    for line in S:
        white.append(line.count("1"))
    w = sum(white)

    if w <= K:
        print(0)
        exit()

    ans = 10**5
    for i in range(2**(H-1)):
        x = 0
        y = [0]*(bin(i).count("1")+1)
        j = 0
        while j < W:
            m = 0
            for k in range(H):
                if S[k][j] == "1":
                    y[m] += 1
                    if y[m] > K:
                        x += 1
                        y = [0]*(bin(i).count("1")+1)
                        j -= 1
                        break
                if (i >> k) & 1:
                    m += 1
            j += 1
        #print(y)
        #print(ans, x, len(y)-1)
        ans = min(ans, x + len(y) - 1)


    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
H,W,K=map(int,input().split())
CO=np.array([[0]*W]*H)
DO=np.array([[0]*W]*H)
for i in range(H):
 C=input()
 for j in range(W):
  DO[i][j]=int(C[j])
F=1000000
for s in range(2**(H-1)):
 D=0
 E=0
 Sui=[0]*(H-1)
 for t in range(H-1):
  if ((s >> t) & 1):
   Sui[t]+=1
 for m in range(H-1):
  E+=Sui[m]
 CO[H-1]=DO[H-1]
 for k in range(H-1):
  if Sui[k]==0:
   CO[H-k-2]=DO[H-k-2]+CO[H-k-1]
   CO[H-k-1]=[0]*W
  else:
   CO[H-k-2]=DO[H-k-2]
 for h in range(W-1):
  if np.amax(CO[:,h])>K:
   E=1000000
   break
  elif np.amax(CO[:,h])<=K and np.amax(CO[:,h]+CO[:,h+1])>K:
   D+=1
  else:
   CO[:,h+1]=CO[:,h]+CO[:,h+1]
 if np.amax(CO[:,W-1])>K:
  E=1000000
 if D==0 and E==0:
  F=0
 elif E==0:
  continue
 else:
  F=min(F,D+E)
print(F)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
H,W,K=map(int,input().split())
CO=np.array([[0]*W]*H)
DO=np.array([[0]*W]*H)
for i in range(H):
 C=input()
 for j in range(W):
  DO[i][j]=int(C[j])
F=1000000
for s in range(2**(H-1)):
 D=0
 E=0
 Sui=[0]*(H-1)
 for t in range(H-1):
  if ((s >> t) & 1):
   Sui[t]+=1
 for m in range(H-1):
  E+=Sui[m]
 CO[H-1]=DO[H-1]
 for k in range(H-1):
  if Sui[k]==0:
   CO[H-k-2]=DO[H-k-2]+CO[H-k-1]
   CO[H-k-1]=[0]*W
  else:
   CO[H-k-2]=DO[H-k-2]
 for h in range(W-1):
  CO[:,h+1]=CO[:,h]+CO[:,h+1]
  if np.amax(CO[:,h])>K:
   E=1000000   
   break
  elif np.amax(CO[:,h])<=K and np.amax(CO[:,h+1])>K:
   CO[:,h+1]=CO[:,h+1]-CO[:,h]
   D+=1
 if np.amax(CO[:,W-1])>K:
  E=1000000
 if D==0 and E==0:
  F=0
 elif E==0:
  continue
 else:
  F=min(F,D+E)
print(F)

Submission status: Time Limit Exceeded

Solution code:
H,W,K = map(int,input().split())
A = [0]*H
for i in range(H):
    A[i] = input()
s = 10000
for i in range(2**(H-1)):
    count = 0
    B = [0]*H
    for j in range(H-1):
        if (i >> j & 1):
            B[j] = 1
            count += 1
    C = [0]*(count + 1)
    for j in range(W):
        a = [0]*(count + 1)
        n = 0
        for k in range(H):
            a[n] += int(A[k][j])
            C[n] += int(A[k][j])
            if B[k] == 1:
                n += 1      
        if max(C) > K:
            count += 1
            C[:] = a[:]
    if s > count:
        s = count
print(s)

Submission status: Time Limit Exceeded

Solution code:
import re
import numpy as np

H,W,K = map(int,input().split())
grid = []
for i in range(H):
  S = input()
  grid.append( [S[i] for i in range(W) ])
grid = np.array(grid,dtype='int64')

min_cnt = 1000*10+1
#横の区切りを作る
for j in range(2**(H-1)):
  cnt = 0
  #二進数の文字列を取得
  bin_str = format(j,"0{}b".format(H-1)) 
  #区切りのインデックスリスト
  l_p =[0]+[ x.start()+1 for x in re.finditer("1",bin_str) ] +[H]

  #cntに区切りの分だけ付け加える
  cnt = cnt + len(l_p)-2
  
  #決めた行の区切りに対して、列ごとの和の配列を取得
  L = np.empty((0,W),int)
  for i in range(len(l_p)-1):
    slice_wa = [np.sum(grid[l_p[i]:l_p[i+1],:],axis=0)]
    L = np.append(L, slice_wa ,axis=0)

  tate = np.zeros( len(l_p)-1 ,dtype='int64')
  for w in range(W):#k以上の要素があるか
    tate = tate + L[:,w]
    if True in (tate > K):
      cnt = cnt + 1
      tate = np.zeros( len(l_p)-1 ,dtype='int64')+L[:,w]   
      
  min_cnt = min(cnt,min_cnt)   

###
print(min_cnt)

Submission status: Time Limit Exceeded

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):
        
        num = np.zeros(len(lis))
        ans = 0
        for i in range(w):
            num2 = np.zeros(len(lis))
            for j in range(h):
                if l[j][i] == "1":
                    num2[d[j]] += 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 = []
        d = []
        for j in range(h):
            d.append(count)
            if (i >> j) & 1:
                lis1.append(j)
                count += 1
        lis1.append(count+1)
        
        ans = min(ans,count+check(lis1))
        
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import re
import numpy as np

H,W,K = map(int,input().split())
grid = []
for i in range(H):
  S = input()
  grid.append( [S[i] for i in range(W) ])
grid = np.array(grid,dtype='int64')

min_cnt = 1000*10+1
#横の区切りを作る
for j in range(2**(H-1)):
  cnt = 0
  #二進数の文字列を取得
  bin_str = format(j,"0{}b".format(H-1)) 
  #区切りのインデックスリスト
  l_p =[0]+[ x.start()+1 for x in re.finditer("1",bin_str) ] +[H]

  #cntに区切りの分だけ付け加える
  cnt = cnt + len(l_p)-2
  
  #決めた行の区切りに対して、列ごとの和の配列を取得
  L = np.empty((0,W),int)
  for i in range(len(l_p)-1):
    slice_wa = [np.sum(grid[l_p[i]:l_p[i+1],:],axis=0)]
    L = np.append(L, slice_wa ,axis=0)

  tate = np.zeros( len(l_p)-1 ,dtype='int64')
  for w in range(W):#k以上の要素があるか
    n_tate = tate + L[:,w]
    if True in (n_tate > K):
      cnt = cnt + 1
      tate = np.zeros( len(l_p)-1 ,dtype='int64')+L[:,w]   
    else:
      tate = n_tate
  min_cnt = min(cnt,min_cnt)   
###
print(min_cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import product
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
h, w, k = map(int, readline().split())
CHOCO = [list(map(int, line.rstrip().decode())) for line in readlines()]
INF = 10**5
it = ["01"]*(h-1)
ans = INF
for x in product(*it):
    cnt = sum(map(int, x))
    agg = [[0]*(w) for _ in range(cnt+1)]
    *ls, = map(int, x+('1',))
    for i in range(w):
        prev = c = 0
        for j, split in enumerate(ls):
            if split:
                agg[c][i] = prev+CHOCO[j][i]
                prev = 0
                c += 1
            else:
                prev += CHOCO[j][i]
    tmp = [0]*(cnt+1)
    for xyz in zip(*agg):
        cannot_split = False
        can_continue = True
        for i, x in enumerate(xyz):
            if x > k:
                cannot_split = True
                break
            if x+tmp[i] > k:
                can_continue = False
                break

        if cannot_split:
            break

        if can_continue:
            for i, x in enumerate(xyz):
                tmp[i] += x
                continue
        else:
            for i, x in enumerate(xyz):
                tmp[i] = x
            cnt += 1

    if cannot_split:
        continue

    ans = min(ans, cnt)
print(ans)