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:
h,w=map(int,input().split())
A=[]
B=[]
for i in range(h):
    A.append([int(i) for i in input().split()])
for i in range(h):
    B.append([int(i) for i in input().split()])

for i in range(h):
    A[i]=[abs(A[i][q]-B[i][q]) for q in range(w)]
    

DP=[[[0 for i in range(12801)] for q in range(w)] for r in range(h)]
DP[0][0][A[0][0]]=1

for i in range(h):
    for q in range(w):
        now=DP[i][q]
        if i<h-1:
            nex=DP[i+1][q]
            for r in range(12801):
                if now[r]==1:
                    nxsc=A[i+1][q]
                    nex[abs(r-nxsc)]=1
                    if r+nxsc<12801:
                        nex[r+nxsc]=1
                        
        if q<w-1:
            nex=DP[i][q+1]
            for r in range(12801):
                if now[r]==1:
                    nxsc=A[i][q+1]
                    nex[abs(r-nxsc)]=1
                    if r+nxsc<12801:
                        nex[r+nxsc]=1

las=DP[-1][-1]
ans=12801
for i in range(12800,-1,-1):
    if las[i]==1:
        ans=i
print(ans)

Submission status: Accepted

Solution code:
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)]# 答えから80*(H+W-1)を引く
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

Submission status: Accepted

Solution code:
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] * (13000 * (w + 1)) for _ in range(h + 1)]
dp[1][0] = 1
dp[0][13000] = 1
for i in range(1, h + 1):
    for j in range(1, w + 1):
        x = c[i - 1][j - 1]
        for k in range(13000):
            y = 0
            if k + x <= 12999:
                dp[i][13000 * j + k] |= (dp[i - 1][13000 * j + k + x] | dp[i][13000 * (j - 1) + k + x])
            dp[i][13000 * j + k] |= (dp[i - 1][13000 * j + abs(k - x)] | dp[i][13000 * (j - 1) + abs(k - x)])
for i in range(13000):
    if dp[h][13000 * w + i]:
        ans = i
        print(ans)
        exit()

Submission status: Accepted

Solution code:
'''
研究室PCでの解答
'''
import math
#import numpy as np
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7 #998244353
dir = [(-1,0),(1,0),(0,-1),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"


def main():
    h,w = map(int,ipt().split())
    a = [[int(i) for i in ipt().split()] for j in range(h)]
    b = [[int(i) for i in ipt().split()] for j in range(h)]
    dp = [[set() for j in range(w)] for i in range(h)]

    d = abs(a[0][0]-b[0][0])
    dp[0][0].add(d)
    for i in range(1,h):
        d = a[i][0]-b[i][0]
        for j in dp[i-1][0]:
            dp[i][0].add(abs(j-d))
            dp[i][0].add(abs(j+d))
    for i in range(1,w):
        d = a[0][i]-b[0][i]
        for j in dp[0][i-1]:
            dp[0][i].add(abs(j-d))
            dp[0][i].add(abs(j+d))

    for i in range(1,h):
        for j in range(1,w):
            d = a[i][j]-b[i][j]
            for k in dp[i][j-1]:
                dp[i][j].add(abs(k-d))
                dp[i][j].add(abs(k+d))
            for k in dp[i-1][j]:
                dp[i][j].add(abs(k-d))
                dp[i][j].add(abs(k+d))


    print(min(dp[h-1][w-1]))


    return None

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

def resolve():
    # (O):80（縦最大） × 80（横最大） × 80（各マスの最大の偏り）× 160（最大何回移動する必要があるか）
    H, W = map(int, input().split())
    A = [tuple(map(int, input().split())) for _ in range(H)]
    B = [tuple(map(int, input().split())) for _ in range(H)]
    Sub = [[0] * W for i in range(H)]
    for i in range(H):
        for j in range(W):
            Sub[i][j] = abs(A[i][j] - B[i][j])

    # 移動直前の偏りをkとし、移動先のマス(i, j)
    # についてd = abs(A[i][j] - B[i][j])とした際に、
    # 移動後の偏りを abs(k - d) とするか abs(k + d) とするか」を考えることと同値である。
    # dp[i][j][k] : マス (i, j) までの経路の偏りが k になることがあるか？

    # Bitset演算 (3次元TLE)
    max_k = 80 * (H + W)
    dp = [[0] * W for _ in range(H)]
    dp[0][0] = 1 << (max_k + Sub[0][0]) | 1 << (max_k - Sub[0][0])

    for i in range(H):
        for j in range(W):
            d = Sub[i][j]
            if i:
                dp[i][j] |= dp[i - 1][j] << d | dp[i - 1][j] >> d
            if j:
                dp[i][j] |= dp[i][j - 1] << d | dp[i][j - 1] >> d

    ans = 10 ** 18
    for i in range(max_k * 2 + 1):
        if dp[H - 1][W - 1] & (1 << i):
            ans = min(ans, abs(max_k - i))
    print(ans)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
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
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
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()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
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
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
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()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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: A-Bの絶対値を持つ
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# 80*(H+W-1)の半分を超えるのは無駄
dp = [[[0]*(K+1) for _ in range(W)] for _ in range(H)]# 答えから80*(H+W-1)を引く
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

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

Submission status: Accepted

Solution code:
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 = [ [INF]*6400 for _ in range(h) ]
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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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 compile >>>
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)
# <<< numba compile <<<


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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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