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: Runtime Error

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
from re import split
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy
import re

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7

h, w, k = LI()
s = SRL(h)
ans = INF
for bits in range(2 ** (h - 1)):
    res = sum([int(j) for j in f'{bits:b}'])
    div_cnt = res + 1
    cnt = [0] * div_cnt
    x = 0
    flg = 0
    while x < w:
        cur = 0
        for y in range(h):
            if s[y][x] == '1':
                cnt[cur] += 1
            if bits >> y & 1:
                cur += 1
        if max(cnt) > k:
            if flg == 0:
                break
            else:
                cnt = [0] * div_cnt
                flg = 0
                res += 1
        else:
            flg = 1
            x += 1
    ans = min(ans, res)


print(ans)

Submission status: Runtime Error

Solution code:
# https://atcoder.jp/contests/abc159/tasks/abc159_e
import sys

ans = sys.maxsize
H, W, K = map(int, input().split())
s = [input() for _ in range(H)]

for h in range(1 << (H - 1)):
    g = 0
    ids = [-1 for _ in range(H)]
    for i in range(H):
        ids[i] = g
        if (h >> i) & 1:
            g += 1

    g += 1
    c = [[[0] * W] for _ in range(g)]
    for i in range(H):
        for j in range(W):
            c[ids[i]][j] = c[ids[i]][j] + (s[i][j] == '1')

    num = g - 1
    now = [0 for _ in range(g)]


    def add(j):
        for i in range(g):
            now[i] += c[i][j]

        for i in range(g):
            if now[i] > K:
                return False

        return True


    if num >= ans:
        continue

    for j in range(W):
        if not add(j):
            num += 1
            if num >= ans:
                continue
            now = [0 for _ in range(g)]
            if not add(j):
                num = sys.maxsize
                break

    ans = min(ans, num)

print(ans)

Submission status: Runtime Error

Solution code:
import math
h, w, k = map(int, input().split())
s = [list(map(int, input())) for i in range(h)]
count = 0
for el in s:
    count += el.count(1)
if k == 1:
    k = 2
result = math.ceil(math.log(count, k))
if result == 1:
    result = 0
print(result)

Submission status: Runtime Error

Solution code:
import math
h, w, k = map(int, input().split())
s = [list(map(int, input())) for i in range(h)]
count = 0
for el in s:
    count += el.count(1)
result = math.ceil(math.log(count, k))
if result == 1:
    result = 0
print(result)

Submission status: Runtime Error

Solution code:
import numpy as np

def str_to_array(rows):
  array = []
  for row in rows:
    col_array = []
    array.append(col_array)
    for column in row:
      col_array.append(int(column))
  return np.array(array)

H, W, K = (int(n) for n in input().split(' '))
rows = []
for i in range(H):
  rows.append(input())
choco = str_to_array(rows)

cuts = 0

while np.sum(choco) > K:
  cuts += 1
  min_diff = H * W
  choco_left = None
  for i in range(1, H - 1):
    top = choco[:i]
    bot = choco[i:]
    top_sum = np.sum(top)
    bot_sum = np.sum(bot)
    diff = np.abs(top_sum - bot_sum)
    if diff < min_diff:
      if top_sum <= K:
        choco_left = bot
        min_diff = diff
      elif bot_sum <= K:
        choco_left = top
        min_diff = diff
  for i in range(1, W - 1):
    left = choco[:,:i]
    right = choco[:,i:]
    left_sum = np.sum(left)
    right_sum = np.sum(right)
    diff = np.abs(left_sum - right_sum)
    if diff < min_diff:
      if left_sum <= K:
        choco_left = right
        min_diff = diff
      elif right_sum <= K:
        choco_left = left
        min_diff = diff
  choco = choco_left
      
print(cuts)

Submission status: Runtime Error

Solution code:
def isCont(l):
    return bool(l[-1]+l[-2] <= k)

def cutChoco(l):
    l[-2] += l[-1]
    l.pop(-1)

h, w, k = map(int,input().split())
ans = (w-1)*(h-1)+1
s = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
    row = input()
    for j in range(w):
        s[i][j] = int(row[j])

for i in range(2**(h-1)):
    if ans < bin(i)[2:].count('1'):
        continue
    tmp = [s[0]]
    div = 0
    for j in range(h-1):
        if ((i >> j) & 1) == 1:
            tmp[j] = [x+y for (x,y) in zip(tmp[j],s[j+1])]
        else:
            tmp.append(s[j+1])
            div += 1
    for n in range(w):
        if len(tmp[0]) == 1:
            break
        contflag = 1
        for item in tmp:
#            print(item)
            contflag *= isCont(item)
        if contflag == 1:
            for item in tmp:
                cutChoco(item)
        else:
            div += 1
            for item in tmp:
                item.pop(-1)
    ans = min(ans,div)            
print(ans)

Submission status: Runtime Error

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()

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

    ans = 10 ** 9

    for bit in range(1 << (H-1)):
        canSolve = True
        ord = [0] * (H + 1)
        N = 0
        for i in range(H):
            if bit & 1 << i:
                ord[i+1] = ord[i] + 1
                N += 1
            else:
                print(i)
                ord[i+1] = ord[i]
        nums = [0] * N
        for w in range(W):
            one = [0] * N
            overK = False
            for h in range(H):
                one[ord[h]] += int(S[h][w])
                nums[ord[h]] += int(S[h][w])
                if one[ord[h]] > K:
                    canSolve = False
                if nums[ord[h]] > K:
                    overK = True
            if not canSolve:
                break
            if overK:
                N += 1
                nums = one
        if canSolve and ans > N:
            ans = N
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()

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

    ans = 10 ** 9

    for bit in range(1 << (H-1)):
        canSolve = True
        ord = [0] * H
        N = 0
        for i in range(H):
            if bit & 1 << i:
                ord[i+1] = ord[i] + 1
                N += 1
            else:
                ord[i+1] = ord[i]
        nums = [0] * H
        for w in range(W):
            one = [0] * H
            overK = False
            for h in range(H):
                one[ord[h]] += int(S[h][w])
                nums[ord[h]] += int(S[h][w])
                if one[ord[h]] > K:
                    canSolve = False
                if nums[ord[h]] > K:
                    overK = True
            if not canSolve:
                break
            if overK:
                N += 1
                nums = one
        if canSolve and ans > N:
            ans = N
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n, m, k = [int(i) for i in input().split()]

subsets = []
splits = [i for i in range(1, n)]
n -= 1
for i in range(2**n):
    x = []
    for j in range(n):
        if i&(1<<j):
            x.append(j)
    subsets.append(x)

n+=1

A = []
for i in range(n):
    A.append([int(j) for j in input()])
#print(A)

ans = n*m


for subset in subsets:
    cur_ans = len(subset)
    #print(subset)
    tmp = []
    col = 0
    subset.append(1000000000)
    running_sum = [0 for i in range(len(subset)+10)]    
    while col<m:
        row_ptr = 0    
        for row in range(n):
            if row > subset[row_ptr]:
                row_ptr += 1

            running_sum[row_ptr] += A[row][col]
            if running_sum[row_ptr] > k:
                #print(dict(update_at = (row,col)), running_sum)
                col -= 1
                
                running_sum = [0 for i in range(len(subset)+10)]
                cur_ans += 1
                
        col += 1                
    #print(subset, cur_ans)
    ans = min(ans, cur_ans)
print(ans)

Submission status: Runtime Error

Solution code:
n, m, k = [int(i) for i in input().split()]

subsets = []
splits = [i for i in range(1, n)]
n -= 1
for i in range(2**n):
    x = []
    for j in range(n):
        if i&(1<<j):
            x.append(j)
    subsets.append(x)

n+=1

A = []
for i in range(n):
    A.append([int(j) for j in input()])
#print(A)

ans = n*m


for subset in subsets:
    cur_ans = len(subset)
    #print(subset)
    tmp = []
    col = 0
    subset.append(1000000000)
    running_sum = [0 for i in range(len(subset)+10)]    
    while col<m:
        row_ptr = 0    
        for row in range(n):
            if row > subset[row_ptr] and row_ptr+1 < len(subset):
                row_ptr += 1
            #print(subset, row, row_ptr, running_sum)    
            running_sum[row_ptr] += A[row][col]
            if running_sum[row_ptr] > k:
                #print(dict(update_at = (row,col)), running_sum)
                col -= 1
                
                running_sum = [0 for i in range(len(subset)+10)]
                cur_ans += 1
                
            
            
        col += 1                
    #print(subset, cur_ans)
    ans = min(ans, cur_ans)
print(ans)

Submission status: Runtime Error

Solution code:
n, m, k = [int(i) for i in input().split()]

subsets = []
splits = [i for i in range(1, n)]
n -= 1
for i in range(2**n):
    x = []
    for j in range(n):
        if i&(1<<j):
            x.append(j)
    subsets.append(x)

n+=1

A = []
for i in range(n):
    A.append([int(j) for j in input()])
#print(A)

ans = n*m

def solve(mat, k):
    ret_val = 0
    running_sum = 0
    i = 0
    #print(mat)
    while i<len(mat[0]): # col
        
        for j in range(len(mat)): # row
            running_sum += mat[j][i]
        if running_sum > k:
            ret_val += 1
            #print(dict(adding_at=(j,i)))
            i -= 1
            running_sum = 0
        i += 1
    #print(mat, ret_val)    
    return ret_val                    
    

for subset in subsets:
    cur_ans = len(subset)
    #print(subset)
    tmp = []
    col = 0
    subset.append(1000000000)
    running_sum = [0 for i in range(len(subset)+1)]    
    while col<m:
        row_ptr = 0    
        for row in range(n):
            if row > subset[row_ptr] and row_ptr+1 < len(subset):
                row_ptr += 1
            #print(subset, row, row_ptr, running_sum)    
            running_sum[row_ptr] += A[row][col]
            if running_sum[row_ptr] > k:
                #print(dict(update_at = (row,col)), running_sum)
                col -= 1
                
                running_sum = [0 for i in range(len(subset))]
                cur_ans += 1
                
            
            
        col += 1                
    #print(subset, cur_ans)
    ans = min(ans, cur_ans)
print(ans)

Submission status: Runtime Error

Solution code:
a

Submission status: Runtime Error

Solution code:
H,W,k=map(int,input().split())
M=[]
for _ in range(H):
    M.append([int(s) for s in input()])
ans=2000
for i in range(2**(H-1)):
    S=format(i,'b')
    S=str(S).zfill(H-1)
    cnt=S.count('1')
    lst=[[*M[0]]]
    for i in range(H-1):
        if S[i]=='1':
            lst.append(M[i+1])
        else:
            lst[-1]=[lst[-1][j]+int(M[i+1][j]) for j in range(W)]
    L=len(lst)
    R=[0]*L
    for w in range(W):
        if max(lst[i][w] for i in range(L))>k:
            break
        tmp=[R[i]+lst[i][w] for i in range(L)]
        if max(tmp)>k:
            cnt+=1
            R=[lst[i][w] for i in range(L)]
        else:
            R=tmp
    else:
        ans=min(ans,cnt)
print(ans)

Submission status: Runtime Error

Solution code:
H,W,k=map(int,input().split())
M=[input() for _ in range(H)]
ans=2000
for i in range(2**(H-1)):
    S=format(i,'b')
    S=str(S).zfill(H-1)
    cnt=S.count('1')
    lst=[[*M[0]]]
    for i in range(H-1):
        if S[i]=='1':
            lst.append(S[i+1])
        else:
            lst[-1]=[lst[-1][j]+S[i+1][j] for j in range(W)]
    L=len(lst)
    R=[0]*L
    for w in range(W):
        if max(lst[i][w] for i in range(L))>k:
            break
        tmp=[R[i]+lst[i][w] for i in range(L)]
        if max(tmp)>k:
            cnt+=1
            R=[lst[i][w] for i in range(L)]
        else:
            R=tmp
    else:
        ans=min(ans,cnt)
print(ans)

Submission status: Runtime Error

Solution code:
from itertools import *
H, W, K = map(int, input().split())
S = [list(map(int, input())) for i in range(H)]
ans = 100000
for p in product([0,1],repeat=H-1):
    tmp_ans = sum(p)
    index = []
    for i,j in enumerate(p):
        if j == 1:
            index.append(i+1)
    count = [0] * (len(index) +1)
    for w in range(W):
        plate = [yoko[w] for yoko in S]
        tmp = [0]*(len(index)+1)
        if index == []:
            tmp[0] = sum(plate)
        else:
            tmp[0] = sum(plate[0:index[0]])
            for itr in range(len(index)):
                if itr == len(index) -1:
                    tmp[itr+1] += sum(plate[index[itr]:])
                else:
                    tmp[itr+1] += sum(plate[index[itr]:index[itr+1]])
        if max(tmp_sum) > K :
            tmp_ans = 11111111111
        tmp_sum = [x+y for (x,y) in zip(count,tmp)]
        if max(tmp_sum) > K:
            tmp_ans +=1
            count = tmp
        else:
            count = tmp_sum
    if tmp_ans < ans:
        ans = tmp_ans

print(ans)

Submission status: Runtime Error

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

cut = 0
num = sum(S)
while K < num:
  cut += 1
  K = 2 * K

if cut == 0:
  print(cut)
else:
  print(cut+1)

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict, Counter
def input(): return sys.stdin.readline().rstrip()

def main():
    H, W, K = map(int, input().split())
    choco = [input() for _ in range(H)]

    ans = 10 ** 9
    for i in range(2 ** (H-1)):
        opt = 0
        memoCounter = Counter({})
        for j in range(W):
            c = 0
            memo = defaultdict(int)
            for k in range(H):
                if i & 1 << k:
                    c += 1
                memo[c] += int(choco[k][j])
            if max(memo) > K:
                    break
            memo = Counter(memo)
            memoCounter += memo
            if memoCounter.most_common()[0][1] > K:
                opt += 1
                memoCounter = Counter(memo)
        else:
            opt += format(i, 'b').count('1')
            if ans > opt:
                ans = opt
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict, Counter
def input(): return sys.stdin.readline().rstrip()

def main():
    H, W, K = map(int, input().split())
    choco = [input() for _ in range(H)]

    ans = 10 ** 9
    for i in range(2 ** (H-1)):
        opt = 0
        memoCounter = Counter({})
        for j in range(W):
            c = 0
            memo = defaultdict(int)
            for k in range(H):
                if i & 1 << k:
                    c += 1
                memo[c] += int(choco[k][j])
            if max(memo) > K:
                    break
            memoCounter += memo
            if memoCounter.most_common()[0][1] > K:
                opt += 1
                memoCounter = Counter(memo)
        else:
            opt += format(i, 'b').count('1')
            if ans > opt:
                ans = opt
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict, Counter
def input(): return sys.stdin.readline().rstrip()

def main():
    H, W, K = map(int, input().split())
    choco = [input() for _ in range(H)]

    ans = 10 ** 9
    for i in range(2 ** (H-1)):
        opt = 0
        memoCounter = Counter({})
        for j in range(W):
            c = 0
            memo = defaultdict(int)
            for k in range(H):
                if i & 1 << k:
                    c += 1
                memo[c] += int(choco[k][j])
            if max(memo) > K:
                    break
            memoCounter += memo
            if memoCounter.most_common()[0][1] > K:
                opt += 1
                memoCounter = Counter(memo)
        else:
            opt += format(i, 'b').count('1')
            if ans > opt:
                ans = opt
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#E
h, w, K = map(int, input().split())
ans = 1000000
choco = []
for i in range(h):
    l = list(str(input()))
    p = []
    for j in range(w):
        z = int(l[j])
        p.append(z)

    choco.append(p)

if h == 1:
    cou = 0
    for i in range(w):
        if choco[i] == 1:
            cou += 1
    print(cou // k)
else:
    for i in range(1<<h-1):
        #print(i)
        sep = [] #境界
        for j in range(h-1):
            q = 2 ** (h-2-j)
            #print(i)
            #print(q)
            sep.append(i // q)
            if (i // q) == 1:
                i -= q

        sep.append(1)
        #print(sep) #ランダムに仕切りができてるか確認
        tsep = -1

        LI = [[0] * w for _ in range(h)] #横の仕切りで分けられた範囲内の各列のwhiteの和
        cou = 0 #LIのどの行に足していくか
        for j in range(h):
            s = choco[j]
            for k in range(w):
                LI[cou][k] += s[k]

            if sep[j] == 1:
                tsep += 1
                cou += 1

        #print(cou)
        #print(LI)
        SUML = [0 for _ in range(cou)]　
        for i in range(w):
            over = False
            for j in range(cou):
                if (SUML[j] + LI[j][i]) > K:
                    tsep += 1
                    over = True
                    #print('over')
                    break
                else:
                    SUML[j] += LI[j][i]
                    #print('within')

            if over:
                for k in range(cou):
                    SUML[k] = LI[k][i]
            #print(SUML)
        for i in range(h):　#そもそも1列でoverするケースはだめなので排除
            for j in range(w):
                if LI[i][j] > K:
                    tsep = 1000000
                    break
            else:
                break

        #print(tsep)
        if ans > tsep:
            ans = tsep

print(ans)

Submission status: Runtime Error

Solution code:
#bit 貪欲法
def add(j):
    for i in range(g):
        now[i] += c[i][j]
    for i in range(g):
        if now[i] > k: return False
    return True

import sys
input = lambda: sys.stdin.readline().rstrip()

f_inf = float('inf')

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

ans = f_inf
for div in range(1<<(h-1)):
    g = 0 #g: the number of group
    id = [0] * h  
    for i in range(h):
        id[i] = g
        if div >> i & 1:
            g += 1
    g += 1

    c = [[0] * 11 for _ in range(1005)]
    for i in range(h):
        for j in range(w):
            c[id[i]][j] += S[i][j]
    num = g - 1
    now = [0] * g
    for j in range(w):
        if not add(j):
            num += 1
            now = [0] * g
            if not add(j):
              num = f_inf
              break
    ans = min(ans, num)
print(ans)

Submission status: Runtime Error

Solution code:
def add(j):
    for i in range(g):
        now[i] += c[i][j]
    for i in range(g):
        if now[i] > k: return False
    return True

import sys
input = lambda: sys.stdin.readline().rstrip()

f_inf = float('inf')
c = [[0] * 10 for _ in range(1005)]

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

ans = f_inf
for div in range(1<<(h-1)):
    g = 0 #g: the number of group
    id = [0] * h  
    for i in range(h):
        id[i] = g
        if div >> i & 1:
            g += 1
    g += 1

    for i in range(g):
        for j in range(w):
            c[i][j] = 0
    for i in range(h):
        for j in range(w):
            c[id[i]][j] += S[i][j]
    num = g - 1
    now = [0] * g
    for j in range(w):
        if not add(j):
            num += 1
            now = [0] * g
            if not add(j):
              num = f_inf
              break
    ans = min(ans, num)
print(ans)

Submission status: Runtime Error

Solution code:
def add(j):
    for i in range(g+1):
        now[i] += c[i][j]
    for i in range(g+1):
        if now[i] > k: return False
    return True

import sys
input = lambda: sys.stdin.readline().rstrip()

f_inf = float('inf')
c = [[0] * 10 for _ in range(1005)]

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

ans = f_inf
for div in range(1<<(h-1)):
    g = 0 #g: the number of group
    id = [0] * h  
    for i in range(h):
        id[i] = g
        if div >> i & 1:
            g += 1
    g += 1

    for i in range(g):
        for j in range(w):
            c[i][j] = 0
    for i in range(h):
        for j in range(w):
            c[id[i]][j] += S[i][j]
    ok = True
    for i in range(g):
        for j in range(w):
            if c[i][j] > k:
                ok = False
    if not ok: continue

    num = g - 1
    now = [0] * (g+1)
    for j in range(w):
        if not add(j):
            num += 1
            now = [0] * (g+1)
            add(j)
    ans = min(ans, num)
print(ans)

Submission status: Runtime Error

Solution code:
#bit 貪欲法
#二次元マトリックスinput

def add(j):
    for i in range(g):
        now[i] += c[i][j]
    for i in range(g):
        if now[i] > k: return False
    return True

import sys
input = lambda: sys.stdin.readline().rstrip()

f_inf = float('inf')
c = [[0] * 10 for _ in range(1005)]

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

ans = f_inf
for div in range(1<<(h-1)):
    g = 0 #g: the number of group
    id = [0] * h  
    for i in range(h):
        id[i] = g
        if div >> i & 1:
            g += 1
    g += 1

    for i in range(g):
        for j in range(w):
            c[i][j] = 0
    for i in range(h):
        for j in range(w):
            c[id[i]][j] += S[i][j]
    ok = True
    for i in range(g):
        for j in range(w):
            if c[i][j] > k:
                ok = False
    if not ok: continue

    num = g - 1
    now = [0] * g 
    for j in range(w):
        if not add(j):
            num += 1
            now = [0] * g
            add(j)
    ans = min(ans, num)
print(ans)

Submission status: Runtime Error

Solution code:

def add(j):
    for i in range(g):
        now[i] += c[i][j]
    for i in range(g):
        if now[i] > k: return False
    return True

import sys
input = lambda: sys.stdin.readline().rstrip()

f_inf = float('inf')
c = [[0] * 10 for _ in range(1005)]

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

ans = f_inf
for div in range(1<<(h-1)):
    g = 0 #g: the number of group
    id = [0] * h
    for i in range(h):
        id[i] = g
        if (div>>i) and 1:
            g += 1
    g += 1

    for i in range(g):
        for j in range(w):
            c[i][j] = 0
    for i in range(h):
        for j in range(w):
            c[id[i]][j] += S[i][j]
    ok = True
    for i in range(g):
        for j in range(w):
            if c[i][j] > k:
                ok = False
    if not ok: continue

    num = g - 1
    now = [0] * g
    for j in range(w):
        if not add(j):
            num += 1
            now = [0] * g
            add(j)
    ans = min(ans, num)
print(ans)

Submission status: Runtime Error

Solution code:
def add(j):
    for i in range(g):
        now[i] += c[i][j]
    for i in range(g):
        if now[i] > k: return False
    return True

import sys
input = lambda: sys.stdin.readline().rstrip()
sys.setrecursionlimit(100000)

f_inf = float('inf')
c = [[0] * 10 for _ in range(1005)]

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

ans = f_inf
for div in range(1<<(h-1)):
    g = 0 #g: the number of group
    id = [0] * h
    for i in range(h):
        id[i] = g
        if (div>>i) & 1:
            g += 1
    g += 1

    for i in range(g):
        for j in range(w):
            c[i][j] = 0
    for i in range(h):
        for j in range(w):
            c[id[i]][j] += S[i][j]
    ok = True
    for i in range(g):
        for j in range(w):
            if c[i][j] > k:
                ok = False
    if not ok: continue

    num = g - 1
    now = [0] * g
    for j in range(w):
        if not add(j):
            num += 1
            now = [0] * g
            add(j)
    ans = min(ans, num)
print(ans)

Submission status: Runtime Error

Solution code:
def add(j):
    for i in range(g):
        now[i] += c[i][j]
    for i in range(g):
        if now[i] > k: return False
    return True

f_inf = float('inf')
c = [[0] * 10 for _ in range(1005)]

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

ans = f_inf
for div in range(1<<(h-1)):
    g = 0 #g: the number of group
    id = [0] * h
    for i in range(h):
        id[i] = g
        if (div>>i) & 1:
            g += 1
    g += 1

    for i in range(g):
        for j in range(w):
            c[i][j] = 0
    for i in range(h):
        for j in range(w):
            c[id[i]][j] += S[i][j]
    ok = True
    for i in range(g):
        for j in range(w):
            if c[i][j] > k:
                ok = False
    if not ok: continue

    num = g - 1
    now = [0] * g
    for j in range(w):
        if not add(j):
            num += 1
            now = [0] * g
            add(j)
    ans = min(ans, num)
print(ans)

Submission status: Runtime Error

Solution code:
def add(j):
    for i in range(g):
        now[i] += c[i][j]
    for i in range(g):
        if now[i] > k: return False
    return True

import sys
input = sys.stdin.readline

f_inf = float('inf')
c = [[0] * 10 for _ in range(1005)]

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

ans = f_inf
for div in range(1<<(h-1)):
    g = 0 #g: the number of group
    id = [0] * h
    for i in range(h):
        id[i] = g
        if (div>>i) & 1:
            g += 1
    g += 1

    for i in range(g):
        for j in range(w):
            c[i][j] = 0
    for i in range(h):
        for j in range(w):
            c[id[i]][j] += S[i][j]
    ok = True
    for i in range(g):
        for j in range(w):
            if c[i][j] > k:
                ok = False
    if not ok: continue

    num = g - 1
    now = [0] * g
    for j in range(w):
        if not add(j):
            num += 1
            now = [0] * g
            add(j)
    ans = min(ans, num)
print(ans)

Submission status: Runtime Error

Solution code:
def add(j):
    for i in range(g):
        now[i] += c[i][j]
    for i in range(g):
        if now[i] > k: return False
    return True

import sys
input = lambda: sys.stdin.readline().rstrip()

f_inf = float('inf')
c = [[0] * 10 for _ in range(1005)]

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

ans = f_inf
for div in range(1 << (h - 1)):
    g = 0 #g: the number of group
    id = [0] * h
    for i in range(h):
        id[i] = g
        if (div>>i) & 1:
            g += 1
    g += 1

    for i in range(g):
        for j in range(w):
            c[i][j] = 0
    for i in range(h):
        for j in range(w):
            c[id[i]][j] += S[i][j]
    ok = True
    for i in range(g):
        for j in range(w):
            if c[i][j] > k:
                ok = False
    if not ok: continue

    num = g - 1
    now = [0] * g
    for j in range(w):
        if not add(j):
            num += 1
            now = [0] * g
            add(j)
    ans = min(ans, num)
print(ans)

Submission status: Runtime Error

Solution code:
def add(in1, in2):
    return [a + b for a, b in zip(in1, in2)]

def split(ar, k, w):
    a = 0
    if max(ar) > k:
      return -1
    tm = ar[0]
    for i in range(1, w):
        tm = add(tm, ar[i])
        if max(tm) > k:
            a += 1
            tm = ar[i]
    return a        

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

for i in range(2**(h-1)):
    data = []
    temp = s[0]
    sp = bin(i+2**h)[4:]
    if ans < sp.count("1"):
        continue
    for j in range(1, h):
        if sp[j-1] == "0":
            temp = add(temp, s[j])
        else:
            data.append(temp)
            temp = s[j]
    data.append(temp)
    ans_ = split([list(x) for x in zip(*data)], k, w)
    if ans_ == -1:
        continue
    ans_ += sp.count("1")
    if ans > ans_:
        ans = ans_
print(ans)