Problem p02733 (python)

Fixed submission:
import numpy as np
import time
import random

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

start = time.time()

# 2**(H-1)通り試す
# 事前に各行のcumsumを取っておくと多分はやい
s2 = [np.cumsum(row, dtype=np.int32) for row in s]

mi = 10 ** 9
seed = [0] * 1000 + [1] * 1000
selected = []

# 全部0
ls = [0]*(H-1)
# numは横線の数
num = 1
tmp = 0

s3 = np.zeros((num, W))
s3[0] = s2[0]
cnt = 0
for i in range(H - 1):
    if ls[i] == 0:
        s3[cnt] += s2[i + 1]
    else:
        cnt += 1
        s3[cnt] = s2[i + 1]
s3 = s3.T

hosei = np.zeros(num)
for w in range(W):
    if np.max(s3[:][w] - hosei) > K:
        tmp += 1
        if w != 0:
            hosei = s3[:][w - 1]
        else:
            tmp = 10 ** 9
if mi > tmp:
    mi = tmp


# 全部1
ls = [1]*(H-1)
# numは横線の数
num = H
tmp = num - 1

s3 = np.zeros((num, W))
s3[0] = s2[0]
cnt = 0
for i in range(H - 1):
    if ls[i] == 0:
        s3[cnt] += s2[i + 1]
    else:
        cnt += 1
        s3[cnt] = s2[i + 1]
s3 = s3.T

hosei = np.zeros(num)
for w in range(W):
    if np.max(s3[:][w] - hosei) > K:
        tmp += 1
        if w != 0:
            hosei = s3[:][w - 1]
        else:
            tmp = 10 ** 9
if mi > tmp:
    mi = tmp
    
while time.time() - start < 1.7:
    t = random.sample(seed, k=H - 1)
    if t in selected:
        continue
    selected.append(t)
    ls = t
    # numは横線の数
    num = sum(ls) + 1
    tmp = num - 1
    
    s3 = np.zeros((num, W))
    s3[0] = s2[0]
    cnt = 0
    for i in range(H - 1):
        if ls[i] == 0:
            s3[cnt] += s2[i + 1]
        else:
            cnt += 1
            s3[cnt] = s2[i + 1]
    s3 = s3.T
    
    hosei = np.zeros(num)
    for w in range(W):
        if np.max(s3[:][w] - hosei) > K:
            tmp += 1
            if w != 0:
                hosei = s3[:][w - 1]
            else:
                tmp = 10 ** 9
    if mi > tmp:
        mi = tmp
z = 0
for row in s:
    z += np.sum(row)
if z <= K:
    mi = 0
print(mi)

Buggy submission (verdict: Runtime Error):
from itertools import product
import numpy as np
import time
import random

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

start = time.time()

# 2**(H-1)通り試す
# 事前に各行のcumsumを取っておくと多分はやい
s2 = [np.cumsum(row, dtype=np.int32) for row in s]

rate = H*W//5
mi = 10 ** 9
seed = [0, 1]
tgt = product(seed, repeat=H-1)
selected = []
# for ls in tgt:
while time.time()-start < 1.9:
    t = random.choices(seed, k=H - 1)
    if t in selected:
        continue
    selected.append(t)
    ls = t
    # numは横線の数
    num = sum(ls)+1
    tmp = num - 1
    
    s3 = np.zeros((num, W))
    s3[0] = s2[0]
    cnt = 0
    for i in range(H - 1):
        if ls[i] == 0:
            s3[cnt] += s2[i + 1]
        else:
            cnt += 1
            s3[cnt] = s2[i + 1]
    s3 = s3.T
    
    hosei = np.zeros(num)
    for w in range(W):
        if np.max(s3[:][w] - hosei) > K:
            tmp += 1
            if w != 0:
                hosei = s3[:][w - 1]
            else:
                tmp = 10 ** 9
    if mi > tmp:
        mi = tmp
z = 0
for row in s:
    z += np.sum(row)
if z <= K:
    mi = 0
print(mi)