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 itertools

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

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

print(ans)

Submission status: 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):
    cnt = t.count(1)
    lst = np.copy(S[0]).reshape(1, -1)
    for h in range(H - 1):
        if t[h]:
            lst = np.vstack([lst, S[h + 1]])
        else:
            lst[-1] = lst[-1] + 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:
            cnt += 1
            sum_lst = lst_w
        else:
            sum_lst = lst_s
    else:
        ans = min(ans, cnt)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]

import itertools
import numpy as np

res = 999999999999999999

H, W, K = [int(i) for i in input().split()]
arr = []
for h in range(H):
  arr.append([int(v) for v in input()])

arr = np.vstack(arr)

for p in itertools.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:
      sum_arr = sp[:, c]
      cut_cnt += 1
  if cut_cnt < res:
    res = cut_cnt
print(res)

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
  t_b = 0
  judge = False
  for w in range(1,W+1):
    for a in p:
      if np.sum(a[:,t_b:w])>K:
        if w-1==t_b:
          judge = True
          break
        else:
          t_a += 1
          t_b = w-1
          if np.sum(a[:,t_b:w])>K:
            judge = True
            break
    if judge:
      break
  if judge:
    continue
  else:
    ans = min(ans,t_a)
    
print(ans)

Submission status: Time Limit Exceeded

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

cum_s = [[0 for _ in range(w+1)] for _ in range(h)]
for i in range(1, w+1):
    for j in range (h):
        cum_s[j][i] += (s[j][i-1] == '1') + cum_s[j][i-1]
#print(cum_s)

ans = 10 ** 6
for i in range(2 ** (h-1)):
    sep = []
    tmp = [0]
    for j in range(h-1):
        if (i >> j) & 1:
            tmp.append(j+1)
        else:
            if tmp != []:
                sep.append(tmp)
            tmp = [j+1]
    sep.append(tmp)
    #print(sep)
    
    idx = 0
    cnt = 0
    for j in range(1,w+1):
        flg = False
        for l in sep:
            tmp_sum = sum([cum_s[x][j] - cum_s[x][idx] for x in l])
            if tmp_sum > k:
                if j - idx == 1:
                    cnt = 10 ** 6
                flg = True
        
        if flg:
            cnt += 1
            idx = j-1 
    #print(len(sep)-1, cnt)
    ans = min(ans, len(sep)-1 + cnt)

if w == 1:
    x = sum([s[i] == '1' for i in range(h)])
    print(max(0, -(-x // k)-1))
elif h == 1:
    x = sum([s[0][i] == '1' for i in range(w)])
    print(max(0, -(-x // k)-1))
else:
    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)]
    
    s = np.array(s)

    candidates = []

    for i in range(1<<h-1):
        s_subs = divide(s,i)
        cutnum = 0
        pos = 0
        subsum = np.array([0]*len(s_subs))
        j = 0
        while j<w:
            temp = np.array([np.sum(s_[:,j]) for s_ in s_subs])
            if any([s_>k for s_ in temp]):
                cutnum = -1-bin(i).count('1')
                break

            subsum = subsum+temp
            if any([s_>k for s_ in subsum]):
                cutnum+=1
                subsum = np.array([0]*len(s_subs))
                j-=1
            
            j+=1

        candidates.append((bin(i).count('1')+cutnum))

    print(min([t for t in candidates if t>=0]))

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
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


h, w, k = map(int, input().split())
white_count = [np.zeros(w+1, dtype=np.int64)]

for _ in range(h):
    line = list(map(int, list('0'+input())))
    count = np.cumsum(line)
    white_count.append(count + white_count[-1])

white_count = np.array(white_count)

ans = []
for pattern in range(2 ** (h-1)):
    dived_y = [0]
    for y in range(h-1):
        if (pattern >> y) & 1:
            dived_y.append(y + 1)
    dived_y.append(h)

    slash_count = len(dived_y) - 2
    pre_y = dived_y[:-1]
    ny = dived_y[1:]

    prev_x = 0
    for nx in range(1, w+1):
        pre_x_arr = white_count[:, prev_x]
        nx_arr = white_count[:, nx]
        whites = nx_arr[ny] - nx_arr[pre_y] - pre_x_arr[ny] + pre_x_arr[pre_y]
        white = whites.max()
        if white <= k:
            continue
        else:
            slash = nx - 1
            if slash == prev_x:
                break
            slash_count += 1
            prev_x = slash

    else:
        ans.append(slash_count)

print(min(ans))

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numpy as np

res = 999999999999999999

H, W, K = [int(i) for i in input().split()]
arr = np.zeros((H, W), int)
for h in range(H):
  for w, v in enumerate(input()):
  	arr[h, w] = int(v)

for p in itertools.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:
      sum_arr = sp[:, c]
      cut_cnt += 1
  if cut_cnt < res:
    res = cut_cnt
print(res)

Submission status: Time Limit Exceeded

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

s=[list(map(int,[x for x in input()])) for _ in range(h)]

cnt=10001

for i in range(2**(h-1)):
    split=[(i>>j)&1 for j in range(h)]

    curcnt=sum(split)
    nsplit=curcnt+1
    sumlst=[0]*(nsplit)
    
    cw=0
    while cw<w:
        l=0
        for ch in range(h):
            sumlst[l]+=s[ch][cw]

            if sumlst[l]>k:
                sumlst=[0]*(nsplit)
                curcnt+=1
                break

            if split[ch]:
                l+=1
        else:
            cw+=1
    
    cnt=min(cnt,curcnt)

print(cnt)

Submission status: Time Limit Exceeded

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

s=[list(map(int,[x for x in input()])) for _ in range(h)]

cnt=10001

for i in range(2**(h-1)):
    split=[(i>>j)&1 for j in range(h)]

    curcnt=sum(split)
    nsplit=curcnt+1
    sumlst=[0]*(nsplit)
    
    cw=0
    while cw<w:
        l=0
        for ch in range(h):
            sumlst[l]+=s[ch][cw]

            if sumlst[l]>k:
                sumlst=[0]*(nsplit)
                curcnt+=1
                break

            if split[ch]==1:
                l+=1
        else:
            cw+=1
    
    cnt=min(cnt,curcnt)

print(cnt)

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)]
    
    s = np.array(s)

    candidates = []

    for i in range(1<<h):
        s_subs = divide(s,i)
        cutnum = 0
        pos = 0
        subsum = np.array([0]*len(s_subs))
        j = 0
        while j<w:
            temp = np.array([np.sum(s_[:,j]) for s_ in s_subs])
            if any([s_>k for s_ in temp]):
                cutnum = -1-bin(i).count('1')
                break

            subsum = subsum+temp
            if any([s_>k for s_ in subsum]):
                cutnum+=1
                subsum = np.array([0]*len(s_subs))
                j-=1
            
            j+=1

        candidates.append((bin(i).count('1')+cutnum))

    print(min([t for t in candidates if t>=0]))

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
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from itertools import product

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

Count = [sum(c == '1' for c in s) for s in S]
total = sum(Count)

while 0 in Count:
  i = Count.index(0)
  del S[i]
  del Count[i]
H = len(S)

if total <= K:
  answer = 0
else:
  answer = H * W
  for X in product([False, True], repeat=H-1):
    ans = sum(X)
    if ans > answer:
      continue
    DS = []
    for s, x in zip(S, [True] + list(X)):
      if x:
        DS.append([])
      DS[-1].append(s)
    DC = [[sum(s[j] == '1' for s in ds) for ds in DS] for j in range(W)]
    D = [0] * len(DS)
    for dc in DC:
      if any(d + c > K for d, c in zip(D, dc)):
        ans += 1
        if ans > answer:
          break
        D = [0] * len(DS)
      for k, c in enumerate(dc):
        D[k] += c
    answer = min(answer, ans)

print(answer)

Submission status: Time Limit Exceeded

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

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

def f(n):
  if n == 1:
    return [[0], [1]]
  a = f(n-1)
  na = []
  for v in a:
    na.append([0] + v)
    na.append([1] + v)
  return na

def min_split(h):
  sum_cnt = [0] * H
  num_split = 0
  for j in range(W):
    c = 0
    cnt = [0] * H
    for i in range(H):
      if choco[i][j] == 1:
        cnt[c] += 1
      if i < H-1 and h[i] == 1:
        c += 1
    new_cnt = [x + y for x, y in zip(sum_cnt, cnt)]
    if max(new_cnt) > K:
      num_split += 1
      sum_cnt = cnt
    else:
      sum_cnt = new_cnt
  return num_split + sum(h)

min_m = float('inf')
for h in f(H-1):
  m = min_split(h)
  min_m = min(min_m, m)
print(min_m)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

s=np.array([list(map(int,[x for x in input()])) for _ in range(h)],dtype=np.int)

cnt=10000

for i in range(2**(h-1)):
    split=[]

    for j in range(h-1):
        if (i>>j)&1==1:
            split.append(j+1)
    
    curcnt=len(split)
    nsplit=curcnt+1
    sumlst=[0]*(nsplit)
    
    split=[0]+split+[h]
    
    cw=0
    while cw<w:
        for sp_idx in range(nsplit):
            sumlst[sp_idx]+=np.sum(s[split[sp_idx]:split[sp_idx+1],cw])

            if sumlst[sp_idx]>k:
                sumlst=[0]*(nsplit)
                curcnt+=1
                break
        else:
            cw+=1
    
    cnt=min(cnt,curcnt)

print(cnt)

Submission status: Time Limit Exceeded

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

# 横の割り方を全通り試す(2**(H-1))
ans = float('inf')
for i in range(2**(H-1)):
    _ans = bin(i).count('1')
    chocos = [list(map(int, S[0]))]
    for j in range(H-1):
        if i >> j & 1:
            chocos.append(list(map(int, S[j+1])))
        else:
            for w in range(W):
                chocos[-1][w] += int(S[j+1][w])
    
    ns = len(chocos)
    nums = [0] * ns
    is_next = False
    flag = False
    for w in range(W):
        for j in range(ns):
            nums[j] += chocos[j][w]
            if chocos[j][w] > K:
                _ans = float('inf')
                flag = True
                break
            if nums[j] > K:
                _ans += 1
                is_next = True
                break
        if flag:
          flag = False
          break        
        if is_next:
            for j in range(ns):
                nums[j] = chocos[j][w]
            is_next = False
    
    ans = min(ans, _ans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import itertools

H, W, K = map(int, input().split())
chocolate = list()
for i in range(H):
    chocolate.append(list(map(int, [i for i in input()])))
    
row_comb = list(itertools.product([0, 1], repeat=H-1))
count_min = float('inf')
for row in row_comb:
    choco_array = np.array(chocolate)
    for i, k in enumerate(row):
        if k == 0:
            amount = choco_array[i:i+2, :].sum(axis=0)
            choco_array[i, :] = amount
            choco_array[i+1, :] = amount
            
    
    column = np.ones([W-1])
    for i in range(W-1):
        amount = choco_array[:, i:i+2].sum(axis=1)
        if np.all(amount<=K):
            choco_array[:, i+1] = amount
            column[i] = 0
    
    count = int(sum(row) + column.sum())
    if count < count_min:
        count_min = count

print(count_min)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from itertools import product

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

Count = [sum(c == '1' for c in s) for s in S]
total = sum(Count)

while 0 in Count:
  i = Count.index(0)
  del S[i]
  del Count[i]
H = len(S)

if total <= K:
  answer = 0
else:
  answer = H * W
  for X in product([False, True], repeat=H-1):
    DS = defaultdict(list)
    i = 0
    for j, s in enumerate(S):
      if j > 0 and X[j-1]:
        i += 1
      DS[i].append(s)
    ans = sum(X)
    DC = defaultdict(int)
    for j in range(W):
      if any(DC[k] + sum(s[j] == '1' for s in s_list) > K for k, s_list in DS.items()):
        ans += 1
        DC = defaultdict(int)
      for k, s_list in DS.items():
        DC[k] += sum(s[j] == '1' for s in s_list)
    answer = min(answer, ans)

print(answer)

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)]
    
    s = np.array(s)

    candidates = []

    for i in range(1<<h):
        s_subs = divide(s,i)
        cutnum = 0
        pos = 0

        for j in range(w):

            subsum = [np.sum(s_[:,pos:j])>k for s_ in s_subs]
            if any(subsum):
                pos = j-1
                cutnum+=1
        
        if any([np.sum(s_[:,pos:])>k for s_ in s_subs]):
            cutnum+=1


        candidates.append((bin(i).count('1')+cutnum))

    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
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    h, w, K = map(int, input().split())
    grid = [list(input()) for _ in [0]*h]
    m = 10**9
    for i in range(2**(h-1)):
        i = (("0"*h)+bin(i)[2:])[-h:]+"2"
        memo = [0]
        for j in range(h):
            if i[j] == i[j+1]:
                pass
            else:
                memo.append(j+1)
        ans = len(memo)-1
        ans2 = [0]
        memo2 = [0]*ans
        j = 0
        flag = False
        while j < w:
            if flag:
                break
            for k in range(ans):
                memo2[k] += [grid[l][j]
                             for l in range(memo[k], memo[k+1])].count("1")
                if memo2[k] > K:
                    ans2.append(j)
                    memo2 = [0]*ans
                    if ans2[-1] == ans2[-2]:
                        flag = True
                    break
            else:
                j += 1
        if flag == False:
            m = min(m, ans+(len(ans2)-2))
    print(m)


main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations as comb
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
l = np.sum(s, axis=0, keepdims=True)
cnt = count(l)
if cnt>=0:
    ans = min(ans, cnt)

li = list(range(1, h))
for i in range(1, h):
    combs = list(comb(li, i))
    for cmb in combs:
        r = 0
        l = []
        for j in cmb:
            l.append(np.sum(s[r:j, :], axis=0))
            r = j
        l.append(np.sum(s[r:, :], axis=0))
        cnt = count(np.vstack(l))
        if cnt>=0:
            ans = min(ans, cnt+i)
print(ans)

Submission status: Time Limit Exceeded

Solution code:

import numpy as np
from functools import *
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline




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


def II():
    return int(input())

directions=np.array([[1,0],[0,1],[-1,0],[0,-1]])
directions = list(map(np.array, directions))

mod = 10**9+7


def factorial(n):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
    return fact



def serch(x, count):
    #print("top", x, count)
            

    for d in directions:
        nx = d+x
        #print(nx)
        if np.all(0 <= nx) and np.all(nx < (H, W)):
            if field[nx[0]][nx[1]] == "E":
                count += 1 
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)  
                continue
            if field[nx[0]][nx[1]] == "#":
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)    
                 
    return count

H,W,K=acinput()

field=[]
for i in range(H):
    tmp=map(int,list(input())[:-1])
    field.append(list(tmp))

#wchoko=np.zeros((H,W))
wchoko=[]
for i in range(H):
    wchoko.append(np.cumsum(field[i]))

import itertools as it
#for k in range(2**H):
#   
#  l=map(int,list(bin(k)[2:].zfill(H)))

#mjjjmdxcc≈≈ççkprint(wchoko)
#print(wchoko)
res=10**9
for i in range(H):
    for c in  it.combinations(range(1,H),i):
        c=list(c)
        group=[]
        l=0
        c.append(H)
        for r in c:
            tmp=np.zeros([1,W])
            for a in range(l,r):
                tmp+=wchoko[a]       
            group.append(tmp) 
            l=r

        #print(group,c)
        count=0
        bef=0
        for cl in range(1,W):
            for g in range(len(group)):
                if bef==0:
                    tmp=0
                else:
                    tmp = group[g][0][bef-1]
                #print(group[g][0])
                if group[g][0][cl]-tmp>K:
                    bef=cl
                    count+=1
                    #print(cl)
    
        res=min(res,i+count)           
    
print(res)

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.reshape(H, W).astype('int')

l = [[0, 1] for _ in range(H - 1)]
ans = 10**10
for arr in product(*l):
    cut = arr.count(1)
    subset = []
    arr = np.array(arr, dtype='bool')
    idx = np.arange(1, H)[arr]
    if len(idx) == 0:
        subset = [S]
    elif len(idx) == 1:
        subset.append(S[:idx[0], :])
        subset.append(S[idx[0]:, :])
    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]:, :])

    cumsum = []
    for i in range(len(subset)):
        # print('subset', subset[i])
        tmp = (subset[i].sum(axis=0)).cumsum()
        # tmp = [subset[i][:, :j].sum() for j in range(1, W + 1)]
        # print('tmp', tmp)
        cumsum.append(tmp)
    cumsum = np.array(cumsum).reshape(len(subset), -1)
    # 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:
h,w,k=map(int,input().split())
Cho=[list(map(int,list(input()))) for _ in range(h)]
ans=10000000
for i in range(2**(h-1)):
	need=0
	seq=[]
	t=[]
	for j in range(h-1):
		t.append(j)
		if i&(1<<j):
			need+=1
			seq.append(t)
			t=[]
	seq.append(t+[h-1])
	f=1
	q=need+1
	cnt=[0]*q
	for x in range(w):
		cntp=[0]*q
		for i,g in enumerate(seq):
			cntg=0
			for y in g:
				cntg+=Cho[y][x]
				if cntg>k:
					f=0
					break
				cntp[i]+=Cho[y][x]
			if not f:
				break
		if not f:
			break
		for xx in range(q):
			cnt[xx]+=cntp[xx]
		if any(xxx>k for xxx in cnt):
			need+=1
			if need>ans:
				f=0
				break
			cnt=cntp
	if f:
		ans=min(ans,need)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product

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

ans = float("inf")
for pat in product([1, 0], repeat=h):
    prev = 2
    sm = -1
    for e in pat:
        if e != prev:
            sm += 1
        prev = e
    #print(pat)
    #print(sm)

    ss = [[0] * w for _ in range(h)]
    for wi in range(w):
        acc = 0
        prev = 2
        for hi, e in enumerate(pat):
            if e != prev:
                acc = 0
            if s[hi][wi]:
                acc += 1
            ss[hi][wi] = acc
            prev = e

    sss = [[0] * w for _ in range(h)]
    for hi in range(h):
        for wi in range(w):
            if wi == 0:
                sss[hi][wi] = ss[hi][wi]
            else:
                sss[hi][wi] = sss[hi][wi-1] + ss[hi][wi]

    base = [0] * h
    cp_prev = [0] * h
    for wi in range(w):
        mx = 0
        cp = [0] * h
        for hi in range(h):
            mx = max(mx, sss[hi][wi] - base[hi])
            cp[hi] = sss[hi][wi]
        if mx > k:
            if wi == 0:
                sm = 10000
            sm += 1
            base = cp_prev
        cp_prev = cp

    ans = min(ans, sm)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations as comb
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
l = list(np.sum(s, axis=0))
cnt = count([l])
if cnt>=0:
    ans = min(ans, cnt)

li = list(range(1, h))
for i in range(1, h):
    combs = list(comb(li, i))
    for cmb in combs:
        r = 0
        l = []
        for j in cmb:
            l.append(list(np.sum(s[r:j, :], axis=0)))
            r = j
        l.append(list(np.sum(s[r:, :], axis=0)))
        cnt = count(l)
        if cnt>=0:
            ans = min(ans, cnt+i)
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)
cumsum = np.cumsum(S.cumsum(axis=1).copy(), axis=0)
#cumsum = np.cumsum(S, axis=1)
#print(cumsum)
#for h in range(H-1):
#  cumsum[h+1] += cumsum[h]
#cum_h = S.cumsum(axis=0)

ans = 0
hs = 1
ws = 1
#print(cumsum)
while True:
  if hs < H:
    for h in range(hs, H):
      if cumsum[h,-1] > K:
        ans += 1
        for h2 in range(h, H):
          cumsum[h2] -= cumsum[h-1]
        hs = h if hs != H-1 else H
        break
  elif ws < W:
    for w in range(ws, W):
      if cumsum[-1,w] > K:
        ans += 1
        for w2 in range(w, W):
          cumsum[:,w2] -= cumsum[:,w-1]
        ws = w if ws != W-1 else W
        break
  else:
    break
print(ans)

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
        break
        
  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(input()) for i in range(H)]

fans = 10 ** 5
for i in range(1 << (H-1)):
    slc = []
    scnt = 1
    ans = 0
    switch = 1
    for j in range(H-1):
        if (i >> j) % 2 == 1:
            slc.append(j+1)
            scnt += 1
            ans += 1
    slc.append(H)
    stock = [0] * scnt 
    for j in range(W):
        kari = [0] * scnt
        ss = slc[0]
        idx = 0
        for k in range(H):
            if ss == k:
                idx += 1
                ss = slc[idx]
            if S[k][j] == "1":
                kari[idx] += 1
            if kari[idx] > K:
                switch = 0
                break
        if switch == 0:
            break
        for k in range(scnt):
            if stock[k] + kari[k] <= K:
                stock[k] += kari[k]
            else:
                stock = kari
                ans += 1
                break
    if switch == 1:
        fans = min(fans, ans)

print(fans)

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
        use = np.cumsum(use,axis=1)
        l,r = 0,1
        while r<=W:
            f = use[:,r]-use[:,l]
            if np.max(f) > K:
                count += 1
                l = r-1
            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())
s = []
ss = s.append
for i in range(h):
  si = str(input())
  ss(si)
mn = float("inf")
for i in range(2**(h-1)):
  bi = bin(i)[2:]
  c = 0
  for bii in bi:
    if bii == "1":
      c += 1
  bi = "0"*(h-1-len(bi)) + bi + "0"
  cc = c
  wh = [0 for _ in range(cc+1)]
  j = 0
  flag = True
  while j < w:
    if not flag:
      break
    p = 0  
    whn = [0 for _ in range(cc+1)]
    for l in range(h):
      if s[l][j] == "1":
        wh[p] += 1
        whn[p] += 1
      if bi[l] == "1":
        p += 1
    if max(whn) > k:
      flag = False
      break
    if max(wh) > k:
      c += 1
      wh = whn
    j += 1
  if j == w:
    if c < mn:
      mn = c
print(mn)