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:
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

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]*ma 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
            continue
        elif i == 0:
            up = min((i+j+1)*80+1, ma-k)
            for l in range(up):
                DP[i][j][l] = DP[i][j-1][abs(l-k)] | DP[i][j-1][l+k]
        elif j == 0:
            for l in range(up):
                DP[i][j][l] = DP[i-1][j][abs(l-k)] | DP[i-1][j][l+k]
        else:
            for l in range(up):
                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]
for i in range(ma):
    if DP[-1][-1][i]:
        print(i)
        exit()

Submission status: Accepted

Solution code:
def main():
    h,w=map(int,input().split())
    L=80*(h+w)+1
    a=[list(map(int,input().split())) for i in range(h)]
    b=[list(map(int,input().split())) for i in range(h)]


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

    L=12800
    
    state=[[0]*w for _ in range(h)]
    delta=x[0][0]
    state[0][0]=(2**L>>delta)|(2**L<<delta)

    for j in range(1,w):
        delta=x[0][j]
        state[0][j]=(state[0][j-1]>>delta)|(state[0][j-1]<<delta)

    for i in range(1,h):
        delta=x[i][0]
        state[i][0]=(state[i-1][0]>>delta)|(state[i-1][0]<<delta)

    for i in range(1,h):
        for j in range(1,w):
            delta=x[i][j]
            state[i][j]=(state[i][j-1]>>delta)|(state[i][j-1]<<delta)
            state[i][j]|=(state[i-1][j]>>delta)|(state[i-1][j]<<delta)

    
    ans = 10**9
    for i in range(L*2):
        if state[h-1][w-1] & 1:
            ans = min(ans,abs(i-L))
        state[h-1][w-1]>>=1
    print(ans)



if __name__ == '__main__':
    main()

Submission status: Accepted

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

# mod=10**9+7
# rstrip().decode('utf-8')
# map(int,input().split())
# 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)]
	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=[[0]*w for _ in range(h)]
	D[0][0]=(1<<C[0][0]+5000)|(1>>C[0][0]+5000)
	for i in range(h):
		for j in range(w):
			if i>0:
				D[i][j]=D[i][j]|(D[i-1][j]<<C[i][j])|(D[i-1][j]>>C[i][j])
			if j>0:
				D[i][j] = D[i][j]|(D[i][j-1] << C[i][j]) | (D[i][j-1] >> C[i][j])

	val=D[-1][-1]
	ans=5000

	for i in range(10000):
		if val>>i&1:
			ans=min(ans,abs(i-5000))
	print(ans)

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
h,w = map(int,input().split())
la = [list(map(int,input().split())) for i in range(h)]
for i in range(h):
    l = list(map(int,input().split()))
    for j,num in enumerate(l):
        la[i][j] = abs(la[i][j]-num)
dp = [[0 for i in range(w)] for j in range(h)]
k = (h+w)*80+2
dp[0][0] = 1 << (k+la[0][0]) | 1 << (k-la[0][0])

for i in range(h):
    for j in range(w):
        if i:
            dp[i][j] |= (dp[i-1][j] << la[i][j]) | dp[i-1][j] >> la[i][j]
        if j:
            dp[i][j] |= (dp[i][j-1] << la[i][j]) | dp[i][j-1] >> la[i][j]

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
h,w = map(int,input().split())
la = [list(map(int,input().split())) for i in range(h)]
for i in range(h):
    l = list(map(int,input().split()))
    for j,num in enumerate(l):
        la[i][j] = abs(la[i][j]-num)
dp = [[0 for i in range(w)] for j in range(h)]
k = (h+w)*80+2
dp[0][0] = 1 << (k+la[0][0]) | 1 << (k-la[0][0])

for i in range(h):
    for j in range(w):
        if i:
            dp[i][j] |= (dp[i-1][j] << la[i][j]) | dp[i-1][j] >> la[i][j]
        if j:
            dp[i][j] |= (dp[i][j-1] << la[i][j]) | dp[i][j-1] >> la[i][j]
        
s = bin(dp[-1][-1])[2:]
l = len(s)-1
ans = float('inf')
for i in range(l,-1,-1):
  if s[i]=='1':
    m = abs(l-i-k)
    if m<ans:
      ans = m
print(ans)

Submission status: Accepted

Solution code:
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)]
    C = [[abs(A[i][j] - B[i][j]) for j in range(W)] for i in range(H)]

    M = 160*80
    dp = [[0 for _ in range(W)] for __ in range(H)]
    dp[0][0] = 1 << (C[0][0] + M)
    for i in range(H):
        for j in range(W):
            for ni,nj in [(i,j+1),(i+1,j)]:
                if ni >= H or nj >= W: continue
                t = C[ni][nj]
                dp[ni][nj] |= dp[i][j] << t
                dp[ni][nj] |= dp[i][j] >> t
    
    a = dp[H-1][W-1]
    ans = 0
    while True:
        if a & (1 << (M+ans)) or a & (1 >> (M-ans)): break
        ans += 1
    print(ans)

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 = [[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
d = 80*(h+w-1)
D = 2*d+1
dp = [[0]*w for j in range(h)]
dp[0][0] = np.zeros(D, np.bool)
dp[0][0][d+C[0][0]] = 1
for i in range(h):
    for j in range(w):
        if i == 0 and j == 0:
            continue
        x = np.zeros(D, np.bool)
        if i != 0:
            x[C[i][j]:] |= dp[i-1][j][:D-C[i][j]]
            x[:D-C[i][j]] |= dp[i-1][j][C[i][j]:]
        if j != 0:
            x[C[i][j]:] |= dp[i][j-1][:D-C[i][j]]
            x[:D-C[i][j]] |= dp[i][j-1][C[i][j]:]
        dp[i][j] = x

temp = np.where(dp[-1][-1]>0)[0] - d
temp = abs(temp)
print(min(temp))

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

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

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

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

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

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

Submission status: Accepted

Solution code:
import math

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

diff = [[abs(x-y) for x,y in zip(ar,br)] for ar,br in zip (a,b)]

M = 80*(h+w)
dp = [[0 for j in range(w)] for i in range(h)]
dp[0][0] = 1<<(diff[0][0]+M)
for i in range(h):
    for j in range(w):
        if i > 0:
            dp[i][j] |= (dp[i-1][j]<<diff[i][j])|(dp[i-1][j]>>diff[i][j])
        if j > 0:
            dp[i][j] |= (dp[i][j-1]<<diff[i][j])|(dp[i][j-1]>>diff[i][j])
        dp[i][j] &= (1<<(M*2))-1
for k in range(M):
    if (dp[h-1][w-1]>>(k+M))&1 == 1:
        print(k)
        break

Submission status: Accepted

Solution code:
def fold(x,m):
    y = 0
    for _ in range(m):
        y |= x&1
        y <<= 1
        x >>= 1
    return x|y

lmi = lambda: list(map(int, input().split()))

h,w = lmi()
a = [lmi() for _ in range(2*h)]
g = [[abs(a[i][j] - a[i+h][j]) for j in range(w)] for i in range(h)]
m = 12801
mask = (1<<m) - 1

a = [0]*(w+1)
a[0] = 1
for i in range(h):
  for j in range(w):
    cur,par = g[i][j], a[j]|a[j-1]
    a[j] = par<<cur&mask|fold(par,cur)
v = a[-2]
print((v&-v).bit_length() - 1)

Submission status: Accepted

Solution code:

h,w = map(int, input().split( ))
a = []
for i in range(h):
    ai = list(map(int, input().split( )))
    a.append(ai)
for i in range(h):
    bi = list(map(int, input().split( )))
    for j in range(w):
        a[i][j]-=bi[j]
        a[i][j] = abs(a[i][j])
###差のmaxまでをlistで確保する代わりに可能な値をsetで保持
###値が小さいのでsetからbitで保持に変更
dp = [[0 for j in range(w)] for i in range(h)]
a2 = [a[i][j] for i in range(h) for j in range(w)]
mxa = max(a2)
###中心を取る
###間違えやすいし最大値決め打ちか
tmp=1<<mxa*(h+w)+10

dp[0][0]|=tmp<<a[0][0]
dp[0][0]|=tmp>>a[0][0]

for j in range(1,w):
    dp[0][j]=dp[0][j-1]<<a[0][j]
    dp[0][j]|=dp[0][j-1]>>a[0][j]

for i in range(1,h):
    for j in range(w):###ループ一つ抜けてるわw
        dp[i][j]=dp[i-1][j]<<a[i][j]
        dp[i][j]|=dp[i-1][j]>>a[i][j]
        if j:
            dp[i][j]|=dp[i][j-1]<<a[i][j]
            dp[i][j]|=dp[i][j-1]>>a[i][j]

tmp1 = dp[h-1][w-1]

tmp1>>=mxa*(h+w)+10

###mxa=0でrange(0)になる式だと答えが出ない
for k in range(mxa*(h+w)+10):
    if tmp1&1:
        print(k)
        exit()
    tmp1>>=1

Submission status: Accepted

Solution code:
import numpy as np
import itertools

H,W=map(int,input().split())
A=[list(map(int, input().split())) for _ in range(H*2)]
M=[[abs(A[i][j]-A[H+i][j]) for j in range(W)] for i in range(H)]
m=max(max(j for j in i) for i in M)
r=m*(H+W)+1
dp=np.zeros((H,W,r),dtype='bool')
dp[0][0][M[0][0]]=True
it = itertools.product(range(H),range(W))
next(it)
for h,w in it:
    m=M[h][w]
    dp[h][w][m:] |= dp[h][w-1][:r-m] | dp[h-1][w][:r-m]
    dp[h][w][:r-m] |= dp[h][w-1][m:] | dp[h-1][w][m:]
    dp[h][w][:m] |= dp[h][w-1][m:0:-1] | dp[h-1][w][m:0:-1]

for i in range(r):
    if dp[-1][-1][i]:
        print(i)
        break

Submission status: Accepted

Solution code:
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)]
    C = [[0] * W for _ in range(H)]
    for h in range(H):
        for w in range(W):
            C[h][w] = abs(A[h][w] - B[h][w])

    dp = [[0 for _ in range(6400)] for _ in range(H*W)]
    dp[0][C[0][0]] = 1

    for d in range(H*W):
        h, w = divmod(d, W)
        for k in range(6400):
            if not dp[h*W+w][k]:
                continue
            nh, nw = h+1, w+1
            if nh < H:
                if k + C[nh][w] < 6400:
                    dp[nh*W+w][k+C[nh][w]] = 1
                dp[nh*W+w][abs(k-C[nh][w])] = 1
            if nw < W:
                if k + C[h][nw] < 6400:
                    dp[h*W+nw][k+C[h][nw]] = 1
                dp[h*W+nw][abs(k-C[h][nw])] = 1

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
ab = []
for i in range(h * 2):
    ab.extend(list(map(int, input().split())))

abs_table = [[0] * w for _ in range(h)]
dp = [[0] * w for _ in range(h)]

s = h * w
i = 0
j = 0
for k in range(s):
    if w == j:
        j = 0
        i += 1
    a, b = ab[k], ab[k+s]
    abs_table[i][j] = abs(a - b)
    j += 1
   
n = abs_table[0][0]  
dp[0][0] = 2**(n * 2)  | 1
    
for i in range(h):
    for j in range(w):
        a = abs_table[i][j]
        u = 0
        l = 0
        if i:
            u = dp[i-1][j]
            u = u << a * 2 | u | u
        if j:
            l = dp[i][j-1]
            l = l << a * 2 | l | l
            
        if not u and not l:
            pass
        elif not l:
            dp[i][j] = u
        elif not u:
            dp[i][j] = l
        else:
            len_u = len(bin(u)[2:])
            len_l = len(bin(l)[2:])
            delta = len_u - len_l
            if delta == 0:
                dp[i][j] = u | l
            elif delta < 0:
                dp[i][j] = u << abs(delta) // 2 | l
            else:
                dp[i][j] = u | l << delta // 2

flag = bin(dp[-1][-1])[2:]
zero = len(flag) // 2
for i, v in enumerate(flag[zero:]):
    if v == '1':
        print(i)
        break

Submission status: Accepted

Solution code:
def main():
    import sys

    H, W = map(int, sys.stdin.readline().split())
    A = [list(map(int, sys.stdin.readline().split())) for i in range(H)]
    B = [list(map(int, sys.stdin.readline().split())) for i in range(H)]
    X = [[0] * W for i in range(H)]
    for h in range(H):
        for w in range(W):
            X[h][w] = abs(A[h][w] - B[h][w])

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

    for h in range(H):
        for w in range(W):
            if h == 0 and w == 0:
                continue
            x = X[h][w]
            s = set()

            if h > 0:
                for d in dp[h - 1][w]:
                    s.add(d + x)
                    s.add(abs(d - x))

            if w > 0:
                for d in dp[h][w - 1]:
                    s.add(d + x)
                    s.add(abs(d - x))

            dp[h][w] = s

    ans = min([abs(s) for s in dp[H - 1][W - 1]])
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
arr=[list(map(int,input().split())) for _ in range(2*h)]
board=[[0]*w for _ in range(h)]
for i in range(h):
  for j in range(w):
    board[i][j]+=arr[i][j]
for i in range(h):
  for j in range(w):
    board[i][j]=abs(board[i][j]-arr[h+i][j])
dp=[[set() for _ in range(w)] for _ in range(h)]
dp[0][0].add(board[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((k+board[i][j])%640)
        dp[i][j].add(abs(k-board[i][j])%640)
    if j!=0:
      for k in dp[i][j-1]:
        dp[i][j].add((k+board[i][j])%640)
        dp[i][j].add(abs(k-board[i][j])%640)
print(min(dp[h-1][w-1]))

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
arr=[list(map(int,input().split())) for _ in range(2*h)]
board=[[0]*w for _ in range(h)]
for i in range(h):
  for j in range(w):
    board[i][j]+=arr[i][j]
for i in range(h):
  for j in range(w):
    board[i][j]=abs(board[i][j]-arr[h+i][j])
dp=[[set() for _ in range(w)] for _ in range(h)]
dp[0][0].add(board[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((k+board[i][j])%800)
        dp[i][j].add(abs(k-board[i][j])%800)
    if j!=0:
      for k in dp[i][j-1]:
        dp[i][j].add((k+board[i][j])%800)
        dp[i][j].add(abs(k-board[i][j])%800)
print(min(dp[h-1][w-1]))

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 = [[0 for j in range(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 for k in range(6400)] for g in range(H*W)]
dp[0][C[0][0]] = 1

for g in range(H*W):
    i,j = divmod(g,W)
    for k in range(6400):
        if not dp[i*W+j][k]:
            continue
        ni,nj = i+1,j+1
        if ni < H:
            if k+C[ni][j]<6400:
                dp[ni*W+j][k+C[ni][j]] = 1
            dp[ni*W+j][abs(k-C[ni][j])] = 1
        if nj < W:
            if k+C[i][nj]<6400:
                dp[i*W+nj][k+C[i][nj]] = 1
            dp[i*W+nj][abs(k-C[i][nj])] = 1

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

Submission status: Accepted

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

    C = [[0 for j in range(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 for k in range(6400)] for g in range(H*W)]
    dp[0][C[0][0]] = 1

    for g in range(H*W):
        i,j = divmod(g,W)
        for k in range(6400):
            if not dp[i*W+j][k]:
                continue
            ni,nj = i+1,j+1
            if ni < H:
                if k+C[ni][j]<6400:
                    dp[ni*W+j][k+C[ni][j]] = 1
                dp[ni*W+j][abs(k-C[ni][j])] = 1
            if nj < W:
                if k+C[i][nj]<6400:
                    dp[i*W+nj][k+C[i][nj]] = 1
                dp[i*W+nj][abs(k-C[i][nj])] = 1

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

main()

Submission status: Accepted

Solution code:
def examE():
    H, W = LI()
    A = [LI() for _ in range(H)]
    B = [LI() for _ in range(H)]
    Diff = [[0] * W for _ in range(H)]
    M = 0
    for i in range(H):
        for j in range(W):
            m = abs(A[i][j] - B[i][j])
            Diff[i][j] = m
            M += m
    dp = [[0] * (W + 1) for _ in range(H + 1)]
    dp[0][0] |= (1 << Diff[H-1][W-1])
    for i in range(H):
        for j in range(W):
            here = dp[i][j]
            s = Diff[i][j]
            ni = (here << s) | (here >> s)
            ex = 0
            #溢れる分
            for k in range(1, s + 1):
                if (here >> k) & 1:
                    ex |= (1 << (s - k))
            dp[i + 1][j] |= (ni | ex)
            dp[i][j + 1] |= (ni | ex)
#            print(s,ni,here,ex,dp[i+1][j])

    a = dp[H - 1][W - 1]
    ans = 0
    for k in range(M + 1):
        if (a >> k) & 1:
            ans = k
            break
    print(dp)
    print(ans)
    return

def examE2():
    H, W = LI()
    A = [LI() for _ in range(H)]
    B = [LI() for _ in range(H)]
    dp = [0]*(H*W)
    cur = abs(A[0][0] - B[0][0])
    dp[0] |= (1 << cur)
    for i in range(H):
        for j in range(W):
            now = dp[i*W + j]
            if i < H - 1:
                cur = abs(A[i + 1][j] - B[i + 1][j])
                ni = (now << cur) | (now >> cur)
                ex = 0
                for k in range(1, cur + 1):
                    if (now >> k) & 1:
                        ex |= (1 << (cur - k))
                dp[(i+1)*W +j] |= (ni | ex)
            if j < W - 1:
                cur = abs(A[i][j + 1] - B[i][j + 1])
                ni = (now << cur) | (now >> cur)
                ex = 0
                for k in range(1, cur + 1):
                    if (now >> k) & 1:
                        ex |= (1 << (cur - k))
                dp[i*W +j+1] |= (ni | ex)
    #print(dp[-1])
    ans = inf
    for i,f in enumerate(str(bin(dp[-1]))[::-1]):
        if f=="1":
            ans = i
            break
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examE2()

Submission status: Accepted

Solution code:
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 = [lr() for _ in range(H)]
B = [lr() for _ in range(H)]
diff = [[0] * W for _ in range(H)]
for i in range(H):
    for j in range(W):
        diff[i][j] = abs(A[i][j] - B[i][j])

X = (H+W) * 80
L = X + X + 1 #真ん中を0とする、最後に-X
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, di in enumerate(diff[h]):
        if h == 0 and w == 0:
            continue
        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]
possible = np.where(dp)[0] - X
answer = np.abs(possible).min()
print(answer)
# 07

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')


max_ = 2*(80*80)+1
def transform(x):
    return x+max_


def main():
    H,W=MI()
    A=LLIN(H)
    B=LLIN(H)
    DP = [[0]*W for _ in range(H)]
    DP[0][0] = (1<<transform(abs(A[0][0]-B[0][0]))) | (1<<transform(abs(A[0][0]-B[0][0])))
    for i in range(H):
        for j in range(W):
            ab = abs(A[i][j] - B[i][j])
            if i:
                DP[i][j] |= (DP[i-1][j]>>ab) | (DP[i-1][j]<<ab)
            if j:
                DP[i][j] |= (DP[i][j-1]>>ab) | (DP[i][j-1]<<ab)

    ans = inf
    for val in range(-max_, max_+1):
        if DP[-1][-1]>>transform(val)&1:
            ans = min(ans, abs(val))
    print(ans)

if __name__ == '__main__':
    main()

# #
# # 　　  ⋀_⋀　 
# #　　  (･ω･)  
# # .／ Ｕ ∽ Ｕ＼
# #  │＊　合　＊│
# #  │＊　格　＊│ 
# #  │＊　祈　＊│ 
# #  │＊　願　＊│ 
# #  │＊　　　＊│ 
# #      ￣
# #
# import sys
# sys.setrecursionlimit(10**6)
# input=sys.stdin.readline
# from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
# from heapq import heappop, heappush, heappushpop
# from collections import Counter,defaultdict,deque
# from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
# from bisect import bisect_left,bisect_right
# from copy import deepcopy
# inf=float('inf')
# mod = 10**9+7
# def pprint(*A): 
#     for a in A:     print(*a,sep='\n')
# def INT_(n): return int(n)-1
# def MI(): return map(int,input().split())
# def MF(): return map(float, input().split())
# def MI_(): return map(INT_,input().split())
# def LI(): return list(MI())
# def LI_(): return [int(x) - 1 for x in input().split()]
# def LF(): return list(MF())
# def LIN(n:int): return [I() for _ in range(n)]
# def LLIN(n: int): return [LI() for _ in range(n)]
# def LLIN_(n: int): return [LI_() for _ in range(n)]
# def LLI(): return [list(map(int, l.split() )) for l in input()]
# def I(): return int(input())
# def F(): return float(input())
# def ST(): return input().replace('\n', '')
# def main():
#     H,W=MI()
#     A=LLIN(H)
#     B=LLIN(H)
#     X=80*(H+W)
#     can = [[0]*W for _ in range(H)]
#     can[0][0] += 1<<(X-abs(A[0][0]-B[0][0]))
#     for h in range(H):
#         for w in range(W):
#             absol = abs(A[h][w]-B[h][w])
#             if h:
#                 can[h][w]|=can[h-1][w]<<absol
#                 can[h][w]|=can[h-1][w]>>absol
#             if w:
#                 can[h][w]|=can[h][w-1]<<absol
#                 can[h][w]|=can[h][w-1]>>absol
#     for i in range(160*(H+W)+5):
#         if can[-1][-1] & ((1<<X<<i) | (1<<X>>i)):
#             print(i)
#             break

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

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
A = []

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()))
    for j, num in enumerate(line):
        A[i][j] = abs(A[i][j] - num)

const = 6400
mask = 1 << const
DP = [0]*w
DP[0] = mask >> A[0][0]


def slide_down(y, x):
    bit = DP[x]
    delta = A[y+1][x]
    new1 = bit << delta
    new2 = bit >> delta
    DP[x] = new1 | new2


def slide_right(y, x):
    bit = DP[x]
    delta = A[y][x+1]
    new1 = bit << delta
    new2 = bit >> delta
    DP[x+1] |= new1 | new2


for y in range(h):
    for x in range(w):
        if x < w-1:
            slide_right(y, x)
        if y < h-1:
            slide_down(y, x)

pattern = DP[w-1]
for i in range(81):
    if (pattern >> const+i) & 1 or (pattern >> const-i) & 1:
        print(i)
        exit()

Submission status: Accepted

Solution code:
import numpy as np
import itertools

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

D = [[abs(A[h][w] - B[h][w]) for w in range(W)] for h in range(H)]
max_num = 80 * (H + W)
table = np.zeros((H, W, max_num), dtype='bool')
table[0][0][D[0][0]] = True

it = itertools.product(range(H), range(W))
next(it)  # h=w=0 捨てる
for h, w in it:
    d = D[h][w]
    table[h][w][d:] += table[h - 1][w][:max_num - d] + table[h][w - 1][:max_num - d]
    table[h][w][:max_num - d] += table[h - 1][w][d:] + table[h][w - 1][d:]
    table[h][w][d:0:-1] += table[h - 1][w][:d] + table[h][w - 1][:d]

print(np.amin(*np.where(table[H - 1][W - 1])))

Submission status: Accepted

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

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

SIZE = 20000
dp = [[0 for _ in range(W)] for _ in range(H)]
dp[0][0] = 1 << (SIZE + C[0][0]) | 1 << (SIZE - C[0][0])

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

for i in range(SIZE):
    if (dp[-1][-1] >> (i + SIZE)) & 1:
        print(i)
        exit()

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
A = [[0]*W for i in range(H)]
B = [[0]*W for i in range(H)]
for i in range(H):
  inf = [int(c) for c in input().split()]
  for j in range(W):
    A[i][j] = inf[j]

for i in range(H):
  inf = [int(c) for c in input().split()]
  for j in range(W):
    B[i][j] = inf[j]

X = (H+W)*80
dp = [[0]*W for i in range(H)]
d = abs(A[0][0]-B[0][0])
dp[0][0] = 1<<(X+d)

for i in range(H):
  for j in range(W):
    if i==0 and j==0:
      continue
    d = abs(A[i][j]-B[i][j])
    if i!=0:
      dp[i][j] |= dp[i-1][j]>>d
      dp[i][j] |= dp[i-1][j]<<d
    if j!=0:
      dp[i][j] |= dp[i][j-1]>>d
      dp[i][j] |= dp[i][j-1]<<d

s = bin(dp[-1][-1])[2:]
l = len(s)-1
ans = float('inf')
for i in range(l,-1,-1):
  if s[i]=='1':
    m = abs(l-i-X)
    if m<ans:
      ans = m
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
H,W = map(int,input().split())
A = [[0]*W for i in range(H)]
B = [[0]*W for i in range(H)]
for i in range(H):
  inf = [int(c) for c in input().split()]
  for j in range(W):
    A[i][j] = inf[j]
    
for i in range(H):
  inf = [int(c) for c in input().split()]
  for j in range(W):
    B[i][j] = inf[j]

X = (H + W) * 80
L = X + X + 1
# X点持った状態から始める
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,(a,b) in enumerate(zip(A[h],B[h])):
        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

dp2 = dp[-1][-1]
can_make = np.where(dp2)[0] - X

answer = np.abs(can_make).min()
print(answer)