ソースコード 拡げる

Copy
```#!/usr/bin/ python3.8
import sys
import itertools
H, W, K = map(int, readline().split())
S = [list(map(int, line.rstrip().decode())) for line in readlines()]
# transpose
S = tuple(itertools.chain(*zip(*S)))

INF = 10 ** 9

def solve(s):
dp = list(S)
for j in range(H - 1):
if s & (1 << j):
for n in range(0, H * W, H):
dp[n + j + 1] += dp[n + j]
cut = H - 1 - bin(s).count('1')
for n in range(0, H * W, H):
if any(dp[n + i] > K for i in range(H)):
return INF
if n + H == H * W:
return cut
if any(dp[n + i] + dp[n + i + H] > K for i in range(H)):
cut += 1
continue
for i in range(H):
dp[n + i + H] += dp[n + i]
return cut

answer = min(solve(s) for s in range(1 << (H - 1)))
```

#### 提出情報

提出日時 2020-03-22 22:16:32+0900 E - Dividing Chocolate maspy PyPy3 (2.4.0) 500 979 Byte AC 652 ms 56668 KB

#### ジャッジ結果

セット名 得点 / 配点 テストケース
Sample 0 / 0 sample_01, sample_02, sample_03
All 500 / 500 max_01, max_02, max_03, max_04, max_05, max_06, random_01, random_02, random_03, random_04, random_05, random_06, random_07, random_08, random_09, random_10, sample_01, sample_02, sample_03
ケース名 結果 実行時間 メモリ
max_01 641 ms 55516 KB
max_02 270 ms 45148 KB
max_03 639 ms 55260 KB
max_04 642 ms 55132 KB
max_05 652 ms 56668 KB
max_06 270 ms 45148 KB
random_01 203 ms 42220 KB
random_02 242 ms 43996 KB
random_03 345 ms 46300 KB
random_04 226 ms 44252 KB
random_05 316 ms 46812 KB
random_06 196 ms 40944 KB
random_07 206 ms 42716 KB
random_08 228 ms 42860 KB
random_09 334 ms 46044 KB
random_10 222 ms 44124 KB
sample_01 168 ms 38256 KB
sample_02 167 ms 38256 KB
sample_03 168 ms 38256 KB