Contest Duration: - (local time) (100 minutes) Back to Home

Submission #11126752

Source Code Expand

Copy
```#!/usr/bin/ python3.8
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
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)))
print(answer)
```

Submission Info

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

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
 AC × 3
 AC × 19
Set Name Test Cases
Sample sample_01, sample_02, sample_03
All 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
Case Name Status Exec Time Memory
max_01 AC 641 ms 55516 KB
max_02 AC 270 ms 45148 KB
max_03 AC 639 ms 55260 KB
max_04 AC 642 ms 55132 KB
max_05 AC 652 ms 56668 KB
max_06 AC 270 ms 45148 KB
random_01 AC 203 ms 42220 KB
random_02 AC 242 ms 43996 KB
random_03 AC 345 ms 46300 KB
random_04 AC 226 ms 44252 KB
random_05 AC 316 ms 46812 KB
random_06 AC 196 ms 40944 KB
random_07 AC 206 ms 42716 KB
random_08 AC 228 ms 42860 KB
random_09 AC 334 ms 46044 KB
random_10 AC 222 ms 44124 KB
sample_01 AC 168 ms 38256 KB
sample_02 AC 167 ms 38256 KB
sample_03 AC 168 ms 38256 KB