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:
# 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:]])
    if white.sum() < k:
        return '0'

    ret = h*w
    for b in range(2**(h-1)):
        px = 0
        hcuts = [i for i in range(h-1) if (b >> i) & 1 == 1]+[h]
        count = len(hcuts)-1
        for x in range(w):
            py = 0
            for y in hcuts:
                if k < white[py:y+1, px:x+1].sum():
                    count += 1
                    px = x
                    break
                py = y+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(0,H)]
for i in range(0,H):
    S[i]=input()

ans=10**4
for i in range(0,2**(H-1)):
    segment=[]
    start=0
    end=0
    for j in range(0,H-1):
        if (i>>j) & 1==1:
            end=j
            segment.append((start,end))
            start=end+1
    segment.append((start,H-1))
    white=[0 for j in range(0,len(segment))]
    count=0
    for j in range(0,W):
        for k in range(0,len(segment)):
            start,end=segment[k]
            white[k]+=sum((int(S[r][j])&1) for r in range(start,end+1))
        if max(white)>K:
            count+=1
            for k in range(0,len(segment)):
                start,end=segment[k]
                white[k]=sum((int(S[r][j])&1) for r in range(start,end+1))
            if max(white)>K:
                break
    else:
        test=count+len(segment)-1
        if test<ans:
            ans=test

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8
import sys
import copy

sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = True

def index(a,b):
    return str(min(a,b)) + "," +  str(max(a, b))

def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]

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

    ans = 10000000

    for i in range(2 ** (H-1)):
        x = [0] * (bin(i).count('1') + 1)
        counter = 0
        for j in range(W):
            y = [0] * (bin(i).count('1') + 1)
            c = 0
            for k in range(H):
                y[c] += S[k][j]
                moji = bin(i)[2:].zfill(H-1) + "0"
                if moji[k] == '1':
                    c += 1

            change = False
            for xx in range(len(x)):
                if x[xx] + y[xx] > K:
                    change = True
                    break
            if change:
                counter += 1
                x = copy.copy(y)
            else:
                for xx in range(len(x)):
                    x[xx] += y[xx]


        ans = min(ans, counter + str(bin(i)).count('1'))

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

h,w,k = (int(x) for x in input().split())

s_list = np.array([[x for x in input()] for _ in range(h)])

cut_num = h + w - 2

def clear(c_list):
  c_w = [0]
  c_h = [0]
  for c in c_list:
    if c < w:
      c_w.append(c)
    else:
      c_h.append(c-w+1)
      
  c_w.append(w)
  c_h.append(h)
  flg = True
  for i in range(1,len(c_w)):
    for j in range(1,len(c_h)):
      field = s_list[c_h[j-1]:c_h[j],c_w[i-1]:c_w[i]]
      if np.count_nonzero(field=='1') > k:
        flg = False
        
  return flg
      
def cut(c_list,k):
  if k > cut_num:
    if clear(c_list):
      return len(c_list)
    else:
      return cut_num + 1
  
  if clear(c_list):
    return len(c_list)
    
  c_list.append(k)
  x = cut(c_list,k+1)

  c_list.remove(k)
  x = min(x,cut(c_list,k+1))
  
  return x

x = cut([],1)
print(x)

Submission status: Time Limit Exceeded

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

def cumsum(s):
    n = len(s)
    cs = [0] * (n+1)
    for i in range(n):
        cs[i+1] = cs[i] + s[i]
    return cs
cums = [cumsum(c) for c in s]
ans = float("inf")    

for i in range(2 ** (h-1)):
    seps = [(i >> j) & 1 for j in range(h-1)] + [1]
    c = [[0] * (w+1) for _ in range(sum(seps))]
    idx = 0
    for j in range(h):
        for k in range(w+1):
            c[idx][k] += cums[j][k]
        if seps[j]: idx += 1
    
    flg = False
    for j in range(len(c)):
        for k in range(w):
            if c[j][k+1]-c[j][k] > K:
                flg = True
    if flg: continue                

    res = 0
    left = 0
    for j in range(w-1):
        for cc in c:
            if cc[j+2] - cc[left] > K:
                break
        else: continue
        res += 1
        left = j+1
    
    ans = min(ans, res+sum(seps)-1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys
from itertools import accumulate
from bisect import bisect_right

def main():
    def input(): return sys.stdin.readline().strip()
    def list2d(a, b, c): return [[c] * b for i in range(a)]
    def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
    def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
    def ceil(x, y=1): return int(-(-x // y))
    def INT(): return int(input())
    def MAP(): return map(int, input().split())
    def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
    def Yes(): print('Yes')
    def No(): print('No')
    def YES(): print('YES')
    def NO(): print('NO')
    sys.setrecursionlimit(10 ** 9)
    INF = 10 ** 18
    MOD = 10 ** 9 + 7

    def build_grid(H, W, intv, _type, space=True, padding=False):
        # 入力がスペース区切りかどうか
        if space:
            _input = lambda: input().split()
        else:
            _input = lambda: input()
        _list = lambda: list(map(_type, _input()))
        # 余白の有無
        if padding:
            offset = 1
        else:
            offset = 0
        grid = list2d(H+offset*2, W+offset*2, intv)
        for i in range(offset, H+offset):
            row = _list()
            for j in range(offset, W+offset):
                grid[i][j] = row[j-offset]
        return grid

    def popcount(i):
        return bin(i).count('1')

    H, W, K = MAP()
    grid = build_grid(H, W, 0, int, space=0)

    ans = INF
    for S in range(1<<(H-1)):
        N = popcount(S) + 1
        A = list2d(N, W, 0)
        for w in range(W):
            A[0][w] = grid[0][w]
        h = 0
        for k in range(H-1):
            if S & 1<<k:
                h += 1
            for w in range(W):
                A[h][w] += grid[k+1][w]
        for i in range(N):
            A[i] = [0] + list(accumulate(A[i]))
        cnt = 0
        idx = 1
        while 1:
            nxt = INF
            for i in range(N):
                j = idx
                cur = K + A[i][idx-1]
                while j < W+1 and A[i][j] <= cur:
                    j += 1
                nxt = min(nxt, j)
                # nxt = min(nxt, bisect_right(A[i], K+A[i][idx-1], lo=idx))
            idx = nxt
            if idx == W+1:
                break
            cnt += 1
        ans = min(ans, N-1+cnt)
    print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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


min_cnt = H * W
for row_choice in range(2**(H-1)):
    S = np.copy(S_orig)
    row_splits = []
    for r in range(H-1):
        if (row_choice >> r) & 1:
            row_splits.append(r+1)
    splitted_rows = np.vsplit(S, row_splits)
    splitted_rows = np.array([np.sum(row, axis=0) for row in splitted_rows])
    splitted_rows_cum = np.hstack([np.zeros((splitted_rows.shape[0], 1), dtype=np.uint32), np.cumsum(splitted_rows, 1)])
    
    cnt = len(row_splits)
    start = 0
    for i in range(W+1):
        if (splitted_rows_cum[:, i] - splitted_rows_cum[:, start] > K).any():
        #if (splitted_rows[:, start: i].sum(axis=1) > K).any():
            start = i - 1
            cnt += 1
    min_cnt = min([cnt, min_cnt])
    
print(min_cnt)

Submission status: Time Limit Exceeded

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

# S = S.astype('bool')
S = S.reshape(H, W).astype('int')
# print('S')
# print(S)

l = [[0, 1] for _ in range(H - 1)]
ans = 10**10
for arr in product(*l):
    # arr = (0, 1)
    # print('arr', arr)
    cut = arr.count(1)
    subset = []
    arr = np.array(arr, dtype='bool')
    idx = np.arange(1, H)[arr]
    # print('idx', idx)
    if len(idx) == 0:
        subset = [S]
        # print('subset', subset)
    elif len(idx) == 1:
        subset.append(S[:idx[0], :])
        subset.append(S[idx[0]:, :])
        # print('subset', subset)
    else:
        subset.append(S[:idx[0], :])
        for i in range(len(idx) - 1):
            subset.append(S[idx[i]:idx[i + 1], :])
        subset.append(S[idx[-1]:, :])
    # print('subset', subset, len(subset))

    cumsum = []
    for i in range(len(subset)):
        tmp = [subset[i][:, :j].sum() for j in range(1, W + 1)]
        cumsum.append(tmp)
    cumsum = np.array(cumsum)
    # print('cumsum', cumsum)
    for i in range(1, W):
        # print(cumsum[:, i] > K)
        if np.any(cumsum[:, i] > K):
            cut += 1
            for j in range(cumsum.shape[0]):
                cumsum[j, :] -= cumsum[j, i - 1]
                # print('update cumsum', cumsum)
    # print('cut', cut)
    ans = min(ans, cut)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(700000)
from itertools import product

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

def print_l(l):
    print(' '.join(map(str, l)))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

h, w, k = l_in()
S = list(map(lambda _: s_in(), range(h)))

sums = [[0 for _ in range(w)] for _ in range(h)]

sums[0][0] = int(S[0][0])

for i in range(1, h):
    sums[i][0] = sums[i-1][0] + int(S[i][0])

for j in range(1, w):
    sums[0][j] = sums[0][j-1] + int(S[0][j])

for i in range(1, h):
    for j in range(1, w):
        sums[i][j] = sums[i][j-1] + sums[i-1][j] - sums[i-1][j-1] + int(S[i][j])

def sq(x1, x2, y1, y2):
    if x1 > 0 and y1 > 0:
        return -sums[x1-1][y2] - sums[x2][y1-1] + sums[x1-1][y1-1] + sums[x2][y2]
    if x1 > 0 and y1 == 0:
        return -sums[x1-1][y2] + sums[x2][y2]
    if x1 == 0 and y1 > 0:
        return -sums[x2][y1-1] + sums[x2][y2]
    if x1 == 0 and y1 == 0:
        return sums[x2][y2]

def exec(i, list):
    current = i
    while current < h:
        exec(current, )

        current += 1

res = h*w

# print(S)
# print(sums)

for ss in product('01', repeat=h-1):
    lis = []
    start = 0
    current = 0
    for s in ss:
        if s == '1':
            lis.append((start, current))
            start = current + 1
        current += 1
    lis.append((start, h-1))

    # print(lis)
    j1 = 0
    cut = 0
    for j2 in range(w-1):
        for i1, i2 in lis:
            if sq(i1, i2, j1, j2) <= k and sq(i1, i2, j1, j2+1) > k:
                # print("cut", j1, j2)
                cut += 1
                j1 = j2+1


    # for i1, i2 in lis:
    #     print(i1,i2,j1,w-1, sq(i1, i2, j1, w-1) <= k)
    # print(j1, all(sq(i1, i2, j1, w-1) <= k for i1, i2 in lis))
    if all(sq(i1, i2, j1, w-1) <= k for i1, i2 in lis):
        cut += 1
        res = min(res, cut-1+len(lis)-1)

print(res)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys
from itertools import accumulate
from bisect import bisect_right

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def build_grid(H, W, intv, _type, space=True, padding=False):
    # 入力がスペース区切りかどうか
    if space:
        _input = lambda: input().split()
    else:
        _input = lambda: input()
    _list = lambda: list(map(_type, _input()))
    # 余白の有無
    if padding:
        offset = 1
    else:
        offset = 0
    grid = list2d(H+offset*2, W+offset*2, intv)
    for i in range(offset, H+offset):
        row = _list()
        for j in range(offset, W+offset):
            grid[i][j] = row[j-offset]
    return grid

def popcount(i):
    return bin(i).count('1')

H, W, K = MAP()
grid = build_grid(H, W, 0, int, space=0)

ans = INF
for S in range(1<<(H-1)):

    N = popcount(S) + 1
    A = list2d(N, W, 0)
    for w in range(W):
        A[0][w] = grid[0][w]
    h = 0
    for k in range(H-1):
        if S & 1<<k:
            h += 1
        for w in range(W):
            A[h][w] += grid[k+1][w]
    for i in range(N):
        A[i] = [0] + list(accumulate(A[i]))
    cnt = 0
    idx = 1
    while 1:
        nxt = INF
        for i in range(N):
            j = idx
            cur = K + A[i][idx-1]
            while j < W+1 and A[i][j] <= cur:
                j += 1
            nxt = min(nxt, j)
            # nxt = min(nxt, bisect_right(A[i], K+A[i][idx-1], lo=idx))
        idx = nxt
        if idx == W+1:
            break
        cnt += 1
    ans = min(ans, N-1+cnt)
print(ans)

Submission status: Time Limit Exceeded

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

area = [input() for _ in range(H)]
ans = float('inf')
S = []
for w in range(W):
    s = [0, ]
    for h in range(H):
        if area[h][w] == '1':
            s.append(s[-1]+1)
        else:
            s.append(s[-1])
    S.append(s)

for i in range(1 << H-1):
    flag = False
    tmp_ans = 0

    tmp = 0
    flag1 = [False for _ in range(H)]
    flag1[-1] = True
    for j in range(H):
        if i >> j & 1 == 1:
            tmp_ans += 1
            flag1[j] = True
    T = tmp_ans+1
    counter = [0 for _ in range(T)]

    for w in range(W):
        tmp_counter = []
        before = 0
        for k, f in enumerate(flag1):
            if f:
                tmp_counter.append(S[w][k+1] - S[w][before])
                before = k+1
        
        for tmp in tmp_counter:
            if tmp > K:
                flag = True
        if flag:
            tmp_ans = float('inf')
            break

        for k, tmp in enumerate(tmp_counter):
            if counter[k]+tmp > K:
                tmp_ans += 1
                counter = tmp_counter
                break
            else:
                counter[k] += tmp
    ans = min(ans, tmp_ans)

print(ans)

Submission status: Time Limit Exceeded

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

ans=10**4
for i in range(0,2**(H-1)):
    segment=[]
    start=0
    end=0
    for j in range(0,H-1):
        if (i>>j) & 1==1:
            end=j
            segment.append((start,end))
            start=end+1
    segment.append((start,H-1))
    white=[0 for j in range(0,len(segment))]
    count=0
    for j in range(0,W):
        for k in range(0,len(segment)):
            start,end=segment[k]
            white[k]+=sum((int(S[r][j])&1) for r in range(start,end+1))
        if max(white)>K:
            count+=1
            for k in range(0,len(segment)):
                start,end=segment[k]
                white[k]=sum((int(S[r][j])&1) for r in range(start,end+1))
    test=count+len(segment)-1
    if test<ans:
        ans=test

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
#input = sys.stdin.buffer.readline
import numpy as np
 
def main():
    H,W,K = map(int,input().split())
    a = [input() for _ in range(H)]
    
    x = np.zeros((H,W+1),dtype=int)
    for i in range(H):
        for j in range(W):
            if a[i][j] == "1":
                x[i][j+1] = 1
            else:
                x[i][j+1] = 0

    ans = 10**5
    for i in range(1<<H-1):
        use = np.zeros((H,W+1),dtype=int)
        u,now,count = 0,0,0
        for j in range(H-1):
            if (i>>j)&1 == 1:
                count += 1
                bl = x[u:j+1,:]
                bl = np.sum(bl,axis=0)
                u = j+1
                use[now] = bl
                now += 1
        bl = np.sum(x[u:,:],axis=0)
        use[now] = bl
        r,vol = 1,np.zeros((1,H),dtype=int)
        while r<=W:
            f = use[:,r]
            vol += f
            if np.max(vol)>K:
                count += 1
                vol = f
            r += 1
        ans = min(ans,count)
        
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from itertools import combinations
import sys
input = sys.stdin.buffer.readline
H,W,K= map(int,input().split())
s = np.array([list(map(int,list(input().decode()[:-1]))) for i in range(H)]).astype(np.int32)

#s = np.array([list(map(int,list(input()))) for i in range(H)]).astype(np.int32)
#H,W,K = 10,1000,10000
#s = np.ones((10,1000)).astype(np.int32)

def solve():
    ans = 10 * 1000 + 100
    for i in range(H):
        for p in combinations(range(1,H),i):
            p = [0] + list(p) + [H]
            cand = np.array([np.sum(s[f:g],axis=0) for f,g in zip(p,p[1:])]).T

            if np.count_nonzero(cand > K):
               continue 

            temp = i
            cnt = np.zeros(i+1,dtype=np.int32)
            for c in cand:
                cnt += c
                #if np.count_nonzero(cnt > K):
                if (cnt > K).any():
                    temp += 1
                    if temp > ans:
                        break
                    cnt = c
            ans = min(temp,ans)
    return ans

#from time import time
#st = time()
print(solve())
#print(time() - st)

Submission status: Time Limit Exceeded

Solution code:
import math
import numpy as np
from itertools import combinations

def main():
    import sys
    H,W,K=list(map(int,sys.stdin.readline().split()))
    
    C=np.zeros((H,W))
    for i in range(H):
        C[i]=np.array(list(sys.stdin.readline().strip()))
    
    output=10**9

    cut=0
    cut_pos=0
    for j in range(1,W+1):
        if np.sum(C[:,cut_pos:j])>K:
            cut+=1
            if cut_pos==j-1:
                cut=10**9
                break
            cut_pos=j-1

    output=cut if cut<output else output
    
    if output<=1:
        print(output)
        return 


    for i in range(1,H):
        for cmb in combinations(list(range(1,H+1)),i):#横線の組み合わせ
            cut=0
            cut_pos=0
            cut+=len(cmb)
            for j in range(1,W+1):
                for k in range(len(cmb)):
                    if k==0:
                        if np.sum(C[:cmb[k],cut_pos:j])>K:
                            cut+=1
                            if cut_pos==j-1:
                                cut=10**9
                                break
                            cut_pos=j-1
                    else:
                        if np.sum(C[cmb[k-1]:cmb[k],cut_pos:j])>K:
                            cut+=1
                            if cut_pos==j-1:
                                cut=10**9
                                break

                            cut_pos=j-1

                    if cut>output:
                        break
                
                if np.sum(C[cmb[-1]:,cut_pos:j])>K:
                    cut+=1
                    cut_pos=j-1

                if cut>output:
                    break
            

            output=cut if cut<output else output


    print(output)



main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
H,W,K = map(int,input().split())
S = np.array([list(map(int,input())) for _ in range(H)], dtype=np.int64)
ans = float("inf")
for i in range(2**(H-1)):
    kari = 0
    l = np.array([0]*H, dtype=np.int64)
    if H > 1:
        for j in range(0,H-1):
            if i >> j & 1:
                l[j+1] = l[j]+1
                kari += 1
            else:
                l[j+1] = l[j]
    num = np.array([0]*H, dtype=np.int64)

    for w in range(W):
        tmp = np.array([0]*H, dtype=np.int64)
        for h in range(H):
            if S[h,w]:
                tmp[l[h]] += 1

        if np.max(tmp) > K:
            break
        if np.max(num+tmp) <= K:
            num += tmp
        else:
            num = tmp
            kari += 1
    else:

        ans = min(ans,kari)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
#input = sys.stdin.buffer.readline
import numpy as np
 
def main():
    H,W,K = map(int,input().split())
    a = [input() for _ in range(H)]
    
    x = np.zeros((H,W+1),dtype=int)
    for i in range(H):
        for j in range(W):
            if a[i][j] == "1":
                x[i][j+1] = 1
            else:
                x[i][j+1] = 0

    ans = 10**5
    for i in range(1<<H-1):
        use = np.zeros((H,W+1),dtype=int)
        u,now,count = 0,0,0
        for j in range(H-1):
            if (i>>j)&1 == 1:
                count += 1
                bl = x[u:j+1,:]
                bl = np.sum(bl,axis=0)
                u = j+1
                use[now] = bl
                now += 1
        bl = np.sum(x[u:,:],axis=0)
        use[now] = bl
        r,vol = 1,np.zeros((H,1),dtype=int)
        while r<=W:
            f = use[:,r].reshape(-1,1)
            vol += f
            if np.max(vol)>K:
                count += 1
                vol = f
            r += 1
        ans = min(ans,count)
        
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

ch = []
for __ in range(h):
    ch.append([_ for _ in input()])


def count_ones(sl_x, sl_y):
    sl_x = sorted(sl_x)
    sl_y = sorted(sl_y)
    max_ones = 0
    for y in range(len(sl_y)-1):
        for x in range(len(sl_x)-1):
            ones = 0
            for yy in range(sl_y[y],sl_y[y+1]):
                for xx in range(sl_x[x],sl_x[x+1]):
                    if ch[yy][xx] == '1':
                        ones+=1
            max_ones = max(ones,max_ones)
    if max_ones > k:
        return False
    return True


def slicer(sl_x,sl_y):
    if count_ones(sl_x,sl_y):
        sl_c = len(sl_x)+len(sl_y)-4
        return sl_c

    mins = 9999999
    for y in range(h):
        if y not in sl_y:
            mins = min(mins,slicer(sl_x,sl_y+[y]))
    for x in range(w):
        if x not in sl_x:
            mins = min(mins,slicer(sl_x+[x],sl_y))
    return mins


slx = [0,w]
sly = [0,h]

print(slicer(slx,sly))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys
from itertools import accumulate
from bisect import bisect_right

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def build_grid(H, W, intv, _type, space=True, padding=False):
    # 入力がスペース区切りかどうか
    if space:
        _input = lambda: input().split()
    else:
        _input = lambda: input()
    _list = lambda: list(map(_type, _input()))
    # 余白の有無
    if padding:
        offset = 1
    else:
        offset = 0
    grid = list2d(H+offset*2, W+offset*2, intv)
    for i in range(offset, H+offset):
        row = _list()
        for j in range(offset, W+offset):
            grid[i][j] = row[j-offset]
    return grid

def popcount(i):
    return bin(i).count('1')

H, W, K = MAP()
grid = build_grid(H, W, 0, int, space=0)


ans = INF
for S in range(1<<(H-1)):

    N = popcount(S) + 1
    A = list2d(N, W, 0)
    for w in range(W):
        A[0][w] = grid[0][w]
    h = 0
    for k in range(H-1):
        if S & 1<<k:
            h += 1
        for w in range(W):
            A[h][w] += grid[k+1][w]
    for i in range(N):
        A[i] = [0] + list(accumulate(A[i]))
    cnt = 0
    idx = 1
    while 1:
        nxt = INF
        for i in range(N):
            nxt = min(nxt, bisect_right(A[i], K+A[i][idx-1], lo=idx))
        idx = nxt
        if idx == W+1:
            break
        cnt += 1
    ans = min(ans, N-1+cnt)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input=sys.stdin.readline
    h,w,k=map(int,input().split())
    S=[]
    for _ in range(h):
        s=list(map(int,list(input().rstrip())))
        S.append(s)
    ans=10**5
    for i in range(2**(h-1)):
        l=[0]
        for j in range(h-1):
            if i&1<<j:
                l.append(l[-1]+1)
            else:
                l.append(l[-1]) 
        ans_=l[-1]
        ll=[0]*h
        j=0
        while j<w:
            for p in range(h):
                ll[l[p]]+=S[p][j]
            if max(ll)>k:
                ans_+=1
                ll=[0]*h
            else:
                j+=1
        ans=min(ans,ans_)
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from itertools import combinations
import sys
input = sys.stdin.buffer.readline
H,W,K= map(int,input().split())
s = np.array([list(map(int,list(input().decode()[:-1]))) for i in range(H)]).astype(np.int32)

#s = np.array([list(map(int,list(input()))) for i in range(H)]).astype(np.int32)
#H,W,K = 10,1000,10000
#s = np.ones((10,1000)).astype(np.int32)

def solve():
    ans = 10 * 1000 + 100
    for i in range(H):
        for p in combinations(range(1,H),i):
            p = [0] + list(p) + [H]
            cand = np.array([np.sum(s[f:g],axis=0) for f,g in zip(p,p[1:])]).T

            if np.count_nonzero(cand > K):
               continue 

            temp = i

            cnt = np.zeros(i+1,dtype=np.int32)
            for c in cand:
                #cnt += cand[w]
                cnt += c
                if np.count_nonzero(cnt > K):
                    temp += 1
                    if temp > ans:
                        break
                    #cnt = cand[w]
                    cnt = c
            ans = min(temp,ans)
    return ans

#from time import time
#st = time()
print(solve())
#print(time() - st)

Submission status: Time Limit Exceeded

Solution code:
def main():
    from itertools import product
    H, W, K = map(int, raw_input().split())
    G = [list(map(int, list(raw_input()))) for _ in range(H)]

    ans = float('inf')
    for pattern in product([0, 1], repeat=H-1):
        tmp_ans = 0
        div = [0] + [i for i, p in enumerate(pattern, start=1) if p == 1] + [100]
        grids = []
        for i in range(len(div) - 1):
            grids.append(G[div[i]: div[i + 1]])

        rows = []
        for grid in grids:
            row = []
            for w in range(W):
                v = 0
                for h in range(len(grid)):
                    v += grid[h][w]
                row.append(v)
            rows.append(row)

        w = 0
        counts = [0] * len(rows)
        while w < W:
            for i, row in enumerate(rows):
                counts[i] += row[w]
                if counts[i] > K:
                    tmp_ans += 1
                    counts = [0] * len(rows)
                    break
            else:
                w += 1

        tmp_ans += len(div) - 2
        ans = min(ans, tmp_ans)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input=sys.stdin.readline
    h,w,k=map(int,input().split())
    S=[]
    for _ in range(h):
        s=list(map(int,list(input().rstrip())))
        S.append(s)
    ans=10**5
    for i in range(2**(h-1)):
        l=[0]
        for j in range(h-1):
            if i&1<<j:
                l.append(l[-1]+1)
            else:
                l.append(l[-1]) 
        ans_=l[-1]
        ll=[0]*h
        j=0
        while j<w:
            flag=0
            for p in range(h):
                ll[l[p]]+=S[p][j]
                if ll[l[p]]>k:
                    flag=1
            if flag:
                ans_+=1
                ll=[0]*h
            else:
                j+=1
        ans=min(ans,ans_)
    print(ans)
if __name__ == '__main__':
    main()