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: Accepted

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, m, K = na()
b = []
for i in range(n):
    b.append(ns())

ans = 999999999999999
for ptn in range(1<<n-1):
    lans = 0
    x = ptn
    while x > 0:
        lans += x&1
        x //= 2

    to = [0] * n
    for i in range(1,n):
        if ptn>>i-1&1:
            to[i] = i
        else:
            to[i] = to[i-1]
    f = [0] * n
    ok = True
    o = ord("0")
    for j in range(m):
        plus = [0] * n
        for r in range(n):
            plus[to[r]] += ord(b[r][j])-o
            if plus[to[r]] > K:
                ok = False
                break

        if not ok:
            break
        reset = any(f[r] + plus[r] > K for r in range(n))
        if reset:
            lans += 1
            f = plus
        else:
            for i in range(n):
                f[i] += plus[i]
    if not ok:
        continue
    ans = min(ans, lans)
print(ans)

Submission status: Accepted

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

ans = 10 ** 9
for i in range(2 ** (h - 1)):
    aa = 0
    for j in range(h - 1):
        if (i >> j) & 1 == 1:
            aa += 1
    c = aa
    b = [0] * (c + 1)
    ook = True
    for j in range(w):
        k = 0
        for l in range(h):
            if s[l][j] == "1":
                b[k] += 1
            if (i >> l) & 1 == 1:
                k += 1

        ok = True
        for l in b:
            if l > kk:
                ok = False

        if not ok:
            aa += 1
            b = [0] * (c + 1)

            k = 0
            for l in range(h):
                if s[l][j] == "1":
                    b[k] += 1
                if (i >> l) & 1 == 1:
                    k += 1

            ok = True
            for l in b:
                if l > kk:
                    ok = False
            if not ok:
                ook = False
                break
    if ook:
        ans = min(ans, aa)

print(ans)

Submission status: Runtime Error

Solution code:
import sys
from io import StringIO
import unittest
import os
from collections import deque

# 再帰処理上限(dfs作成時に設定するのが面倒なので限度近い値を組み込む)
sys.setrecursionlimit(999999999)


# 実装を行う関数
def resolve(test_def_name=""):
    n, m = map(int, input().split())
    u_s = [list(map(int, input().split())) for i in range(m)]
    s, t = map(int, input().split())

    point_s = [[] for i in range(n + 1)]
    [point_s[u[0]].append(u[1]) for u in u_s]

    # deq作成
    ans = [999999999 for i in range(n + 1)]
    ans[s] = 0
    que = deque()
    que.appendleft(s)

    # BFS開始
    while len(que) is not 0:
        now = que.pop()

        # ケンケンパ
        ken = point_s[now]
        kenken = [point_s[k] for k in ken]
        kenkenpo = [[point_s[k] for k in ken] for ken in kenken]

        work_s = []
        for kenken in kenkenpo:
            for ken in kenken:
                work_s += ken

        work_s = set(work_s)
        for work in work_s:
            # 最短経路なら
            if ans[work] > ans[now] + 1:
                ans[work] = ans[now] + 1
                # キューに追加(先頭に追加するのでappendleft())
                # que.appendleft(work)
                que.append(work)

    if ans[t] == 999999999:
        ans[t] = -1

    print(ans[t])


# テストクラス
class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """4 4
1 2
2 3
3 4
4 1
1 3"""
        output = """2"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """3 3
1 2
2 3
3 1
1 2"""
        output = """-1"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """2 0
1 2"""
        output = """-1"""
        self.assertIO(test_input, output)

    def test_input_4(self):
        test_input = """6 8
1 2
2 3
3 4
4 5
5 1
1 4
1 5
4 6
1 6"""
        output = """2"""
        self.assertIO(test_input, output)

    # 自作テストパターンのひな形(利用時は「tes_t」のアンダーバーを削除すること
    def tes_t_1original_1(self):
        test_input = """データ"""
        output = """データ"""
        self.assertIO(test_input, output)


# 実装orテストの呼び出し
if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        # AtCoder提出時の場合
        resolve()

    else:
        # 自PCの場合
        unittest.main()

Submission status: Runtime Error

Solution code:
from itertools import product


def makelist(BIT):
    LIST, tmp = [], s[0]
    for i, bi in enumerate(BIT, 1):
        if bi == 1:
            LIST.append(tmp)
            tmp = s[i]
        elif bi == 0:
            tmp = [p + q for p, q in zip(tmp, s[i])]
    else:
        LIST.append(tmp)
    return LIST


def solve(LIST):
    CNT, tmp = 0, [l[0] for l in LIST]
    for i in range(1, w):
        cal = [tmp[j] + LIST[j][i] for j in range(len(LIST))]
        if any(num > k for num in cal):
            CNT += 1
            tmp = [l[i] for l in LIST]
        else:
            tmp = cal
    return CNT


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

for bit in product([0, 1], repeat=(h - 1)):
    numlist = makelist(bit)
    ans = min(ans, solve(numlist) + sum(bit))
print(ans)

Submission status: Runtime Error

Solution code:
h,w,kk=list(map(int,input().split()))
s=[list(map(int,list(input()))) for i in range(h)]
l=[]
for i in range(2**(h-1)):
  ll=[0]
  for j in range(h-1):
    if i & 2**j:
      ll.append(ll[-1]+1)
    else:
      ll.append(ll[-1])
  l.append(ll)

mc=w+h
for i in l:
  c=[0 for i in range(h)]
  cc=0
  f=1
  #print(i,0)
  for j in range(w):
    #print(c)
    ff=0
    for k in range(h):
      c[i[k]]+=s[k][j]
    for k in range(h):
      if c[k]>kk:
        ff=1
        break
    if ff:
      if f:
        cc=w+h
        print(c)
        break
      cc+=1
      c=[0 for i in range(h)]
      for k in range(h):
        c[i[k]]+=s[k][j]
    f=0
  #print(cc)
  if mc>cc+len(set(i)-1):
    mc=cc
print(mc)

Submission status: Runtime Error

Solution code:
"""

制約の小ささから見て全探索

"""

from itertools import product, accumulate
from bisect import *
import sys
input = sys.stdin.readline

H, W, K = map(int, input().split())
S = []
T = []
for i in range(H):
    S.append(list(map(int, input().strip())))
    T.append(list(accumulate([0] + S[-1])))

cnt_list = []
for a in product((0,1),repeat=H):
    past_a = a[0]
    T2 = [[0]*(W+1)]
    for i in range(H):
        if a[i] == past_a:
            for j, t in enumerate(T[i]):
                T2[-1][j] += t
        else:
            T2.append(T[i])
        past_a = a[i]
    cnt = len(T2) - 1
    l = 0
    flg = False
    while True:
        temp = []
        for s in T2:
            temp.append(bisect_right(s[l+1:], K + s[l]) + l)
        if min(temp) == 0:
            flg = True
            break
        else:
            l = min(temp)
        if l >= W:
            break
        else:
            cnt += 1
    if not flg:
        cnt_list.append(cnt)

print(min(cnt_list))

Submission status: Runtime Error

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

h,w,k = inpl()
s = [list(input()) for _ in range(h)]
res = INF
for yoko in itertools.product([0,1], repeat=(h-1)):
    # 0:uncut 1:cut
    ln = sum(yoko)
    gr = [[] for _ in range(ln+1)] 
    gr[0].append(0)
    ind = 0
    for i in range(1,h):
        if yoko[i-1]: ind += 1
        gr[ind].append(i)
    possible = True
    for x in range(w):
        for ind in range(ln+1):
            cnt = 0
            for y in gr[ind]:
                if s[y][x] == '1':
                    cnt += 1
            if cnt > k:
                possible = False
                break
        if not possible:
            break
    else:
        cutcnt = 0
        now = [0] * (ln+1)
        for x in range(w):
            for ind in range(ln+1):
                for y in gr[ind]:
                    if s[y][x] == '1':
                        now[ind] += 1
            if max(now) > k:
                now = [0] * (ln+1)
                cutcnt += 1
                for ind in range(ln+1):
                    for y in gr[ind]:
                        if s[y][x] == '1':
                            now[ind] += 1
    res = min(res, cutcnt + ln)
print(res)

Submission status: Runtime Error

Solution code:
#!/usr/bin/python3
# import bisect
# from collections import Counter, deque, OrderedDict, defaultdict
# from copy import copy, deepcopy # pythonのみ．copyは1次元，deepcopyは多次元．
# from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
# from functools import reduce
# from heapq import heapify, heappop, heappush
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import statistics # Pythonのみ
# import string
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    h,w=map(int,input().split())
    g=[[_ for _ in input()] for _ in range(w)]
    
    for div in range(2**(h-1)):
        g=0
        id=[0]*h
        for i in range(h):
            id[i]=g
            if div>>i&1: g+=1
        g+=1

        c=[[0]*10 for _ in range(1005)]
        

# resolve()

import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3 5 4
11100
10001
00111"""
        output = """2"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """3 5 8
11100
10001
00111"""
        output = """0"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """4 10 4
1110010010
1000101110
0011101001
1101000111"""
        output = """3"""
        self.assertIO(input, output)


if __name__ == "__main__":
    unittest.main()

Submission status: Runtime Error

Solution code:
# import numpy as np
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]
pl = lambda x: print(*x, sep='\n')
from copy import copy, deepcopy

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

# for h in range(H):
#     for w in range(W):
#         cumS[h+1][w+1] += cumS[h+1][w]
for h in range(H):
    for w in range(W):
        print(h, w)
        cumS[h+1][w+1] += S[h][w]
        cumS[h+1][w+1] += cumS[h][w+1]

n = H-1
cut_min = 10**9
for i in range(2**n):
    cut = 0
    # print('i:', i)
    yoko = [0]
    for j in range(n):
        if ((i>>j) & 1):
            yoko.append(j+1)

    cut += len(yoko) - 1
    # tate
    yoko = yoko + [H]
    cnt = [0]*(len(yoko)-1)
    ncnt = [0]*(len(yoko)-1)
    for j in range(W):
        for k, (y1, y2) in enu(zip(yoko[:-1], yoko[1:])):
            ncnt[k] = cumS[y2][j+1] - cumS[y1][j+1]

        for ind, nc in enu(ncnt):
            cnt[ind] += nc
            if K < cnt[ind]:
                cut += 1
                cnt = ncnt.copy()
                break
    #     print(cnt)
    # print(cut)
    cut_min = min(cut_min, cut)
print(cut_min)

Submission status: Runtime Error

Solution code:
# import numpy as np
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]
pl = lambda x: print(*x, sep='\n')
from copy import copy, deepcopy

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

# for h in range(H):
#     for w in range(W):
#         cumS[h+1][w+1] += cumS[h+1][w]
for h in range(H):
    for w in range(W):
        print(h, w)
        cumS[h+1][w+1] += S[h][w]
        cumS[h+1][w+1] += cumS[h][w+1]

n = H-1
cut_min = 10**9
for i in range(2**n):
    cut = 0
    # print('i:', i)
    yoko = [0]
    for j in range(n):
        if ((i>>j) & 1):
            yoko.append(j+1)

    cut += len(yoko) - 1
    # tate
    yoko = yoko + [H]
    cnt = [0]*(len(yoko)-1)
    ncnt = [0]*(len(yoko)-1)
    for j in range(W):
        for k, (y1, y2) in enu(zip(yoko[:-1], yoko[1:])):
            ncnt[k] = cumS[y2][j+1] - cumS[y1][j+1]

        for ind, nc in enu(ncnt):
            cnt[ind] += nc
            if K < cnt[ind]:
                cut += 1
                cnt = ncnt.copy()
                break
    #     print(cnt)
    # print(cut)
    cut_min = min(cut_min, cut)
print(cut_min)

Submission status: Runtime Error

Solution code:
def main():
    import sys
    sys.setrecursionlimit(10**9)
    input = sys.stdin.readline
    INF = 10**9

    H, W, K = map(int, input().split())
    chocolate = [ input()[:-1] for _ in range(H) ]
    
    loop_H = range(H)
    loop_W = range(W)
    white_chocolate = [ [0]*(W+1) for _ in range(10) ]
    min_cut = INF-1
    for div in range(1 << (H-1)):
        # 横割りでグループ分け
        group = [[]]
        group_number = 0
        for i in loop_H:
            group[group_number].append(i)
            if div >> i & 1:
                group.append([])
                group_number += 1
        # グループごと白チョコを数える
        for i in loop_W:
            for g in range(group_number+1):
                white_chocolate[g][i] = 0
                for j in group[g]:
                    if chocolate[j][i] == '1':
                        white_chocolate[g][i] += 1
        # 縦に切っていく
        cut = group_number
        zeros = [0] * len(group_number+1)
        now = zeros.copy()
        for w in loop_W:
            for g in range(len(white_chocolate)):
                if white_chocolate[g][w] > K:
                    cut = INF
                    break
                else:
                    now[g] += white_chocolate[g][w]
                if now[g] + white_chocolate[g][w+1] > K:
                    cut += 1
                    now = zeros.copy()
                    break
            if cut == INF:
                break
        if cut < min_cut:
            min_cut = cut
    print(min_cut)

main()

Submission status: Runtime Error

Solution code:
def main():
    import sys
    sys.setrecursionlimit(10**9)
    input = sys.stdin.readline
    INF = 10**9

    H, W, K = map(int, input().split())
    chocolate = [ input()[:-1] for _ in range(H) ]
    
    loop_H = range(H)
    loop_W = range(W)
    white_chocolate = [ [0]*(W+1) for _ in range(group_number+1) ]
    min_cut = INF-1
    for div in range(1 << (H-1)):
        # 横割りでグループ分け
        group = [[]]
        group_number = 0
        for i in loop_H:
            group[group_number].append(i)
            if div >> i & 1:
                group.append([])
                group_number += 1
        # グループごと白チョコを数える
        for i in loop_W:
            for g in range(group_number+1):
                white_chocolate[g][i] = 0
                for j in group[g]:
                    if chocolate[j][i] == '1':
                        white_chocolate[g][i] += 1
        # 縦に切っていく
        cut = group_number
        zeros = [0] * len(white_chocolate)
        now = zeros.copy()
        for w in loop_W:
            for g in range(len(white_chocolate)):
                if white_chocolate[g][w] > K:
                    cut = INF
                    break
                else:
                    now[g] += white_chocolate[g][w]
                if now[g] + white_chocolate[g][w+1] > K:
                    cut += 1
                    now = zeros.copy()
                    break
            if cut == INF:
                break
        if cut < min_cut:
            min_cut = cut
    print(min_cut)

main()

Submission status: Runtime Error

Solution code:
ans = 10**4
H,W,K = map(int,input().split())
chocolate = []
for _ in range(H):
    chocolate.append(list(map(int,input())))
    

for bit in range(2**(H-1)):
    # 先に横に割る
    # 横方向に割ったあとの、縦の和のリストを作る
    i = 0
    new_choco = []
    new_choco.append(chocolate[0])
    for each_bit in range(H-1):
        if((bit>>each_bit)&1):
            i += 1
            new_choco.append(chocolate[each_bit+1])
        else:
            new_choco[i] = [new_choco[i][j]+chocolate[each_bit+1][j] for j in range(W)]
    # そもそも可能かどうか
    possible = True
    #　縦方向に何回割ったか
    count = 0
    
    #最後に割ったところ
    laststop = 0
    for stop in range(1,W+1):
        #左からどん欲に考える
        
        each_ok = True
        for row in new_choco:
            if sum(row[laststop:stop]) > K:
                each_ok = False
                break
        if each_ok:
            maxstop = stop
        else:
            if maxstop!=laststop:
                laststop = stop
                count += 1
            else:
                possible = False
                break
    if possible:
        tmpans = (bin(bit).count('1')+count)
        ans = tmpans if ans > tmpans else ans
print(ans)

Submission status: Runtime Error

Solution code:
ans = 10**4
H,W,K = map(int,input().split())
chocolate = []
for _ in range(H):
    chocolate.append(list(map(int,input())))
    
for bit in range(2**(H-1)):
    i = 0
    new_choco = []
    new_choco.append(chocolate[0])
    for each_bit in range(H-1):
        if((bit>>each_bit)&1):
            i += 1
            new_choco.append(chocolate[each_bit+1])
        else:
            new_choco[i] = [new_choco[i][j]+chocolate[each_bit+1][j] for j in range(W)]
            
    possible = True
    count = 0
    laststop = 0
    for stop in range(1,W+1):
        each_ok = True
        for row in new_choco:
            if sum(row[laststop:stop]) > K:
                each_ok = False
                break
        if each_ok:
            maxstop = stop
        else:
            if maxstop!=laststop:
                laststop = maxstop
                count += 1
            else:
                possible = False
                break
    if possible:
        tmpans = (bin(bit).count('1')+count)
        ans = tmpans if ans > tmpans else ans
print(ans)

Submission status: Runtime Error

Solution code:
ans = 10*4
H,W,K = map(int,input().split())
chocolate = []
for _ in range(H):
    chocolate.append(list(map(int,input())))
    
for bit in range(2**(H-1)):
    i = 0
    new_choco = []
    new_choco.append(chocolate[0])
    for each_bit in range(H-1):
        if((bit>>each_bit)&1):
            i += 1
            new_choco.append(chocolate[each_bit+1])
        else:
            new_choco[i] = [new_choco[i][j]+chocolate[each_bit+1][j] for j in range(W)]
            
    possible = True
    count = 0
    laststop = 0
    for stop in range(1,W+1):
        each_ok = True
        for row in new_choco:
            if sum(row[laststop:stop]) > K:
                each_ok = False
                break
        if each_ok:
            maxstop = stop
        else:
            if maxstop!=laststop:
                laststop = maxstop
                count += 1
            else:
                possible = False
                break
    if possible:
        tmpans = (bin(bit).count('1')+count)
        ans = tmpans if ans > tmpans else ans
print(ans)

Submission status: Runtime Error

Solution code:
ans = 1020
H,W,K = map(int,input().split())
chocolate = []
for _ in range(H):
    chocolate.append(list(map(int,input())))
    
for bit in range(2**(H-1)):
    i = 0
    new_choco = []
    new_choco.append(chocolate[0])
    for each_bit in range(H-1):
        if((bit>>each_bit)&1):
            i += 1
            new_choco.append(chocolate[each_bit+1])
        else:
            new_choco[i] = [new_choco[i][j]+chocolate[each_bit+1][j] for j in range(W)]
            
    possible = True
    count = 0
    laststop = 0
    for stop in range(1,W+1):
        each_ok = True
        for row in new_choco:
            if sum(row[laststop:stop]) > K:
                each_ok = False
                break
        if each_ok:
            maxstop = stop
        else:
            if maxstop!=laststop:
                laststop = maxstop
                count += 1
            else:
                possible = False
                break
    if possible:
        tmpans = (bin(bit).count('1')+count)
        ans = tmpans if ans > tmpans else ans
print(ans)

Submission status: Runtime Error

Solution code:
ans = 1020
H,W,K = map(int,input().split())
chocolate = []
for _ in range(H):
    chocolate.append(list(map(int,input())))
    
for bit in range(2**(H-1)):
    i = 0
    new_choco = []
    new_choco.append(chocolate[0])
    for each_bit in range(H-1):
        if((bit>>each_bit)&1):
            i += 1
            new_choco.append(chocolate[each_bit+1])
        else:
            new_choco[i] = [new_choco[i][j]+chocolate[each_bit+1][j] for j in range(W)]
            
    possible = True
    count = 0
    laststop = 0
    for stop in range(1,W+1):
        each_ok = True
        for row in new_choco:
            if sum(row[laststop:stop]) > K:
                each_ok = False
                break
        if each_ok:
            maxstop = stop
        else:
            if maxstop!=laststop:
                laststop = maxstop
                count += 1
            else:
                possible = False
                break
    if possible:
        tmpans = (bin(bit).count('1')+count)
        ans = tmpans if ans > tmpans else ans
print(ans)

Submission status: Runtime Error

Solution code:
ans = 1020
H,W,K = map(int,input().split())
chocolate = []
for _ in range(H):
    chocolate.append(list(map(int,input())))
    
bit_dic = []
    
for bit in range(2**(H-1)):
    i = 0
    new_choco = []
    new_choco.append(chocolate[0])
    for each_bit in range(H-1):
        if((bit>>each_bit)&1):
            i += 1
            new_choco.append(chocolate[each_bit+1])
        else:
            new_choco[i] = [new_choco[i][j]+chocolate[each_bit+1][j] for j in range(W)]
            
    stoplist = [0]
    possible = True
    for stop in range(1,W+1):
        each_ok = True
        for row in new_choco:
            if sum(row[stoplist[-1]:stop]) > K:
                each_ok = False
                break
        if each_ok:
            maxstop = stop
        else:
            if maxstop!=stoplist[-1]:
                stoplist.append(maxstop)
            else:
                possible = False
                break
    if possible:
        tmpans = (bin(bit).count('1')+len(stoplist)-1)
        ans = tmpans if ans > tmpans else ans
print(ans)

Submission status: Runtime Error

Solution code:
ans = 10**8
H,W,K = map(int,input().split())
chocolate = []
for _ in range(H):
    chocolate.append(list(map(int,input())))
    
bit_dic = []
    
for bit in range(2**(H-1)):
    i = 0
    new_choco = []
    new_choco.append(chocolate[0])
    for each_bit in range(H-1):
        if((bit>>each_bit)&1):
            i += 1
            new_choco.append(chocolate[each_bit+1])
        else:
            new_choco[i] = [new_choco[i][j]+chocolate[each_bit+1][j] for j in range(W)]
            
    stoplist = [0]
    possible = True
    for stop in range(1,W+1):
        each_ok = True
        for row in new_choco:
            if sum(row[stoplist[-1]:stop]) > K:
                each_ok = False
                break
        if each_ok:
            maxstop = stop
        else:
            if maxstop!=stoplist[-1]:
                stoplist.append(maxstop)
            else:
                possible = False
                break
    if possible:
        tmpans = (bin(bit).count('1')+len(stoplist)-1)
        ans = tmpans if ans > tmpans else ans
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque
ans = 10**8
H,W,K = map(int,input().split())
chocolate = []
for _ in range(H):
    chocolate.append(list(map(int,input())))
    
bit_dic = []
    
for bit in range(2**(H-1)):
    i = 0
    new_choco = []
    new_choco.append(chocolate[0])
    for each_bit in range(H-1):
        if((bit>>each_bit)&1):
            i += 1
            new_choco.append(chocolate[each_bit+1])
        else:
            new_choco[i] = [new_choco[i][j]+chocolate[each_bit+1][j] for j in range(W)]
            
    stoplist = [0]
    possible = True
    for stop in range(1,W+1):
        each_ok = True
        for row in new_choco:
            if sum(row[stoplist[-1]:stop]) > K:
                each_ok = False
                break
        if each_ok:
            maxstop = stop
        else:
            if maxstop!=stoplist[-1]:
                stoplist.append(maxstop)
            else:
                possible = False
                break
    if possible:
        tmpans = (bin(bit).count('1')+len(stoplist)-1)
        ans = tmpans if ans > tmpans else ans
print(ans)

Submission status: Runtime Error

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

a = 10**10
for i in range(1 << (h-1)):

    cnt = 0
    d = np.zeros((h, w))
    for j in range(h):
        d[cnt] += chocolate[j]
        if i & (1 << j):
            cnt += 1

    check = np.zeros(cnt+1)
    flg = False
    ans = 0
    for j in range(w):
        if not all(check <= K):
            flg = True
            break
        check += d[:, j]
        if not all(check <= K):
            ans += 1
            check = d[:, j]

    if flg:
        continue

    a = min(a, ans+cnt)

print(a)

Submission status: Runtime Error

Solution code:
h,*s=open(0)
h,w,k,*m=map(int,h.split())
b=512
while b:
  b-=1;r=t=j=0;d=[0]*h
  while w-j:
    i=c=0
    while h-i:
      d[c]+=s[i][j]>'0';f=d[c]>k
      if(t<j)&f: r+=1;t=j;d[0]*h;break
      r+=h*w*f;c+=b>>i&1;i+=1
    else:j+=1;v=c
  m+=r+v
print(min(m))

Submission status: Runtime Error

Solution code:
x,*s=open(0)
h,w,k,*m=map(int,x.split())
for b in range(512):
  r=t=j=0;d[0]*h
  while w-j:
    i=c=0
    while(h-i):
      d[c]+=s[i][j]>'0'; x=d[c]>k
      if(t<j)&x:r+=1;t=j;d=[0]*h;break
      r+=h*w*x;c+=b>>i&1;i+=1
      else:j+=1
  m+=r+bin(b).count('1'),
print(min(m))

Submission status: Runtime Error

Solution code:
x,*s=open(0)
h,w,k=map(int,x.split())
p=lambda b:b and(b&1)+p(b>>1)
g=lambda b,j,t,d,i=0,c=0:j==w and~p(b)or i==h and g(b,j+1,t,d)or d.__setitem__(c,d[c]+int(s[i][j]))or d[c]>k and(t<j and-1+g(b,j,j,[0]*h)or h*w)or g(b,j,t,d,i+1,c+(b>>i&1))
print(min(~g(b,0,0,[0]*h)for b in range(512)))

Submission status: Runtime Error

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

ans = float("inf")

for pattern in product([0, 1], repeat = H - 1):
    div = [0] + [i for i, p in enumerate(pattern, 1) if p == 1] + [20]
    rows = []
    for i in range(len(div) - 1):
        rows.append(np.count_nonzero(G[div[i]: div[i + 1]], axis=0)) # 列方向

    tmp_ans = 0
    cnt = [0] * len(rows)
    w = 0
    flag = False

    while w < W:
        for r in range(len(rows)):
            cnt[r] += rows[r][w]
        if np.any(np.array(cnt) > K):
            if w == 0:
                flag = True
                break
            cnt = [0] * len(rows)
            tmp_ans += 1
            w -= 1
        w += 1
    
    if not flag:
        tmp_ans += pattern.count(1)
        ans = min(ans, tmp_ans)

print(ans)

Submission status: Runtime Error

Solution code:
IN = iter(Input.split('\n')).__next__
def input():
    return IN()

# 入力
h, w, k = map(int, input().split())
s = []
for _ in range(h):
    s_ = [int(i) for i in input()]
    s.append(s_)
ans = float("INF")
for i in range(2**(h-1)):
    d = [(i >> j) & 1 for j in range(h-1)]
    count, count_tmp = [0]*(sum(d)+1), [0]*(sum(d)+1)
    ans_, res = 0, 0
    flag = False
    for w_ in range(w):
        count[0] += s[0][w_]
        count_tmp[0] += s[0][w_]
        res += 1
        tmp = 0
        for h_ in range(1, h):
            if d[h_-1]: tmp += 1
            if s[h_][w_]:
                count[tmp] += 1
                count_tmp[tmp] += 1
        for j in count:
            if j > k:
                if res==1:
                    flag = True
                    break
                else:
                    for idx in range(sum(d)+1):
                        count[idx] = count_tmp[idx]
                    ans_ += 1
                    res = 0
                    break
        if flag: break
        count_tmp = [0]*(sum(d)+1)
    ans_ += sum(d)
    ans = min(ans, ans_)
print(ans)