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

Solution (Python):
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 _ in range(h)]
for i in range(h):
    for j in range(w):
        C[i][j] = abs(A[i][j]-B[i][j])

import numpy as np
dp = [[0]*(w+1) for _ in range(h+1)]
import numpy as np
d = 80*(h+w-1)+1
D = 2*d+1
dp[0][0] = np.zeros(D, np.bool)
dp[0][0][C[0][0]+d] = 1

for i in range(h):
    for j in range(w):
        c = C[i][j]
        if i == 0 and j == 0:
            continue
        elif i == 0:
            b = np.zeros(D, np.bool)
            b[c:] |= dp[i][j-1][:D-c]
            b[:D-c] |= dp[i][j-1][c:]
        elif j == 0:
            b = np.zeros(D, np.bool)
            b[c:] |= dp[i-1][j][:D-c]
            b[:D-c] |= dp[i-1][j][c:]
        else:
            b = np.zeros(D, np.bool)
            b[c:] |= dp[i][j-1][:D-c]
            b[:D-c] |= dp[i][j-1][c:]
            b[c:] |= dp[i-1][j][:D-c]
            b[:D-c] |= dp[i-1][j][c:]
        dp[i][j] = b

ans = float('inf')
for i in range(D):
    if dp[h-1][w-1][i]:
        
        ans = min(ans, abs(i-d))
print(ans)

Solution (Python):
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)]
F = 80 * 200 + 100
dp[0][0] = (1 << F)

for h in range(H):
    for w in range(W):
        a = A[h][w]
        b = B[h][w]
        d = dp[h][w]
        dp[h + 1][w] |= (d << abs(a - b)) | (d >> abs(a - b))
        dp[h][w + 1] |= (d << abs(a - b)) | (d >> abs(a - b))

res = dp[H][W - 1] | dp[H - 1][W]
ans = 10**18
for d in range(F * 2):
    if (res & (1 << d)) != 0:
        ans = min(ans, abs(d - F))
print(ans)

Solution (Python):
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=[w*[0]for _ in range(h)]
dp[0][0]=(1<<(80+(a[0][0]-b[0][0])))|(1<<(80+(b[0][0]-a[0][0])))
for i in range(h):
  for j in range(w):
    if i!=0:
      dp[i][j]|=dp[i-1][j]<<(80+(a[i][j]-b[i][j]))
      dp[i][j]|=dp[i-1][j]<<(80+(b[i][j]-a[i][j]))
    if j!=0:
      dp[i][j]|=dp[i][j-1]<<(80+(a[i][j]-b[i][j]))
      dp[i][j]|=dp[i][j-1]<<(80+(b[i][j]-a[i][j]))
ans=1<<50000
for i in range(50000):
  if dp[h-1][w-1]&(1<<i):ans=min(abs(i-(h+w-1)*80),ans)
print(ans)

Solution (Python):
import sys
from collections import deque
def input(): return sys.stdin.readline().strip()


def main():
    H, W = map(int, input().split())
    A = []
    for _ in range(H):
        A.append(list(map(int, input().split())))
    B = []
    for _ in range(H):
        B.append(list(map(int, input().split())))
    
    """
    明らかなdp臭。
        dp[i][j] = (マス(0, 0)から(i, j)に進むときの偏りとしてありうるものの集合)
    とおく。(0<=i<=H-1, 0<=j<=W-1, 0<=d<=80)

    残念ながらPypyだとsetでdp値を保持しているとTLEするので、setではなくビットで偏りの値を管理する
    ただし-diffの方向にビットシフトするとき0桁目以下が切り捨てられてしまうので、最初から適当に
    offsetで桁の水増しをしておく
    """

    offset = 80 * 164

    dp = [[0] * W for _ in range(H)]
    dp[0][0] |= 1 << (A[0][0] - B[0][0] + offset)
    dp[0][0] |= 1 << (B[0][0] - A[0][0] + offset)
    for i in range(1, H):
        diff = abs(A[i][0] - B[i][0])
        dp[i][0] |= dp[i - 1][0] << diff
        dp[i][0] |= dp[i - 1][0] >> diff
    for j in range(1, W):
        diff = abs(A[0][j] - B[0][j])
        dp[0][j] |= dp[0][j - 1] << diff
        dp[0][j] |= dp[0][j - 1] >> diff

    for i in range(1, H):
        for j in range(1, W):
            diff = abs(A[i][j] - B[i][j])
            dp[i][j] |= dp[i - 1][j] << diff
            dp[i][j] |= dp[i - 1][j] >> diff
            dp[i][j] |= dp[i][j - 1] << diff
            dp[i][j] |= dp[i][j - 1] >> diff
    
    ans1 = offset
    while not (dp[H - 1][W - 1] & (1 << ans1)):
        ans1 += 1
    ans2 = offset
    while not (dp[H - 1][W - 1] & (1 << ans2)):
        ans2 -= 1
    print(min(ans1 - offset, offset - ans2))


if __name__ == "__main__":
    main()

Solution (Python):
import sys 
def input():return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10**7)
H,W=map(int,input().split())
A=[[int(x) for x in input().split()] for _ in range(H)]
B=[[int(x) for x in input().split()] for _ in range(H)]
C=[[0] * W for _ in range(H)]
for i in range(H):
    for j in range(W):
        C[i][j]=abs(A[i][j]-B[i][j])
center=80 * (H + W)
dp=[[0]*W for _ in range(H)]
dp[0][0]=(1<<(center - C[0][0]))|(1<<(center+C[0][0]))
for i in range(H):
    for j in range(W):
        if i:
            dp[i][j]|=dp[i-1][j]<<C[i][j]
            dp[i][j]|=dp[i-1][j]>>C[i][j]
        if j:
            dp[i][j]|=dp[i][j-1]<<C[i][j]
            dp[i][j]|=dp[i][j-1]>>C[i][j]            
ans=center*2
for i in range(center*2):
    if (dp[H-1][W-1]>>i)&1:
        ans=min(ans,abs(i-center))
print(ans)

Solution (Python):
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 for j in range(w)] for i in range(h)]
for i in range(h):
    for j in range(w):
        d[i][j] = abs(a[i][j]-b[i][j])

dp = [[0 for _ in range(6400)] for _ in range(h*w)]
dp[0][d[0][0]]=1

for i in range(h*w):
    nowh,noww = divmod(i,w)
    for k in range(6400):
        if not dp[nowh*w + noww][k]==1:
            continue
        nxth,nxtw=nowh+1, noww+1
        if nxtw<w:
            if k+d[nowh][nxtw] < 6400:
                dp[nowh*w + nxtw][k+d[nowh][nxtw]] = 1
            dp[nowh*w + nxtw][abs(k-d[nowh][nxtw])] = 1
        if nxth<h:
            if k+ d[nxth][noww]< 6400:
                dp[nxth*w + noww][k+d[nxth][noww]] = 1
            dp[nxth*w + noww][abs(k-d[nxth][noww])] = 1


for k in range(6400):
    if dp[-1][k]==1:
        print(k)
        exit()

Solution (Python):
import sys
def main():
    input=sys.stdin.readline
    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)]
    ofset = 80*164
    
    dp=[[0 for i in range(w)] for j in range(h)]
    dp[0][0] |= 1 << (a[0][0] - b[0][0] + ofset)
    dp[0][0] |= 1 << (b[0][0] - a[0][0] + ofset)
    for i in range(h):
        for j in range(w):
            if i < h - 1:
                A = abs(a[i+1][j] - b[i+1][j])
                dp[i+1][j] |= (dp[i][j] << A)
                dp[i+1][j] |= (dp[i][j] >> A)
            if j < w - 1:
                A = abs(a[i][j+1] - b[i][j+1])
                dp[i][j+1] |= (dp[i][j] << A)
                dp[i][j+1] |= (dp[i][j] >> A)
    ans = 10000000000
    for i in range(ofset, 80*330):
        if (dp[h-1][w-1]>>i)&1:
            ans = i - ofset
            break
    for i in reversed(range(ofset)):
        if (dp[h-1][w-1]>>i)&1:
            ans = min(ans, ofset - i)
            break
    print(ans)
if __name__=='__main__':
  main()

Solution (Python):
import sys
def main():
    input=sys.stdin.readline
    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)]
    ofset = 80*164
    
    dp=[[0 for i in range(w)] for j in range(h)]
    dp[0][0] |= 1 << (a[0][0] - b[0][0] + ofset)
    dp[0][0] |= 1 << (b[0][0] - a[0][0] + ofset)
    for i in range(h):
        for j in range(w):
            if i < h - 1:
                A = abs(a[i+1][j] - b[i+1][j])
                dp[i+1][j] |= (dp[i][j] << A)
                dp[i+1][j] |= (dp[i][j] >> A)
            if j < w - 1:
                A = abs(a[i][j+1] - b[i][j+1])
                dp[i][j+1] |= (dp[i][j] << A)
                dp[i][j+1] |= (dp[i][j] >> A)
    ans = 10000000000
    for i in range(ofset, 80*330):
        if (dp[h-1][w-1]>>i)&1: ans = min(ans, i - ofset)
    for i in range(ofset):
        if (dp[h-1][w-1]>>i)&1: ans = min(ans, ofset - i)
    print(ans)
if __name__=='__main__':
  main()

Solution (Python):
import sys
def main():
  input=sys.stdin.readline
  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)]
  m=80*162
  flg=(1<<(m*2))-1
  dp=[[0]*w for j in range(h)]
  dp[0][0]|=1<<(a[0][0]-b[0][0]+m)
  dp[0][0]|=1<<(b[0][0]-a[0][0]+m)
  for i in range(h):
    for j in range(w):
      if i<h-1:
        ne=abs(a[i+1][j]-b[i+1][j])
        dp[i+1][j]|=(dp[i][j]<<ne)&flg
        dp[i+1][j]|=(dp[i][j]>>ne)&flg
      if j<w-1:
        ne=abs(a[i][j+1]-b[i][j+1])
        dp[i][j+1]|=(dp[i][j]<<ne)&flg
        dp[i][j+1]|=(dp[i][j]>>ne)&flg
  ans=10**10
  for i in range(160*162):
    if (dp[h-1][w-1]>>i)&1:
      ans=min(ans,abs(i-m)) 
  return print(ans)
if __name__=='__main__':
  main()

Solution (Python):
h,w=map(int,input().split())
A=[[0]*w for i in range(h)]
for i in range(h):
  A[i]=list(map(int,input().split()))
B=[[0]*w for i in range(h)]
for i in range(h):
  B[i]=list(map(int,input().split()))
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])
dp=[[[0]*6401 for j in range(h+1)] for i in range(h+w+1)]
dp[0][0][C[0][0]]=1
for i in range(h+w):
  for j in range(max(0,i-w),min(i,h)+1):
    for k in range(6401):
      if dp[i][j][k]==1:
        if i-j<w-1:
          if k+C[j][i-j+1]<6400:
            dp[i+1][j][k+C[j][i-j+1]]=1
          dp[i+1][j][abs(k-C[j][i-j+1])]=1
        if j<h-1:
          if k+C[j+1][i-j]<6400:
            dp[i+1][j+1][k+C[j+1][i-j]]=1
          dp[i+1][j+1][abs(k-C[j+1][i-j])]=1
for k in range(6400):
  if dp[h+w-2][h-1][k]==1:
    print(k)
    exit()

Solution (Python):
import sys
def main():
    input=sys.stdin.readline
    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)]
    ofset = 80*164
    mask = (1 << (ofset*2)) - 1
    dp=[[0 for i in range(w)] for j in range(h)]
    dp[0][0] |= 1 << (a[0][0] - b[0][0] + ofset)
    dp[0][0] |= 1 << (b[0][0] - a[0][0] + ofset)
    for i in range(h):
        for j in range(w):
            if i < h - 1:
                A = abs(a[i+1][j] - b[i+1][j])
                dp[i+1][j] |= (dp[i][j] << A) & mask
                dp[i+1][j] |= (dp[i][j] >> A) & mask
            if j < w - 1:
                A = abs(a[i][j+1] - b[i][j+1])
                dp[i][j+1] |= (dp[i][j] << A) & mask
                dp[i][j+1] |= (dp[i][j] >> A) & mask
    ans = 10000000000
    for i in range(ofset, 80*330):
        if (dp[h-1][w-1]>>i)&1: ans = min(ans, i - ofset)
    for i in range(ofset):
        if (dp[h-1][w-1]>>i)&1: ans = min(ans, ofset - i)
    print(ans)
if __name__=='__main__':
  main()

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    h, w = list(map(int, readline().split()))
    a = [list(map(int, readline().split())) for _ in range(h)]
    b = [list(map(int, readline().split())) for _ in range(h)]

    diff = [[abs(an - bn) for an, bn in zip(arow, brow)] for arow, brow in zip(a, b)]

    dp = [[1 << (80 * 160 + 1) for _ in range(w)] for _ in range(h)]
    dp[0][0] |= 1 << diff[0][0]

    from itertools import product

    for row, col in product(range(h), range(w)):
        diff_cur = diff[row][col]
        prevset = 0

        if row - 1 >= 0:
            prevset |= dp[row - 1][col]
        if col - 1 >= 0:
            prevset |= dp[row][col - 1]

        dp[row][col] |= (prevset << diff_cur)
        dp[row][col] |= (prevset >> diff_cur)
        temp = 0
        for i in range(diff_cur):
            if prevset >> i & 1:
                temp += (1 << diff_cur - i)
        dp[row][col] |= temp

    for i in range(12801):
        if dp[h - 1][w - 1] >> i & 1:
            print(i)
            sys.exit()


if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 998244353


h, w = LI()
A = LIR(h)
B = LIR(h)
dp = [[0] * w for _ in range(h)]
n = 80 * 160
dp[0][0] = 1 << n + abs(A[0][0] - B[0][0]) | 1 << n - abs(A[0][0] - B[0][0])
for y in range(h):
    for x in range(w):
        if y + 1 < h:
            dp[y + 1][x] |= dp[y][x] >> abs(A[y + 1][x] - B[y + 1][x]) | dp[y][x] << abs(A[y + 1][x] - B[y + 1][x])
        if x + 1 < w:
            dp[y][x + 1] |= dp[y][x] >> abs(A[y][x + 1] - B[y][x + 1]) | dp[y][x] << abs(A[y][x + 1] - B[y][x + 1])


ans = INF
for i in range(n * 2):
    if dp[h - 1][w - 1] >> i & 1:
        ans = min(ans, abs(i - n))

print(ans)

Solution (Python):
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)]

for i in range(h):
    for j in range(w):
        a[i][j] = abs(a[i][j] - b[i][j])

base = 2**12800 - 1
dp = [[0] * (w+1) for _ in range(h+1)]
dp[1][1] = (2**6400 >> a[0][0])|(2**6400 << a[0][0])&base
for i in range(1,h+1):
    for j in range(1,w+1):
        if(i==1)&(j==1):
            dp[1][1] = (2**6400 >> a[0][0])|(2**6400 << a[0][0])&base
            continue

        dp[i][j] = ((dp[i-1][j] >> a[i-1][j-1])|(dp[i-1][j] << a[i-1][j-1])|
                    (dp[i][j-1] >> a[i-1][j-1])|(dp[i][j-1] << a[i-1][j-1]))&base

ans = 6400
ans_bit = dp[-1][-1]
for i in range(6300,6500):
    if((ans_bit >> i)&1 == 1):
        ans = min(ans, abs(6400-i))

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline


h, w = map(int, input().split())
inf = float('INF')
A = []
B = []

for i in range(h):
    line = list(map(int, input().split()))
    A.append(line)

for i in range(h):
    line = list(map(int, input().split()))
    B.append(line)

D = [[0]*w for i in range(h)]
for i in range(h):
    for j in range(w):
        D[i][j] = abs(A[i][j] - B[i][j])


def slide_down(y, x, possible):
    new = set()
    delta = D[y+1][x]
    limit = (h+w) * 80
    for num in possible:
        if num + delta <= limit - (y+x)*80:
            new.add(num+delta)
        if abs(num-delta) <= limit - (y+x)*80:
            new.add(abs(num-delta))
    return new


def slide_right(y, x, possible):
    new = set()
    delta = D[y][x+1]
    limit = (h+w) * 80
    for num in possible:
        if num + delta <= limit - (y+x)*80:
            new.add(num+delta)
        if abs(num-delta) <= limit - (y+x)*80:
            new.add(abs(num-delta))
    return new


DP = [[set() for j in range(w)] for i in range(h)]
DP[0][0] = {D[0][0]}
for row in range(h):
    for col in range(w):
        possible = DP[row][col]
        if col < w-1:
            new = slide_right(row, col, possible)
            DP[row][col+1] |= new
        if row < h-1:
            new = slide_down(row, col, possible)
            DP[row+1][col] |= new

ans = min(DP[h-1][w-1])
print(ans)

Solution (Python):
import numpy as np
def main():
    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)]
    n = 80*(80+80) + 10
    m = n//2
    dp = [[None]*w for i in range(h)]
    for i in range(h):
        for j in range(w):
            dp[i][j] = np.zeros(n, np.bool)
    dp[0][0][m+abs(a[0][0] - b[0][0])] = True
    dp[0][0][m-abs(a[0][0] - b[0][0])] = True
    for i in range(h):
        for j in range(w):
            x = abs(a[i][j] - b[i][j])
            if 0 < i and 0 < h:
                dp[i][j][x:] |= dp[i-1][j][:n-x]
                dp[i][j][:n-x] |= dp[i-1][j][x:]
                dp[i][j][x:] |= dp[i][j-1][:n-x]
                dp[i][j][:n-x] |= dp[i][j-1][x:]
            elif 0 < i:
                dp[i][j][x:] |= dp[i-1][j][:n-x]
                dp[i][j][:n-x] |= dp[i-1][j][x:]
            elif 0 < j:
                dp[i][j][x:] |= dp[i][j-1][:n-x]
                dp[i][j][:n-x] |= dp[i][j-1][x:]
    ans = float("inf")
    for i in range(m-80-1, m+80+2):
        if dp[h-1][w-1][i]:
            ans = min(ans, abs(m-i))
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
import sys

input=sys.stdin.readline

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

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

dp=[[0 for i in range(0,W)] for i in range(0,H)]
if C[0][0]!=0:
    dp[0][0]=pow(2,6400+C[0][0])+pow(2,6400-C[0][0])
else:
    dp[0][0]=pow(2,6400)
for i in range(0,H):
    for j in range(0,W):
        ans1=0
        ans2=0
        if i!=0:
            ans1=(dp[i-1][j]<<C[i][j])|(dp[i-1][j]>>C[i][j])
        if j!=0:
            ans2=(dp[i][j-1]<<C[i][j])|(dp[i][j-1]>>C[i][j])
        if (i,j)!=(0,0):
            dp[i][j]=ans1|ans2

ans=100
for i in range(0,80+1):
    test=100
    if dp[H-1][W-1]>>(6400+i) &1 ==1:
        test=i
    if ans>test:
        ans=test

print(ans)

Solution (Python):
import time
t1 = time.time()
h,w = map(int,input().split())
grid = []
for i in range(h):
    grid.append(list(map(int,input().split())))
for i in range(h):
    lst = list(map(int,input().split()))
    for j in range(w):
        grid[i][j] = abs(grid[i][j]-lst[j])
lst = [[set() for _ in range(w)] for _ in range(h)]
lst[0][0].add(grid[0][0])
for j in range(1,w):
    for x in lst[0][j-1]:
        lst[0][j].add(abs(grid[0][j]-x))
        if (grid[0][j] + x) <= 6400:
            lst[0][j].add(grid[0][j]+x)
for i in range(1,h):
    for x in lst[i-1][0]:
        lst[i][0].add(abs(grid[i][0]-x))
        if grid[i][0] + x <= 6400:
            lst[i][0].add(grid[i][0]+x)
for i in range(1,h):
    for j in range(1,w):
        for x in lst[i][j-1]:
            lst[i][j].add(abs(grid[i][j]-x))
            if grid[i][j] + x <= 6400:
                lst[i][j].add(grid[i][j]+x)
        for x in lst[i-1][j]:
            lst[i][j].add(abs(grid[i][j]-x))
            if grid[i][j] + x <= 6400:
                lst[i][j].add(grid[i][j]+x)
        t = time.time()
        if t - t1 > 1.8:
            print(0)
            exit()
print(min(lst[h-1][w-1]))

Solution (Python):
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

H, W = lr()
A = np.array([lr() for _ in range(H)])
B = np.array([lr() for _ in range(H)])
diff = np.abs(A - B).tolist()

X = (H+W) * 80
L = X + X + 1 
dp = [[np.zeros(L, np.bool) for _ in range(W)] for _ in range(H)]
di = diff[0][0]
dp[0][0][X+di] = 1; dp[0][0][X-di] = 1
for i in range(H):
    for j in range(W):
        if i == 0 and j == 0:
            continue
        di = diff[i][j]
        if i > 0:
            prev = dp[i-1][j]
            dp[i][j][di:] |= prev[:L-di]
            dp[i][j][:L-di] |= prev[di:]
        if j > 0:
            prev = dp[i][j-1]
            dp[i][j][di:] |= prev[:L-di]
            dp[i][j][:L-di] |= prev[di:]

dp = dp[-1][-1][X:]
possible = np.nonzero(dp)[0]
answer = possible.min()
print(answer)

Solution (Python):
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

H, W = lr()
A = np.array([lr() for _ in range(H)])
B = np.array([lr() for _ in range(H)])
diff = np.abs(A - B).tolist()

X = (H+W) * 80
L = X + X + 1 
dp = [[np.zeros(L, np.bool)] * W for _ in range(H)]
dp[0][0] = np.zeros(L, np.bool)
di = diff[0][0]
dp[0][0][X+di] = 1; dp[0][0][X-di] = 1
for h in range(H):
    for w in range(W):
        if h == 0 and w == 0:
            continue
        di = diff[h][w]
        x = np.zeros(L, np.bool)
        if h > 0:
            prev = dp[h-1][w]
            x[di:] |= prev[:L-di]
            x[:L-di] |= prev[di:]
        if w > 0:
            prev = dp[h][w-1]
            x[di:] |= prev[:L-di]
            x[:L-di] |= prev[di:]
        dp[h][w] = x

dp = dp[-1][-1][X:]
possible = np.nonzero(dp)[0]
answer = possible.min()
print(answer)

Solution (Python):
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

H, W = lr()
A = np.array([lr() for _ in range(H)])
B = np.array([lr() for _ in range(H)])
diff = np.abs(A - B).tolist()

X = (H+W) * 80
L = X + X + 1 
dp = [[None] * W for _ in range(H)]
dp[0][0] = np.zeros(L, np.bool)
di = diff[0][0]
dp[0][0][X+di] = 1; dp[0][0][X-di] = 1
for h in range(H):
    for w in range(W):
        if h == 0 and w == 0:
            continue
        di = diff[h][w]
        x = np.zeros(L, np.bool)
        if h > 0:
            prev = dp[h-1][w]
            x[di:] |= prev[:L-di]
            x[:L-di] |= prev[di:]
        if w > 0:
            prev = dp[h][w-1]
            x[di:] |= prev[:L-di]
            x[:L-di] |= prev[di:]
        dp[h][w] = x

dp = dp[-1][-1][X:]
possible = np.nonzero(dp)[0]
answer = possible.min()
print(answer)

Solution (Python):
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

H, W = lr()
A = np.array([lr() for _ in range(H)])
B = np.array([lr() for _ in range(H)])
diff = np.abs(A - B).tolist()

X = (H+W) * 80
L = X + X + 1 
dp = [[None] * W for _ in range(H)]
dp[0][0] = np.zeros(L, np.bool)
dp[0][0][X+diff[0][0]] = 1; dp[0][0][X-diff[0][0]] = 1 
for h in range(H):
    for w in range(W):
        if h == 0 and w == 0:
            continue
        di = diff[h][w]
        x = np.zeros(L, np.bool)
        if h > 0:
            x[di:] |= dp[h-1][w][:L-di]
            x[:L-di] |= dp[h-1][w][di:]
        if w > 0:
            x[di:] |= dp[h][w-1][:L-di]
            x[:L-di] |= dp[h][w-1][di:]
        dp[h][w] = x

dp = dp[-1][-1][X:]
possible = np.where(dp==1)[0]
answer = possible.min()
print(answer)

Solution (Python):
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

H, W = lr()
A = np.array([lr() for _ in range(H)])
B = np.array([lr() for _ in range(H)])
diff = np.abs(A - B)

X = (H+W) * 80
L = X + X + 1 
dp = [[None] * W for _ in range(H)]
dp[0][0] = np.zeros(L, np.bool)
dp[0][0][X+diff[0][0]] = 1; dp[0][0][X-diff[0][0]] = 1 
for h in range(H):
    for w in range(W):
        if h == 0 and w == 0:
            continue
        di = diff[h][w]
        x = np.zeros(L, np.bool)
        if h > 0:
            x[di:] |= dp[h-1][w][:L-di]
            x[:L-di] |= dp[h-1][w][di:]
        if w > 0:
            x[di:] |= dp[h][w-1][:L-di]
            x[:L-di] |= dp[h][w-1][di:]
        dp[h][w] = x

dp = dp[-1][-1][X:]
possible = np.where(dp==1)[0]
answer = possible.min()
print(answer)

Solution (Python):
import sys


def main():
    inp = lambda: list(map(int, input().split())) 
    h,w=inp()
    a=[inp() for _ in range(h)]
    b=[inp() for _ in range(h)]
    d=[[0]*w for _ in range(h)]
    for i in range(h):
        for j in range(w):
            d[i][j]=abs(a[i][j]-b[i][j])
    zero=80*(h+w)+2
    dp=[[0]*w for _ in range(h)]
    dp[0][0]=1<<(zero+d[0][0])|1<<(zero-d[0][0])
    for i in range(h):
        for j in range(w):
            if i==0:
                if j==0:
                    continue
                else:
                    dp[i][j]=dp[i][j-1]<<d[i][j]|dp[i][j-1]>>d[i][j]
            else:
                if j==0:
                    dp[i][j]=dp[i-1][j]<<d[i][j]|dp[i-1][j]>>d[i][j]
                else:
                    dp[i][j]=dp[i-1][j]<<d[i][j]|dp[i-1][j]>>d[i][j]
                    dp[i][j]=dp[i][j]|(dp[i][j-1]<<d[i][j]|dp[i][j-1]>>d[i][j])
    ans=dp[-1][-1]
    for i in range(zero):
        if ans>>(zero+i)&1 or ans>>(zero-i)&1:
            print(i)
            exit()

if __name__ == '__main__':
    main()

Solution (Python):
import sys

def input(): return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10 ** 7)

H, W = map(int, input().split())
A = [[int(x) for x in input().split()] for _ in range(H)]
B = [[int(x) for x in input().split()] for _ in range(H)]
C = [[0] * W for _ in range(H)]
for i in range(H):
    for j in range(W):
        C[i][j] = abs(A[i][j] - B[i][j])
center = 80 * (H+W) 

dp = [[0] *W for _ in range(H)]
dp[0][0] = (1 << (center - C[0][0])) | (1 << (center + C[0][0]))
for i in range(H):
    for j in range(W):
        if i:
            dp[i][j] |= dp[i-1][j] << C[i][j]
            dp[i][j] |= dp[i-1][j] >> C[i][j]
        if j:
            dp[i][j] |= dp[i][j-1] << C[i][j]
            dp[i][j] |= dp[i][j-1] >> C[i][j]
ans = center * 2
for i in range(center*2):
    if (dp[H-1][W-1] >> i) & 1:
        ans = min(ans, abs(i-center))
print(ans)

Solution (Python):
import sys

def input(): return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10 ** 7)

H, W = map(int, input().split())
A = [[int(x) for x in input().split()] for _ in range(H)]
B = [[int(x) for x in input().split()] for _ in range(H)]
C = [[0] * W for _ in range(H)]
for i in range(H):
    for j in range(W):
        C[i][j] = abs(A[i][j] - B[i][j])
center = 80 * (H+W) 

dp = [[0] *W for _ in range(H)]
dp[0][0] = (1 << (center - C[0][0])) | (1 << (center + C[0][0]))
for i in range(H):
    for j in range(W):
        if i:
            dp[i][j] |= dp[i-1][j] << C[i][j]
            dp[i][j] |= dp[i-1][j] >> C[i][j]
        if j:
            dp[i][j] |= dp[i][j-1] << C[i][j]
            dp[i][j] |= dp[i][j-1] >> C[i][j]
ans = center * 2
for i in range(center*2):
    if (dp[H-1][W-1] >> i) & 1:
        ans = min(ans, abs(i-center))
print(ans)

Solution (Python):






import sys
input = sys.stdin.readline

import math
from collections import deque
from fractions import gcd
from functools import lru_cache






MOD = 10**9 +7
INF = float('inf')






def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr


def lcm(a, b):
    return a * b // gcd (a, b)





H,W = inputIL()
a = inputILL(H)
b = inputILL(H)

ma = 80*160
    
dp = [[0 for __ in range(W)] for ___ in range(H)]

for i in range(H):
  for j in range(W):
    k = abs(a[i][j]-b[i][j])
    if i|j: 
      m = dp[i-1][j] | dp[i][j-1]
    else:
      m = 1<<ma
    dp[i][j] = (m<<k)|(m>>k)

k = 1<<ma
for i in range(m):
  if dp[-1][-1]&(k<<i) or  dp[-1][-1]&(k>>i):
    print(i)
    exit()

Solution (Python):
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)]

ma = 80*2*80
DP = [[0]*w for i in range(h)]

for i in range(h):
    for j in range(w):
        k = abs(a[i][j]-b[i][j])
        if i|j:
            m = DP[i-1][j]|DP[i][j-1]
        else:
            m = 1<<ma
        DP[i][j] = (m<<k)|(m>>k)

k = 1<<ma
for i in range(ma):
    if DP[-1][-1]&(k>>i) or DP[-1][-1]&(k<<i):
        print(i)
        exit()

Solution (Python):
def x():
	return map(int,input().split())
v=list
c=abs
r=range
h,w=x()
p=v(r(h))
a=[v(x())for i in p]
b=[v(x())for i in p]
m=13120
D=[[[0]*m for i in r(w)]for i in p]
for i in p:
	for j in r(w):
		k=c(a[i][j]-b[i][j])
		if i|j:
			for l in r((i+j+1)*80+1):
				e=c(l-k)
				D[i][j][l]=D[i][j-1][e]|D[i][j-1][l+k]|D[i-1][j][e]|D[i-1][j][l+k]
		else:
			D[i][j][k]=1
print(D[-1][-1].index(1))

Solution (Python):
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)]
m = 13120
DP = [[[0]*m for i in range(w)] for i in range(h)]

for i in range(h):
    for j in range(w):
        k = abs(a[i][j]-b[i][j])
        if i==0 and j==0:
            DP[i][j][k] = 1
        else:
            for l in range((i+j+1)*80+1):
                DP[i][j][l] = DP[i][j-1][abs(l-k)] | DP[i][j-1][l+k] | DP[i-1][j][abs(l-k)] | DP[i-1][j][l+k]
print(DP[-1][-1].index(1))