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: Runtime Error

Solution code:
h,w = map(int,input().split())
a = []
b = []
for i in range(h):
    a1 = list(map(int,input().split()))
    a.append(a1)
for i in range(h):
    b1 = list(map(int,input().split()))
    b.append(b1)
l = [[] for i in range(h)]
for i in range(h):
    for j in range(w):
        l[i].append(abs(a[i][j]-b[i][j]))
dp = [[[0 for i in range(81*(h+w)//2+1)] for i in range(w)] for i in range(h)]
for i in range(h):
    for j in range(w):
        #print(dp)
        for k in range(81*(h+w)//2+1):
            if i == 0:
                if j == 0:
                    dp[i][j][l[i][j]] = 1
                else:
                    if dp[i][j-1][k] == 1:
                        if dp[i][j][k+l[i][j]] <= 81*(h+w)//2:
                            dp[i][j][k+l[i][j]] = 1
                        dp[i][j][abs(k-l[i][j])] = 1
            else:
                if j == 0:
                    if dp[i-1][j][k] == 1:
                        if dp[i][j][k+l[i][j]] <= 81*(h+w)//2:
                            dp[i][j][k+l[i][j]] = 1
                        dp[i][j][abs(k-l[i][j])] = 1
                else:
                    if dp[i-1][j][k] == 1:
                        if dp[i][j][k+l[i][j]] <= 81*(h+w)//2:
                            dp[i][j][k+l[i][j]] = 1
                        dp[i][j][abs(k-l[i][j])] = 1
                    if dp[i][j-1][k] == 1:
                        if dp[i][j][k+l[i][j]] <= 81*(h+w)//2:
                            dp[i][j][k+l[i][j]] = 1
                        dp[i][j][abs(k-l[i][j])] = 1
ans = 80
for i in range(81):
    if dp[h-1][w-1][i] == 1:
        ans = i
        break
print(ans)

Submission status: Runtime Error

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

d = 3200
D = 2*d+1
dp = [[[0]*D for i in range(w)] for j in range(h)]
dp[0][0][d+C[0][0]] = 1
for i in range(h):
    for j in range(w):
        if i+1< h:
            for k in range(D):
                if dp[i][j][k] != 0:
                    dp[i+1][j][k+C[i+1][j]] = 1
                    dp[i+1][j][k-C[i+1][j]] = 1
        if j+1<w:
            for k in range(D):
                if dp[i][j][k] != 0:
                    dp[i][j+1][k+C[i][j+1]] = 1
                    dp[i][j+1][k-C[i][j+1]] = 1
ans = d
for i in range(d, D):
    if dp[-1][-1][i] != 0:
        ans = min(ans, i-d)
for i in reversed(range(d)):
    if dp[-1][-1][i] != 0:
        ans = min(ans, d-i)
print(ans)

Submission status: Runtime Error

Solution code:
h, w = [int(i) for i in input().split()]
a = [[int(i) for i in input().split()] for _ in range(h)]
b = [[int(i) for i in input().split()] for _ in range(h)]
m = max([abs(a[i][j]-b[i][j]) for i in range(w) for j in range(h)])

dp = [[[False] * (160 * m*2) for _ in range(w)] for _ in range(h)]
dp[0][0][0] = True

for i in range(h):
    for j in range(w):
        if i != 0:
            for k in range(-160 * m, 160 * m):
                if dp[i - 1][j][k]:
                    dp[i][j][k + a[i][j] - b[i][j]] = True
                    dp[i][j][k - a[i][j] + b[i][j]] = True

        if j != 0:
            for k in range(-160 * m, 160 * m):
                if dp[i][j-1][k]:
                    dp[i][j][k + a[i][j] - b[i][j]] = True
                    dp[i][j][k - a[i][j] + b[i][j]] = True
ans = 10**9
for i in range(-160*m, 160*m):
    if dp[-1][-1][i]:
        ans = min(ans, abs(i))

print(ans)

Submission status: Runtime Error

Solution code:
H,W = map(int, input().split())
A=[]
B=[]
for _ in range(H):
    A.append(list(map(int, input().split())))
for _ in range(H):
    B.append(list(map(int, input().split())))
M=[[] for _ in range(W)]
m=0
for i in range(H):
    for j in range(W):
        M[i][j]=abs(A[i][j]-B[i][j])
        m=max(M[i][j],m)
r=m*(H+W)
dp=[[[False for _ in range(r)] for _ in range(W)] for _ in range(H)]
dp[0][0][abs(A[0][0]-B[0][0])]=True
for i in range(H):
    for j in range(W):
        if i==0 and j==0: continue
        for k in range(r):
            if i==0:
                if dp[i][j-1][abs(k-M[i][j])] or dp[i][j-1][k+M[i][j]]:
                    dp[i][j][k]=True
            elif j==0:
                if dp[i-1][j][abs(k-M[i][j])] or dp[i-1][j][k+M[i][j]]:
                    dp[i][j][k]=True
            elif dp[i][j-1][abs(k-M[i][j])] or dp[i][j-1][k+M[i][j]] or dp[i-1][j][abs(k-M[i][j])] or dp[i-1][j][k+M[i][j]]:
                dp[i][j][k]=True
for i in range(r):
    if dp[H-1][W-1][i]:
        print(i)
        break

Submission status: Runtime Error

Solution code:
import numpy as np
h,w=map(int,input().split())

A=np.array([list(map(int,input().split())) for i in range(h)])
B=np.array([list(map(int,input().split())) for i in range(h)])
T=np.abs(A-B) #絶対値配列の作成

k=(h+w+1)*np.max(T) #偏りkの探索範囲
dp=np.zeros((h,w,k)) #3次元配列の作成
dp[0][0][T[0][0]]=1 #最初のマスの偏りを登録

for i in range(h):
    for j in range(w):
        for z in range(k):
            if dp[i][j][z]==1: #偏りk=zになり得るとき
                if i+1<h: #端っこじゃなければ
                    t=T[i+1][j] #隣の偏りを取得
                    dp[i+1][j][abs(z+t)]=1 #あり得る偏りを登録
                    dp[i+1][j][abs(z-t)]=1
                if j+1<w:
                    t=T[i][j+1]
                    dp[i][j+1][abs(z+t)]=1
                    dp[i][j+1][abs(z-t)]=1                
print(np.where(dp[h-1][w-1]==1)[0][0])

Submission status: Runtime Error

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

dp = [[[False for i in range(1000)] for j in range(w)] for k in range(h)]
dp[0][0][abs(a[0][0] - b[0][0])] = True

for i in range(h):
  for j in range(w):
    if i + 1 < h:
      for k in range(1000):
        if dp[i][j][k]:
          dp[i + 1][j][k + abs(a[i + 1][j] - b[i + 1][j])] = True
          dp[i + 1][j][abs(k - abs(a[i + 1][j] - b[i + 1][j]))] = True
    if j + 1 < w:
      for k in range(1000):
        if dp[i][j][k]:
          dp[i][j + 1][k + abs(a[i][j + 1] - b[i][j + 1])] = True
          dp[i][j + 1][abs(k - abs(a[i][j + 1] - b[i][j + 1]))] = True

for k in range(1000):
  if dp[h - 1][w - 1][k]:
    print(k)
    break

Submission status: Runtime Error

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

dp = [[[False for i in range(300)] for j in range(w)] for k in range(h)]
dp[0][0][abs(a[0][0] - b[0][0])] = True

for i in range(h):
  for j in range(w):
    if i + 1 < h:
      for k in range(300):
        if dp[i][j][k]:
          dp[i + 1][j][k + abs(a[i + 1][j] - b[i + 1][j])] = True
          dp[i + 1][j][abs(k - abs(a[i + 1][j] - b[i + 1][j]))] = True
    if j + 1 < w:
      for k in range(300):
        if dp[i][j][k]:
          dp[i][j + 1][k + abs(a[i][j + 1] - b[i][j + 1])] = True
          dp[i][j + 1][abs(k - abs(a[i][j + 1] - b[i][j + 1]))] = True

for k in range(300):
  if dp[h - 1][w - 1][k]:
    print(k)
    break

Submission status: Runtime Error

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

dp = [[[False for i in range(300)] for j in range(w)] for k in range(h)]
print(a, b)
dp[0][0][abs(a[0][0] - b[0][0])] = True

for i in range(h):
  for j in range(w):
    if i + 1 < h:
      for k in range(300):
        if dp[i][j][k]:
          dp[i + 1][j][k + abs(a[i + 1][j] - b[i + 1][j])] = True
          dp[i + 1][j][abs(k - abs(a[i + 1][j] - b[i + 1][j]))] = True
    if j + 1 < w:
      for k in range(300):
        if dp[i][j][k]:
          dp[i][j + 1][k + abs(a[i][j + 1] - b[i][j + 1])] = True
          dp[i][j + 1][abs(k - abs(a[i][j + 1] - b[i][j + 1]))] = True

for k in range(300):
  if dp[h - 1][w - 1][k]:
    print(k)
    break

Submission status: Runtime Error

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)]
table = np.zeros((H, W, 80 * (H + W)), 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][:-d] + table[h][w - 1][:-d]
    table[h][w][:-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: Runtime Error

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

Submission status: Runtime Error

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)]
SIZE = 10

AB = [[0 for _ in range(W)] for _ in range(H)]

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


dp = [[0 for _ in range(W)] for _ in range(H)]

dp[0][0] = 1 << (SIZE + AB[i][j] - 1) | 1 << (SIZE - AB[i][j] - 1)
for i in range(H):
    for j in range(W):
        dp[i][j] |= (dp[i - 1][j] << AB[i][j]) | (dp[i - 1][j] >> AB[i][j])
        dp[i][j] |= (dp[i][j - 1] << AB[i][j]) | (dp[i][j - 1] >> AB[i][j])

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

Submission status: Runtime Error

Solution code:
h,w = map(int,input().split())
raw = []
for i in range(h):
  raw.append(list(map(int,input().split())))
for i in range(h):
  tmp = list(map(int,input().split()))
  for j in range(w):
    raw[i][j] -= tmp[j]
    raw[i][j] = abs(raw[i][j])
#print(raw)
scale = 6401
#scale = 21
dp = [[[0 for _ in range(scale)] for _ in range(w)] for _ in range(h)]
dp[0][0][raw[0][0]] = 1
for i in range(h):
  for j in range(w):
    if i != 0:
      for d in range(scale):
        if dp[i-1][j][d] == 1:
          dp[i][j][d+raw[i][j]] = 1
          dp[i][j][abs(d-raw[i][j])] = 1
    if j != 0:
      for d in range(scale):
        if dp[i][j-1][d] == 1:
          dp[i][j][d+raw[i][j]] = 1
          dp[i][j][abs(d-raw[i][j])] = 1
    #print(dp[i][j])
#print(dp[-1][-1])
for d in range(scale):
  if dp[-1][-1][d] == 1:
    print(d)
    break

Submission status: Runtime Error

Solution code:
from math import ceil

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)]
    M = max([abs(a[i]-b[i]) for i in range(W)  for a,b in zip(A,B)])*(H + W)
    key = {(0,0):set( [ abs(A[0][0] - B[0][0]) ] ) }
    for w in range(1,W):
        a = A[0][w]
        b = B[0][w]
        key[(0,w)] = set()
        for k in key[(0,0)]:
             if k + abs(a - b) <= M:key[(0,w)].add(k + abs(a - b))
            if abs(k - abs(a - b)):key[(0,w)].add(abs(k - abs(a - b))
    for h in range(1,H):
        a = A[h][0]
        b = B[h][0]
        key[(h,0)] = set()
        for k in key[(0,0)]:
            if k + abs(a - b) <= M:key[(h,0)].add(k + abs(a - b))
            if abs(k - abs(a - b)) <= M:key[(h,0)].add(abs(k - abs(a - b)))

    for h in range(1,H):
        for w in range(1,W):
            a = A[h][w]
            b = B[h][w]
            key[(h,w)] = set()
            for k in key[(h-1,w)]:
                if k + abs(a - b) <= M:key[(h,w)].add(k + abs(a - b))
                if abs(k - abs(a - b)) <= M:key[(h,w)].add(abs(k - abs(a - b)))
            for k in key[(h,w-1)]:
                if k + abs(a - b) <= M:key[(h,w)].add(k + abs(a - b))
                if abs(k - abs(a - b)) <= M:key[(h,w)].add(abs(k - abs(a - b)))
    print(min(key[(H-1,W-1)]))
    return

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from math import ceil

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)]
    M = max([abs(a[i]-b[i]) for i in range(W)  for a,b in zip(A,B)])*(H + W)
    key = {(0,0):set( [ abs(A[0][0] - B[0][0]) ] ) }
    for w in range(1,W):
        a = A[0][w]
        b = B[0][w]
        key[(0,w)] = set()
        for k in key[(0,0)]:
             if k + abs(a - b) <= M:key[(0,w)].add(k + abs(a - b))
            if abs(k - abs(a - b)):key[(0,w)].add(abs(k - abs(a - b)))
    for h in range(1,H):
        a = A[h][0]
        b = B[h][0]
        key[(h,0)] = set()
        for k in key[(0,0)]:
            if k + abs(a - b) <= M:key[(h,0)].add(k + abs(a - b))
            if abs(k - abs(a - b)) <= M:key[(h,0)].add(abs(k - abs(a - b)))

    for h in range(1,H):
        for w in range(1,W):
            a = A[h][w]
            b = B[h][w]
            key[(h,w)] = set()
            for k in key[(h-1,w)]:
                if k + abs(a - b) <= M:key[(h,w)].add(k + abs(a - b))
                if abs(k - abs(a - b)) <= M:key[(h,w)].add(abs(k - abs(a - b)))
            for k in key[(h,w-1)]:
                if k + abs(a - b) <= M:key[(h,w)].add(k + abs(a - b))
                if abs(k - abs(a - b)) <= M:key[(h,w)].add(abs(k - abs(a - b)))
    print(min(key[(H-1,W-1)]))
    return

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import itertools

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

for _ in range(H):
    B.append(list(map(int,input().split())))

S = [[0] * W for _ in range(H)]
for i in range(H):
    for j in range(W):
        S[i][j] = abs(A[i][j] - B[i][j])

S_S = sorted(list(itertools.chain.from_iterable(S)),reverse=True)
MAX_S = sum(S_S[0:H+W-1])
MAX_SF = [[0] * W for _ in range(H)]
MAX_SR = [[0] * W for _ in range(H)]


MAX_SF[0][0] = S[0][0]
MAX_SR[H-1][W-1] = S[H-1][W-1]
for i in range(H):
    for j in range(W):
        if i == 0 and j == 0:
            continue
        if i == 0:
            MAX_SF[i][j] = MAX_SF[i][j-1] + S[i][j]
        elif j == 0:
            MAX_SF[i][j] = MAX_SF[i-1][j] + S[i][j]
        else:
            MAX_SF[i][j] = max(MAX_SF[i][j-1],MAX_SF[i-1][j]) + S[i][j]

for i in range(H-1,0,-1):
    for j in range(W-1,0,-1):
        if i == H-1 and j == W-1:
            continue
        if i == H-1:
            MAX_SR[i][j] = MAX_SR[i][j+1] + S[i][j]
        elif j == W-1:
            MAX_SR[i][j] = MAX_SR[i+11][j] + S[i][j]
        else:
            MAX_SR[i][j] = min(MAX_SR[i][j+1],MAX_SR[i+1][j]) + S[i][j]

DP = [[[False for _ in range(MAX_S+1)] for _ in range(W)] for _ in range(H)]

for i in range(H):
    for j in range(W):
        if i == 0 and j == 0:
            DP[0][0][S[0][0]] = True
        else:
            for d in ((1, 0), (0, 1)):

                if i - d[0] >= 0 and j - d[1] >= 0:
                    for k in range(min(MAX_SF[i][j],abs(MAX_SF[i][j] - MAX_SR[i][j])) + 1):
                        if k + S[i][j] <= MAX_S:
                            if DP[i-d[0]][j-d[1]][k + S[i][j]]:
                                DP[i][j][k] = True

                        if DP[i-d[0]][j-d[1]][abs(k - S[i][j])]:
                            DP[i][j][k] = True

for i in range(MAX_S+1):
    if DP[H-1][W-1][i]:
        print (i)
        exit(0)

Submission status: Runtime Error

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

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)]
  
  dp=[[[] for i in range(w)] for j in range(h)]
  dp[0][0].append(abs(a[0][0]-b[0][0]))
  for i in range(h):
    for j in range(w):
      c[i][j]=abs(a[i][j]-b[i][j])
      for k in dp[i-1][j]:
        dp[i][j].append(abs(k-c[i][j]))
        dp[i][j].append(k+c[i][j])
      for k in dp[i][j-1]:
        dp[i][j].append(abs(k-c[i][j]))
        dp[i][j].append(k+c[i][j])
      dp[i][j]=list(set(dp[i][j]))
  print(min(dp[h-1][w-1]))

if __name__=='__main__':
  main()

Submission status: Runtime Error

Solution code:
dp = [[[0 for i in range(80*(W+H)+1)] for i in range(H+1)] for i in range(W+1)]
H,W = map(int,input().split())
dp[0][0] = 1
A = []
B = []
for i in range(H):
    a = list(map(int,input().split()))
    A.append(a)
for i in range(H):
    b = list(map(int,input().split()))
    B.append(b)
for i in range(1,W+1):
    for j in range(1,H+1):
        x = i-1
        y = j-1
        z = A[x][y] - B[x][y]
        if z < 0:
            z = -z
        for k in range(80*(H+W)+1):
            if k >= z:
                if dp[i][j-1][k-z] == 1:
                    dp[i][j][k] = 1
                if dp[i-1][j][k-z] == 1:
                    dp[i][j][k] = 1
            if dp[i][j-1][k+z] == 1:
                dp[i][j][k] = 1
            if dp[i-1][j][k+z] == 1:
                dp[i][j][k] = 1
for i in range(80*(W+H)+1):
    if dp[H][W][i] == 1:
        print(i)
        quit()

Submission status: Runtime Error

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)]
AB=[[abs(A[i][j]-B[i][j]) for j in range(W)] for i in range(H)]
 
G=[[[0]*(80*160+1) for j in range(W)] for i in range(H)]
G[0][0][AB[0][0]]=1
 
for i in range(1, W):
  owari=80*i+1
  G[0][i][:owari]=[1 if G[0][i-1][abs(k-AB[0][i])]+G[0][i-1][abs(k+AB[0][i])]>0 else 0 for k in range(owari+1)]
  
for i in range(1, H):
  owari=80*i+1
  G[i][0][:owari]=[1 if G[i-1][0][abs(k-AB[i][0])]+G[0][i-1][abs(k+AB[i][0])]>0 else 0 for k in range(owari+1)]

from collections import deque

def f(data):
  i=data[0]
  j=data[1]
  tmp=AB[i][j]
  owari=(i+j)*80+1
  G[i][j][:owari+1]=[1 if G[i-1][j][abs(k-AB[i][j])]+G[i-1][j][abs(k+AB[i][j])]+G[i][j-1][abs(k-AB[i][j])]+G[i][j-1][abs(k+AB[i][j])]>0 else 0 for k in range(owari+1)]
  
  if i<H-1:
    q.append([i+1, j])
  if j<W-1:
    q.append([i, j+1])
    
q=deque()
q.append([1, 1])
while len(q)>0:
  data=q.popleft()
  f(data)
  
out=0
while G[-1][-1][out]==0:
  out+=1
print(out)

Submission status: Runtime Error

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

H,W = map(int,input().split())

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

C = [[0]*W for i in range(H)]

for h in range(H):
    for w in range(W):
        C[h][w] = abs(A[h][w] - B[h][w])
        
#print(C)

ZZZ = 80*73

DP = [[[0]*ZZZ for i in range(W)] for j in range(H)]

for j in range(H):
    for w in range(W):
        if h==0 and w==0:
            DP[h][w][C[h][w]] = 1
        elif h==0:
            for i in range(ZZZ):
                DP[h][w][i] = DP[h][w-1][abs(i-C[h][w])]| (DP[h][w-1][abs(i+C[h][w])] if abs(i+C[h][w])<ZZZ else 0)
        elif w==0:
            for i in range(ZZZ):
                DP[h][w][i] = DP[h-1][w][abs(i-C[h][w])]|(DP[h-1][w][abs(i+C[h][w])] if abs(i+C[h][w])<ZZZ else 0)
        else:
            for i in range(ZZZ):
                DP[h][w][i] = DP[h-1][w][abs(i-C[h][w])]|(DP[h-1][w][abs(i+C[h][w])] if abs(i+C[h][w])<ZZZ else 0)|DP[h][w-1][abs(i-C[h][w])]|(DP[h][w-1][abs(i+C[h][w])] if abs(i+C[h][w])<ZZZ else 0)
                
for i in range(ZZZ):
    if DP[H-1][W-1][i]==1:
        ans = i
        break
print(ans)

Submission status: Runtime Error

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

H,W = map(int,input().split())

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

C = [[0]*W for i in range(H)]

for h in range(H):
    for w in range(W):
        C[h][w] = abs(A[h][w] - B[h][w])
        
#print(C)

ZZZ = 80*73

DP = [[[0]*ZZZ for i in range(W)] for j in range(H)]

for j in range(H*W):
    h = j//H
    w = j%H
    if h==0 and w==0:
        DP[h][w][C[h][w]] = 1
    elif h==0:
        for i in range(ZZZ):
            DP[h][w][i] = DP[h][w-1][abs(i-C[h][w])]| (DP[h][w-1][abs(i+C[h][w])] if abs(i+C[h][w])<ZZZ else 0)
    elif w==0:
        for i in range(ZZZ):
            DP[h][w][i] = DP[h-1][w][abs(i-C[h][w])]|(DP[h-1][w][abs(i+C[h][w])] if abs(i+C[h][w])<ZZZ else 0)
    else:
        for i in range(ZZZ):
            DP[h][w][i] = DP[h-1][w][abs(i-C[h][w])]|(DP[h-1][w][abs(i+C[h][w])] if abs(i+C[h][w])<ZZZ else 0)|DP[h][w-1][abs(i-C[h][w])]|(DP[h][w-1][abs(i+C[h][w])] if abs(i+C[h][w])<ZZZ else 0)
                
for i in range(ZZZ):
    if DP[H-1][W-1][i]==1:
        ans = i
        break
print(ans)

Submission status: Runtime Error

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

H,W = map(int,input().split())

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

C = [[0]*W for i in range(H)]

for h in range(H):
    for w in range(W):
        C[h][w] = abs(A[h][w] - B[h][w])
        
#print(C)

ZZZ = 80*73

DP = [[[0]*ZZZ for i in range(W)] for j in range(H)]

for j in range(H*W):
    h = j//H
    w = j%H
    if h==0 and w==0:
        DP[h][w][C[h][w]] = 1
    elif h==0:
        for i in range(ZZZ):
            tmp = DP[h][w-1][i]
            DP[h][w][abs(i-C[h][w])] = tmp
            if i+C[h][w]<ZZZ:
                DP[h][w][abs(i+C[h][w])] = tmp
    elif w==0:
        for i in range(ZZZ):
            tmp = DP[h-1][w][i]
            DP[h][w][abs(i-C[h][w])] = tmp
            if i+C[h][w]<ZZZ:
                DP[h][w][abs(i+C[h][w])] = tmp
    else:
        for i in range(ZZZ):
            tmp = DP[h-1][w][i]
            tmp2 = DP[h][w-1][i]
            DP[h][w][abs(i-C[h][w])] = tmp|tmp2
            if i+C[h][w]<ZZZ:
                DP[h][w][abs(i+C[h][w])] = tmp|tmp2
                
for i in range(ZZZ):
    if DP[H-1][W-1][i]==1:
        ans = i
        break
print(ans)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;

int H, W;
int A[90][90], B[90][90];
bool dp[90][90][30001];

int main() {
    cin >> H >> W;
    for (int i=0; i<H; i++) for (int j=0; j<W; j++) cin >> A[i][j];
    for (int i=0; i<H; i++) for (int j=0; j<W; j++) cin >> B[i][j];
    for (int i=0; i<H; i++) for (int j=0; j<W; j++) for (int k=0; k<=30000; k++) dp[i][j][k] = false;
    dp[0][0][A[0][0]-B[0][0]+15000] = true;
    dp[0][0][B[0][0]-A[0][0]+15000] = true;
    
    for (int i=0; i<H; i++) {
        for (int j=0; j<W; j++) {
            if (i>0) {
                for (int k=0; k<=30000; k++) {
                    if (dp[i-1][j][k]) {
                        if (0<=k+A[i][j]-B[i][j] && k+A[i][j]-B[i][j]<=30000) dp[i][j][k+A[i][j]-B[i][j]] = true;
                        if (0<=k+B[i][j]-A[i][j] && k+B[i][j]-A[i][j]<=30000) dp[i][j][k+B[i][j]-A[i][j]] = true;
                    }
                }
            }
            if (j>0) {
                for (int k=0; k<=30000; k++) {
                    if (dp[i][j-1][k]) {
                        if (0<=k+A[i][j]-B[i][j] && k+A[i][j]-B[i][j]<=30000) dp[i][j][k+A[i][j]-B[i][j]] = true;
                        if (0<=k+B[i][j]-A[i][j] && k+B[i][j]-A[i][j]<=30000) dp[i][j][k+B[i][j]-A[i][j]] = true;
                    }
                }
            }
        }
    }
    
    int ans = 1000000;
    
    for (int i=0; i<=30000; i++) {
        if (dp[H-1][W-1][i]) {
            ans = min(ans, abs(i-15000));
        }
    }
    
    cout << ans << endl;
}

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3

import sys
from pprint import pprint
sys.setrecursionlimit(300000)


def solve(H: int, W: int, A: "List[List[int]]", B: "List[List[int]]"):
    diffs = [[0] * (W + 1) for _ in range(H + 1)]
    for i in range(H):
        for j in range(W):
            diffs[i][j] = abs(A[i][j] - B[i][j])
    dp = [[[0] * 6400 for _ in range(W + 1)] for _ in range(H + 1)]
    dp[0][0][diffs[0][0]] += 1
    for i in range(H):
        for j in range(W):
            tmp = dp[i][j]
            for val, flg in enumerate(tmp):
                if not flg:
                    continue
                dp[i + 1][j][abs(val + diffs[i + 1][j])] += 1
                dp[i + 1][j][abs(val - diffs[i + 1][j])] += 1
                dp[i][j + 1][abs(val + diffs[i][j + 1])] += 1
                dp[i][j + 1][abs(val - diffs[i][j + 1])] += 1
                #dp[i + 1][j].add(abs(val + diffs[i + 1][j]))
                #dp[i + 1][j].add(abs(val - diffs[i + 1][j]))
                #dp[i][j + 1].add(abs(val + diffs[i][j + 1]))
                #dp[i][j + 1].add(abs(val - diffs[i][j + 1]))
    #ret = min(dp[H - 1][W - 1])
    ret = 0
    for val, flg in enumerate(dp[H - 1][W - 1]):
        if flg:
            ret = val
            break
    print(ret)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    A = [[int(next(tokens)) for _ in range(W)] for _ in range(H)]  # type: "List[List[int]]"
    B = [[int(next(tokens)) for _ in range(W)] for _ in range(H)]  # type: "List[List[int]]"
    solve(H, W, A, B)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
t=a[i-1][j-1]
dp[i][j][k]=(dp[i-1][j][abs(k+t)]
             or dp[i-1][j][abs(k-t)]
             or dp[i][j-1][abs(k+t)]
             or dp[i][j-1][abs(k-t)])

Submission status: Runtime Error

Solution code:
from fractions import gcd
# from datetime import date, timedelta
from heapq import*
import math
from collections import defaultdict, Counter, deque
from bisect import *
import itertools
import fractions
# import sys
# sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7
# input = sys.stdin.readline


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

    dp = [[[False for i in range(1001)]
           for j in range(w + 1)] for i in range(h + 1)]

    dp[0][0][abs(a[0][0] - b[0][0])] = True
    for i in range(h):
        for j in range(w):
            for k in range(1000):
                if i + 1 < h:
                    dp[i + 1][j][k] |= dp[i][j][k +
                                            abs(a[i + 1][j] - b[i + 1][j])] or dp[i][j][abs(k - abs(a[i + 1][j] - b[i + 1][j]))]
                if j + 1 < w:
                    dp[i][j+1][k] |= dp[i][j][k +
                                            abs(a[i][j+1] - b[i][j+1])] or dp[i][j][abs(k - abs(a[i][j+1] - b[i][j+1]))]


    for i in range(1001):
        if dp[h - 1][w - 1][i]:
            print(i)
            exit()


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from fractions import gcd
# from datetime import date, timedelta
from heapq import*
import math
from collections import defaultdict, Counter, deque
from bisect import *
import itertools
import fractions
# import sys
# sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7
# input = sys.stdin.readline


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

    dp = [[[False for i in range(1001)]
           for j in range(w + 1)] for i in range(h + 1)]

    dp[0][0][abs(a[0][0] - b[0][0])] = True
    for i in range(h):
        for j in range(w):
            for k in range(1001):
                if i + 1 < h:
                    dp[i + 1][j][k] |= dp[i][j][k +
                                            abs(a[i + 1][j] - b[i + 1][j])] or dp[i][j][abs(k - abs(a[i + 1][j] - b[i + 1][j]))]
                if j + 1 < w:
                    dp[i][j+1][k] |= dp[i][j][k +
                                            abs(a[i][j+1] - b[i][j+1])] or dp[i][j][abs(k - abs(a[i][j+1] - b[i][j+1]))]


    for i in range(1001):
        if dp[h - 1][w - 1][i]:
            print(i)
            exit()


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
H,W = map(int,input().split())
A = np.zeros((H,W))
for c in [1,-1]:
    for i in range(H):
        num = list(map(int,input().split()))
        A[i,:] += np.array(num) * c

M = 160*80
dp = [[0]*W for _ in range(H)]
dp[0][0] = 1 << M
for i in range(H):
    for j in range(W):
        if i > 0:
            dp[i][j] |= dp[i-1][j]
        if j > 0:
            dp[i][j] |= dp[i][j-1]
        a = abs(A[i,j])
        dp[i][j] = (dp[i][j] << int(a)) | (dp[i][j] >> int(a))
i = M
while True:
    if (dp[H-1][W-1] >> i) & 1:
        print(i-M)
        break
    i += 1