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

Submission #8873191

Source Code Expand

Copy
```import sys

A = [list(map(int,readline().split())) for _ in range(H)]
B = [list(map(int,readline().split())) for _ in range(H)]

X = (H + W) * 80
# X点持った状態から始める
dp = [[0] * W for _ in range(H)]
d = abs(A[0][0] - B[0][0])
dp[0][0] = (1 << (X - d))
for h in range(H):
for w,(a,b) in enumerate(zip(A[h],B[h])):
if h == w == 0:
continue
d = abs(a - b)
x = 0
if h != 0:
x |= (dp[h-1][w] << d)
x |= (dp[h-1][w] >> d)
if w != 0:
x |= (dp[h][w-1] << d)
x |= (dp[h][w-1] >> d)
dp[h][w] = x

dp = dp[-1][-1]

B = bin(dp)[2:]
can_make = [i - X for i,b in enumerate(B[::-1]) if b == '1']

answer = min(x if x >= 0 else -x for x in can_make)

Submission Info

Submission Time 2019-12-08 23:46:35+0900 E - Balanced Path maspy Python (3.4.3) 500 951 Byte AC 82 ms 20724 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
 AC × 2
 AC × 25
Set Name Test Cases
Sample sample_01, sample_02
All hand_01, hand_02, hand_03, hand_04, hand_05, hand_06, max_01, max_02, max_03, max_04, max_05, random_01, random_02, random_03, random_04, random_05, random_06, random_07, random_08, random_09, random_10, random_11, random_12, sample_01, sample_02
Case Name Status Exec Time Memory
hand_01 AC 61 ms 14196 KB
hand_02 AC 62 ms 14452 KB
hand_03 AC 63 ms 14452 KB
hand_04 AC 63 ms 14196 KB
hand_05 AC 62 ms 14196 KB
hand_06 AC 62 ms 14452 KB
max_01 AC 72 ms 17140 KB
max_02 AC 62 ms 14196 KB
max_03 AC 62 ms 13940 KB
max_04 AC 61 ms 14196 KB
max_05 AC 80 ms 20212 KB
random_01 AC 41 ms 8308 KB
random_02 AC 40 ms 8180 KB
random_03 AC 45 ms 9588 KB
random_04 AC 42 ms 8692 KB
random_05 AC 31 ms 5748 KB
random_06 AC 82 ms 20724 KB
random_07 AC 82 ms 20724 KB
random_08 AC 82 ms 20724 KB
random_09 AC 82 ms 20724 KB
random_10 AC 82 ms 20724 KB
random_11 AC 80 ms 20084 KB
random_12 AC 80 ms 20084 KB
sample_01 AC 17 ms 3064 KB
sample_02 AC 17 ms 3064 KB