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
Task E - Dividing Chocolate
User maspy
Language PyPy3 (2.4.0)
Score 500
Code Size 979 Byte
Status
Exec Time 652 ms
Memory 56668 KB

Test Cases

Set Name Score / Max Score Test Cases
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
Case Name Status Exec Time Memory
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