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:
import sys
input() = sys.stdin.readline().rstrip()

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

ans = h + w - 2
for i in range(1<<(h-1)):
    l = []
    tmp = s[0]
    for j in range(h-1):
        if i >> j & 1:
            tmp = [tmp[m] + s[j+1][m] for m in range(w)]
        else:
            l.append(tmp)
            tmp = s[j+1]
    l.append(tmp)
    c = [0] * len(l)
    cnt = 0
    flag = False
    j = 0
    while j < w:
        for m in range(len(l)):
            c[m] += l[m][j]
            if c[m] > k:
                flag = True
        if flag:
            c = [0] * len(l)
            cnt += 1
            flag = False
            j -= 1
        j += 1
    ans = min(ans, len(l) + cnt - 1)

print(ans)

Submission status: Runtime Error

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

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

ans = h + w - 2
for i in range(1<<(h-1)):
    l = []
    tmp = s[0]
    for j in range(h-1):
        if i >> j & 1:
            tmp = [tmp[m] + s[j+1][m] for m in range(w)]
        else:
            l.append(tmp)
            tmp = s[j+1]
    l.append(tmp)
    c = [0] * len(l)
    cnt = 0
    flag = False
    j = 0
    while j < w:
        for m in range(len(l)):
            c[m] += l[m][j]
            if c[m] > k:
                flag = True
        if flag:
            c = [0] * len(l)
            cnt += 1
            flag = False
            j -= 1
        j += 1
    ans = min(ans, len(l) + cnt - 1)

print(ans)

Submission status: Runtime Error

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

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

if h == 1:
    j = 0
    c = 0
    cnt = 0
    while j < w:
        c += s[j]
        if c > k:
            flag = True
        if flag:
            c = 0
            cnt += 1
            flag = False
            j -= 1
        j += 1
    print(w + cnt - 1)
    sys.exit()

ans = h + w - 2
for i in range(2**(h-1)):
    l = []
    tmp = s[0]
    for j in range(h-1):
        if i >> j & 1:
            tmp = [tmp[m] + s[j+1][m] for m in range(w)]
        else:
            l.append(tmp)
            tmp = s[j+1]
    l.append(tmp)
    c = [0] * len(l)
    cnt = 0
    flag = False
    j = 0
    while j < w:
        for m in range(len(l)):
            c[m] += l[m][j]
            if c[m] > k:
                flag = True
        if flag:
            c = [0] * len(l)
            cnt += 1
            flag = False
            j -= 1
        j += 1
    ans = min(ans, len(l) + cnt - 1)

print(ans)

Submission status: Runtime Error

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

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

ans = h + w - 2
for i in range(2**(h-1)):
    l = []
    tmp = s[0]
    for j in range(h-1):
        if i >> j & 1:
            tmp = [tmp[m] + s[j+1][m] for m in range(w)]
        else:
            l.append(tmp)
            tmp = s[j+1]
    l.append(tmp)
    c = [0] * len(l)
    cnt = 0
    flag = False
    j = 0
    while j < w:
        for m in range(len(l)):
            c[m] += l[m][j]
            if c[m] > k:
                flag = True
        if flag:
            c = [0] * len(l)
            cnt += 1
            flag = False
            j -= 1
        j += 1
    ans = min(ans, len(l) + cnt - 1)

print(ans)

Submission status: Runtime Error

Solution code:

import heapq
from collections import defaultdict, deque
from math import ceil, factorial, gcd
from itertools import accumulate, permutations
import sys
import bisect


sys.setrecursionlimit(10 ** 7)
INF = float("inf")
MOD = 10 ** 9 + 7

si = lambda: input().strip()
ii = lambda: int(input())
mii = lambda: map(int, input().split())
msi = lambda: map(str, input().split())
lmii = lambda: list(map(int, input().split()))
lmsi = lambda: list(map(str, input().split()))
smii = lambda: sorted(map(int, input().split()))
# ----------

H, W, K = mii()
S = []
for i in range(H):
    S.append(si())

ans = INF
for div in range(1<<(H-1)):
    id = [0] * H
    g = 0
    for i in range(H):
        id[i] = g
        if div >> i & 1:
            g += 1

    c = [[0] * W for _ in range(g+1)]

    for i in range(H):
        for j in range(W):
            if S[i][j] == '1':
                c[id[i]][j] += 1

    now = defaultdict(int)

    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

    num = g
    for j in range(W):
        if not add(j):
            num += 1
            now = defaultdict(int)
            if not add(j):
                num = INF
                break

    ans = min(ans, num)

print(ans)

Submission status: Runtime Error

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
    zero = 0
    key = 1
    for j in range(len(ss)):
        if ss[j] == "0":
            zero += 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)
        
        keykey = 1
        for n in range(zero+1):
            if keykey:
                if now[n] + next[n] > k:
                    now = next
                    cnt += 1
                    keykey = 0
                else:
                    now[n] += next[n]
                    
    if key:ans = min(ans,cnt+zero)
print(ans)

Submission status: Runtime Error

Solution code:
#include<bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < n; i++)
using namespace std;
using ll = long long;

int main(){
    int INF = 1e8;
    int ans = INF;
    int c[10][1005];
    int h,w,k;
    cin >> h >> w >> k;
    vector<string> s(h);
    rep(i,h) cin >> s[i];
    rep(div,1<<(h-1)){
        int g=0;
        vector<int> id(h);
        rep(i,h){
            id[i]=g;
            if(div>>i&1)g++;
        }
        g++;
        
        int num = g-1;
        rep(i,g)rep(j,w) c[i][j]=0;
        rep(i,h)rep(j,w) c[id[i]][j] += (s[i][j]-'0');
        vector<int> now(g);
        
        auto add = [&](int j){
            rep(i,g) now[i] += c [i][j];
            rep(i,g) if(now[i]>k) return false;
            return true;
        };
        rep(j,w){
            if(!add(j)){
                num++;
                now = vector<int>(g);
                if(!add(j)){
                    num = INF;
                    break;
                }
            }
        }
        ans = min(ans,num);
    }
    cout << ans << endl;
	return 0;
}

Submission status: Runtime Error

Solution code:
H,W,K = map(int,input().split(sep=" "))
S = [list(map(int,list(input()))) for i in range(0,H,1)]
minimum = H+W
for sepH in range(0,2**(H-1),1):
    bitcounter = 0
    tmp_sepH = sepH
    while tmp_sepH > 0:
        if tmp_sepH & 1 == 1:
            bitcounter+=1
        tmp_sepH = tmp_sepH//2
    A = [[0 for i in range(0,W,1)] for j in range(0,bitcounter+1,1)]
    index=[[]for i in range(0,bitcounter+1,1)]
    countInd = 0
    for i in range(0,H,1):
        index[countInd].append(i)
        if (sepH >> i) & 1:
            countInd +=1
   
    for j in range(0,bitcounter+1,1):
        for i in range(0,W,1):
            for k in range(0,len(index[j]),1):
                if S[index[j][k]][i] == 1:
                    A[j][i]+=1
    countA=[0 for i in range(0,bitcounter+1,1)]
    sepCounter = 0
    dame = False
    for i in range(0,W,1):
        if i == 0:
        for j in range(0,bitcounter+1,1):
            if A[j][i] > K:
                dame = True
            if countA[j] + A[j][i] > K:
                sepCounter +=1
                j=0
                for i in range(0,bitcounter+1,1):
                    countA[i]=0
                
            countA[j] += A[j][i]

    if bitcounter+sepCounter < minimum and (not dame):
        minimum = bitcounter +sepCounter

print(minimum)

Submission status: Runtime Error

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" * (h - 1 - len(bin(x)[2:])) + bin(x)[2:]


h, w, k = map(int, input().split())
S = []
ans = inf
for i in range(h):
    S.append(input().strip())
# for way_cut in range(1 << (h - 1)):
for way_cut in range(2,3):
    way_cut = two(way_cut)
    number_cut_horizontal = way_cut.count("1")
    number_cut_vertical = 0
    CUT = [-1]
    for i in range(len(way_cut)):
        if way_cut[i] == '1':
            CUT.append(i)
    CUT.append(len(way_cut))
    SUM = [0] * (w)
    PRE = [0] * (w)
    for col in range(w):
        for i in range(1, len(CUT)):
            for between in range(CUT[i - 1] + 1, CUT[i] + 1):
                SUM[i] += 1 if S[between][col] == "1" else 0
        isok = True
        for i in range(1, len(CUT)):
            if PRE[i] + SUM[i] > k:
                isok = False
        if not isok:
            number_cut_vertical += 1
            PRE = copy(SUM)
            SUM = [0]*(w)
            # recheck
            for i in range(1, len(CUT)):
                if PRE[i] > k:
                    number_cut_vertical = inf
                    break
        else:
            for i in range(1, len(CUT)):
                PRE[i] += SUM[i]
                SUM[i] = 0
    ans = min(ans, number_cut_vertical + number_cut_horizontal)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**9)

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

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 = []
        for m in range(h):
            p.append(num%2)
            num >>= 1
        nex = [0 for _ in range(checker+1)]
        for m in range(h):
            nex[p[m]] += s[m][0]
        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
            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: Runtime Error

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 = []
        for m in range(h):
            p.append(num%2)
            num >>= 1
        nex = [0 for _ in range(checker+1)]
        for m in range(h):
            nex[p[m]] += s[m][0]
        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))

Submission status: Runtime Error

Solution code:
import itertools
import numpy as np

H, W, K = map(int, input().split())
grid = np.array([list(map(int, list(input()))) for _ in range(H)], dtype=np.int32)
min_cost = None


for H_div_pattern in itertools.product([0, 1], repeat=H-1):
    H_div_num = [i+1 for i, j in enumerate(H_div_pattern) if j == 1] + [H]
    
    sum_grid = np.zeros((len(H_div_num), W), dtype=np.int32)
    start_H = 0
    for idx, div_num in enumerate(H_div_num):
        for w in range(W):
            sum_grid[idx, w] = np.sum(grid[start_H:div_num, w])
        start_H = div_num
    
    cost = len(H_div_num) - 1
    if (sum_grid > K).any():
        break
    
    block_cost = sum_grid[:, 0]
    for w in range(1, W):
        tmp = sum_grid[:, w] + block_cost
        if (tmp <= K).all():
            block_cost = tmp
        else:
            block_cost = sum_grid[:, w]
            cost += 1
            
        if min_cost is not None and cost >= min_cost:
            break
    
    if min_cost is None or min_cost > cost:
        min_cost = cost

if min_cost is None:
    print(0)
else:
    print(ans)

Submission status: Runtime Error

Solution code:
import itertools
import numpy as np

H, W, K = map(int, input().split())
grid = np.array([list(map(int, list(input()))) for _ in range(H)], dtype=np.int32)
min_cost = None


for H_div_pattern in itertools.product([0, 1], repeat=H-1):
    H_div_num = [i+1 for i, j in enumerate(H_div_pattern) if j == 1] + [H]
    sum_grid = np.zeros((len(H_div_num), W), dtype=np.int32)
    if len(H_div_num) != 0:
        start_H = 0
        for idx, div_num in enumerate(H_div_num):
            for w in range(W):
                sum_grid[idx, w] = np.sum(grid[start_H:div_num, w])
            start_H = div_num
    
    cost = len(H_div_num) - 1
    if (sum_grid > K).any():
        break
    
    block_cost = sum_grid[:, 0]
    for w in range(1, W):
        tmp = sum_grid[:, w] + block_cost
        if (tmp <= K).all():
            block_cost = tmp
        else:
            block_cost = sum_grid[:, w]
            cost += 1
        if cost >= min_cost:
            break
    
    if min_cost is None or min_cost > cost:
        min_cost = cost
    
print(min_cost)

Submission status: Runtime Error

Solution code:
def main():
    import numpy as np
    import sys
    inf = 100100100
    ans = inf
    H, W, K = map(int, input().split())
    S = [0]*H
    for i in range(H):
        s[i] = sys.stdin.readline().strip()
    S = np.array(S)
    for i in range(2**(H-1)):
        group = [0]
        g = 0
        for j in range(H-1):
            if (i >> j) & 1:
                g += 1
            group.append(g)
        group = np.array(group)
        g += 1
        c = np.array([[0]*W]*g)
        for j in range(H):
            for k in range(W):
                c[group[j],k] += S[j,k]
        num = g-1
        now = np.zeros(g)
        def large(now):
            for n in now:
                if n > K:
                    return True
            else:
                return False
        for k in range(W):
            now += c[:,k]
            if large(now):
                now = c[:,k]
                num += 1
                if large(now):
                    num = inf
                    break
        ans = min(ans, num)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def main():
    import copy
    H,W,K=map(int,input().split())
    S=[]
    for _ in range(H):
        S.append([int(x) for x in list(input())])

    ans=(H-1)+(W-1)

    for i in range(2**(H-1)):
        check=[0]*H
        for j in range(H-1):
            if ((i>>j)&1):
                check[j+1]=check[j]+1
            else:
                check[j+1]=check[j]

        g=check[H-1]+1
        A=[0]*g
        c=0
        f=0
        for j in range(W):
            B=[0]*g
            for k in range(H):
                if S[k][j]==1:
                    B[check[k]]+=1
                if B[check[k]]>K:
                    c=10**4
                    f=1
                    break
            if f:
                break
            #print("AB",A,B)
            for l in range(g):
                if B[l]==0:
                    continue
                elif A[l]+B[l]>K:
                    c+=1
                    A=copy.copy(B)
                    break
                else:
                    A[l]+=B[l]
        ans=min(ans,c+g-1)

print(ans)




if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    def divide_choco(bit):
        divrow_num = bin(bit).count("1") + 1  # 割った回数+1
        choco_current: List[List[int]] = [[0] * w for _ in range(divrow_num)]

        row_divided_cur = 0

        for col, piece in enumerate(choco[0]):
            choco_current[0][col] = piece

        for row in range(h - 1):
            if bit >> row & 1:
                row_divided_cur += 1
            for col, piece in enumerate(choco[row + 1]):
                choco_current[row_divided_cur][col] += piece

        return choco_current, divrow_num

    h, w, k = list(map(int, readline().split()))
    choco: List[List[int]] = []

    for i in range(h):
        choco_in = input()
        choco_add = [int(c) for c in choco_in]
        choco.append(choco_add)

    ans = INF

    for bit in range(1 << (h - 1)):
        choco_current, divrow_num = divide_choco(bit)
        choco_cursum = [0] * divrow_num
        is_exceed = False  # 超えてる場合True

        ans_temp = bin(bit).count("1")
        if divrow_num > 1:
            for col in range(w):
                choco_currow = [choco_current[dr][col] for dr in range(divrow_num)]
                for drow, pieces in enumerate(choco_currow):
                    if pieces > k:
                        ans_temp += INF
                    elif choco_cursum[drow] + pieces > k:
                        is_exceed = True

                if is_exceed:
                    choco_cursum = [cc for cc in choco_currow]
                    ans_temp += 1
                    is_exceed = False
                else:
                    choco_cursum = [cc + cs for cc, cs in zip(choco_currow, choco_cursum)]
        else:
            choco_cursum = 0
            for pieces in choco_current[0]:
                if pieces > k:
                    ans_temp += INF
                elif choco_cursum + pieces > k:
                    choco_cursum = pieces
                    ans_temp += 1
                else:
                    choco_cursum = choco_cursum + pieces

        ans = min(ans, ans_temp)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

sum = [[0] * (W+1) for i in range((H+1))]
for i in range(H):
    for j in range(W):
        sum[i+1][j+1] = sum[i][j+1] + sum[i+1][j] - sum[i][j] + (1 if s[i][j] == '1' else 0)

ans = H + W - 2

for ptn in range(1<<H-1): # 2^H - 1 通り
    cand = 0

    sep = [0] # 横方向の分割リスト、ここ天才
    for i in range(H-1):
        if((ptn >> i) & 1): # & を取ることで、上の桁を消せる
            sep.append(i+1)
            cand += 1
    sep.append(H)

    left = 0 # left は直前の分割
    for pos in range(W):
    	cur = [] # cur は今見てるホワイトチョコの個数のリスト

    	# 横方向に分割されている各部分について
    	for i in range(len(sep) - 1):
    		cur.append(sum[sep[i+1]][pos+1] - sum[sep[i+1]][left] - sum[sep[i]][pos+1] + sum[sep[i]][left])

    	if max(cur) > K:
    		if left == pos: # 縦に分割できない場合(一列しかない場合)
    			cand = H * W
    			break
    		else:
    			cand += 1
    			left = pos

    ans = min(ans, cand)

print(ans)

Submission status: Runtime Error

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

sum = [[0] * (W+1) for i in range((H+1))]
for i in range(H):
    for j in range(W):
        sum[i+1][j+1] = sum[i][j+1] + sum[i+1][j] - sum[i][j] + (1 if s[i][j] == '1' else 0)

ans = H + W - 2

for ptn in range(1<<H-1): # 2^H - 1 通り
    cand = 0

    sep = [0] # 横方向の分割リスト、ここ天才
    for i in range(H-1):
        if((ptn >> i) & 1): # & を取ることで、上の桁を消せる
            sep.append(i+1)
            cand += 1
    sep.append(H)

    left = 0 # left は直前の分割
    for pos in range(W):
    	cur = [] # cur は今見てるホワイトチョコの個数のリスト

    	# 横方向に分割されている各部分について
    	for i in range(len(sep) - 1):
    		cur.append(sum[sep[i+1]][pos+1] - sum[sep[i+1]][left] - sum[sep[i]][pos+1] + sum[sep[i]][left])

    	if max(cur) > K:
    		if left == pos: # 縦に分割できない場合(一列しかない場合)
    			cand = H * W
    			break
    		else:
    			cand += 1
    			left = pos

    ans = min(ans, cand)

   print(ans)

Submission status: Runtime Error

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

from itertools import product
ans = [0]*(2**(h-1))

for idx,cond in enumerate(product((True,False),repeat=h-1)):
    div = sum(cond)
    spl = [arr[0][:]]
    for i in range(h-1):
        if h_cond[i]:
            spl.append(arr[i+1][:])
        else:
            spl[-1] = [spl[-1][j] + arr[i+1][j] for j in range(w)]
    num = len(spl)
    cnt = [0]*num
    
    for v in range(w):
        tmp = [spl[i][v] for i in range(num)]
        if max(tmp) > k:
            break
        if max([cnt[i] + tmp[i] for i in range(num)]) > k:
            div += 1
            cnt = tmp[:]
        else:
            cnt  = [cnt[i] + tmp[i] for i in range(num)]
    else:    
        ans = min(ans,div)
            
print(min(ans))

Submission status: Runtime Error

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

# H <= 10であるため2^(H-1)を全探索し、
# W <= 1000 については貪欲に左から探索していけば良い

'''
3 5 4
11100
10001
00111
'''

import numpy as np


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

# multiple = 100
# multiple_H = 3
# W *= multiple
# H *= multiple_H

data = np.array([[None] * W for _ in range(H)])

for i in range(H):
    temp = input()
    for j in range(W):
        data[i, j] = int(temp[j])

# print(data)

current_best = np.inf

# Hに関する全ての場合を試す
for cnt in range(2 ** (H-1)):
    # bitで1の場所が切れ目とする
    option_h = np.array([int(s) for s in list(bin(cnt))[2:][::-1]])
    kireme = np.where(option_h == 1)[0]

    # 各グループについて1の数を集計する
    li = 0
    g = np.array([[None] * W for _ in range(len(kireme) + 1)])
    if len(kireme) == 0:
        g[0] = data[li:, :].sum(axis=0)
    else:
        for cnt, j in enumerate(kireme):
            g[cnt] = data[li:j+1, :].sum(axis=0)
            li = j + 1
        g[-1] = data[li:, :].sum(axis=0)

    # 左から順に足していく
    score = len(kireme)
    if score > current_best:
        # すでにこの時点で回数かかっていれば探索打ち切り
        continue
    cnt = np.zeros(len(kireme) + 1)
    for col in range(W):
        cnt = cnt + g[:, col]
        # どこか1つのグループでもKを超えてしまったらその左で切る
        if (cnt > K).any():
            score += 1
            # 最小を求めたいので、それまでの結果と同じ値になってしまったら終了
            if score >= current_best:
                break
            cnt = g[:, col]
            # 現在の列だけで条件を満たせないのであれば不可能なので終了
            if (cnt > K).any():
                score = np.inf
                break
    # スコアの更新
    if score < current_best:
        current_best = score


print(current_best)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from itertools import combinations
import copy
h, w, k = map(int, input().split())
# test splits from 1 -> inf                                                                                                                      
# Horizontally, 10cN                                                                                                                             
# then, we can DP vertical                                                                                                                       

choco = [list(map(int, list(input()))) for i in range(h)]
#print(choco)                                                                                                                                    


def listSum(lists):
    ret = copy.copy(lists[0])
    if len(lists) != 1:
        for i in range(1, len(lists)):
            for j in range(len(lists[i])):
                ret[j] += lists[i][j]
    return ret

def merge(choco, stend):
    ret = []
    for s,e in stend:
        ret.append(listSum(choco[s:e]))
    return ret

def testVertical(merged, vs, k):
    vsTotal = 0
    vsList = []
    last = 0
    tot = defaultdict(int)
    numS = len(merged)
    for j in range(len(merged[0])):
        for i in range(numS):
            if merged[i][j] > k:
                return False
            if merged[i][j] + tot[i] > k:
                vsTotal += 1
                vsList.append(j)
                if vsTotal > vs:
                    return False
                last = j
                break
        for i in range(numS):
            if last == j:
                tot[i] = merged[i][j]
            else:
                tot[i] += merged[i][j]
#    print('vslist', vsList)                                                                                                                     
    return True

def test(choco, hs, vs, k):
    splits = combinations(range(1, h), hs) # split at the end of each row in splits                                                              
    for split in splits:
        sstart = [0] + list(split)
        send = list(split) + [h]
        merged = merge(choco, list(zip(sstart, send)))
	if any(map(any, map(lambda x: x>k, merged))):
            return False
        if testVertical(merged, vs, k):
#            print('passed')                                                                                                                     
#            print('hs', hs)                                                                                                                     
#            print(merged)                                                                                                                       
            return True
    return False

for i in range(0, h+w):
#    print('total', i)                                                                                                                           
    for hs in range(0, min(i+1, h)):
        vs = i-hs
        if test(choco, hs, vs, k):
            print(i)
            exit()

Submission status: Runtime Error

Solution code:
x, y, a, b, c = map(int, input().split())
p = sorted(list(map(int, input().split())))
q = sorted(list(map(int, input().split())))
r = sorted(list(map(int, input().split())))
 
ans = p[-x:] + q[-y:] + sorted(r)

print(str(sum(sorted(ans)[-x-y:])))

Submission status: Runtime Error

Solution code:
x, y, a, b, c = map(int, input().split())
p = sorted(list(map(int, input().split())))
q = sorted(list(map(int, input().split())))
r = sorted(list(map(int, input().split())))

ans = p[-x:] + q[-y:] + sorted(r)

print(sum(sorted(ans)[-x-y:]))

Submission status: Runtime Error

Solution code:
x, y, a, b, c = map(int, input().split())
p = sorted(list(map(int, input().split())))
q = sorted(list(map(int, input().split())))
r = sorted(list(map(int, input().split())))

ans = p[-X:] + q[-Y:] + sorted(r)

print(str(sum(sorted(ans)[-X-Y:])))

Submission status: Runtime Error

Solution code:
X,Y,A,B,C = map(int,input().split())
ps = list(map(int, input().split()))
qs = list(map(int, input().split()))
rs = list(map(int, input().split()))

ans = sorted(qs)[-X:] + sorted(ps)[-Y:] + sorted(rs)

print(str(sum(sorted(ans)[-X-Y:])))