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
from copy import deepcopy
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))
def solve():
    H, W, K = map(int, input().split())
    SHW = [list(map(int, list(input()))) for _ in range(H)]
    tSHW = list(zip(*SHW))

    def vcut(cuts: list):
        num = 0
        cuts = [0] + cuts + [H]

        iparts = [0]*(len(cuts)-1)
        parts = deepcopy(iparts)
        w = 0
        while w < W:
            for i, (sc, ec) in enu(zip(cuts, cuts[1:])):
                if K < parts[i]+sum(tSHW[w][sc:ec]):
                    num += 1
                    parts = deepcopy(iparts)
                    break
                else:
                    parts[i] += sum(tSHW[w][sc:ec])
            else:
                w += 1
        return num

    res = (H-1)*(W-1)
    for i in range(2**(H-1)):
        cnt = 0
        cuts = [] # cut index
        for j in range((H-1)):
            if ((i >> j) & 1):
                cnt += 1
                cuts.append(j+1)
        cnt += vcut(cuts)
        if res > cnt:
            res = cnt

    print(res)

if __name__=='__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
from copy import deepcopy
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

H, W, K = map(int, input().split())
SHW = [list(map(int, list(input()))) for _ in range(H)]
tSHW = list(zip(*SHW))

def vcut(cuts: list):
    num = 0
    cuts = [0] + cuts + [H]

    iparts = [0]*(len(cuts)-1)
    parts = deepcopy(iparts)
    w = 0
    while w < W:
        for i, (sc, ec) in enu(zip(cuts, cuts[1:])):
            if K < parts[i]+sum(tSHW[w][sc:ec]):
                num += 1
                parts = deepcopy(iparts)
                break
            else:
                parts[i] += sum(tSHW[w][sc:ec])
        else:
            w += 1
    return num

res = (H-1)*(W-1)
for i in range(2**(H-1)):
    cnt = 0
    cuts = [] # cut index
    for j in range((H-1)):
        if ((i >> j) & 1):
            cnt += 1
            cuts.append(j+1)
    cnt += vcut(cuts)
    if res > cnt:
        res = cnt

print(res)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

# main
stack=deque([str(1),str(0)])
result=H-1+W-1
while stack:# O(2^H)
    edge=stack.pop()
    if len(edge)<H-1:
        stack.append(edge+str(1))
        stack.append(edge+str(0))
    else:
        ii=0
        for i in range(H-1):
            ii+=int(edge[i])
        Nk=[0]*(ii+1)
        Nw=0
        for iw in range(W):# O(W)
            Nh=0
            Nk0=[0]*(ii+1)
            for ih in range(H-1):# O(H)
                Nk[Nh]+=int(S[ih][iw])
                Nk0[Nh]+=int(S[ih][iw])
                if int(edge[ih])==1:
                    Nh+=1
            Nk[Nh]+=int(S[ih+1][iw])
            Nk0[Nh]+=int(S[ih+1][iw])
            if K<max(Nk):
                Nw+=1
                Nk=Nk0
            elif K<max(Nk0):
                Nh=H-1
                Nw=W-1
                break
        result=min(result,Nh+Nw)
print(result)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
H,W,K=map(int, input().split())
S=[]
for h in range(H):
    s=list(map(int,list(input())))
    S.append(s)
S=np.array(S)
ans=H*W
for b in range(2**(H-1)):
    count=0
    tate=bin(b).count("1")
    count+=tate
    L=np.zeros((tate+1))
    nowgroup=0
    blacks=0
    flag=True
    for i in range(W):
        s=S[:,i]
        subL=np.zeros((tate+1))
        subL[nowgroup]+=s[0]
        idx=1
        for j in range(H-1):
            if b>>j&1==1:
                nowgroup+=1
            #print(nowgroup, idx)
            subL[nowgroup]+=s[idx]
            idx+=1
        nowgroup=0
        #print(L,subL)
        if (L+subL).max()>K:
            count+=1
            L=subL
        else:
            L=L+subL
            if subL.max()>K:
                flag=False
                break
    if flag:
        ans=min(ans, count)

print(ans)

Submission status: Time Limit Exceeded

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

sum_tab = [[0] for _ in range(H)]
for i in range(H):
    sum_tmp = 0
    for j in range(W):
        sum_tmp += S[i][j]
        sum_tab[i].append(sum_tmp)

ans = 1000000007
for case in range(1 << (H - 1)):
    t = 0
    divs = []
    case_tmp = case
    for i in range(1, H):
        if case_tmp % 2 > 0:
            divs.append((t, i))
            t = i
        case_tmp >>= 1
    else:
        divs.append((t, H))
    #
    # print("#", divs)
    ans_tmp = len(divs) - 1
    l = 0
    for x in range(W):
        cnt_max = 0
        for y_str, y_end in divs:
            cnt_tmp = sum([sum_tab[y][x + 1] - sum_tab[y][l] for y in range(y_str, y_end)])
            cnt_max = max(cnt_tmp, cnt_max)
        #
        if cnt_max > K:
            ans_tmp += 1
            # print("##", cnt_max, x)
            l = x
    #
    ans = min(ans, ans_tmp)

print(ans)

Submission status: Time Limit Exceeded

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

G = [list(input()) for _ in range(H)]

ans = H * W

def calc(lst):
    group = sum(lst) + 1
    tmp = [[0] * W for _ in range(group)] #何グループに分かれるか
    k = 0
    for j in range(W):
        for i in range(H):
            if G[i][j] == '1':
                tmp[k][j] += 1
            if lst[i] == 1 or i == H - 1:
                k = (k + 1) % group
    
    cut = group - 1
    for j in range(W):
        flag = False
        for i in range(group):
            if tmp[i][j] > K:
                return 10 ** 9
            if j < W - 1:
                if tmp[i][j] + tmp[i][j + 1] > K: #次の戸合わせてKより大きくなるなら切る
                    flag = True
        if flag:
            cut += 1
        else:
            for i in range(group):
                if j < W - 1:
                    tmp[i][j + 1] += tmp[i][j]
    return cut


for i in range(2 ** (H - 1)): #ビットでカットするラインを探索
    lst = [0] * H
    for j in range(H - 1):
        if (i >> j) & 1: #切れるとき
            lst[j] = 1
    # print (lst)
    ans = min(ans, calc(lst))

print (ans)

Submission status: Time Limit Exceeded

Solution code:
import math

h,w,k = map(int,input().split())
s = [str(input()) for i in range(h)]
ans = h * w

if h == 1:
    print(math.ceil("1".count(s[0])/k))
    exit()

for i in range(2 ** (h-1)):
    ss = str(format(i,"b").zfill(h-1))
    cnt = 0
    zerocnt = 0
    key = 1
    for j in range(len(ss)):
        if ss[j] == "0":
            zerocnt += 1
    now = [0 for i in range(zerocnt+1)]

    for j in range(w):
        next = []
        num = 0
        for n in range(h):
            if s[n][j] == "1":
                num += 1
            if num > k:
                key = 0
            if n < h-1 and ss[n] == "0":
                next.append(num)
                num = 0
        next.append(num)
  #        print(next,now)
        keykey = 1
        for n in range(zerocnt+1):
            if keykey:
                if now[n] + next[n] > k:
                    now = next
                    cnt += 1
                    keykey = 0
                else:
                    now[n] += next[n]
  #    print(now)
  #    print(ans,cnt,zerocnt)
    if key:ans = min(ans,cnt+zerocnt)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import numpy as np
    h, w, K = map(int, input().split())
    grid = np.array([list(map(int, list(input())))
                     for _ in [0]*h], dtype=np.int16)
    m = 10**9
    for i in range(2**(h-1)):
        i = (("0"*h)+bin(i)[2:])[-h:]+"2"
        memo = [0]
        ma = memo.append
        [ma(j+1) for j in range(h) if i[j] != i[j+1]]
        ans = len(memo)-1
        ans2 = [0]
        aa = ans2.append
        memo2 = [0]*ans
        j = 0
        flag = False
        while j < w:
            if flag:
                break
            for k in range(ans):
                memo2[k] += np.sum(grid[memo[k]:memo[k+1], j])
                if memo2[k] > K:
                    aa(j)
                    memo2 = [0]*ans
                    if j == ans2[-2]:
                        flag = True
                    break
            else:
                j += 1
        if not flag:
            m = min(m, ans+(len(ans2)-2))
    print(m)


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]
        ma = memo.append
        [ma(j+1) for j in range(h) if i[j] != i[j+1]]
        ans = len(memo)-1
        ans2 = [0]
        aa = ans2.append
        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:
                    aa(j)
                    memo2 = [0]*ans
                    if j == ans2[-2]:
                        flag = True
                    break
            else:
                j += 1
        if not flag:
            m = min(m, ans+(len(ans2)-2))
    print(m)


main()

Submission status: Time Limit Exceeded

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

H,W,K = map(int,readline().split())
grid = [None] * (H+1)
grid[0] = [0] * (W+1)
for i in range(1,H+1):
  grid[i] = [0] + list(map(int,list(input())))
  
# 二次元累積和でチョコレートの数を管理
# 直前に選んだチョコのY座標をp,X座標をqとすると、
# チョコレートの数をO(1)で求められる
# 最初に空行を入れているので1-indexで。

for i in range(len(grid)-1):
  for j in range(len(grid[i])):
    grid[i+1][j] = grid[i][j] + grid[i+1][j]

for i in range(len(grid)):
  for j in range(len(grid[i])-1):
    grid[i][j+1] = grid[i][j] + grid[i][j+1]
  
def get_choco_cnt(i,j,p,q):
#  print("i",i,"j",j,"p",p,"q",q)
  return grid[i][j] - grid[i][q] - grid[p][j] + grid[p][q]
  
# Hが10と少ないので、切る場所9箇所をすべて試しても2^9 = 512通り
# すべてに対して、Wのどこを切るかを求める。
# 二分探索なら　O(2^(H-1) * log W) = 約5120
# 線形探索でも　O(2^(H-1) * WH) = 5,120,000

def isOk(x,lastq,cond,K,H,W):
  # xで切ったとき、iで分割されたすべての領域の数がK以下になればOK
#  print("x",x)
  lastp = 0 # Hを最後に切った場所
  for j in range(H-1):
    if (cond >> j) & 1: # j+1で切る
#      print(get_choco_cnt(j+1,x,lastp,lastq))
      if get_choco_cnt(j+1,x,lastp,lastq) > K:
        return False
      lastp = j+1
  # 最後に切った場所から、最後まで
  if get_choco_cnt(H,x,lastp,lastq) > K:
    return False
  return True
  
def decide_cut(cond,lastq,K,H,W):
  ok = lastq
  ng = W+1
  while abs(ok - ng) > 1:
    mid = abs(ok + ng) // 2
    if isOk(mid,lastq,cond,K,H,W):
      ok = mid
    else:
      ng = mid
#  print("ok",ok)
  return ok

ans = 10000
for cond in range(2 ** (H-1)):
#  print("---",bin(cond)[2:].zfill(3),"---")
  # この条件下で、Wを切る位置を決めていく
  cut_num = (bin(cond)[2:]).count("1") # カットした回数
  lastq = 0 # 最後にカットした場所
  while lastq < W+1:
#    print(lastq,"以降でカット")
    new_lastq = decide_cut(cond,lastq,K,H,W)
#    print("new_lastq",new_lastq)
    if new_lastq == W:
      break
    cut_num += 1
    lastq = new_lastq
#  print("cut_num",cut_num)
  if ans > cut_num:
    ans = cut_num
print(ans)

Submission status: Time Limit Exceeded

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

def vertical_line(h, w, k, s):
    ans = 0
    mark = [0 for _ in range(h)]
    for i in range(w):
        for j in range(h):
            mark[j] += s[j][i]
            if mark[j] > k:
                ans += 1
                mark = [s[l][i] for l in range(h)]
                break
    return ans

from copy import deepcopy
ans = []
for i in range(2 ** (h - 1)):
    s_copy = deepcopy(s)
    flag = False
    h_copy = h
    for j in range(h - 2, -1, -1):
        if i % 2 == 1:
            h_copy -= 1
            for l in range(w):
                s_copy[j][l] += s_copy[j+1][l]

                if s_copy[j][l] > k:
                    flag = True
                    break

            del s_copy[j+1]

        if flag:
            break

        i //= 2

    if flag:
        continue

    ans.append(h_copy - 1 + vertical_line(h_copy, w, k, s_copy))
print(min(ans))

Submission status: Time Limit Exceeded

Solution code:
import queue


def split_each(q, h, w, k, white_sets, done_dict, typ):
  size = h if typ == 0 else w
  for div_idx in range(size - 1):
    if (1, div_idx) in done_dict: continue

    is_answer = True
    next_white_sets = []
    for white_set in white_sets:
      set_a = set()
      set_b = set()
      for pos in white_set:
        if pos[typ] <= div_idx:
          set_a.add(pos)
        else:
          set_b.add(pos)

      if is_answer and (len(set_a) > k or len(set_b) > k):
        is_answer = False

      next_white_sets.extend([set_a, set_b])

    # print(white_sets)
    # print(done_dict)
    if is_answer:
      print(len(done_dict) + 1)
      exit()

    next_done_dict = dict.fromkeys(done_dict, 0)
    next_done_dict[0, div_idx] = 0
    q.put((next_white_sets, next_done_dict))


def main():
  h, w, k = tuple(map(int, input().split(" ")))
  white_sets = [set()]
  for i in range(h):
    for j, c in enumerate(input()):
      if c == '1': white_sets[0].add((i, j))

  if len(white_sets[0]) <= k:
    print(0)
    return

  q = queue.Queue()
  # dicts, done_dict, 横線: 0 or 縦線: 1, idx
  q.put((white_sets, {}))

  while q.qsize() > 0:
    white_sets, done_dict = q.get()

    split_each(q, h, w, k, white_sets, done_dict, 0)
    split_each(q, h, w, k, white_sets, done_dict, 1)


main()

Submission status: Time Limit Exceeded

Solution code:
h, w, k = map(int, input().split())
S = [[int(s) for s in list(input())] for i in range(h)]
ans = 10**4
for b in range(2**(h-1)):
    cnt = bin(b).count('1')
    B = format(b, 'b').zfill(h-1)+'1'
    T = [[0]*w for i in range(cnt+1)]
    for j in range(w):
        t, c = 0, 0
        for i in range(h):
            t += S[i][j]
            if B[i] == '1':
                T[c][j] += t
                t = 0
                c += 1
    if max([max(T[i]) for i in range(cnt+1)]) > k:
        continue
    A = [T[i][0] for i in range(cnt+1)]
    tmp = cnt
    for j in range(1, w):
        A = [A[i]+T[i][j] for i in range(cnt+1)]
        if any([a > k for a in A]):
            A = [T[i][j] for i in range(cnt+1)]
            tmp += 1
    ans = min(ans, tmp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    H, W, K = [int(x) for x in input().split()]
    S = [list(input().strip()) for _ in range(H)]

    ans = float("inf")

    for n in range(2 ** (H - 1)):
        tmp = 0
        wn = [0] * 10

        for i in range(H):
            if n >> i & 1:
                tmp += 1

        for i in range(W):
            f = False
            ni = 0
            for j in range(H):
                if wn[ni] + int(S[j][i]) > K:
                    tmp += 1
                    f = True
                    break
                else:
                    wn[ni] += int(S[j][i])
                if n >> j & 1:
                    ni += 1
            ff = False
            if f:
                if i == 0:
                    tmp = float("inf")
                    break
                for j in range(H):
                    wn[j] = 0
                ni = 0
                for j in range(H):
                    wn[ni] += int(S[j][i])
                    if wn[ni] > K:
                        tmp = float("inf")
                        ff = True
                        break
                    if n >> j & 1:
                        ni += 1
            if ff:
                break

        ans = min(ans, tmp)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
from itertools import accumulate
INF = float("inf")


def bit(n, k):
    return (n >> k) & 1


def bit_sum(n):
    wa = 0
    while n > 0:
        wa += n & 1
        n >>= 1
    return wa


def bit_kthone(n, k):
    # nを二進数表現した時に、下から1となる桁を数えてk番目となる桁
    for kk in range(1, k):
        n = n ^ (n & -n)
    c = 1
    while n > 1:
        c += 1
        n >>= 1
    return c


def main():

    H, W, K = map(int, input().split())
    S = [[0]*W for _ in range(H)]
    for h in range(H):
        S[h][:] = [int(c) for c in input()]
    acc = [[0]+list(accumulate(S[h])) for h in range(H)]

    min_kaisu = +INF
    for h in range(1 << (H-1)):
        # hは分割方法を与える
        # hは領域をいくつに分割しますか
        n = bit_sum(h)+1
        # n個の配列を作り、累積和を構築します。
        division = [0]
        # まずhによって与えられる分割方向が固定されていると考える(acc)
        # Xの位置で縦方向に分割した時、それより左の領域でのホワイトチョコレートの和は、いくつか
        # K未満になるかどうか
        startend = []
        c = 0
        hh = h
        while hh != 0:
            c += 1
            if hh & 1:
                startend.append(c)
            hh >>= 1
        start = [0]+startend
        end = startend + [H]

        for x in range(1, W+1):
            # xの位置で分割したとき、左の領域のホワイトチョコレートの数
            white = [acc[i][x] - acc[i][division[-1]] for i in range(H)]
            white_sum = []
            for s, e in zip(start, end):
                tot = 0
                for i in range(s, e):
                    tot += white[i]
                white_sum.append(tot)
            white_max = max(white_sum)
            if white_max > K:
                division.append(x-1)
        division_num = len(division)-1
        # hによる分割も考慮する
        division_tot = division_num + bit_sum(h)
        if min_kaisu > division_tot:
            min_kaisu = division_tot
            # print(bin(h), division)
    print(min_kaisu)
    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import copy
H,W,K=map(int,input().split())
S=[list(input()) for _ in range(H)]
ans=10**18
for i in range(1<<(H-1)):
    x=bin(i).count('1')
    cho=[0]*(x+1)
    f=1
    cnt=x
    for w in range(W):
        j=0
        nx=[0]*(x+1)
        for h in range(H):
          cho[j]+=int(S[h][w])
          nx[j]+=int(S[h][w])
          if cho[j]>K:
            if nx[j]>K:
              f=0
              break
            else:
              cho=copy.copy(nx)
              cnt+=1
          if (i>>h)&1:
            j+=1
        if f==0:
          break
    if f:
      ans=min(ans,cnt)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from copy import copy
input = sys.stdin.readline
'''
n, m = map(int, input().split())
n = int(input())
A = list(map(int, input().split()))
S = input().strip()
for test in range(int(input())):
'''
inf = 100000000000000000  # 1e17
mod = 998244353


def two(x):
    return "0" * (w - len(bin(x)[2:])) + bin(x)[2:]


h, w, maxx = map(int, input().split())
A = []
for i in range(h):
    A.append(input().strip())
# for binary in range(1<<(w-1),(1<<(w-1))+1):
ans = inf
for binary in range(1 << (w - 1)):  # every binary
    S = two(binary)
    B = [-1]
    for i in range(len(S)):
        if S[i] == "1":
            B.append(i)
    B.append(len(S) - 1)  # every horizontal cut, contain the head and the tail
#    print(B)
    SUM = [0] * (len(B))
    isok = 1
    cut_vertical = 0
    cut_horizontal = len(B) - 2
    for i in range(h):
        PRE = copy(SUM)  # previous total numbers between every cut
        for j in range(1, len(B)):  # every cut
            for k in range(B[j - 1] + 1, B[j] + 1):
                if A[i][k] == "1":
                    SUM[j] += 1
        flag = 0
        for j in range(1, len(B)):
            if SUM[j] > maxx:
                flag = 1
        if flag:
            for j in range(1, len(B)):
                SUM[j] -= PRE[j]
            cut_vertical += 1
        for j in range(1, len(B)):
            if SUM[j] > maxx:
                isok = 0
        if isok == 0:
            break
    if isok:
        ans = min(ans, cut_vertical + cut_horizontal)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
INF = 110110110
H, W, K = list(map(int, input().split()))
S = [''] * H
for i in range(H):
    S[i] = input()
ans = H * W

for bit in range(2**(H-1)):
    cnt = bin(bit).count('1')
    id = [0] * H
    for i in range(H-1):
        if bit>>i & 1:
            id[i+1] = id[i] + 1
        else:
            id[i+1] = id[i]
    num = [[0] * W for i in range(id[H-1]+1)]
    for i in range(H):
        for j in range(W):
            if S[i][j] == '1':
                num[id[i]][j] += 1
    for i in range(id[H-1]+1):
        for j in range(W):
            if num[i][j] > K:
                cnt = INF
    sum = [0] * (id[H-1]+1)
    for j in range(W):
        need = False
        for i in range(id[H-1]+1):
            if sum[i] + num[i][j] > K:
                need = True
        if need:
            cnt += 1
            for i in range(id[H-1]+1):
                sum[i] = num[i][j]
        else:
            for i in range(id[H-1]+1):
                sum[i] += num[i][j]
    ans = min(ans, cnt)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
h, w, k = map(int, input().split())
s = [list(map(int, list(input()))) for _ in range(h)]
result = []
if h*w<=k:
    result.append(0)
else:
    for i in range(2**(h-1)):
        checker, num, p = 0, i ,[0]
        for _ in range(h):
            p.append(p[-1]+num%2)
            checker += num%2
            num >>= 1
        x = 0
        c = [0 for _ in range(checker+1)]
        for j in range(w):
            num = i
            nex = [0 for _ in range(checker+1)]
            for m in range(h):
                nex[p[m]] += s[m][j]
            if max(nex) > k:
                x = float('inf')
                break            
            for m in range(checker+1):
                c[m] += nex[m]
                if c[m]>k:
                    c = nex
                    x += 1
                    break
        result.append(checker+x)
print(min(result))

Submission status: Time Limit Exceeded

Solution code:
h, w, k = map(int, input().split())
s = [list(map(int, list(input()))) for _ in range(h)]
result = []
if h*w<=k:
    result.append(0)
else:
    for i in range(2**(h-1)):
        checker, num, p = 0, i ,[0]
        for _ in range(h):
            p.append(p[-1]+num%2)
            checker += num%2
            num >>= 1
        x = 0
        c = [0 for _ in range(checker+1)]
        for j in range(w):
            num = i
            nex = [0 for _ in range(checker+1)]
            for m in range(h):
                nex[p[m]] += s[m][j]
            if max(nex) > k:
                x = float('inf')
                break            
            
            if all(nex[m]+c[m] <= k for m in range(checker+1)):
                c = [c[I]+nex[I] for I in range(checker+1)]
            else:
                x += 1
                c = nex
        result.append(checker+x)
print(min(result))

Submission status: Time Limit Exceeded

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

result = []
if h*w<=k:
    result.append(0)
else:
    for i in range(2**(h-1)):
        use_s = s.copy()
        checker, num = 0, i
        while num > 0:
            checker += num%2
            num >>= 1
        x = 0
        c = [0]*(checker+1)

        for j in range(w):
            num = i
            p = 0
            nex = [0]*(checker+1)
            for m in range(h):
                nex[p] += use_s[m]%10
                use_s[m] //= 10
                p += num%2
                num = num >> 1          
            if max(nex)>k:
                x = 10**5
                break

            if all(nex[m]+c[m] <= k for m in range(checker+1)):
                c = [c[I]+nex[I] for I in range(checker+1)]
            else:
                x += 1
                c = nex
        result.append(checker+x)
print(min(result))

Submission status: Time Limit Exceeded

Solution code:
h, w, k = map(int, input().split())
s = [list(map(int, list(input()))) for _ in range(h)]
result = []
if h*w<=k:
    result.append(0)
else:
    for i in range(2**(h-1)):
        checker, num = 0, i
        while num > 0:
            checker += num%2
            num >>= 1
        x = 0
        c = [0]*(checker+1)

        for j in range(w):
            num = i
            p = 0
            nex = [0]*(checker+1)
            for m in range(h):
                nex[p] += s[m][j]
                p += num%2
                num = num >> 1          
            if max(nex)>k:
                x = 10**5
                break

            if all(nex[m]+c[m] <= k for m in range(checker+1)):
                c = [c[I]+nex[I] for I in range(checker+1)]
            else:
                x += 1
                c = nex
        result.append(checker+x)
print(min(result))

Submission status: Time Limit Exceeded

Solution code:
h, w, k = map(int, input().split())
s = [list(map(int, list(input()))) for _ in range(h)]
result = []
if h*w<=k:
    result.append(0)
else:
    for i in range(2**(h-1)):
        checker, num = 0, i
        while num > 0:
            checker += num%2
            num >>= 1
        x = 0
        c = [0 for _ in range(checker+1)]

        for j in range(w):
            num = i
            p = 0
            nex = [0 for _ in range(checker+1)]
            for m in range(h):
                nex[p] += s[m][j]
                p += num%2
                num = num >> 1          
            if max(nex)>k:
                x = 10**5
                break

            if all(nex[m]+c[m] <= k for m in range(checker+1)):
                c = [c[I]+nex[I] for I in range(checker+1)]
            else:
                x += 1
                c = nex
        result.append(checker+x)
print(min(result))

Submission status: Time Limit Exceeded

Solution code:
h, w, k = map(int, input().split())
s = [list(map(int, list(input()))) for _ in range(h)]
result = []
if h*w<=k:
    result.append(0)
else:
    for i in range(2**(h-1)):
        checker, num = 0, i
        while num > 0:
            checker += num%2
            num >>= 1
        x = 0
        c = [0 for _ in range(checker+1)]

        for j in range(w):
            num = i
            p = 0
            nex = [0 for _ in range(checker+1)]
            for m in range(h):
                nex[p] += s[m][j]
                p += num%2
                num = num >> 1          
            if any(nex[m]>k for m in range(checker+1)):
                x = -1
                break

            if all(nex[m]+c[m] <= k for m in range(checker+1)):
                c = [c[I]+nex[I] for I in range(checker+1)]
            else:
                x += 1
                c = nex
        if x >= 0:
            result.append(checker+x)
print(min(result))

Submission status: Time Limit Exceeded

Solution code:
h, w, k = map(int, input().split())
s = [list(map(int, list(input()))) for _ in range(h)]
result = []
if h*w<=k:
    result.append(0)
else:
    for i in range(2**(h-1)):
        checker, num = 0, i
        while num > 0:
            checker += num%2
            num >>= 1
        x = 0
        c = [0 for _ in range(checker+1)]

        for j in range(w):
            num = i
            p = 0
            nex = [0 for _ in range(checker+1)]
            for m in range(h):
                nex[p] += s[m][j]
                p += num%2
                num = num >> 1
            if max(nex) > k:
                x = -1
                break            
            
            if all(nex[m]+c[m] <= k for m in range(checker+1)):
                c = [c[I]+nex[I] for I in range(checker+1)]
            else:
                x += 1
                c = nex
        if x >= 0:
            result.append(checker+x)
print(min(result))

Submission status: Time Limit Exceeded

Solution code:
h, w, k = map(int, input().split())
s = [list(map(int, list(input()))) for _ in range(h)]
result = []
if h*w<=k:
    result.append(0)
else:
    for i in range(2**(h-1)):
        checker, num = 0, i
        while num > 0:
            checker += num%2
            num >>= 1
        x = 0
        c = [0 for _ in range(checker+1)]
        
        num = i
        p = 0
        nex = [0 for _ in range(checker+1)]
        for m in range(h):
            nex[p] += s[m][0]
            p += num%2
            num = num >> 1
        if max(nex) > k:
            x = float('inf')
            continue

        if all(nex[m]+c[m] <= k for m in range(checker+1)):
            c = [c[I]+nex[I] for I in range(checker+1)]
        else:
            x += 1

        for j in range(1, w):
            num = i
            p = 0
            nex = [0 for _ in range(checker+1)]
            for m in range(h):
                nex[p] += s[m][j]
                p += num%2
                num = num >> 1
            if max(nex) > k:
                x = float('inf')
                break            
            
            if all(nex[m]+c[m] <= k for m in range(checker+1)):
                c = [c[I]+nex[I] for I in range(checker+1)]
            else:
                x += 1
                c = nex
        result.append(checker+x)
print(min(result))