Submission #8878906


Source Code Expand

Copy
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import itertools
import numpy as np

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

X = (H + W) * 80
L = X + X + 1
# X点持った状態から始める
dp = [[0] * W for _ in range(H)]
d = abs(A[0][0] - B[0][0])
dp[0][0] = np.zeros(L,np.bool)
dp[0][0][X+d] = 1
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 = np.zeros(L,np.bool)
        if h != 0:
            x[d:] |= dp[h-1][w][:L-d]
            x[:L-d] |= dp[h-1][w][d:]
        if w != 0:
            x[d:] |= dp[h][w-1][:L-d]
            x[:L-d] |= dp[h][w-1][d:]
        dp[h][w] = x

dp = dp[-1][-1]
can_make = np.where(dp)[0] - X

answer = np.abs(can_make).min()
print(answer)

Submission Info

Submission Time
Task E - Balanced Path
User maspy
Language Python (3.4.3)
Score 500
Code Size 989 Byte
Status AC
Exec Time 437 ms
Memory 173476 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 432 ms 173472 KB
hand_02 AC 430 ms 173472 KB
hand_03 AC 437 ms 173472 KB
hand_04 AC 428 ms 173472 KB
hand_05 AC 427 ms 173344 KB
hand_06 AC 437 ms 173344 KB
max_01 AC 430 ms 170400 KB
max_02 AC 434 ms 170400 KB
max_03 AC 423 ms 167456 KB
max_04 AC 434 ms 173472 KB
max_05 AC 433 ms 173344 KB
random_01 AC 271 ms 69024 KB
random_02 AC 265 ms 67232 KB
random_03 AC 295 ms 83232 KB
random_04 AC 278 ms 72864 KB
random_05 AC 216 ms 41120 KB
random_06 AC 431 ms 173476 KB
random_07 AC 433 ms 173472 KB
random_08 AC 433 ms 173472 KB
random_09 AC 431 ms 173472 KB
random_10 AC 426 ms 173344 KB
random_11 AC 427 ms 167456 KB
random_12 AC 430 ms 167456 KB
sample_01 AC 155 ms 12468 KB
sample_02 AC 149 ms 12464 KB