提出 #8873191

---

ソースコード 拡げる

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

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
# 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)
print(answer)

提出情報

ジャッジ結果