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:
import numpy as np
h, w, k = map(int, input().split())
s = []
for _ in range(h):
    s.append(list(map(int, list(input()))))
s = np.array(s)

def count(li):
    if np.max(li) > k:
        return -1
    tmp = np.zeros(len(li), dtype=int)
    cnt = 0
    for i in range(w):
        tmp += li[:, i]
        if np.max(tmp) > k:
            cnt += 1
            tmp = li[:, i]
    return cnt

ans = 1000000
for i in range(2**(h-1)):
    r = 0
    l = []
    for j in range(h-1):
        if (i>>j)&1:
            l.append(np.sum(s[r:j+1, :], axis=0))
            r = j+1
    l.append(np.sum(s[r:, :], axis=0))
    cnt = count(np.vstack(l))
    if cnt>=0:
        ans = min(ans, cnt+len(l)-1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import string
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
from bisect import bisect, bisect_left, bisect_right
import numpy as np

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)

H, W, K = map(int, input().split())
S = [list(map(int, list(input()))) for _ in range(H)]
ans = INF
for i in range(2 ** (H - 1)):
    p = deque()
    for j in range(H - 1):
        if (i >> j) & 1:
            p.append(j + 1)
    num = len(p)
    if len(p) == 0:
        check = 0
        for j in range(W):
            temp_sum = sum([S[l][j] for l in range(H)])
            if check + temp_sum > K:
                check = temp_sum
                num += 1
            else:
                check += temp_sum
    else:
        p.appendleft(0)
        p.append(H)
        check = [0] * (len(p) - 1)
        for j in range(W):
            for l in range(len(p)-1):
                if p[l+1] - p[l] == 1:
                    check[l] += S[l][j]
                else:
                    check[l] += sum([S[t][j] for t in range(p[l], p[l+1])])
            for l in check:
                if l > K:
                    num += 1
                    for l in range(len(p) - 1):
                        if p[l + 1] - p[l] == 1:
                            check[l] = S[l][j]
                        else:
                            check[l] = sum([S[t][j] for t in range(p[l], p[l + 1])])
                    break
    if num < ans:
        ans = num
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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


def solve(blocks):
    n_vert_cut = 0
    n_block = len(blocks)
    vals = [0 for _ in range(n_block)]

    for c in range(W):
        adds = [block[c] for block in blocks]
        if any(add > K for add in adds):
            return H * W

        sums = [val + add for val, add in zip(vals, adds)]
        if any(x > K for x in sums):
            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):
    mask = [1] + list(mask) + [1]
    pivots = [r for r in range(H + 1) if mask[r]]
    blocks = [A[p1:p2] for p1, p2 in zip(pivots[:-1], pivots[1:])]
    blocks = [[sum(row[c] for row in block) for c in range(W)] for block in blocks]
    # print(blocks, '->', solve(blocks))
    ans = min(ans, solve(blocks))
print(ans)

Submission status: Time Limit Exceeded

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]+a[w]
      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: Time Limit Exceeded

Solution code:
# coding: utf-8
import itertools

h, w, k = map(int, raw_input().split())
g = [raw_input() for i in xrange(h)]

#for gi in g: print gi
def testit(kx):
    #print 'test kx=', kx

    if kx == 0:
        return sum(r.count('1') for r in g) <= k

    hr = min(h - 1, kx)
    for hi in xrange(hr):
        #print 'hi=',hi
        ln_hs = list(itertools.combinations(range(1, h), hi))
        #ln_hs = [0] + ln_hs + [h]
        #print ln_hs
        #print hi
        #print kx - hi
        ln_ws = list(itertools.combinations(range(1, w), kx - hi))
        #ln_ws = [0] + ln_ws + [w]
        #print ln_ws

        for ln_h in ln_hs:
            ln_h = [0] + list(ln_h) + [h]
            for ln_w in ln_ws:
                ln_w = [0] + list(ln_w) + [w]

                #print '**TEST',ln_h, ln_w
                isok = True
                for h0, h1 in zip(ln_h, ln_h[1:]):
                    for w0, w1 in zip(ln_w, ln_w[1:]):
                        #print h0, h1, w0, w1
                        #print [row[w0:w1] for row in g[h0:h1]]

                        # 各セグメントに含まれる個数がk以下か
                        s = sum(row[w0:w1].count('1') for row in g[h0:h1])
                        #print 'segment count',s

                        if s > k:
                            # NG
                            #print 'NG'
                            isok = False
                            break
                    
                    if not isok:
                        break

                if isok:
                    # OK
                    #print '=>OK'
                    return True

    #print '=>NG ALL'
    return False

def main():
    rht = (h-1) + (w-1)
    lft = 0
    while lft < rht:
        kx = lft + (rht - lft) // 2
        cond = testit(kx)
        if cond:
            #print 'update rht',kx
            rht = kx
        else:
            #print 'update lft',kx+1
            lft = kx + 1
        
        #print 'step',lft,rht
    print lft

main()

Submission status: Time Limit Exceeded

Solution code:
h, w, k = map(int, input().split())
s = []
for i in range(h):
    s.append(list(map(int, list(input()))))
mini = 1010
for i in range(1<<(h-1)):
# for i in [0]:
    bit = (i<<1) | (1<<h) | (1)
    # print(bin(bit))
    h_cut = []
    for j in range(h+1):
        if (bit>>j) & 1 == 1:
            h_cut.append(j)
    l_cut = [0, 1]
    j = 0
    while True:
        flug = True
        left = l_cut[j]
        right = l_cut[j+1]
        for l in range(len(h_cut)-1):
            high = h_cut[l+1]
            low = h_cut[l]
            cnt = 0
            for x in range(left, right):
                for y in range(low, high):
                    if s[y][x] == 1:
                        cnt += 1
            if cnt > k:
                flug = False
                break
        if flug:
            if right >= w:
                break
            else:
                l_cut[j+1] += 1
        else:
            # if right >= w:
            #     break
            l_cut.append(l_cut[j+1])
            l_cut[j+1] -= 1
            j += 1
        # print(h_cut, j, left, right, flug, l_cut)
    cnt_cut = len(h_cut) + len(l_cut) - 4
    mini = min(mini, cnt_cut)
print(mini)

Submission status: Time Limit Exceeded

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

def count(li):
    if np.max(li) > k:
        return -1
    tmp = np.zeros(len(li))
    cnt = 0
    for i in range(w):
        tmp += li[:, i]
        if np.max(tmp) > k:
            cnt += 1
            tmp = li[:, i]
    return cnt

ans = 1000000
for i in range(2**(h-1)):
    r = 0
    l = []
    for j in range(h-1):
        if (i>>j)&1:
            l.append(np.sum(s[r:j+1, :], axis=0))
            r = j+1
    l.append(np.sum(s[r:, :], axis=0))
    cnt = count(np.vstack(l))
    if cnt>=0:
        ans = min(ans, cnt+len(l)-1)
print(ans)

Submission status: Time Limit Exceeded

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
      else:
        l[x]=y
  ans = min(ans,t_a)
    
print(ans)

Submission status: Time Limit Exceeded

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] = l[x]+a[w]
      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: Time Limit Exceeded

Solution code:
# coding: utf-8
import numpy as np


def solve(*args: str) -> str:
    h, w, k = map(int, args[0].split())
    white = np.array([[n for n in map(int, S)] for S in args[1:]])

    ret = h*w
    for b in range(2**(h-1)):
        y_end = [i+1 for i in range(h-1) if (b >> i) & 1 == 1]
        count = len(y_end)
        A = np.array(tuple(x.sum(axis=0) for x in np.vsplit(white, y_end)))
        S = np.zeros((1, len(A)), dtype=int)
        for x in range(w):
            S += A[:, x]
            if (k < S).any():
                S = A[:, x]
                count += 1

        ret = min(ret, count)

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Time Limit Exceeded

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)):
    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)
                cnt=0
        for j in range(len(C)):
            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: Time Limit Exceeded

Solution code:
import numpy as np
import itertools

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

ans = 2000
for t in itertools.product([0, 1], repeat=H - 1):
    cut = t.count(1)
    lst = np.zeros((cut + 1, W), dtype=np.int)
    lst[0] += S[0]
    c = 0
    for h in range(H - 1):
        if t[h]:
            c += 1
        lst[c] += S[h + 1]
    L = len(lst)
    sum_lst = np.zeros(L)
    for w in range(W):
        lst_w = lst[:, w]
        if lst_w.max() > K:
            break

        lst_s = sum_lst + lst_w
        if lst_s.max() > K:
            cut += 1
            sum_lst = lst_w
        else:
            sum_lst = lst_s
    else:
        ans = min(ans, cut)
print(ans)

Submission status: Time Limit Exceeded

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

def count(li):
    hh = len(li)
    tmp = [0]*hh
    cnt = 0
    for i in range(w):
        for j in range(hh):
            if li[j, i]>k:
                return -1
            if tmp[j]+li[j, i]>k:
                cnt += 1
                for x in range(hh):
                    tmp[x] = li[x, i]
                break
            tmp[j] += li[j, i]
    return cnt

ans = 1000000
for i in range(2**(h-1)):
    r = 0
    l = []
    for j in range(h-1):
        if (i>>j)&1:
            l.append(np.sum(s[r:j+1, :], axis=0))
            r = j+1
    l.append(np.sum(s[r:, :], axis=0))
    cnt = count(np.vstack(l))
    if cnt>=0:
        ans = min(ans, cnt+len(l)-1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
  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
    l = [0]*len(p)
    for w in range(W):
      for x,a in enumerate(p):
        l[x]+=a[w]
        if l[x]>K:
          t_a+=1
          l = [0]*len(p)
          for z,b in enumerate(p):
            l[z] = b[w]
          break
    ans = min(ans,t_a)

  print(ans)
  
main()

Submission status: Time Limit Exceeded

Solution code:
import copy
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)):
    now=0
    S1=copy.copy(S)
    cnt=0
    T=[]
    y=0
    for j in range(h-1):
        if (i>>j)&1:
            y+=1
    C=[0]*(y+1)
    for x in range(w):
        T=[]
        for j in range(h):        
            cnt+=S1[j]&1
            S1[j]=S1[j]>>1
            if (i>>j)&1: #横の区切り判定
                T.append(cnt)
                cnt=0
            if j==h-1:
                T.append(cnt)
                cnt=0
        for j in range(len(C)):
            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: Time Limit Exceeded

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
  l = [0]*len(p)
  for w in range(W):
    for x,a in enumerate(p):
      l[x]+=a[w]
      if l[x]>K:
        t_a+=1
        l = [0]*len(p)
        for z,b in enumerate(p):
          l[z] = b[w]
        break
  ans = min(ans,t_a)
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from itertools import product

H,W,K=map(int,input().split(' '))
arr = np.vstack([[int(i) for i in input()] for j in range(H)])
ans = H+W-2
for p in product([0,1],repeat=H-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(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from itertools import product

H,W,K=map(int,input().split(' '))
arr = np.vstack([[int(i) for i in input()] for j in range(H)])
ans = H+W-2
for p in product([0,1],repeat=H-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]
    ans = min(cut_cnt,ans)
print(ans)

Submission status: Time Limit Exceeded

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

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()
  for a in range(len(q)-1):
    p.append(cum[q[a+1]]-cum[q[a]])
  
  t_a = len(q)-2
  l = [0]*len(p)
  judge = False
  for w in range(W):
    for x,a in enumerate(p):
      y = a[w]
      if y>K:
        judge = True
        break
      else:
        l[x]+=y
        if l[x]>K:
          t_a+=1
          l = [0]*len(p)
          for z,b in enumerate(p):
            l[z] = b[w]
          break
    if judge:
      break
  if judge:
    continue
  else:
    ans = min(ans,t_a)
    
print(ans)

Submission status: Time Limit Exceeded

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, [H])):
        result.append(Sss[s:e])
    return result


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


def v_end(Ssss, start, K):
    return min(map(lambda Sss: _v_end(Sss, start, K), Ssss))


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


h_cands = list(range(1, H))
ans = -1
for n in range(len(h_cands) + 1):
    for comb in combinations(h_cands, n):
        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: Time Limit Exceeded

Solution code:
import numpy as np

def main():
    h, w, k = map(int, input().split())
    s = np.array([[int(i) for i in list(input())] for _ in range(h)])
    cnt = [bin(i).count("1") for i in range(2**(h - 1))]
    for i in range(2**(h - 1)):
        ss = np.split(s, [j + 1 for j in range(h - 1) if i & 2**j])
        stack = np.zeros(cnt[i] + 1, dtype=int)
        for j in range(w):
            sm = [st.T[j].sum() for st in ss]
            if max(sm) > k:
                cnt[i] = 100000
                break
            for t, st in enumerate(sm):
                stack[t] += st
            if max(stack) > k:
                for t, st in enumerate(sm):
                    stack[t] = st
                cnt[i] += 1
    print(min(cnt))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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):
    return min(map(lambda Sss: _v_end(Sss, start, K), Ssss))


def v_div_count(Ssss, K):
    start, result = 0, 0
    while True:
        end = v_end(Ssss, start, K)
        if end < start:
            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):
        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: Time Limit Exceeded

Solution code:
import sys
import math
import string
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
from bisect import bisect, bisect_left, bisect_right
import numpy as np

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)

H, W, K = map(int, input().split())
S = [list(map(int, list(input()))) for _ in range(H)]
ans = INF
for i in range(2 ** (H - 1)):
    num = 0
    p = [0]
    S_part = []
    for j in range(H - 1):
        if (i >> j) & 1:
            if j + 1 - p[-1] > 1:
                S_part.append(S[p[-1]:j + 1])
            else:
                temp_S_part = S[p[-1]:j + 1]
                temp_S_part = np.insert(temp_S_part, 1, np.zeros(W), axis=0)
                S_part.append(temp_S_part)
            p.append(j + 1)
    if p[-1] != H:
        temp_S_part = S[p[-1]:H]
        temp_S_part = np.insert(temp_S_part, 1, np.zeros(W), axis=0)
        S_part.append(temp_S_part)
    num = len(S_part) - 1
    if len(S_part) == 1:
        S_part.append(np.zeros((2, W)))
    for j in range(len(S_part)):
        S_part[j] = np.cumsum(S_part[j], axis=0)
    check = [0] * (len(S_part))
    for j in range(W):
        for l in range(len(S_part)):
            check[l] += S_part[l][-1][j]
        for l in range(len(S_part)):
            if check[l] > K:
                if j == 0:
                    num += INF
                check = [S_part[l][-1][j] for l in range(len(S_part))]
                num += 1
                break
    if ans > num:
        ans = num
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
import numpy as np

def main():
    h,w,k = tuple([int(t)for t in input().split()])

    s = [[int(i) for i in list(input())] for _ in range(h)]
    
    cusum = [accumelist(s_) for s_ in s]

    candidates = []

    for i in range(1<<(h-1)):
        subcu = divide(cusum,i)
        subcusum = []
        for sub_ in subcu:
            subcusum.append(np.sum(np.array(sub_),axis=0))

        subcusum = np.array(subcusum)

        cutnum = 0
        j=0
        temp = 0
        for j in range(w):
            subsum = subcusum[:,j]-temp
            if np.any(subsum>k):
                temp = subcusum[:,j-1]
                cutnum+=1
        
        candidates.append(cutnum+bin(i).count('1'))

    print(min(candidates))
            
def divide(s,i):
    subs = []
    counter = 0
    pos = 0
    while i!= 0:
        counter +=1
        if i%2==1:
            subs.append(s[pos:counter])
            pos = counter
        i >>=1
 
    subs.append(s[pos:])
    return subs

def accumelist(s):
    if s == []:
        return []
    res = [s[0]]
    for i in range(1,len(s)):
        res.append(res[i-1]+s[i])

    return res
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import string
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
from bisect import bisect, bisect_left, bisect_right
import numpy as np

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)

H, W, K = map(int, input().split())
S = [list(map(int, list(input()))) for _ in range(H)]
ans = INF
for i in range(2 ** (H - 1)):
    num = 0
    p = [0]
    S_part = []
    for j in range(H - 1):
        if (i >> j) & 1:
            if j + 1 - p[-1] > 1:
                S_part.append(S[p[-1]:j + 1])
            else:
                temp_S_part = S[p[-1]:j + 1]
                temp_S_part = np.insert(temp_S_part, 1, np.zeros(W), axis=0)
                S_part.append(temp_S_part)
            p.append(j + 1)
    if p[-1] != H:
        temp_S_part = S[p[-1]:H]
        temp_S_part = np.insert(temp_S_part, 1, np.zeros(W), axis=0)
        S_part.append(temp_S_part)
    num = len(S_part) - 1
    if len(S_part) == 1:
        S_part.append(np.zeros((2, W)))
    for j in range(len(S_part)):
        S_part[j] = np.cumsum(S_part[j], axis=0)
    check = [0] * (len(S_part))
    for j in range(W):
        for l in range(len(S_part)):
            check[l] += S_part[l][-1][j]
        for l in range(len(S_part)):
            if check[l] > K:
                if j == 0:
                    num += INF
                check = [0] * (len(S_part))
                num += 1
                for l in range(len(S_part)):
                    check[l] += S_part[l][-1][j]
                break
    if ans > num:
        ans = num
print(ans)

Submission status: Time Limit Exceeded

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 = [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 = [0]*len(p)
          for z,b in enumerate(p):
            l[z] = np.sum(b[:,w])
          break
    if judge:
      break
  if judge:
    continue
  else:
    ans = min(ans,t_a)
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import itertools

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

ans = 2000
for t in itertools.product([0, 1], repeat=H - 1):
    cut = t.count(1)
    lst = np.zeros((cut + 1, W), dtype=np.int)
    lst[0] += S[0]
    c = 0
    for h in range(H - 1):
        if t[h]:
            c += 1
        lst[c] += S[h + 1]
    L = len(lst)
    sum_lst = np.zeros(L)
    for w in range(W):
        lst_w = lst[:, w]
        if lst_w.max() > K:
            break

        lst_s = sum_lst + lst_w
        if lst_s.max() > K:
            cut += 1
            sum_lst = lst_w
        else:
            sum_lst = lst_s
    else:
        ans = min(ans, cut)
print(ans)