Problem:


Score : 500 points

Problem Statement

We have a grid with H horizontal rows and W vertical columns. Let (i,j) denote the square at the i-th row from the top and the j-th column from the left.

The square (i, j) has two numbers A_{ij} and B_{ij} written on it.

First, for each square, Takahashi paints one of the written numbers red and the other blue.

Then, he travels from the square (1, 1) to the square (H, W). In one move, he can move from a square (i, j) to the square (i+1, j) or the square (i, j+1). He must not leave the grid.

Let the unbalancedness be the absolute difference of the sum of red numbers and the sum of blue numbers written on the squares along Takahashi's path, including the squares (1, 1) and (H, W).

Takahashi wants to make the unbalancedness as small as possible by appropriately painting the grid and traveling on it.

Find the minimum unbalancedness possible.

Constraints

2 \leq H \leq 80

2 \leq W \leq 80

0 \leq A_{ij} \leq 80

0 \leq B_{ij} \leq 80

All values in input are integers.

Input

Input is given from Standard Input in the following format:

H W
A_{11} A_{12} \ldots A_{1W}
:
A_{H1} A_{H2} \ldots A_{HW}
B_{11} B_{12} \ldots B_{1W}
:
B_{H1} B_{H2} \ldots B_{HW}

Output

Print the minimum unbalancedness possible.

Sample Input 1

2 2
1 2
3 4
3 4
2 1

Sample Output 1

0

By painting the grid and traveling on it as shown in the figure below, the sum of red numbers and the sum of blue numbers are 3+3+1=7 and 1+2+4=7, respectively, for the unbalancedness of 0.

Sample Input 2

2 3
1 10 80
80 10 1
1 2 3
4 5 6

Sample Output 2

2



Sample input:
2 2
1 2
3 4
3 4
2 1


Sample output:
0

Submission status: Accepted

Solution code:
def e_balanced_path():
    # 参考: https://atcoder.jp/contests/abc147/submissions/8889160
    H, W = [int(i) for i in input().split()]
    A = [[int(i) for i in input().split()] for j in range(H)]
    B = [[int(i) for i in input().split()] for j in range(H)]

    # ビット列で集合を表現する場合、負の数をうまく扱えないので、バイアスをかける
    MAX_DIFF = (H + W) * 80  # 全マスで偏りが80変化するかもしれない

    diff = [[abs(A[i][j] - B[i][j]) for j in range(W)] for i in range(H)]

    # dp[i][j]: マス (i, j) で取りうる偏りの集合をビット列で持つ
    # ただし、ビット列の基準は MAX_DIFF 桁目である
    dp = [[0] * (W + 1) for _ in range(H + 1)]
    # 左上のマスの更に上に、偏り0のマスがあることにする
    # (下から MAX_DIFF 桁目を1にする)
    dp[0][1] = 1 << MAX_DIFF

    for row in range(1, H + 1):
        for col in range(1, W + 1):
            k = diff[row - 1][col - 1]
            # マス (i, j) に対して左のマスで取りうる偏りに ±k したものが
            # マス (i, j) で取りうる偏り
            dp[row][col] |= dp[row][col - 1] << k
            dp[row][col] |= dp[row][col - 1] >> k
            # 上のマスについて同じことを行う
            dp[row][col] |= dp[row - 1][col] << k
            dp[row][col] |= dp[row - 1][col] >> k

    ans = MAX_DIFF
    # 右下のマスで取りうる偏りを抽出し、絶対値が0に最も近いもの
    # (1が立っているビットのうち、最も MAX_DIFF 桁目に近いもの) が解
    for k in range(2 * MAX_DIFF + 1):
        if (dp[H][W] >> k) & 1:
            # 下から k ビット目が1なら、|k - MAX_DIFF| の偏りを取りうる
            ans = min(ans, abs(k - MAX_DIFF))
    return ans

print(e_balanced_path())

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
h, w = map(int,input().split())
A = [list(map(int,input().split())) for i in range(h)]
B = [list(map(int,input().split())) for i in range(h)]
 
C = [[0] * w for i in range(h)]
for i in range(h):
    for j in range(w):
        C[i][j] = abs(A[i][j]-B[i][j])
 
M = [[0] * w for i in range(h)]
 
s = 0
Q = []
for i in range(h):
    Q.append([i, 0])
for i in range(1, w):
    Q.append([0, i])
for i in range(1, h):
    for j in range(1, w):
        Q.append([i, j])

m = 80
M[0][0] = (1 << m + C[0][0]) | (1 << m - C[0][0])

for s in range(len(Q)):
    i = Q[s][0]
    j = Q[s][1]
    if i+1 < h:
        M[i+1][j] |= (M[i][j] << m + C[i+1][j]) | (M[i][j] << m - C[i+1][j])
    if j+1 < w:
        M[i][j+1] |= (M[i][j] << m + C[i][j+1]) | (M[i][j] << m - C[i][j+1])

        # N[i][j+1] = max(N[i][j+1], N[i][j] + C[i][j+1])
 
# print(M[-1][-1])
b = bin(M[-1][-1])
ans = float("inf")
for i in range(len(b)):
    if b[-1-i] == "1":
        ans = min(ans, abs(i - m*(h+w-1)))
print(ans)

Submission status: Accepted

Solution code:
import itertools
H, W = map(int, input().split())

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

X = (H + W) * 80 # 偏りとしてあり得そうな最大値
# dp[y][x]のn-Xビット目: 上からyマス目、左からxマス目のマスで
# 偏りがnとなり得るか（なり得る場合は1）
dp = [[0] * (W+1) for _ in range(H+1)]

# 左上のマス(dp[1][1])の上のマスに、偏り0があり得るというフラグを立てておく
# (左からXビット目を1にする)
# こうすると、左上から走査を始めるときにX +- abs(A[0][0] - B[i][0])ビット目に
# フラグを立てられる
dp[0][1] = 1 << X

for i in range(1, H + 1):
  for j in range(1, W + 1):
    k = abs(A[i-1][j-1] - B[i-1][j-1]) # マス[i, j]での偏り（の絶対値）
    # 左のマスで取り得る偏りに+-kしたものが、このマスで取り得る偏り
    dp[i][j] |= dp[i][j - 1] << k
    dp[i][j] |= dp[i][j - 1] >> k
    # 上のマスで取り得る偏りに+-kしたものも、このマスで取り得る偏り
    dp[i][j] |= dp[i - 1][j] << k
    dp[i][j] |= dp[i - 1][j] >> k

# print(dp)
ans = X
# 右下のマスで取り得る偏りを抽出し、絶対値が0に最も近いもの
# (1になっているビットの中で最もXビット目に近いもの)を解とする
for k in range(2 * X + 1):
  # 左からkビット目が1だったら、abs(k-X)の偏りが存在し得る
  if (dp[H][W] >> k) & 1:
    ans = min(ans, abs(k - X))

print(ans)

Submission status: Accepted

Solution code:

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

C = [[abs(A[i][j] - B[i][j]) for j in range(W)] for i in range(H)]
M = (H+W)*80

dp = [[0 for j in range(W)] for i in range(H)]

for i in range(H):
    for j in range(W):
        if i == 0:
            if j == 0:
                dp[i][j] = (1 << M) << C[i][j]
            else:
                dp[i][j] |= dp[i][j-1] >> C[i][j]
                dp[i][j] |= dp[i][j-1] << C[i][j]

        else:
            if j != 0:
                dp[i][j] |= dp[i][j-1] >> C[i][j]
                dp[i][j] |= dp[i][j-1] << C[i][j]

            dp[i][j] |= dp[i-1][j] >> C[i][j]
            dp[i][j] |= dp[i-1][j] << C[i][j]

dp = bin(dp[i][j])[2:]
dp = dp[::-1]
ans = M
for i, x in enumerate(dp):
    if x == "1":
        ans = min(ans, abs(i - M))

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
INF = 10**18


def input():
    return sys.stdin.readline().rstrip()


def main():
    H, W = map(int, input().split())
    A = [[] for _ in range(H)]
    B = [[] for _ in range(H)]
    C = [[0] * W for _ in range(H)]
    minusdigit = 80 * 80 * 2
    for i in range(H):
        A[i] = list(map(int, input().split()))
    for i in range(H):
        B[i] = list(map(int, input().split()))
    for i in range(H):
        for j in range(W):
            C[i][j] = abs(A[i][j] - B[i][j])
    dp = [[0] * W for _ in range(H)]
    dp[0][0] = ((1 << minusdigit) << C[0][0]) | ((1 << minusdigit) >> C[0][0])
    for i in range(1, H):
        dp[i][0] = (dp[i - 1][0] << C[i][0]) | (dp[i - 1][0] >> C[i][0])
    for j in range(1, W):
        dp[0][j] = (dp[0][j - 1] << C[0][j]) | (dp[0][j - 1] >> C[0][j])

    for i in range(1, H):
        for j in range(1, W):
            dp[i][j] = (dp[i - 1][j] << C[i][j]) | (dp[i - 1][j] >> C[i][j]) | (dp[i][j - 1] << C[i][j]) | (dp[i][j - 1] >> C[i][j])
    ans = dp[H - 1][W - 1]
    for i in range(len(bin(ans)) - (2 + minusdigit)):
        if (ans >> (i + minusdigit)) & 0b1 == 1 or (-i + minusdigit >= 0 and (ans >> (-i + minusdigit)) & 0b1 == 1):
            print(i)
            exit()


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import numpy as np

    H, W = map(int, input().split())
    A = np.array([[int(x) for x in input().split()] for _ in range(H)])
    B = np.array([[int(x) for x in input().split()] for _ in range(H)])
    D = np.abs(A - B)

    MAX_BIAS_PER_CELL = 80
    UPPER_BOUND_TOTAL_BIAS = MAX_BIAS_PER_CELL * (H + W - 1) + 1

    dp = np.zeros(shape=(H, W, UPPER_BOUND_TOTAL_BIAS * 2 + 1), dtype=np.bool_)
    d = D[0][0]
    dp[0, 0, UPPER_BOUND_TOTAL_BIAS - d] = 1
    dp[0, 0, UPPER_BOUND_TOTAL_BIAS + d] = 1

    for r in range(H):
        for c in range(W):
            d = D[r][c]
            if r > 0:
                dp[r, c, d:] |= dp[r - 1, c, :UPPER_BOUND_TOTAL_BIAS * 2 + 1 - d]
                dp[r, c, :UPPER_BOUND_TOTAL_BIAS * 2 + 1 - d] |= dp[r - 1, c, d:]
            if c > 0:
                dp[r, c, d:] |= dp[r, c - 1, :UPPER_BOUND_TOTAL_BIAS * 2 + 1 - d]
                dp[r, c, :UPPER_BOUND_TOTAL_BIAS * 2 + 1 - d] |= dp[r, c - 1, d:]

    t = dp[H - 1, W - 1, :]
    indices = np.where(t == 1)[0]  # 一次元
    ret = np.abs(indices - UPPER_BOUND_TOTAL_BIAS)
    print(np.min(ret))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def main():
    H, W = map(int, input().split())
    P = W+1
    A = [list(map(int, input().split())) for _ in range(H)]
    B = [list(map(int, input().split())) for _ in range(H)]
    L = 80*80
    dp = [[False]*(L+1) for _ in range((W+1)*(H+1))]
    dp[P+1][abs(A[0][0]-B[0][0])] = True
    
    for h in range(H):
        for w in range(W):
            if h == 0 and w == 0: continue
            c = abs(A[h][w] - B[h][w])
            for l in range(L-c+1):
                b1 = abs(l-c)
                b2 = abs(l+c)
                dp[(h+1)*P+w+1][l] = dp[h*P+w+1][b1] or dp[(h+1)*P+w][b1] or dp[h*P+w+1][b2] or dp[(h+1)*P+w][b2]

    for l in range(L+1):
        if dp[H*P+W][l]:
            print(l)
            break


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
def LI(): return([int(x) for x in sys.stdin.readline().split()])
def main():
    H,W = LI()
    A = [LI() for _ in range(H)]
    B = [LI() for _ in range(H)]
    D = [[abs(A[h][w]-B[h][w]) for w in range(W)] for h in range(H)]
    dp=[[0]*W for _ in range(H)]
    dp[0][0]=1<<D[0][0]<<20000

    for h in range(H):
        for w in range(W):
            if(h>0):
                dp[h][w] |= dp[h-1][w]<<D[h][w]
                dp[h][w] |= dp[h-1][w]>>D[h][w]
            if(w>0):
                dp[h][w] |= dp[h][w-1]<<D[h][w]
                dp[h][w] |= dp[h][w-1]>>D[h][w]
    for i in range(81):
        bit = 1<<(20000+i)
        bit |= 1<<(20000-i)
        if dp[H-1][W-1]&bit:
            return(i)
 
if __name__ == "__main__":
    print(main())

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc147/submissions/8871745
# 写経
# bitset 高速化

def main():
    import numpy as np

    H, W = map(int, input().split())
    A = np.array([[int(x) for x in input().split()] for _ in range(H)])
    B = np.array([[int(x) for x in input().split()] for _ in range(H)])
    D = np.abs(A - B)

    MAX_BIAS_PER_CELL = 80
    UPPER_BOUND_TOTAL_BIAS = MAX_BIAS_PER_CELL * (H + W - 1) + 1

    dp = [[0] * W for _ in range(H)]
    dp[0][0] = 1 << UPPER_BOUND_TOTAL_BIAS
    # dp[r][c]:(r,c)で値の加減を行った後、
    # 達成可能なbiasに該当するbitを立てたbit表現
    # 2**UPPER_BOUND_TOTAL_BIASの位をbias=0とみなす

    # -UPPER_BOUND_TOTAL_BIAS, ..., 0, ...UPPER_BOUND_TOTAL_BIAS [意味するbias]
    # 0, ..., UPPER_BOUND_TOTAL_BIAS, ..., UPPER_BOUND_TOTAL_BIAS*2 [dpに代入されるbit表現の桁]

    # numpyのndarrayを使用しなかった理由
    # dtypeでuint64を採用しても、
    # 2**(UPPER_BOUND_TOTAL_BIAS*2)は収まらない
    # pythonのintなら収まる

    for r in range(H):
        for c in range(W):
            x = dp[r][c]
            if r > 0:
                x |= dp[r - 1][c]
            if c > 0:
                x |= dp[r][c - 1]
            # x:(r,c)到達可能なbiasのbit表現

            d = D[r][c]
            dp[r][c] = (x << d) | (x >> d)
            # (r,c)マスでのbias変化を加味したbit表現

    ret = min(
        abs(UPPER_BOUND_TOTAL_BIAS - shift)
        for shift in range(UPPER_BOUND_TOTAL_BIAS * 2)
        if (dp[H - 1][W - 1] & (1 << shift)) > 0)

    print(ret)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
M = 7000
h, w = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(h)]
b = [list(map(int, input().split())) for _ in range(h)]
dp = [[0] * (w + 1) for _ in range(h + 1)]
dp[0][1] = dp[1][0] = 1 << M
for i in range(h):
    for j in range(w):
        dp[i + 1][j + 1] |= dp[i][j + 1] << abs(a[i][j] - b[i][j])
        dp[i + 1][j + 1] |= dp[i][j + 1] >> abs(a[i][j] - b[i][j])
        dp[i + 1][j + 1] |= dp[i + 1][j] << abs(a[i][j] - b[i][j])
        dp[i + 1][j + 1] |= dp[i + 1][j] >> abs(a[i][j] - b[i][j])
ans = M
for b in range(2 * M + 1):
    if dp[h][w] >> b & 1:
        ans = min(ans, abs(b - M))
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

H,W=map(int,input().split())

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

SA=[[0]*W for i in range(H)]

for i in range(H):
    for j in range(W):
        SA[i][j]=abs(A[i][j]-B[i][j])

DP=[[[0]*6400 for i in range(W)] for j in range(H)]

DP[0][0][SA[0][0]]=1

for i in range(H):
    for j in range(W):
        for k in [l for l in range(6400) if DP[i][j][l]==1]:
            if i+1<H:
                if k+SA[i+1][j]<6400:    
                    DP[i+1][j][k+SA[i+1][j]]=1
                if abs(k-SA[i+1][j])<6400:
                    DP[i+1][j][abs(k-SA[i+1][j])]=1

            if j+1<W:
                if k+SA[i][j+1]<6400:    
                    DP[i][j+1][k+SA[i][j+1]]=1
                if abs(k-SA[i][j+1])<6400:
                    DP[i][j+1][abs(k-SA[i][j+1])]=1

for i in range(6400):
    if DP[-1][-1][i]==1:
        ANS=i
        break

print(ANS)

Submission status: Accepted

Solution code:
import numpy as np
i8 = np.int64
i4 = np.int32


def calc(dp1, dp2, k):
    dp2[k:] |= dp1[:dp1.shape[0]-k]
    dp2[:dp2.shape[0]-k] |= dp1[k:]


def solve(z, dp):
    zero = dp.shape[2] // 2
    dp[0, 0, zero + z[0, 0]] = 1
    dp[0, 0, zero - z[0, 0]] = 1
    for x in range(1, z.shape[1]):
        calc(dp[0, x - 1], dp[0, x], z[0, x])
    for y in range(1, z.shape[0]):
        calc(dp[y - 1, 0], dp[y, 0], z[y, 0])
        for x in range(1, z.shape[1]):
            calc(dp[y, x - 1], dp[y, x], z[y, x])
            calc(dp[y - 1, x], dp[y, x], z[y, x])
    for i in range(zero, dp.shape[2]):
        if dp[dp.shape[0] - 1, dp.shape[1] - 1, i] > 0:
            return i - zero
    return -1


def main():
    stdin = open('/dev/stdin', 'rb')
    pin = np.fromstring(stdin.read(), i8, sep=' ')
    H, W = pin[:2]
    a = pin[2: 2 + H * W].reshape(H, W)
    b = pin[2 + H * W:].reshape(H, W)
    z = np.abs(a - b)
    dp = np.zeros((H, W, 80 * 80 * 2 + 1), i8)
    ans = solve(z, dp)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
H, W = [int(x) for x in input().split()]
 
A = [[0]*W for i in range(H)]
for c in [1, -1]:
    for i in range(H):
        arr = [int(x) for x in input().split()]
        for j in range(W):
            A[i][j] += arr[j] * c
 
M = 160*80
dp = [[0]*W for i in range(H)]
dp[0][0] = 1 << M
for i in range(H):
    for j in range(W):
        if i > 0:
            dp[i][j] |= dp[i-1][j]
        if j > 0:
            dp[i][j] |= dp[i][j-1]
        a = abs(A[i][j])
        dp[i][j] = (dp[i][j] << a) | (dp[i][j] >> a)
 
ans = M
for i in range(2*M):
    if dp[H-1][W-1] & (1 << i) > 0:
        ans = min(ans, abs(M-i))
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#ABC147 E

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

h,w = LI()
a = [LI() for _ in range(h)]
b = [LI() for _ in range(h)]

dp = [[0 for _ in range(w)] for _ in range(h)]
lst = [[0]*w for _ in range(h)]
for i in range(h):
    for j in range(w):
        lst[i][j] = abs(a[i][j] - b[i][j])

dp[0][0] |= 1 << (6400+lst[0][0])
dp[0][0] |= 1 << (6400-lst[0][0])
for i in range(h):
    for j in range(w):
        t = dp[i][j]
        if i+1 < h:
            dp[i+1][j] |= t << lst[i+1][j]
            dp[i+1][j] |= t >> lst[i+1][j]
        if j+1 < w:
            dp[i][j+1] |= t << lst[i][j+1]
            dp[i][j+1] |= t >> lst[i][j+1]

x = dp[-1][-1]
for i in range(6401)[::-1]:
    if (x >> i) & 1:
        print(6400 - i)
        break

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#solve
def solve():
    h, w = LI()
    a = LIR(h)
    b = LIR(h)
    mab = [[abs(a[y][x]-b[y][x]) for x in range(w)] for y in range(h)]
    ab = abs(a[0][0] - b[0][0])
    hw = h + w
    dp = [[0] * w for i in range(h)]
    dp[0][0] |= (1 << (6400 + ab) | 1 << (6400 - ab))
    for i in range(1, h + w - 1):
        for x in range(w):
            y = i - x - 1
            if 0 <= x < w and 0 <= y < h:
                value = dp[y][x]
            else:
                continue
            for mx, my in [[0, 1], [1, 0]]:
                mx += x
                my += y
                if 0 <= mx < w and 0 <= my < h:
                    mxy = mab[my][mx]
                    dp[my][mx] |= ((value << mxy) | (value >> mxy))
    ans = dp[-1][-1]
    for i in range(ans.bit_length()):
        if ans & (1 << (6400-i)):
            print(i)
            return
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, heapq, collections, bisect,copy
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
sys.setrecursionlimit(10**7)
inf = float('inf')
mod = 10**9+7
ans = inf ;count = 0 ;pro = 1

h,w=map(int,input().split())
A=[tuple(map(int,input().split())) for i in range(h)]
B=[tuple(map(int,input().split())) for i in range(h)]
# a=[set() for j in range(w)]
K=160*80
dp = [[0]*w for i in range(h)]
dp[0][0]=1<<K
for i in range(h):
    for j in range(w):
        d=abs(A[i][j]-B[i][j])
        if i-1>=0:
            dp[i][j] |= dp[i-1][j]
        if j-1>=0:
            dp[i][j] |= dp[i][j-1]
        dp[i][j] = (dp[i][j]<<d) | (dp[i][j]>>d)


ans = K
for i in range(2*K):
    if dp[h-1][w-1]  & (1 << i)>0:
        ans = min(ans,abs(K-i))
print(ans)
# for di in dp:
#     print(di)

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
A=[list(map(int,input().split())) for i in range(H)]
B=[list(map(int,input().split())) for i in range(H)]
d=[[0]*W for j in range(H)]
m=80*(H+W)
d[0][0]=1<<m
for h in range(H):
    for w in range(W):
        x=abs(A[h][w]-B[h][w])
        if h>0:
            d[h][w]|=d[h-1][w]
        if w>0:
            d[h][w]|=d[h][w-1]
        d[h][w]=d[h][w]<<x|d[h][w]>>x
x,y=1<<m,1<<m
for i in range(99):
    if d[H-1][W-1]&x or d[H-1][W-1]&y:
        print(i)
        exit()
    x<<=1
    y>>=1

Submission status: Accepted

Solution code:
import numpy as np

H, W = map(int, input().split())
lst1 = []
lst2 = []
for _ in range(H):
    lst1.append([int(i) for i in input().split()])
for _ in range(H):
    lst2.append([int(i) for i in input().split()])
arr1, arr2 = np.array(lst1), np.array(lst2)
arr = np.abs(arr1 - arr2)

d = [[0] * W for _ in range(H)]
m = 80 * (H + W)
d[0][0] = 1 << m
for h in range(H):
    for w in range(W):
        x = arr[h][w]
        if h > 0:
            d[h][w] |= d[h - 1][w]
        if w > 0:
            d[h][w] |= d[h][w - 1]
        d[h][w] = d[h][w] << x | d[h][w] >> x

x, y= 1 << m, 1 << m
for i in range(m + 1):
    if d[H - 1][W - 1] & x or d[H - 1][W - 1] & y:
        print(i)
        quit()
    x<<=1
    y>>=1