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

LIS=[]

def saiki(x,st):
    if x==h-1:
        LIS.append(st)
        return
    else:
        saiki(x+1,st+st[-1])
        saiki(x+1,st+str(int(st[-1])+1))

saiki(0,"0")

DIC1={c:0 for c in "0123456789"}
DIC2={c:0 for c in "0123456789"}
ans=10**9
for cod in LIS:
    for ele in DIC1:
        DIC1[ele]=0
    cnt=int(cod[-1])
    end=False
    for i in range(w):
        for ele in DIC2:
            DIC2[ele]=0
        for q in range(h):
            if S[q][i]=="1":
                DIC2[cod[q]]+=1
        if max(DIC2.values())>k:
            end=True
            break
        flg=True
        for ele in DIC1:
            if DIC1[ele]+DIC2[ele]>k:
                flg=False
                break
        if flg:
            for ele in DIC1:
                DIC1[ele]+=DIC2[ele]
        else:
            for ele in DIC1:
                DIC1[ele]=DIC2[ele]
            cnt+=1
    if end:
        continue
    ans=min(ans,cnt)
    #print(cod,cnt)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product

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

for _ in range(H):
  grid += input()

ans = 10000

for Hcut in product((0, 1), repeat = H-1):
  Gr_num = sum(Hcut) + 1
  old = [0]*Gr_num
  cnt = 0
  for i in range(W):
    #縦一列のchocoを見る
    choco = grid[i::W]
    new = [0]*Gr_num
    gr = 0
    for j in range(H):
      new[gr] += int(choco[j])
      if j < H-1:
        if Hcut[j] == 1:
          gr += 1
    #そもそも一列でオーバーしてたら詰み。
    if max(new) > K:
      cnt += 10000
      break
    #新しい一列を追加しても大丈夫か確認
    check = [old[gr] + new[gr] for gr in range(Gr_num)]
    if max(check) > K:
      old = new[:]
      cnt += 1
    else:
      old = check[:]
  ans = min(ans, cnt+sum(Hcut))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
import copy
H,W,K = list(map(int, input().split()))
A = []
for i in range(H):
  A.append(list(map(int, input())))

#SM = [np.cumsum(A[i]) for i in range(H)]

ANS = []
for pat in product(['0','1'], repeat = H-1):
  res = []
  cnt = 0
  now = copy.copy(A[0])
  for i in range(1,H):
    p = pat[i-1]
    if p == '1':
      res.append(now)
      now = copy.copy(A[i])
      cnt += 1
    else:
      for j in range(W):
        now[j] += A[i][j]
  res.append(now)
  
  """  
  print("---")
  print(pat)
  print(res)
  print(cnt)
  """  
  wk2 = [0] * len(res)
  cnt2 = 0
  flg = True
  for x in range(W):
    for j in range(len(res)):
      if res[j][x] > K:
        # 横に割った段階で、すでに最小単位がKを超えてたら実現不可能
        flg = False
        break
      if wk2[j] + res[j][x] > K:
        cnt2 += 1
        wk2 = [0] * len(res)
        break
    for j in range(len(res)):
      wk2[j] += res[j][x]
    if not flg:
      break
      
  if flg:
    ANS.append(cnt + cnt2)
    #print(pat, cnt, cnt2)
print(min(ANS))

Submission status: Time Limit Exceeded

Solution code:
h, w, k = map(int, input().split())
S = [list(map(int, list(input()))) for _ in range(h)]
ans = float("inf")
for i in range(2**(h-1)):
  L = [0]
  cnt = 0
  for j in range(h-1):
    if i>>j & 1:
      L.append(j+1)
      cnt += 1
  L.append(h)
  C = [0]*(len(L)-1)
  for j in range(w):
    D = [0]*(len(L)-1)
    for l in range(len(L)-1):
      a, b = L[l], L[l+1]
      for s in range(a, b):
        D[l] += S[s][j]
    if max(D) > k:
      break
    for l, d in enumerate(D):
      if C[l]+d > k:
        break
    else:
      for l, d in enumerate(D):
        C[l] += d
      continue
    cnt += 1
    for l, d in enumerate(D):
      C[l] = d
  else:
    ans = min(ans, cnt)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W,K=map(int,input().split())
s=[[int(x) for x in list(input())] for _ in range(H)]
ans = H*W
for h in range(2**(H-1)):
  parts = list()
  upper = 0
  cnt = 0
  for j in range(H-1):
    if h >> j & 1:
      cnt += 1
      parts.append([sum([s[y][x] for y in range(upper, j+1)]) for x in range(W)])
      upper = j+1
  parts.append([sum([s[y][x] for y in range(upper, H)]) for x in range(W)])
  # 貪欲
  summary = [0]*len(parts)
  for i in range(W):
    temp_sum = [summary[j] + parts[j][i] for j in range(len(parts))]
    for ts in temp_sum:
      if ts > K:
        cnt += 1
        summary = [parts[j][i] for j in range(len(parts))]
        break
    else:
      summary = temp_sum
  ans = min(ans, cnt)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

h, w, k = [int(i) for i in input().split()]
s = np.zeros([h,w])
ans = (w-1)*(h-1)

for i in range(h):
    st = [int(j) for j in list(input())]
    s[i,:] = st
idx = []
for i in range(1<<h-1):
    tmp = []
    g = []
    for j in range(h-1):
        if ((i>>j)&1):
            tmp.append(j+1)

    n = len(tmp)
    choco = np.zeros([n+1,w])
    for j in range(n+1):
        if n == 0:
            choco = np.sum(s,axis=0)
        elif n > 0:
            if j == n:
                choco[j] = np.sum(s[tmp[j-1]:,:],axis=0)
            elif j == 0:
                choco[j] = np.sum(s[:tmp[j],:], axis=0)
            else:
                choco[j] = np.sum(s[tmp[j-1]:tmp[j],:], axis=0)
    w_div = 0
    w_div0 = 0
    nn = 0
    ans0 = (w-1)*(h-1)
    
    while w_div < w+1:
        if w_div == 0:
            num_choco = np.zeros((1,1))
            num_choco[0,0] = np.array(np.sum(choco))
        else:
            if n == 0:
                num_choco = np.zeros((1, 2))
                if w_div0 == 0:
                    num_choco[:,0] = np.sum(choco[:w_div])
                else:
                    num_choco[:,0] = np.sum(choco[w_div0:w_div])
                num_choco[:,1] = np.sum(choco[w_div:])
                
            else:
                num_choco = np.zeros((n+1,2))
                if w_div0 == 0:
                    num_choco[:,0] = np.sum(choco[:,:w_div],axis=1).T
                else:
                    num_choco[:,0] = np.sum(choco[:,w_div0:w_div],axis=1).T
                num_choco[:,1] = np.sum(choco[:,w_div:],axis=1).T
                
        if np.any(num_choco > k):
            if np.any(num_choco[:,0] > k) and w_div != 0:
                if w_div - w_div0 == 1:
                    break
                w_div0 = w_div-1
                nn += 1
                w_div += 0
            else:
                w_div +=1
        else:
            if w_div == w:
                ans0 = n + nn
                ans = min(ans,ans0)
            w_div += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

h, w, k = [int(i) for i in input().split()]
s = np.zeros([h,w])
ans = (w-1)*(h-1)

for i in range(h):
    st = [int(j) for j in list(input())]
    s[i,:] = st
idx = []
for i in range(1<<h-1):
    tmp = []
    g = []
    for j in range(h-1):
        if ((i>>j)&1):
            tmp.append(j+1)

    n = len(tmp)
    choco = np.zeros([n+1,w])
    for j in range(n+1):
        if n == 0:
            choco = np.sum(s,axis=0)
        elif n > 0:
            if j == n:
                choco[j] = np.sum(s[tmp[j-1]:,:],axis=0)
            elif j == 0:
                choco[j] = np.sum(s[:tmp[j],:], axis=0)
            else:
                choco[j] = np.sum(s[tmp[j-1]:tmp[j],:], axis=0)
    w_div = 0
    w_div0 = 0
    nn = 0
    ans0 = (w-1)*(h-1)
    
    while w_div < w+1:
        if w_div == 0:
            num_choco = np.zeros((1,1))
            num_choco[0,0] = np.array(np.sum(choco))
        else:
            if n == 0:
                num_choco = np.zeros((1, 2))
                if w_div0 == 0:
                    num_choco[:,0] = np.sum(choco[:w_div])
                else:
                    num_choco[:,0] = np.sum(choco[w_div0:w_div])
                num_choco[:,1] = np.sum(choco[w_div:])
                
            else:
                num_choco = np.zeros((n+1,2))
                if w_div0 == 0:
                    num_choco[:,0] = np.sum(choco[:,:w_div],axis=1).T
                else:
                    num_choco[:,0] = np.sum(choco[:,w_div0:w_div],axis=1).T
                num_choco[:,1] = np.sum(choco[:,w_div:],axis=1).T
                
        if np.any(num_choco > k):
            if np.any(num_choco[:,0] > k) and w_div != 0:
                w_div0 = w_div-1
                nn += 1
                w_div += 0
            else:
                w_div +=1
        else:
            if w_div == w:
                ans0 = n + nn

                ans = min(ans,ans0)
            w_div += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# bit全探索を意識して書いてみる
import numpy as np

h, w, k = [int(i) for i in input().split()]
s = np.zeros([h,w])
ans = (w-1)*(h-1) # 区切りの最大値

for i in range(h):
    st = [int(j) for j in list(input())]
    s[i,:] = st
idx = []
for i in range(1<<h-1):
    tmp = []
    g = []
    for j in range(h-1):
        if ((i>>j)&1):
            tmp.append(j+1)

    n = len(tmp)
    choco = np.zeros([n+1,w])
    for j in range(n+1):
        if n == 0:
            choco = np.sum(s,axis=0)
        elif n > 0:
            if j == n:
                choco[j] = np.sum(s[tmp[j-1]:,:],axis=0)
            elif j == 0:
                choco[j] = np.sum(s[:tmp[j],:], axis=0)
            else:
                choco[j] = np.sum(s[tmp[j-1]:tmp[j],:], axis=0)
#     print(choco)
    w_div = 0
    w_div0 = 0
    nn = 0
    ans0 = (w-1)*(h-1)
    
    # 分割した行列の列方向の合計が来ている状態
    while w_div < w+1:
         # 縦に分割している回数
        # chocoを分割した時の各領域のwhiteChoco合計数
        if w_div == 0:
            num_choco = np.zeros((1,1))
            num_choco[0,0] = np.array(np.sum(choco))
        else:
            if n == 0:
                num_choco = np.zeros((1, 2))
                if w_div0 == 0:
                    num_choco[:,0] = np.sum(choco[:w_div])
                else:
                    num_choco[:,0] = np.sum(choco[w_div0:w_div])
                num_choco[:,1] = np.sum(choco[w_div:])
                
            else:
                num_choco = np.zeros((n+1,2))
                if w_div0 == 0:
                    num_choco[:,0] = np.sum(choco[:,:w_div],axis=1).T # 分割点の左側の合計を計算
                else:
                    num_choco[:,0] = np.sum(choco[:,w_div0:w_div],axis=1).T # 分割点の左側の合計を計算
                num_choco[:,1] = np.sum(choco[:,w_div:],axis=1).T # 分割点の右側の合計を計算
        
#         print(num_choco)
        # それぞれの領域はchocoがk個以下か判定
        if np.any(num_choco > k): # 多いものがあった場合，前回のところで区切る
            if np.any(num_choco[:,0] > k) and w_div != 0:
                w_div0 = w_div-1
                nn += 1
#                 print('nn += 1 : w_div0=',w_div0)
                w_div += 0
            else:
                w_div +=1
        else: # 条件を超えているものがない場合，それはいい感じなのでansと比較する．
            if w_div == w:
                ans0 = n + nn
#                 print('n:', n, 'nn:', nn, 'ans', ans0)
                ans = min(ans,ans0)
            w_div += 1
#     print('---')
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w,k = map(int, input().split())
s = [[int(c) for c in input()] for i in range(h)]
ans = 114514893
for bit in range(1 << (h-1)):
    cut = [-1]
    for i in range(h-1):
        if bit & (1 << i) : cut.append(i)
    cut.append(h-1)
    l = len(cut)-1
    count = l-1
    suml = [0 for i in range(l)]
    ok = True
    for i in range(w):
        sumtemp = [0 for ii in range(l)]
        flag2 = True #kを超えないかどうか
        for j in range(l):
            for kk in range(cut[j]+1,cut[j+1]+1):
                sumtemp[j] = sumtemp[j] + s[kk][i]
            if sumtemp[j] > k:
                ok = False
                break
        if not ok : break
        for j in range(l):
            if suml[j]+sumtemp[j] > k:flag2 = False
        if flag2:
            for j in range(l):
                suml[j] = suml[j]+sumtemp[j]
        else:
            count += 1
            suml = sumtemp[:]   
    if not ok:continue
    ans = min(ans,count)
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import exit
from itertools import product
import numpy as np
HWK,*sss = open(0).read().splitlines()
H,W,K = map(int, HWK.split())
sss = [list(map(int, list(ss))) for ss in sss]
sss = np.cumsum(sss, axis=0)

if H == 1 or W == 1:
    print(0--sss[-1][-1]//K)
    exit()

ans = float('inf')
for flgs in product([False, True], repeat=H-1):
    cnt = sum(flgs)
    tsss = sss[[*flgs, True]]
    tsss = np.concatenate((tsss[:1], np.diff(tsss, axis=0)), axis=0).T

    tmp = 0
    for cur in tsss:
        new = tmp + cur
        if new.max() <= K:
            tmp = new
        else:
            cnt += 1
            if cur.max() > K:
                continue
            else:
                tmp = cur
#     print(flgs)
#     print(cnt, ans, tsss)
    ans = min(ans, cnt)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import exit
from itertools import product
import numpy as np
HWK,*sss = open(0).read().splitlines()
H,W,K = map(int, HWK.split())
sss = [list(map(int, list(ss))) for ss in sss]
sss = np.add.accumulate(sss)

if H == 1 or W == 1:
    print(0--sss[-1][-1]//K)
    exit()

ans = float('inf')
for flgs in product([0,1], repeat=H-1):
    cnt = 0
    hh = [h for h, flg in zip(range(H-1), flgs) if flg]
    cnt += len(hh)
    hh.append(-1)
    tsss = sss[hh]
    tsss = np.concatenate((tsss[:1], np.diff(tsss, axis=0)), axis=0)
    
    tmp = np.zeros(tsss.shape[0])
    for w in range(W):
        cur = tsss[:,w]
        new = tmp + cur
        if new.max() <= K:
            tmp = new
        else:
            cnt += 1
            if cur.max() > K:
                continue
            else:
                tmp = cur
#     print(cnt, ans, tsss)
    ans = min(ans, cnt)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
import copy
H,W,K = list(map(int, input().split()))
A = []
for i in range(H):
  A.append(list(map(int, input())))

#SM = [np.cumsum(A[i]) for i in range(H)]

ANS = []
for pat in product(['0','1'], repeat = H-1):
  res = []
  cnt = 0
  now = copy.copy(A[0])
  for i in range(1,H):
    p = pat[i-1]
    if p == '1':
      res.append(now)
      now = copy.copy(A[i])
      cnt += 1
    else:
      for j in range(W):
        now[j] += A[i][j]
  res.append(now)
  
  wk = [0 for _ in range(len(res))]
  for x in range(W):
    flg = True
    while flg:
      for j in range(len(res)):
        wk[j] += res[j][x]
      if max(wk) > K:
        cnt += 1
        flg = True
        wk = [0 for _ in range(len(res))]
      else:
        break
  ANS.append(cnt)
  
print(min(ANS))

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
import numpy as np
H,W,K = list(map(int, input().split()))
A = []
for i in range(H):
  A.append(np.array(list(map(int, input()))))

#SM = [np.cumsum(A[i]) for i in range(H)]

ANS = []
for pat in product(['0','1'], repeat = H-1):
  res = []
  cnt = 0
  now = np.copy(A[0])
  for i in range(1,H):
    p = pat[i-1]
    if p == '1':
      res.append(now)
      now = np.copy(A[i])
      cnt += 1
    else:
      now += A[i]
  res.append(now)
  
  wk = [0 for _ in range(len(res))]
  for x in range(W):
    flg = True
    while flg:
      for j in range(len(res)):
        wk[j] += res[j][x]
      if max(wk) > K:
        cnt += 1
        flg = True
        wk = [0 for _ in range(len(res))]
      else:
        break
  ANS.append(cnt)
  
print(min(ANS))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys 
import numpy as np
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
H, W, K = map(int, readline().split())
S = [readline().decode().rstrip() for _ in range(H)]
INF = 10**30
data = [[0]*W for _ in range(H)]
for i in range(H):
    cnt = 0 
    for j in range(W):
        if S[i][j] == '1':
            data[i][j] += 1
data = np.array(data)

ans_cnt = INF   
for bit_H in range(1 << (H-1)):
    cnt = 0
    ans = []
    new_data = []
    for i in range(H-1):
        if (bit_H >> i) & 1:
            ans.append(i)
    ans.append(H-1)
    tmp = [0]*W
    for i in range(H):
        tmp += data[i]
        if i in ans:
            new_data.append(tmp)
            tmp = [0]*W
    group = len(new_data)
    cnt += group-1
    white = [0] * group
    flag = True
    for i in range(W):
        diff = [0] * group
        for j in range(group):
            diff[j] += new_data[j][i]
            white[j] += new_data[j][i]
        max_diff = max(diff)
        if max_diff > K:
            flag = False
            break
        max_white = max(white)
        if max_white > K:
            cnt +=1
            white = diff[:]
    if flag:
        ans_cnt = min(ans_cnt,cnt)
print(ans_cnt)

Submission status: Time Limit Exceeded

Solution code:
h , w , k = map(int,input().split())
cho = [list(input()) for i in range(h)]
ans = 10**9
for i in range(2**(h-1)):
    cut = [0 for i in range(h)]
    for j in range(h-1):
        if i >> j & 1 == 1:
            cut[j+1] = cut[j]+1
        else:
            cut[j+1] = cut[j]
    maxcut = max(cut)+1
    cou = [0 for i in range(maxcut)]
    ccho = [[0 for i in range(w)] for j in range(maxcut)]
    for j in range(h):
        for l in range(w):
            ccho[cut[j]][l] += int(cho[j][l])
    tyu = maxcut - 1
    hukanou = False
    for j in range(w):
        flag = True
        for l in range(maxcut):
            if cou[l] + ccho[l][j] > k:
                flag = False
                break
        if flag:
            for l in range(maxcut):
                cou[l] += ccho[l][j]
        elif not flag:
            tyu += 1
            for l in range(maxcut):
                if ccho[l][j] > k:
                    hukanou = True
                    break
                cou[l] = ccho[l][j]
        if hukanou:
            break
    if hukanou:
        continue
    ans = min(ans,tyu)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys 
import numpy as np
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
H, W, K = map(int, readline().split())
S = [readline().decode().rstrip() for _ in range(H)]
INF = 10**30
data = [[0]*W for _ in range(H)]
for i in range(H):
    cnt = 0 
    for j in range(W):
        if S[i][j] == '1':
            cnt +=1
        data[i][j] = cnt
data = np.array(data)

ans_cnt = INF   
for bit_H in range(1 << (H-1)):
    cnt = 0
    ans = []
    new_data = []
    for i in range(H-1):
        if (bit_H >> i) & 1:
            ans.append(i)
    ans.append(H-1)
    tmp = [0]*W
    for i in range(H):
        tmp += data[i]
        if i in ans:
            new_data.append(tmp)
            tmp = [0]*W
    new_data = np.array(new_data)
    l = len(new_data)
    cnt += l-1
    for i in range(W):
        max_cnt = new_data.max(axis=0)[i]
        if max_cnt > K and i >=1:
            cnt +=1
            for j in range(l):
                new_data[j] -= new_data[j][i-1]
        max_cnt = new_data.max(axis=0)[i]
        if max_cnt > K:
            cnt = INF
            break 
    ans_cnt = min(ans_cnt,cnt)
print(ans_cnt)

Submission status: Time Limit Exceeded

Solution code:
H, W, K = map(int, input().split())
S = []
for _ in range(H):
  S.append(input())
hsummation = [[int(S[0][k])]for k in range(W)]
for k in range(W):
  for j in range(1, H):
    hsummation[k].append(hsummation[k][j-1] + int(S[j][k]))

ans = float('inf')
anskouho = 0
h = -1
binhh = []
for j in range(2**(H-1)):
  h += 1
  binh = "0"*(H-len(str(bin(h)))+1)+str(bin(h))[2:]
  c = 0
  for k in range(len(binh)):
    if binh[k] == '1':
      c += 1
  binhh.append([binh, c])
binhh.sort(key = lambda x:x[1]) #, reverse= True)

for j in range(2**(H-1)):
  hlist=[]
  for k in range(H-1):
    if binhh[j][0][k] == '1':
      hlist.append(k)
  hlist.append(-1)
  anskouho = len(hlist)-1
  now = 0
  while now < W:
    counter = [0 for _ in range(len(hlist))]
    while now < W:
      counter[0] += hsummation[now][hlist[0]]
      if counter[0] > K:
        anskouho += 1
        break
      for l in range(1, len(hlist)):
        counter[l] += - hsummation[now][hlist[l-1]] + hsummation[now][hlist[l]]
        if counter[l] > K:
          anskouho += 1
          break
      else:
        now += 1
        continue
      break
    if anskouho > ans:
      break
  else:
    ans = anskouho
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W, K = map(int, input().split())
S = []
for _ in range(H):
  S.append(input())
hsummation = [[int(S[0][k])]for k in range(W)]
for k in range(W):
  for j in range(1, H):
    hsummation[k].append(hsummation[k][j-1] + int(S[j][k]))
#print(hsummation)
ans = float('inf')
anskouho = 0
h = -1
for j in range(2**(H-1)):
  h += 1
  binh = "0"*(H-len(str(bin(h)))+1)+str(bin(h))[2:]
  hlist=[]
  for k in range(H-1):
    if binh[-k-1] == '1':
      hlist.append(k)
  hlist.append(-1)
  #print(hlist)
  anskouho = len(hlist)-1
  if anskouho > ans:
    break
  now = 0
  while now < W:
    counter = [0 for _ in range(len(hlist))]
    while now < W:
      for l in range(len(hlist)):
        if l == 0:
          counter[l] += hsummation[now][int(hlist[l])]
          continue
        else:
          counter[l] += - hsummation[now][hlist[l-1]] + hsummation[now][hlist[l]]
      if max(counter) > K:
        anskouho += 1
        break
      else:
        now += 1
    if anskouho > ans:
      break
  else:
    ans = min(ans, anskouho)
 
      #print(counter)
#print(anskouho)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W, K = map(int, input().split())
S = []
for _ in range(H):
  S.append(input())
hsummation = [[int(S[0][k])]for k in range(W)]
for k in range(W):
  for j in range(1, H):
    hsummation[k].append(hsummation[k][j-1] + int(S[j][k]))
#print(hsummation)
ans = float('inf')
anskouho = 0
h = -1
for j in range(2**(H-1)):
  h += 1
  binh = "0"*(H-len(str(bin(h)))+1)+str(bin(h))[2:]
  hlist=[]
  for k in range(H-1):
    if binh[-k-1] == '1':
      hlist.append(k)
  hlist.append(-1)
  #print(hlist)
  anskouho = len(hlist)-1
  now = 0
  while now < W:
    counter = [0 for _ in range(len(hlist))]
    while now < W:
      for l in range(len(hlist)):
        if l == 0:
          counter[l] += hsummation[now][int(hlist[l])]
          continue
        else:
          counter[l] += - hsummation[now][hlist[l-1]] + hsummation[now][hlist[l]]
      if max(counter) > K:
        anskouho += 1
        break
      else:
        now += 1
    if anskouho > ans:
      break
  else:
    ans = min(ans, anskouho)

      #print(counter)
#print(anskouho)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W, K = map(int, input().split())
S = []
for _ in range(H):
  S.append(input())
ans = 0
hsummation = [[int(S[0][k])]for k in range(W)]
for k in range(W):
  for j in range(1, H):
    hsummation[k].append(hsummation[k][j-1] + int(S[j][k]))
#print(hsummation)
anskouho = [0 for _ in range(2**(H-1))]
h = -1
for j in range(2**(H-1)):
  h += 1
  binh = "0"*(H-len(str(bin(h)))+1)+str(bin(h))[2:]
  hlist=[]
  for k in range(H-1):
    if binh[-k-1] == '1':
      hlist.append(k)
  hlist.append(-1)
  #print(hlist)
  anskouho[j] = len(hlist)-1
  now = 0
  s = 0
  while now < W:
    counter = [0 for _ in range(len(hlist))]
    while now < W:
      for l in range(len(hlist)):
        if l == 0:
          counter[l] += hsummation[now][int(hlist[l])]
          continue
        else:
          counter[l] += - hsummation[now][hlist[l-1]] + hsummation[now][hlist[l]]
      if max(counter) > K:
        s += 1
        break
      else:
        now += 1
      #print(counter)
  anskouho[j] = anskouho[j] + s
#print(anskouho)
print(min(anskouho))

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numpy as np
H, W, K = [int(_) for _ in input().split()]
S = np.array(
    [[0] * (W + 1)] + [[0] + list(map(int, input())) for _ in range(H)],
    dtype=np.int64)
cum = S.cumsum(axis=0).cumsum(axis=1)
ans = 10**10
for h in range(H):
    for c in itertools.combinations(range(1, H), h):
        I = np.array([0] + list(c) + [H], dtype=int)
        cum2 = np.diff(cum[I, :], axis=0)
        j = 0
        i = 0
        cnt = h
        while True:
            i += 1
            if i > W:
                break
            if np.max(cum2[:, i] - cum2[:, j]) > K:
                j = i = i - 1
                cnt += 1
        ans = min(ans, cnt)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W, K = map(int, input().split())
S = [input() for _ in range(H)]
ans = 10**9
for bit in range((1 << (H-1))):
    vidx = []
    gok = True
    g = 0
    gid = [0] * H
    for i in range(H-1):
        if (bit >> i) & 1:
            g += 1
        gid[i+1] = g
    g += 1
    gnum = [0]*g
    vertical = 0
    for w in range(W):
        ok = True
        one = [0]*g
        for h in range(H):
            one[gid[h]] += int(S[h][w])
            gnum[gid[h]] += int(S[h][w])
            if one[gid[h]] > K:
                gok = False
            if gnum[gid[h]] > K:
                ok = False
        if not ok:
            vertical += 1
            vidx.append(w)
            gnum = one

    # if bit == 2:
    #    print('aaaaa')
    #    print(gid)
    #    print(vidx)
    #    print(bin(bit), g-1, vertical)
    #    print('aaaaa')
    if gok:
        if ans > g-1 + vertical:
            ans = g-1 + vertical
            # print(bin(bit), g-1, vertical)
            # print(vidx)
            # print(ans)
        # ans = min(ans, g-1 + vertical)
if ans == 10**9:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import itertools
H, W, K = [int(_) for _ in input().split()]
S = np.zeros((H + 1, W + 1), dtype=int)
S[1:, 1:] = [[int(_) for _ in input()] for _ in range(H)]
cum = S.cumsum(axis=0).cumsum(axis=1)
#sum(a,b -> x,y) (1-indexed)
#cum[x][y]+cum[a-1][b-1]-cum[a-1][y]-cum[x][b-1]
ans = 10**10
for bs in itertools.product([True, False], repeat=H - 1):
    bs = [True] + list(bs) + [True]
    idxs = []
    for i, b in enumerate(bs):
        if b:
            idxs += [i]
    cum2 = np.array([cum[i2] - cum[i1] for i1, i2 in zip(idxs, idxs[1:])])
    i = 0
    cnt = sum(bs) - 3
    while i < W:
        i += min(
            np.searchsorted(c[i + 1:] - c[i], K, side='right') for c in cum2)
        cnt += 1
    ans = min(ans, cnt)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from collections import deque
from functools import lru_cache
import bisect
import re
import queue
import decimal


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [Scanner.string() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [Scanner.int() for i in range(n)]


def solve():
    H, W, K = Scanner.map_int()
    S = Scanner.string_list(H)
    ans = int(1e15)
    for i in range(1 << (H - 1)):
        cut = 0
        whites = [[0 for _ in range(W)] for _ in range(H)]
        for j in range(H - 1):
            for w in range(W):
                whites[cut][w] += S[j][w] == '1'
            if i >> j & 1:
                cut += 1
        for w in range(W):
            whites[cut][w] += S[-1][w] == '1'
        flag = True
        for line in whites:
            for cnt in line:
                if cnt > K:
                    flag = False
        if not flag:
            continue
        cnt = [0 for _ in range(H)]
        for w in range(W):
            flag = True
            for j in range(H):
                if cnt[j] + whites[j][w] > K:
                    flag = False
            if not flag:
                cnt = [0 for _ in range(H)]
                cut += 1
            for j in range(H):
                cnt[j] += whites[j][w]
        ans = min(ans, cut)
    print(ans)


def main():
    # sys.setrecursionlimit(1000000)
    # sys.stdin = open("sample.txt")
    # T = Scanner.int()
    # for _ in range(T):
    #     solve()
    # print('YNeos'[not solve()::2])
    solve()


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from numba import njit, i8, void
    import numpy as np
    h, w, K = map(int, input().split())
    grid = np.array([list(map(int, list(input())))
                     for _ in [0]*h], dtype=np.int16)
    m = 10**9
    for i in range(2**(h-1)):
        i = (("0"*h)+bin(i)[2:])[-h:]
        memo = [0]+[j for j in range(1, h) if i[j-1] != i[j]]+[h]
        ans = len(memo)-1
        memo = np.array(memo, dtype=np.int64)
        @njit(cache=True)
        def a(memo):
            j = 0
            flag = False
            memo2 = np.zeros(len(memo)-1, dtype=np.int64)
            ans2 = [0]
            while j < w:
                if flag:
                    break
                p, l = memo[0], ans2[-1]
                for k, q in enumerate(memo[1:ans+1]):
                    memo2[k] += np.sum(grid[p:q, j])
                    p = q
                    if memo2[k] > K:
                        ans2.append(j)
                        memo2 = np.zeros(ans, dtype=np.int64)
                        if j == l:
                            flag = True
                        l = j
                        break
                else:
                    j += 1
            if not flag:
                return len(ans2)
            else:
                return 10**8
        m = min(m, ans+(a(memo)-2))
    print(m)


main()