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

    mx=80*(H+W)
    C=[[abs(A[i][j]-B[i][j]) for j in range(W)] for i in range(H)]
    dp=[[0 for _ in range(W)] for __ in range(H)]
    dp[0][0]=1<<(mx+C[0][0])
    for i in range(H):
        for j in range(W):
            for ni,nj in ((i+1,j),(i,j+1)):
                if ni>=H or nj>=W: continue
                dp[ni][nj] |= dp[i][j] << C[ni][nj]
                dp[ni][nj] |= dp[i][j] >> C[ni][nj]

    for ans in range(mx+1):
        if dp[H-1][W-1] & (1<<(mx+ans) | 1<<(mx-ans)):
            print(ans)
            break

if __name__ == '__main__':
    main()

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

import numpy as np
dp = [[0]*(w+1) for _ in range(h+1)]
import numpy as np
d = 80*(h+w-1)+1
D = 2*d+1
dp[0][0] = np.zeros(D, np.bool)
dp[0][0][C[0][0]+d] = 1
#dp[0][0][-C[0][0]+d] = 1
for i in range(h):
    for j in range(w):
        c = C[i][j]
        if i == 0 and j == 0:
            continue
        elif i == 0:
            b = np.zeros(D, np.bool)
            b[c:] |= dp[i][j-1][:D-c]
            b[:D-c] |= dp[i][j-1][c:]
        elif j == 0:
            b = np.zeros(D, np.bool)
            b[c:] |= dp[i-1][j][:D-c]
            b[:D-c] |= dp[i-1][j][c:]
        else:
            b = np.zeros(D, np.bool)
            b[c:] |= dp[i][j-1][:D-c]
            b[:D-c] |= dp[i][j-1][c:]
            b[c:] |= dp[i-1][j][:D-c]
            b[:D-c] |= dp[i-1][j][c:]
        dp[i][j] = b
#print(dp[h-1][w-1])
ans = float('inf')
for i in range(D):
    if dp[h-1][w-1][i]:
        #print(abs(i-d))
        ans = min(ans, abs(i-d))
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)]

dp = [[0] * (W + 1) for _ in range(H + 1)]
F = 80 * 200 + 100
dp[0][0] = (1 << F)

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

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

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

Submission status: Accepted

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


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

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

    offset = 80 * 164

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

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


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys

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


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

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

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

    from itertools import product

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

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

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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


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


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

print(ans)

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

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

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

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

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

print(ans)

Submission status: Accepted

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


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

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

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

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


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


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


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

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

Submission status: Accepted

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

input=sys.stdin.readline

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

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

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

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

print(ans)

Submission status: Accepted

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

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 = np.array([lr() for _ in range(H)])
B = np.array([lr() for _ in range(H)])
diff = np.abs(A - B).tolist()

X = (H+W) * 80
L = X + X + 1 #真ん中を0とする、最後に-X
dp = [[np.zeros(L, np.bool) for _ in range(W)] for _ in range(H)]
di = diff[0][0]
dp[0][0][X+di] = 1; dp[0][0][X-di] = 1
for i in range(H):
    for j in range(W):
        if i == 0 and j == 0:
            continue
        di = diff[i][j]
        if i > 0:
            prev = dp[i-1][j]
            dp[i][j][di:] |= prev[:L-di]
            dp[i][j][:L-di] |= prev[di:]
        if j > 0:
            prev = dp[i][j-1]
            dp[i][j][di:] |= prev[:L-di]
            dp[i][j][:L-di] |= prev[di:]

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

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 = np.array([lr() for _ in range(H)])
B = np.array([lr() for _ in range(H)])
diff = np.abs(A - B).tolist()

X = (H+W) * 80
L = X + X + 1 #真ん中を0とする、最後に-X
dp = [[np.zeros(L, np.bool)] * W for _ in range(H)]
dp[0][0] = np.zeros(L, np.bool)
di = diff[0][0]
dp[0][0][X+di] = 1; dp[0][0][X-di] = 1
for h in range(H):
    for w in range(W):
        if h == 0 and w == 0:
            continue
        di = diff[h][w]
        x = np.zeros(L, np.bool)
        if h > 0:
            prev = dp[h-1][w]
            x[di:] |= prev[:L-di]
            x[:L-di] |= prev[di:]
        if w > 0:
            prev = dp[h][w-1]
            x[di:] |= prev[:L-di]
            x[:L-di] |= prev[di:]
        dp[h][w] = x

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

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 = np.array([lr() for _ in range(H)])
B = np.array([lr() for _ in range(H)])
diff = np.abs(A - B).tolist()

X = (H+W) * 80
L = X + X + 1 #真ん中を0とする、最後に-X
dp = [[None] * W for _ in range(H)]
dp[0][0] = np.zeros(L, np.bool)
di = diff[0][0]
dp[0][0][X+di] = 1; dp[0][0][X-di] = 1
for h in range(H):
    for w in range(W):
        if h == 0 and w == 0:
            continue
        di = diff[h][w]
        x = np.zeros(L, np.bool)
        if h > 0:
            prev = dp[h-1][w]
            x[di:] |= prev[:L-di]
            x[:L-di] |= prev[di:]
        if w > 0:
            prev = dp[h][w-1]
            x[di:] |= prev[:L-di]
            x[:L-di] |= prev[di:]
        dp[h][w] = x

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

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 = np.array([lr() for _ in range(H)])
B = np.array([lr() for _ in range(H)])
diff = np.abs(A - B).tolist()

X = (H+W) * 80
L = X + X + 1 #真ん中を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 in range(W):
        if h == 0 and w == 0:
            continue
        di = diff[h][w]
        x = np.zeros(L, np.bool)
        if h > 0:
            x[di:] |= dp[h-1][w][:L-di]
            x[:L-di] |= dp[h-1][w][di:]
        if w > 0:
            x[di:] |= dp[h][w-1][:L-di]
            x[:L-di] |= dp[h][w-1][di:]
        dp[h][w] = x

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

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 = np.array([lr() for _ in range(H)])
B = np.array([lr() for _ in range(H)])
diff = np.abs(A - B)

X = (H+W) * 80
L = X + X + 1 #真ん中を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 in range(W):
        if h == 0 and w == 0:
            continue
        di = diff[h][w]
        x = np.zeros(L, np.bool)
        if h > 0:
            x[di:] |= dp[h-1][w][:L-di]
            x[:L-di] |= dp[h-1][w][di:]
        if w > 0:
            x[di:] |= dp[h][w-1][:L-di]
            x[:L-di] |= dp[h][w-1][di:]
        dp[h][w] = x

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

Submission status: Accepted

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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
# input = sys.stdin.buffer.readline
def input(): return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10 ** 7)

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

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

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


#############
# Constants #
#############

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

#############
# Functions #
#############

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

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

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

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

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

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

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

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

#############
# Main Code #
#############

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

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

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

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

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)]
# zeroは真ん中にする
ma = 80*2*80
DP = [[0]*w for i in range(h)]

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

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

Submission status: Accepted

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

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

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

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*80+2
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
        else:
            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] | 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()