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):

import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub


import sys


buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(H, W, A, B):
    C = [[abs(a-b) for a, b in zip(ar, br)] for ar, br in zip(A, B)]

    memo = [[set() for _ in range(W)] for __ in range(H)]
    memo[0][0].add(C[0][0])
    for i in range(H):
        for j in range(W):
            c = C[i][j]
            s = memo[i][j]
            if i > 0:
                for d in memo[i-1][j]:
                    s.add(abs(d + c))
                    s.add(abs(d - c))
            if j > 0:
                for d in memo[i][j-1]:
                    s.add(abs(d + c))
                    s.add(abs(d - c))

    return min(map(abs, memo[H-1][W-1]))




def main():
    H, W = read_int_n()
    A = [read_int_n() for _ in range(H)]
    B = [read_int_n() for _ in range(H)]
    print(slv(H, W, A, B))


if __name__ == '__main__':
    main()

Solution (Python):

import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub


import sys


buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(H, W, A, B):
    C = [[abs(a-b) for a, b in zip(ar, br)] for ar, br in zip(A, B)]

    memo = [[set() for _ in range(W)] for __ in range(H)]
    memo[0][0].add(C[0][0])
    for i in range(H):
        for j in range(W):
            c = C[i][j]
            if i > 0:
                for d in memo[i-1][j]:
                    memo[i][j].add(abs(d + c))
                    memo[i][j].add(abs(d - c))
            if j > 0:
                for d in memo[i][j-1]:
                    memo[i][j].add(abs(d + c))
                    memo[i][j].add(abs(d - c))


    return min(map(abs, memo[H-1][W-1]))




def main():
    H, W = read_int_n()
    A = [read_int_n() for _ in range(H)]
    B = [read_int_n() for _ in range(H)]
    print(slv(H, W, A, B))


if __name__ == '__main__':
    main()

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)]
c=[[abs(a[i][j]-b[i][j]) for j in range(w)]for i in range(h)]
dp=[[0]*(w+1)for _ in range(h+1)]
dp[0][1]=1<<12800
for i in range(1,h+1):
    for j in range(1,w+1):
        t=c[i-1][j-1]
        dp[i][j]=(dp[i][j-1]<<t)|(dp[i][j-1]>>t)|(dp[i-1][j]<<t)|(dp[i-1][j]>>t)
ans=10**20
for i in range(25601):
    if dp[h][w]&(1<<i):
        ans=min(ans,abs(12800-i))
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)]
c=[[abs(a[i][j]-b[i][j]) for j in range(w)]for i in range(h)]
dp=[[0]*(w+1)for _ in range(h+1)]
dp[0][1]=1<<12800
for i in range(1,h+1):
    for j in range(1,w+1):
        t=c[i-1][j-1]
        dp[i][j]=(dp[i][j-1]<<t)|(dp[i][j-1]>>t)|(dp[i-1][j]<<t)|(dp[i-1][j]>>t)
ans=10**20
for i in range(25601):
    if dp[h][w]&(1<<i):
        ans=min(ans,abs(12800-i))
print(ans)

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    H,W = LI()
    A = [LI() for _ in range(H)]
    B = [LI() for _ in range(H)]
    C = [[abs(A[i][j]-B[i][j]) for j in range(W)] for i in range(H)]
    D = [[set() for _ in range(W+1)] for _ in range(H+1)]
    D[0][1] = {0}
    for i in range(1,H+1):
        for j in range(1,W+1):
            for k in D[i-1][j] | D[i][j-1]:
                D[i][j].add(abs(k+C[i-1][j-1]))
                D[i][j].add(abs(k-C[i-1][j-1]))

    print(min(D[-1][-1]))


if __name__ == '__main__':
    main()

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    H,W = LI()
    A = [LI() for _ in range(H)]
    B = [LI() 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])
    D = [[set() for _ in range(W+1)] for _ in range(H+1)]
    D[0][1] = {0}
    for i in range(1,H+1):
        for j in range(1,W+1):
            for k in D[i-1][j] | D[i][j-1]:
                D[i][j].add(abs(k+C[i-1][j-1]))
                D[i][j].add(abs(k-C[i-1][j-1]))

    print(min(D[-1][-1]))


if __name__ == '__main__':
    main()

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


C = [[None]*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])

K = 80*(H+W-1)//2 + 1
dp = [[[0]*(K+1) for _ in range(W)] for _ in range(H)]
dp[0][0][C[0][0]] = 1

for i in range(H):
    for j in range(W):
        for k in range(K+1):
            if i and dp[i-1][j][k]:
                if k+C[i][j] < K:
                    dp[i][j][k+C[i][j]] = 1
                dp[i][j][abs(k-C[i][j])] = 1
            if j and dp[i][j-1][k]:
                if k+C[i][j] < K:
                    dp[i][j][k+C[i][j]] = 1
                dp[i][j][abs(k-C[i][j])] = 1

for k in range(K+1):
    res = dp[H-1][W-1][k]
    if res:
        print(k)
        break

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 = []
for arow,brow in zip(A,B):
    C.append([abs(a-b) for a,b in zip(arow,brow)])

ofs = 80*(H+W)
dp = [0] * W
dp[0] = (1<<(ofs+C[0][0])) | (1<<(ofs-C[0][0]))
for j in range(W-1):
    dp[j+1] = (dp[j] << C[0][j+1]) | (dp[j] >> C[0][j+1])

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

ans = ofs*2
for i in range(ofs*2):
    if dp[-1] & (1<<i):
        ans = min(ans, abs(ofs - i))
print(ans)

Solution (Python):
h,w = map(int, input().split())
al = []
bl = []

for _ in range(h):
    row = list(map(int, input().split()))
    al.append(row)

for _ in range(h):
    row = list(map(int, input().split()))
    bl.append(row)


cl = [ [0]*w for _ in range(h) ]
for i in range(h):
    for j in range(w):
        cl[i][j] = abs(al[i][j] - bl[i][j]) 

INF = 10**9
lim = (h+w)*80//2+1

dp = [ [ [False]*(lim+1)  for _ in range(w) ] for _ in range(h) ]

dp[0][0][cl[0][0]] = True

for i in range(h):
    for j in range(w):
        for k in range(0,lim+1):
            if dp[i][j][k] == True:
                if i+1 < h:
                    v = cl[i+1][j]
                    if k+v <= lim: dp[i+1][j][k+v] = True
                    dp[i+1][j][abs(k-v)] = True
                if j+1 < w:
                    v = cl[i][j+1]
                    if k+v <= lim: dp[i][j+1][k+v] = True
                    dp[i][j+1][abs(k-v)] = True


for i,v in enumerate(dp[-1][-1]):
    if v == True:
        print(i)
        break

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()


def main():
    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)]
    abss = [[abs(A[i][j]-B[i][j])for j in range(w)] for i in range(h)]
    dp = [[0]*w for i in range(h)]
    dp[0][0] = 1 << (abss[0][0]+13000)    
    for i in range(h):
        for j in range(w):
            if i != h-1:
                dp[i+1][j] = dp[i+1][j] | dp[i][j] << abss[i +
                                                           1][j] | dp[i][j] >> abss[i+1][j]
            if j != w-1:
                dp[i][j+1] = dp[i][j+1] | dp[i][j] << abss[i][j +
                                                              1] | dp[i][j] >> abss[i][j+1]
    a = 0
    ans = dp[-1][-1]
    while True:
        if (ans & (1 << (13000-a))):
            print(a)
            break
        elif (ans & (1 << (13000+a))):
            print(a)
            break
        a += 1


if __name__ == '__main__':
    main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()


def main():
    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)]
    abss = [[abs(A[i][j]-B[i][j])for j in range(w)] for i in range(h)]
    kmax = 6400
    dp = [[[0]*kmax for j in range(w)]for i in range(h)]
    dp[0][0][abss[0][0]] = 1
    for i in range(h):
        for j in range(w):
            for k in range(kmax):
                if dp[i][j][k] == 1:
                    if i != h-1:
                        dp[i+1][j][abs(k-abss[i+1][j])] = 1
                        if k+abss[i+1][j] < kmax:
                            dp[i+1][j][k+abss[i+1][j]] = 1
                    if j != w-1:
                        dp[i][j+1][abs(k-abss[i][j+1])] = 1
                        if k+abss[i][j+1] < kmax:
                            dp[i][j+1][k+abss[i][j+1]] = 1
    for k in range(kmax):
        if dp[-1][-1][k] == 1:
            print(k)
            break


if __name__ == '__main__':
    main()

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

    h, w = map(int, input().split())
    g = []
    for _ in range(h):
        g.append(list(map(int, input().split())))
    for i in range(h):
        k = list(map(int, input().split()))
        for j in range(w):
            g[i][j] = abs(g[i][j] - k[j])

    m = (h + w) * 40

    if m == 0:
        print(0)
        exit()

    dp = [[False] * m for _ in range(w)]
    dp[0][g[0][0]] = True
    for j in range(1, w):
        for k in range(m):
            if dp[j-1][k]:
                dp[j][abs(k - g[0][j])] = True
                try:
                    dp[j][k + g[0][j]] = True
                except:
                    pass
    
    for i in range(1, h):
        new_dp = [[False] * m for _ in range(w)]
        for k in range(m):
            if dp[0][k]:
                new_dp[0][abs(k - g[i][0])] = True
                try:
                    new_dp[0][k + g[i][0]] = True
                except:
                    pass
        
        for j in range(1, w):
            for k in range(m):
                if new_dp[j-1][k] or dp[j][k]:
                    new_dp[j][abs(k - g[i][j])] = True
                    try:
                        new_dp[j][k + g[i][j]] = True
                    except:
                        pass
        dp = new_dp

    for j in range(m):
        if dp[w-1][j]:
            print(j)
            break

main()

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

    h, w = map(int, input().split())
    g = []
    for _ in range(h):
        g.append(list(map(int, input().split())))
    for i in range(h):
        k = list(map(int, input().split()))
        for j in range(w):
            g[i][j] = abs(g[i][j] - k[j])

    m = (h + w) * 50

    if m == 0:
        print(0)
        exit()

    dp = [[False] * m for _ in range(w)]
    dp[0][g[0][0]] = True
    for j in range(1, w):
        for k in range(m):
            if dp[j-1][k]:
                dp[j][abs(k - g[0][j])] = True
                try:
                    dp[j][k + g[0][j]] = True
                except:
                    pass
    
    for i in range(1, h):
        new_dp = [[False] * m for _ in range(w)]
        for k in range(m):
            if dp[0][k]:
                new_dp[0][abs(k - g[i][0])] = True
                try:
                    new_dp[0][k + g[i][0]] = True
                except:
                    pass
        
        for j in range(1, w):
            for k in range(m):
                if new_dp[j-1][k] or dp[j][k]:
                    new_dp[j][abs(k - g[i][j])] = True
                    try:
                        new_dp[j][k + g[i][j]] = True
                    except:
                        pass
        dp = new_dp

    for j in range(m):
        if dp[w-1][j]:
            print(j)
            break

main()

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

    h, w = map(int, input().split())
    g = []
    for _ in range(h):
        g.append(list(map(int, input().split())))
    for i in range(h):
        k = list(map(int, input().split()))
        for j in range(w):
            g[i][j] = abs(g[i][j] - k[j])

    m = (h + w) * 80

    if m == 0:
        print(0)
        exit()

    dp = [[False] * m for _ in range(w)]
    dp[0][g[0][0]] = True
    for j in range(1, w):
        for k in range(m):
            if dp[j-1][k]:
                dp[j][abs(k - g[0][j])] = True
                dp[j][k + g[0][j]] = True
    
    for i in range(1, h):
        new_dp = [[False] * m for _ in range(w)]
        for k in range(m):
            if dp[0][k]:
                new_dp[0][abs(k - g[i][0])] = True
                new_dp[0][k + g[i][0]] = True
        
        for j in range(1, w):
            for k in range(m):
                if new_dp[j-1][k] or dp[j][k]:
                    new_dp[j][abs(k - g[i][j])] = True
                    new_dp[j][k + g[i][j]] = True
        dp = new_dp

    for j in range(m):
        if dp[w-1][j]:
            print(j)
            break

main()

Solution (Python):
import os
import sys
import numpy as np

def solve(H, W, AB):
    dp = np.zeros((H, W, 13000), dtype=np.int8)
    dp[0, 0, AB[0, 0]] = True
    dp[0, 0, -AB[0, 0]] = True
    for y in range(H):
        for x in range(W):
            ref = dp[y-1][x] | dp[y][x-1]
            ab = AB[y, x]
            for i in range(-6500, 6500):
                if ref[i+ab] or ref[i-ab]:
                    dp[y][x][i] = True
    ans = 1<<60
    for i in range(-6500, 6500):
        if dp[H-1, W-1, i]:
            a = abs(i)
            if a < ans:
                ans = a
    return ans


numba_config = [
    [solve, "i8(i8,i8,i8[:,:])"],
]
if sys.argv[-1] == "ONLINE_JUDGE":
    from numba import njit
    from numba.pycc import CC
    cc = CC("my_module")
    for func, signature in numba_config:
        vars()[func.__name__] = njit(signature)(func)
        cc.export(func.__name__, signature)(func)
    cc.compile()
    exit()
elif os.name == "posix":
    exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
else:
    from numba import njit
    for func, signature in numba_config:
        vars()[func.__name__] = njit(signature, cache=True)(func)
    print("compiled!", file=sys.stderr)



H, W = map(int, input().split())
AB = np.array(sys.stdin.read().split(), dtype=np.int64).reshape(H*2, W)
AB = AB[:H] - AB[H:]
print(solve(H, W, AB))

Solution (Python):
class bitset:
    def __init__(self,minimum):
        self.b=0
        self.pcnt=0
        self.minimum=abs(minimum)
    def merge(self,x):
        self.b|=x
    def add(self,x):
        self.b|=1<<(x+self.minimum)
        self.pcnt+=1
    def remove(self,x):
        self.b^=1<<(x+self.minimum)
        self.pcnt-=1
    def isin(self,x):
        return self.b>>(x+self.minimum)&1
    def shift(self,x):
        return self.b<<x if x>=0 else self.b>>(abs(x))

H,W=map(int,input().split())
G=[list(map(int,input().split())) for i in range(H)]
for i in range(H):
    B=list(map(int,input().split()))
    for j in range(W):
        G[i][j]=abs(G[i][j]-B[j])

Min=80*(H+W)
s=[[bitset(Min) for i in range(W)] for i in range(H)]
s[0][0].add(G[0][0])
s[0][0].add(-G[0][0])

for i in range(H):
    for j in range(W):
        if i<H-1:
            s[i+1][j].merge(s[i][j].shift(G[i+1][j]))
            s[i+1][j].merge(s[i][j].shift(-G[i+1][j]))
        if j<W-1:
            s[i][j+1].merge(s[i][j].shift(G[i][j+1]))
            s[i][j+1].merge(s[i][j].shift(-G[i][j+1]))
ans=10**30
for i in range(-Min,Min+1):
    if s[H-1][W-1].isin(i):
        ans=min(ans,abs(i))
print(ans)

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

def main():
  h, w = map(int, input().split())
  red = [[int(x) for x in input().split()] for _ in range(h)]
  blue = [[int(x) for x in input().split()] for _ in range(h)]
  
  max_dp = 13000
  dp_first = 2**max_dp
  dp = [[0]*(w+1) for _ in range(h+1)]
  
  for i in range(h):
    for j in range(w):
      sub = dp[i][j+1]|dp[i+1][j]
      sub = sub|dp_first if i == j == 0 else sub
      shift = abs(red[i][j]-blue[i][j])
      dp[i+1][j+1] = (sub << shift)|(sub >> shift)
  
  judge = dp[h][w]
  for i in range(max_dp):
    if (judge >> max_dp+i)&1 or (judge >> max_dp-i)&1:
      print(i)
      sys.exit()
  
if __name__ == "__main__":
  main()

Solution (Python):
def max2(x,y):
    return x if x > y else y

H, W = map(int, input().split())
A = []
B = []
ofs = 80*H*W
for _ in range(H):
    A.append(list(map(int, input().split())))
for _ in range(H):
    B.append(list(map(int, input().split())))
d = [[0]*W for _ in range(H)]
for h in range(H):
    for w in range(W):
        d[h][w] = abs(A[h][w]-B[h][w])

dp = [[0 for _ in range(W)] for _ in range(H)]
dp[0][0] = 1<<ofs
dp[0][0] = (dp[0][0]<<d[0][0])|(dp[0][0]>>d[0][0])
for h in range(H):
    for w in range(W):
        if h < H-1:
            dp[h+1][w] |= (dp[h][w]<<d[h+1][w])|(dp[h][w]>>d[h+1][w])
        if w < W-1:
            dp[h][w+1] |= (dp[h][w]<<d[h][w+1])|(dp[h][w]>>d[h][w+1])
res = dp[-1][-1]>>ofs
print((-res&res).bit_length()-1)

Solution (Python):
import numpy as np


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)]

X = (H + W) * 80
L = X + X + 1
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 in range(W):
        a = A[h][w]
        b = B[h][w]
        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)

Solution (Python):
import numpy as np

H, W = map(int, input().split())
As = [list(map(int, input().split())) for _ in range(H)]
Bs = [list(map(int, input().split())) for _ in range(H)]

ds = [[abs(A-B) for A, B in zip(row_A, row_B)] for row_A, row_B in zip(As, Bs)]

size = 100005

dp = np.full((H, W, size), False)
dp[0][0][ds[0][0]] = True
for i in range(H):
    for j in range(W):
        if i+1 < H:
            d = ds[i+1][j]
            dp[i+1][j][d:] = np.logical_or(dp[i][j][:size-d], dp[i+1][j][d:])
            dp[i+1][j][:size-d] = np.logical_or(dp[i][j][d:], dp[i+1][j][:size-d])
            dp[i+1][j][:d+1] = np.logical_or(dp[i][j][d::-1], dp[i+1][j][:d+1])
        if j+1 < W:
            d = ds[i][j+1]
            dp[i][j+1][d:] = np.logical_or(dp[i][j][:size-d], dp[i][j+1][d:])
            dp[i][j+1][:size-d] = np.logical_or(dp[i][j][d:], dp[i][j+1][:size-d])
            dp[i][j+1][:d+1] = np.logical_or(dp[i][j][d::-1], dp[i][j+1][:d+1])

print(np.min(np.where(dp[-1][-1])))

Solution (Python):
import numpy as np

H, W = map(int, input().split())
As = [list(map(int, input().split())) for _ in range(H)]
Bs = [list(map(int, input().split())) for _ in range(H)]

ds = [[abs(A-B) for A, B in zip(row_A, row_B)] for row_A, row_B in zip(As, Bs)]

size = 10005

dp = np.full((H, W, size), False)
dp[0][0][ds[0][0]] = True
for i in range(H):
    for j in range(W):
        if i+1 < H:
            d = ds[i+1][j]
            dp[i+1][j][d:] = np.logical_or(dp[i][j][:size-d], dp[i+1][j][d:])
            dp[i+1][j][:size-d] = np.logical_or(dp[i][j][d:], dp[i+1][j][:size-d])
            dp[i+1][j][:d+1] = np.logical_or(dp[i][j][d::-1], dp[i+1][j][:d+1])
        if j+1 < W:
            d = ds[i][j+1]
            dp[i][j+1][d:] = np.logical_or(dp[i][j][:size-d], dp[i][j+1][d:])
            dp[i][j+1][:size-d] = np.logical_or(dp[i][j][d:], dp[i][j+1][:size-d])
            dp[i][j+1][:d+1] = np.logical_or(dp[i][j][d::-1], dp[i][j+1][:d+1])

print(np.min(np.where(dp[-1][-1])))

Solution (Python):
I = [int(_) for _ in open(0).read().split()]
H, W = I[:2]
A = I[2:2 + H * W]
B = I[2 + H * W:]
D = [abs(a - b) for a, b in zip(A, B)]
dp = [set([])] + [set([0])] + [set([])] * (W - 1)
for h in range(H):
    dpo = dp
    dp = [set([])] + [None] * W
    for w, d in enumerate(D[W * h:W * (h + 1)]):
        s = dp[w] | dpo[w + 1]
        dp[w + 1] = {v + d for v in s} | {abs(v - d) for v in s}
print(min(dp[-1]))

Solution (Python):
I = [int(_) for _ in open(0).read().split()]
H, W = I[:2]
A = I[2:2 + H * W]
B = I[2 + H * W:]
D = [abs(a - b) for a, b in zip(A, B)]
dp = [set([])] + [set([0])] + [set([])] * (W - 1)
for h in range(H):
    dpo = dp
    dp = [set([])] * (W + 1)
    for w, d in enumerate(D[W * h:W * (h + 1)]):
        s = dp[w] | dpo[w + 1]
        dp[w + 1] = {v + d for v in s} | {abs(v - d) for v in s}
print(min(dp[-1]))

Solution (Python):
I = [int(_) for _ in open(0).read().split()]
H, W = I[:2]
A = I[2:2 + H * W]
B = I[2 + H * W:]
D = [abs(a - b) for a, b in zip(A, B)]
dp = [0] + [1] + [0] * (W - 1)
for h in range(H):
    dpo = dp
    dp = [0] * (W + 1)
    for w, d in enumerate(D[W * h:W * (h + 1)]):
        s = dp[w] | dpo[w + 1]
        dp[w + 1] = (s << d) | (s >> d)
        t = bin(s)[2:][::-1][:d + 1]
        t += '0' * (d + 1 - len(t))
        dp[w + 1] |= int(t, 2)
for i in range(160 * 80):
    if dp[-1] & 2**i:
        print(i)
        exit()

Solution (Python):
I = [int(_) for _ in open(0).read().split()]
H, W = I[:2]
A = I[2:2 + H * W]
B = I[2 + H * W:]
D = [abs(a - b) for a, b in zip(A, B)]
dp = [0] + [1] + [0] * (W - 1)
for h in range(H):
    dpo = dp
    dp = [0] * (W + 1)
    for w, d in enumerate(D[W * h:W * (h + 1)]):
        s = dp[w] | dpo[w + 1]
        dp[w + 1] = (s << d) | (s >> d)
        if d:
            t = bin(s)[2:][::-1][:d + 1]
            t += '0' * (d + 1 - len(t))
            dp[w + 1] |= int(t, 2)
for i in range(160 * 80):
    if dp[-1] & 2**i:
        print(i)
        exit()

Solution (Python):
import sys
read = sys.stdin.buffer.read
input = sys.stdin.buffer.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)]

ab = [[0]*w for i in range(h)]
for ch in range(h):
    for cw in range(w):
        ab[ch][cw] = abs(a[ch][cw] - b[ch][cw])

ab0 = ab[0][0]
size = 80*(h+w)
dp = [[0]*w for hh in range(h)]
dp[0][0] |= 2**(size + ab0)
dp[0][0] |= 2**(size - ab0)
for ch in range(h):
    for cw in range(w):
        if ch < h-1:
            dp[ch+1][cw] |= dp[ch][cw] << ab[ch+1][cw]
            dp[ch+1][cw] |= dp[ch][cw] >> ab[ch+1][cw]
        if cw < w-1:
            dp[ch][cw+1] |= dp[ch][cw] << ab[ch][cw+1]
            dp[ch][cw+1] |= dp[ch][cw] >> ab[ch][cw+1]

a = dp[h-1][w-1]>>size
m = a&(-a)
print(m.bit_length()-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)]

ab = [[0]*w for i in range(h)]
for ch in range(h):
    for cw in range(w):
        ab[ch][cw] = abs(a[ch][cw] - b[ch][cw])

ab0 = ab[0][0]
size = 80*(h+w)
dp = [[0]*w for hh in range(h)]
dp[0][0] |= 2**(size + ab0)
dp[0][0] |= 2**(size - ab0)
for ch in range(h):
    for cw in range(w):
        if ch < h-1:
            dp[ch+1][cw] |= dp[ch][cw] << ab[ch+1][cw]
            dp[ch+1][cw] |= dp[ch][cw] >> ab[ch+1][cw]
        if cw < w-1:
            dp[ch][cw+1] |= dp[ch][cw] << ab[ch][cw+1]
            dp[ch][cw+1] |= dp[ch][cw] >> ab[ch][cw+1]

a = dp[h-1][w-1]>>size
m = a&(-a)
print(m.bit_length()-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)]

ab = [[0]*w for i in range(h)]
for ch in range(h):
    for cw in range(w):
        ab[ch][cw] = abs(a[ch][cw] - b[ch][cw])

ab0 = ab[0][0]
size = 80*(h+w)
dp = [[0]*w for hh in range(h)]
dp[0][0] |= 2**(size + ab0)
dp[0][0] |= 2**(size - ab0)
for ch in range(h):
    for cw in range(w):
        if ch < h-1:
            dp[ch+1][cw] |= dp[ch][cw] << ab[ch+1][cw]
            dp[ch+1][cw] |= dp[ch][cw] >> ab[ch+1][cw]
        if cw < w-1:
            dp[ch][cw+1] |= dp[ch][cw] << ab[ch][cw+1]
            dp[ch][cw+1] |= dp[ch][cw] >> ab[ch][cw+1]

a = dp[h-1][w-1]>>size
m = a&(-a)
print(m.bit_length()-1)

Solution (Python):
H,W=map(int,input().split())
A,B=[],[]
for i in range(H):
  X=list(map(int, input().split()))
  A.append(X)
for i in range(H):
  X=list(map(int, input().split()))
  B.append(X)
C=[]
m=0
for i in range(H):
  D=[]
  for j in range(W):
    D.append(abs(A[i][j]-B[i][j]))
    m+=abs(A[i][j]-B[i][j])
  C.append(D)
dp=[[set() for i in range(W)] for i in range(H)]
dp[0][0].add(C[0][0])
dp[0][0].add(-C[0][0])
for i in range(H):
  for j in range(W):
    if i!=0:
      for k in dp[i-1][j]:
        dp[i][j].add(abs(k-C[i][j]))
        dp[i][j].add(abs(k+C[i][j]))
    if j!=0:
      for k in dp[i][j-1]:
        dp[i][j].add(abs(k-C[i][j]))
        dp[i][j].add(abs(k+C[i][j]))
print(min(dp[-1][-1]))

Solution (Python):
import sys
import math
import bisect
import heapq


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


def main():
    H, W = map(int, input().split())
    A = [[0] * W for _ in range(H)]
    for i in range(H):
        a = list(map(int, input().split()))
        A[i] = a

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

    dp = [[set() for i in range(W)] for i in range(H)]
    
    dp[0][0].add(A[0][0])

    for i in range(H):
        for j in range(W):
            if i != 0:
                for k in dp[i-1][j]:
                    dp[i][j].add(abs(k - A[i][j]))
                    dp[i][j].add(abs(k + A[i][j]))
            if j != 0:
                for k in dp[i][j-1]:
                    dp[i][j].add(abs(k - A[i][j]))
                    dp[i][j].add(abs(k + A[i][j]))

    print(min(dp[H-1][W-1]))


if __name__ == "__main__":
    main()

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


h,w = list(map(int, input().split()))
n = h*w
a = [None]*h
b = [None]*h
for i in range(h):
    a[i] = list(map(int, input().split()))
for i in range(h):
    b[i] = list(map(int, input().split()))


dp = [[None]*(w) for _ in range(h)]
mask = (1<<12800)-1
m = 6400
dp[0][0] = 1<<(a[0][0]-b[0][0]+m) | 1<<(b[0][0]-a[0][0]+m)
for i in range(h):
    for j in range(w):
        if i==j==0:
            continue
        v = abs(a[i][j]-b[i][j])
        bit = 0
        if i>0:
            bit |= (dp[i-1][j]<<v)&mask
            bit |= (dp[i-1][j]>>v)
        if j>0:
            bit |= (dp[i][j-1]<<v)&mask
            bit |= (dp[i][j-1]>>v)
        dp[i][j] = bit

ans = min(abs(val-m) for val in range(12800) if dp[h-1][w-1]>>val&1)
print(ans)