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:
import sys
import  math
import fractions
from collections import defaultdict
stdin = sys.stdin
     
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

INF=10**18

H,W=nm()
A=[]
B=[]
for i in range(H):
    A.append(nl())

for i in range(H):
    B.append(nl())


dp=[[[] for _ in range(W)] for i in range(H)]#yoko tate sa

dp[0][0].append(A[0][0]-B[0][0])
dp[0][0].append(B[0][0]-A[0][0])
for i in range(1,H):
    for k in range(len(dp[0][i-1])):
        dp[0][i].append(dp[0][i-1][k]+A[0][i])
        dp[0][i].append(dp[0][i-1][k]-B[0][i])
        dp[0][i]=list(set(dp[0][i]))

for i in range(H):
    for k in range(W):
        if(k==0):
           for j in range(len(dp[i-1][k])):
                dp[i][k].append(dp[i-1][k][j]+A[i][k]) 
                dp[i][k].append(dp[i-1][k][j]-B[i][k])
        else:
            for j in range(len(dp[i-1][k])):
                dp[i][k].append(dp[i-1][k][j]+A[i][k]) 
                dp[i][k].append(dp[i-1][k][j]-B[i][k])
            for j in range(len(dp[i][k-1])):
                dp[i][k].append(dp[i][k-1][j]+A[i][k]) 
                dp[i][k].append(dp[i][k-1][j]-B[i][k])
        dp[i][k]=list(set(dp[i][k]))

ans_l=dp[H-1][W-1]
ans_l=list(map(lambda x:abs(x),ans_l))
ans_l.sort()

print(ans_l[0])

Submission status: Runtime Error

Solution code:
import sys
import  math
import fractions
from collections import defaultdict
stdin = sys.stdin
     
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

INF=10**18

H,W=nm()
A=[]
B=[]
for i in range(H):
    A.append(nl())

for i in range(H):
    B.append(nl())


dp=[[[] for _ in range(W)] for i in range(H)]#yoko tate sa

dp[0][0].append(A[0][0]-B[0][0])
dp[0][0].append(B[0][0]-A[0][0])
for i in range(1,H):
    for k in range(len(dp[0][i-1])):
        dp[0][i].append(dp[0][i-1][k]+A[0][i]-B[0][i])
        dp[0][i].append(dp[0][i-1][k]+B[0][i]-A[0][i])
        dp[0][i]=list(set(dp[0][i]))

for i in range(H):
    for k in range(W):
        if(k==0):
           for j in range(len(dp[i-1][k])):
                dp[i][k].append(dp[i-1][k][j]+A[i][k]-B[i][k]) 
                dp[i][k].append(dp[i-1][k][j]+B[i][k]-A[i][k])
        else:
            for j in range(len(dp[i-1][k])):
                dp[i][k].append(dp[i-1][k][j]+A[i][k]-B[i][k]) 
                dp[i][k].append(dp[i-1][k][j]+B[i][k]-A[i][k])
            for j in range(len(dp[i][k-1])):
                dp[i][k].append(dp[i][k-1][j]+A[i][k]-B[i][k]) 
                dp[i][k].append(dp[i][k-1][j]+B[i][k]-A[i][k])
        dp[i][k]=list(set(dp[i][k]))

ans_l=dp[H-1][W-1]
ans_l=list(map(lambda x:abs(x),ans_l))
ans_l.sort()

print(ans_l[0])

Submission status: Runtime Error

Solution code:
import sys
import  math
import fractions
from collections import defaultdict
stdin = sys.stdin
     
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

INF=10**18

H,W=nm()
A=[]
B=[]
for i in range(H):
    A.append(nl())

for i in range(H):
    B.append(nl())


dp=[[[] for _ in range(W)] for i in range(H)]#yoko tate sa

dp[0][0].append(A[0][0]-B[0][0])
dp[0][0].append(B[0][0]-A[0][0])
for i in range(1,H):
    for k in range(len(dp[0][i-1])):
        dp[0][i].append(dp[0][i-1][k]+A[0][i]-B[0][i])
        dp[0][i].append(dp[0][i-1][k]+B[0][i]-A[0][i])

for i in range(H):
    for k in range(W):
        if(k==0):
           for j in range(len(dp[i-1][k])):
                dp[i][k].append(dp[i-1][k][j]+A[i][k]-B[i][k]) 
                dp[i][k].append(dp[i-1][k][j]+B[i][k]-A[i][k])
        else:
            for j in range(len(dp[i-1][k])):
                dp[i][k].append(dp[i-1][k][j]+A[i][k]-B[i][k]) 
                dp[i][k].append(dp[i-1][k][j]+B[i][k]-A[i][k])
            for j in range(len(dp[i][k-1])):
                dp[i][k].append(dp[i][k-1][j]+A[i][k]-B[i][k]) 
                dp[i][k].append(dp[i][k-1][j]+B[i][k]-A[i][k])
        dp[i][k]=list(set(dp[i][k]))

ans_l=dp[H-1][W-1]
ans_l=list(map(lambda x:abs(x),ans_l))
ans_l.sort()

print(ans_l[0])

Submission status: Runtime Error

Solution code:
import sys
import  math
import fractions
from collections import defaultdict
stdin = sys.stdin
     
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))


N=int(input())
min_l=[]
max_l=[]
for k in range(N):
    A,B=nm()
    min_l.append(A)
    max_l.append(B)

min_l.sort()
max_l.sort()

if(N%2==1):
    ans=(max_l[(N-1)//2])-(min_l[(N-1)//2])+1

else:
    min_p=(min_l[N//2])
    
    max_p=(max_l[N//2])

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict
readline = sys.stdin.buffer.readline
# sys.setrecursionlimit(10**5)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


@njit
def main():
    H, W = geta(int)
    u = []
    for _ in range(H):
        u.append(list(geta(int)))

    for i in range(H):
        b = tuple(geta(int))
        for j, bj in enumerate(b):
            u[i][j] = abs(u[i][j] - bj)

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

    dp[0][0].add(u[0][0])

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

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


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict
readline = sys.stdin.buffer.readline
# sys.setrecursionlimit(10**5)
import numpy as np
from numba import njit


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


@njit
def main():
    H, W = geta(int)
    u = []
    for _ in range(H):
        u.append(list(geta(int)))

    for i in range(H):
        b = tuple(geta(int))
        for j, bj in enumerate(b):
            u[i][j] = abs(u[i][j] - bj)

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

    dp[0][0].add(u[0][0])

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

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


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict
readline = sys.stdin.buffer.readline
# sys.setrecursionlimit(10**5)
from numba import njit

def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())

@njit
def main():
    H, W = geta(int)
    u = []
    for _ in range(H):
        u.append(list(geta(int)))

    for i in range(H):
        b = tuple(geta(int))
        for j, bj in enumerate(b):
            u[i][j] = abs(u[i][j] - bj)

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

    dp[0][0].add(u[0][0])

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

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


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict
readline = sys.stdin.buffer.readline
# sys.setrecursionlimit(10**5)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


import numpy as np


def main():
    H, W = geta(int)
    u = []
    for _ in range(H):
        u.append(list(geta(int)))

    for i in range(H):
        b = tuple(geta(int))
        for j, bj in enumerate(b):
            u[i][j] = abs(u[i][j] - bj)

    u_max = 160 * H * W

    dp = [[[False] * (u_max + 1) for _ in range(W)] for _ in range(H)]

    dp[0][0][u[0][0]] = True
    for i in range(H):
        for j in range(W):
            for k in range(u_max + 1):
                if dp[i][j][k]:
                    if i != H - 1:
                        dp[i + 1][j][k + u[i + 1][j]] = True
                        dp[i + 1][j][abs(k - u[i + 1][j])] = True
                    if j != W - 1:
                        dp[i][j + 1][k + u[i][j + 1]] = True
                        dp[i][j + 1][abs(k - u[i][j + 1])] = True

    for k, t in enumerate(dp[H - 1][W - 1]):
        if t:
            print(k)
            break


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import numpy as np
h,w=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(h)]
b=[list(map(int,input().split())) for _ in range(h)]
d=[]
for i in range(h):
  d.append([abs(a[i][j]-b[i][j]) for j in range(w)])
dp=np.zeros((h,w,6400),np.int64)
# dp[r][c][j]:(r,c)まで考えたときjにできるか。0：できない。1以上：できる。
dp[0,0,d[0][0]+3200]=1
for i in range(w-1):
  if d[0][i+1]==0:
    dp[0,i+1]+=dp[0,i]
    continue
  dp[0,i+1,d[0][i+1]:]+=dp[0,i,:-d[0][i+1]]
  dp[0,i+1,:-d[0][i+1]]+=dp[0,i,d[0][i+1]:]
for i in range(h-1):
  if d[i+1][0]==0:
    dp[i+1,0]+=dp[i,0]
    continue
  dp[i+1,0,d[i+1][0]:]+=dp[i,0,:-d[i+1][0]]
  dp[i+1,0,:-d[i+1][0]]+=dp[i,0,d[i+1][0]:]
for r in range(1,h):
  for c in range(1,w):
    if d[r][c]==0:
      dp[r,c]+=dp[r-1,c]
      dp[r,c]+=dp[r,c-1]
      continue
    dp[r,c,d[r][c]:]+=dp[r-1,c,:-d[r][c]]
    dp[r,c,:-d[r][c]]+=dp[r-1,c,d[r][c]:]
    dp[r,c,d[r][c]:]+=dp[r,c-1,:-d[r][c]]
    dp[r,c,:-d[r][c]]+=dp[r,c-1,d[r][c]:]
print(min([abs(e-3200) for e in np.where(dp[h-1,w-1]>0)[0]]))

Submission status: Runtime Error

Solution code:
import numpy as np
h,w=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(h)]
b=[list(map(int,input().split())) for _ in range(h)]
d=[]
for i in range(h):
  d.append([abs(a[i][j]-b[i][j]) for j in range(w)])
dp=np.zeros((h,w,200),np.int64)
# dp[r][c][j]:(r,c)まで考えたときjにできるかbool値
dp[0,0,d[0][0]+100]=1
for i in range(w-1):
  if d[0][i+1]==0:
    dp[0,i+1]+=dp[0,i]
    continue
  dp[0,i+1,d[0][i+1]:]+=dp[0,i,:-d[0][i+1]]
  dp[0,i+1,:-d[0][i+1]]+=dp[0,i,d[0][i+1]:]
for i in range(h-1):
  if d[i+1][0]==0:
    dp[i+1,0]+=dp[i,0]
    continue
  dp[i+1,0,d[i+1][0]:]+=dp[i,0,:-d[i+1][0]]
  dp[i+1,0,:-d[i+1][0]]+=dp[i,0,d[i+1][0]:]
for r in range(1,h):
  for c in range(1,w):
    if d[r][c]==0:
      dp[r,c]+=dp[r-1,c]
      dp[r,c]+=dp[r,c-1]
      continue
    dp[r,c,d[r][c]:]+=dp[r-1,c,:-d[r][c]]
    dp[r,c,:-d[r][c]]+=dp[r-1,c,d[r][c]:]
    dp[r,c,d[r][c]:]+=dp[r,c-1,:-d[r][c]]
    dp[r,c,:-d[r][c]]+=dp[r,c-1,d[r][c]:]
print(min([abs(e-100) for e in np.where(dp[h-1,w-1]>0)[0]]))

Submission status: Runtime Error

Solution code:
import numpy as np
h,w=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(h)]
b=[list(map(int,input().split())) for _ in range(h)]
d=[]
for i in range(h):
  d.append([abs(a[i][j]-b[i][j]) for j in range(w)])
dp=np.full((h,w,200),False)
# dp[r][c][j]:(r,c)まで考えたときjにできるかbool値
dp[0,0,d[0][0]+100]=True
for i in range(w-1):
  if d[0][i+1]==0:
    dp[0,i+1]+=dp[0,i]
    continue
  dp[0,i+1,d[0][i+1]:]+=dp[0,i,:-d[0][i+1]]
  dp[0,i+1,:-d[0][i+1]]+=dp[0,i,d[0][i+1]:]
for i in range(h-1):
  if d[i+1][0]==0:
    dp[i+1,0]+=dp[i,0]
    continue
  dp[i+1,0,d[i+1][0]:]+=dp[i,0,:-d[i+1][0]]
  dp[i+1,0,:-d[i+1][0]]+=dp[i,0,d[i+1][0]:]
for r in range(1,h):
  for c in range(1,w):
    if d[r][c]==0:
      dp[r,c]+=dp[r-1,c]
      dp[r,c]+=dp[r,c-1]
      continue
    dp[r,c,d[r][c]:]+=dp[r-1,c,:-d[r][c]]
    dp[r,c,:-d[r][c]]+=dp[r-1,c,d[r][c]:]
    dp[r,c,d[r][c]:]+=dp[r,c-1,:-d[r][c]]
    dp[r,c,:-d[r][c]]+=dp[r,c-1,d[r][c]:]
print(min([abs(e-100) for e in np.where(dp[h-1,w-1]==True)[0]]))

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

H, W = map(int, input().split())
A = np.array([input().split() for _ in range(H)], dtype=int)
B = np.array([input().split() for _ in range(H)], dtype=int)
dif = np.abs(A - B).tolist()

U = (H + W) * 80
Um = U // 2

dp = [[[] for _ in range(W)] for _ in range(H)]
X = np.zeros(U + 1, dtype=bool)
X[Um + dif[0][0]] = True
X[Um - dif[0][0]] = True
dp[0][0] = X


for i in range(H):
    for j in range(W):
        if i == j == 0:
            continue
        X = np.zeros(U + 1, dtype=bool)
        d = dif[i][j]
        if i > 0:
            X[d:] |= dp[i - 1][j][:-d]
            X[:-d] |= dp[i - 1][j][d:]
        if j > 0:
            X[d:] |= dp[i][j - 1][:-d]
            X[:-d] |= dp[i][j - 1][d:]
        dp[i][j] = X

tmp = np.arange(U+1)[dp[H-1][W-1]]
ans = np.abs(tmp - Um).min()
print(ans)

Submission status: Runtime Error

Solution code:


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

amap = [list(map(int, input().split())) for i in range(H)]
bmap = [list(map(int, input().split())) for i in range(H)]
dist_map = [[amap[y][x] - bmap[y][x] for x in range(W)] for y in range(H)]

# mid = 80 * 80 * 5 // 2
mid = 20
dp = [[1 << mid] * W for y in range(H)]

dp[0][0] = ((1 << (dist_map[0][0] + mid)) | (1 << (mid - dist_map[0][0])))


for x in range(1, W):
    y = 0
    d = abs(dist_map[y][x])
    dp[y][x] = (dp[y][x - 1] << d) | (dp[y][x - 1] >> d)


for y in range(1, H):
    x = 0
    d = abs(dist_map[y][x])
    dp[y][x] = (dp[y - 1][x] << d) | (dp[y - 1][x] >> d)


for y in range(1, H):
    for x in range(1, W):
        d = abs(dist_map[y][x])
        dp[y][x] = (dp[y][x - 1] << d) | (dp[y][x - 1] >> d) | ((dp[y - 1][x] << d) | (dp[y - 1][x] >> d))


ans = dp[-1][-1]

for i in range(mid + 1):
    if (ans & (1 << (mid - i))) or (ans & (1 << (mid + i))):
        print(i)
        exit()

Submission status: Runtime Error

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

H, W = map(int, input().split())
Maze = [list(map(int, input().split())) for _ in range(H)]
Mazemax = 0
for y_ in range(H):
    B = list(map(int, input().split()))
    for x_ in range(W):
        z = abs(Maze[y_][x_] - B[x_])
        Maze[y_][x_] = z
        Mazemax += z

DP = [[[False] * (Mazemax*2) for _ in range(W)] for __ in range(H)]
DP[0][0][Maze[0][0]] = True

for i in range(H):
    for j in range(W):
        for k in range(Mazemax):
            if (i == 0) and (j == 0):
                break
            DP[i][j][k] = DP[i-1][j][abs(k-Maze[i][j])] or DP[i-1][j][k+Maze[i][j]] or DP[i][j-1][abs(k-Maze[i][j])] or DP[i][j-1][k + Maze[i][j]]
            if (i == H-1) and (j == W-1):
                if DP[i][j][k]:
                    print(k)
                    exit()

Submission status: Runtime Error

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

H, W = map(int, input().split())
Maze = [list(map(int, input().split())) for _ in range(H)]
Mazemax = 0
for y_ in range(H):
    B = list(map(int, input().split()))
    for x_ in range(W):
        z = abs(Maze[y_][x_] - B[x_])
        Maze[y_][x_] = z
        Mazemax += z

DP = [[[False] * (Mazemax*2) for _ in range(W)] for __ in range(H)]
DP[0][0][Maze[0][0]] = True

for i in range(H):
    for j in range(W):
        for k in range(Mazemax):
            if (i == 0) and (j == 0):
                break
            DP[i][j][k] = DP[i-1][j][abs(k-Maze[i][j])] or DP[i-1][j][k+Maze[i][j]] or DP[i][j-1][abs(k-Maze[i][j])] or DP[i][j-1][k + Maze[i][j]]
ans = float('inf')
for i, an in enumerate(DP[H-1][W-1]):
    if an:
        print(i)
        exit()

Submission status: Runtime Error

Solution code:
h, w = map(int, input().split())
grid = [[0] * (w + 1)]
for _ in range(h):
    grid.append([0] + list(map(int, input().split())))
for i in range(1, h + 1):
    l = [0] + list(map(int, input().split()))
    for j in range(w + 1):
        grid[i][j] = abs(grid[i][j] - l[j])

biggest = max([max(i) for i in grid])
m = (h + w) * biggest

unba = [[[False] * m for _ in range(w + 1)] for _ in range(h + 1)]

for i in range(1, w + 1):
    unba[0][i][0] = True
for i in range(1, h + 1):
    unba[i][0][0] = True

for i in range(1, h + 1):
    for j in range(1, w + 1):
        for k in range(m):
            if unba[i-1][j][k] or unba[i][j-1][k]:
                unba[i][j][grid[i][j] + k] = True
                unba[i][j][abs(grid[i][j] - k)] = True

l = [i for i in range(m) if unba[h][w][i]]
print(min(l))

Submission status: Runtime Error

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

biggest = max([max(i) for i in grid])
m = (h + w) * biggest

unba = [[[False] * m for _ in range(w)] for _ in range(h)]

# 0行目
unba[0][0][grid[0][0]] = True
for i in range(1, w):
    for j in range(m):
        if unba[0][i-1][j]:
            unba[0][i][grid[0][i] + j] = True
            unba[0][i][abs(grid[0][i] - j)] = True

# 1~h-1行目
for i in range(1, h):

    # i行0列
    for j in range(m):
        if unba[i-1][0][j]:
            unba[i][0][grid[i][0] + j] = True
            unba[i][0][abs(grid[i][0] - j)] = True

    # i行j列
    for j in range(1, w):
        for k in range(m):
            if unba[i-1][j][k] or unba[i][j-1][k]:
                unba[i][j][grid[i][j] + k] = True
                unba[i][j][abs(grid[i][j] - k)] = True

l = [i for i in range(m) if unba[h-1][w-1][i]]
print(min(l))

Submission status: Runtime Error

Solution code:
h, w = map(int, input().split())
mat = []
for i in range(h):
  a = list(map(int, input().split()))
  mat.append(a)
for i in range(h):
  b = list(map(int, input().split()))
  for j in range(w):
    mat[i][j] = abs(mat[i][j]-b[j])
m = max(map(max, mat))
dp = [[[False]*(m*(h+w)) for i in range(w)] for k in range(h)]
dp[0][0][mat[0][0]] = True
for y in range(h):
  for x in range(w):
      for k in range(m*(y+x)):
        if x > 0 and dp[y][x-1][k] or y > 0 and dp[y-1][x][k]:
          d = dp[y][x]
          d[k+mat[y][x]] = True
          d[abs(k-mat[y][x])] = True

for k in range(m*(h+w)):
  if dp[h-1][w-1][k]:
    print(k)
    exit()

Submission status: Runtime Error

Solution code:
h, w = map(int, input().split())
mat = []
for i in range(h):
  a = list(map(int, input().split()))
  mat.append(a)
for i in range(h):
  b = list(map(int, input().split()))
  for j in range(w):
    mat[i][j] = abs(mat[i][j]-b[j])

dp = [[[False]*(80*(h+w)) for i in range(w)] for k in range(h)]
dp[0][0][mat[0][0]] = True
for y in range(h):
  for x in range(w):
      for k in range(sum(map(sum, mat[y][x]))):
        if x > 0 and dp[y][x-1][k] or y > 0 and dp[y-1][x][k]:
          d = dp[y][x]
          d[k+mat[y][x]] = True
          d[abs(k-mat[y][x])] = True

for k in range(80*(h+w)):
  if dp[h-1][w-1][k]:
    print(k)
    exit()

Submission status: Runtime Error

Solution code:
h, w = map(int, input().split())
mat = []
count = 0
for i in range(h):
  a = list(map(int, input().split()))
  mat.append(a)
for i in range(h):
  b = list(map(int, input().split()))
  for j in range(w):
    mat[i][j] = abs(mat[i][j]-b[j])
    count += mat[i][j]

dp = [[[False]*(count) for i in range(w)] for k in range(h)]
dp[0][0][mat[0][0]] = True
for y in range(h):
  for x in range(w):
      for k in range(count):
        if x > 0 and dp[y][x-1][k] or y > 0 and dp[y-1][x][k]:
          d = dp[y][x]
          d[k+mat[y][x]] = True
          d[abs(k-mat[y][x])] = True

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

Submission status: Runtime Error

Solution code:
h, w = map(int, input().split())
mat = []
for i in range(h):
  a = list(map(int, input().split()))
  mat.append(a)
for i in range(h):
  b = list(map(int, input().split()))
  for j in range(w):
    mat[i][j] = abs(mat[i][j]-b[j])

dp = [[80*80*80]*w for i in range(h)]
for y in range(h):
  for x in range(w):
    if x > 0:
      dp[y][x] = min(dp[y][x], abs(dp[y][x-1]-mat[y][x]))
    if y > 0:
      dp[y][x] = min(dp[y][x], abs(dp[y-1][x]-mat[y][x]))
print(dp[h][w])

Submission status: Runtime Error

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

biggest = max([max(i) for i in grid])
m = (h + w) * biggest

unba = [[[False for _ in range(m)] for _ in range(w)] for _ in range(h)]

# 0行目
unba[0][0][grid[0][0]] = True
for i in range(1, w):
    for j in range(m):
        if unba[0][i-1][j]:
            unba[0][i][grid[0][i] + j] = True
            unba[0][i][abs(grid[0][i] - j)] = True

# 1~h-1行目
for i in range(1, h):

    # i行0列
    for j in range(m):
        if unba[i-1][0][j]:
            unba[i][0][grid[i][0] + j] = True
            unba[i][0][abs(grid[i][0] - j)] = True

    # i行j列
    for j in range(1, w):
        for k in range(m):
            if unba[i-1][j][k] or unba[i][j-1][k]:
                unba[i][j][grid[i][j] + k] = True
                unba[i][j][abs(grid[i][j] - k)] = True

l = [i for i in range(m) if unba[h-1][w-1][i]]
print(min(l))

Submission status: Runtime Error

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

biggest = max([max(i) for i in grid])
m = (h + w) * biggest

unba = [[[0 for _ in range(m)] for _ in range(w)] for _ in range(h)]

# 0行目
unba[0][0][grid[0][0]] = 1
for i in range(1, w):
    for j in range(m):
        if unba[0][i-1][j] == 1:
            unba[0][i][grid[0][i] + j] = 1
            unba[0][i][abs(grid[0][i] - j)] = 1

# 1~h-1行目
for i in range(1, h):

    # i行0列
    for j in range(m):
        if unba[i-1][0][j] == 1:
            unba[i][0][grid[i][0] + j] = 1
            unba[i][0][abs(grid[i][0] - j)] = 1

    # i行j列
    for j in range(1, w):
        for k in range(m):
            if unba[i-1][j][k] == 1 or unba[i][j-1][k] == 1:
                unba[i][j][grid[i][j] + k] = 1
                unba[i][j][abs(grid[i][j] - k)] = 1

l = [i for i in range(m) if unba[h-1][w-1][i] == 1]
print(min(l))

Submission status: Runtime Error

Solution code:
h, w = map(int, input().split())
grid = []
for _ in range(h):
    grid.append(list(map(int, input().split())))
for i in range(h):
    l = list(map(int, input().split()))
    for j in range(w):
        grid[i][j] = grid[i][j] - l[j]

biggest = max([max([max(i) for i in grid]), -min([min(i) for i in grid])])
m = (h + w) * biggest

unba = [[[0 for _ in range(2*m)] for _ in range(w)] for _ in range(h)]

# 0行目
unba[0][0][grid[0][0]] = 1
unba[0][0][-grid[0][0]] = 1
for i in range(1, w):
    for j in range(-m, m):
        if unba[0][i-1][j] == 1:
            unba[0][i][grid[0][i] + j] = 1
            unba[0][i][grid[0][i] - j] = 1

# 1~h-1行目
for i in range(1, h):

    # i行0列
    for j in range(-m, m):
        if unba[i-1][0][j] == 1:
            unba[i][0][grid[i][0] + j] = 1
            unba[i][0][grid[i][0] - j] = 1

    # i行j列
    for j in range(1, w):
        for k in range(-m, m):
            if unba[i-1][j][k] == 1 or unba[i][j-1][k]:
                unba[i][j][grid[i][j] + k] = 1
                unba[i][j][grid[i][j] - k] = 1

ans = [abs(i) for i in range(-m, m) if unba[h-1][w-1][i] == 1]
print(min(ans))

Submission status: Runtime Error

Solution code:
h, w = map(int, input().split())
grid = []
for _ in range(h):
    grid.append(list(map(int, input().split())))
for i in range(h):
    l = list(map(int, input().split()))
    for j in range(w):
        grid[i][j] = grid[i][j] - l[j]

biggest = max([max(i) for i in grid])
m = (h + w) * biggest

unba = [[[0 for _ in range(2*m)] for _ in range(w)] for _ in range(h)]

# 0行目
unba[0][0][grid[0][0]] = 1
unba[0][0][-grid[0][0]] = 1
for i in range(1, w):
    for j in range(-m, m):
        if unba[0][i-1][j] == 1:
            unba[0][i][grid[0][i] + j] = 1
            unba[0][i][grid[0][i] - j] = 1

# 1~h-1行目
for i in range(1, h):

    # i行0列
    for j in range(-m, m):
        if unba[i-1][0][j] == 1:
            unba[i][0][grid[i][0] + j] = 1
            unba[i][0][grid[i][0] - j] = 1

    # i行j列
    for j in range(1, w):
        for k in range(-m, m):
            if unba[i-1][j][k] == 1 or unba[i][j-1][k]:
                unba[i][j][grid[i][j] + k] = 1
                unba[i][j][grid[i][j] - k] = 1

ans = [abs(i) for i in range(-m, m) if unba[h-1][w-1][i] == 1]
print(min(ans))

Submission status: Runtime Error

Solution code:
h,w=map(int,input().split())
dp=[[0 for i in range(w+1)] for j in range(h+1)]

A=[list(map(int,input().split())) for j in range(w)]
B=[list(map(int,input().split())) for j in range(w)]
C=[[abs(A[i][j]-B[i][j]) for j in range(h)] for i in range(w)]    

for i in range(h):
    for j in range(w):
        now=C[i][j]
        dp[i+1][j+1]=min(abs(dp[i][j+1]-now),abs(dp[i+1][j]-now))

print(dp[h][w])

Submission status: Runtime Error

Solution code:
h,w=map(int,input().split())
dp=[[[0] for i in range(w+1)] for j in range(h+1)]

A=[list(map(int,input().split())) for j in range(w)]
B=[list(map(int,input().split())) for j in range(w)]
C=[[abs(A[i][j]-B[i][j]) for j in range(h)] for i in range(w)]    

for i in range(h):
    for j in range(w):
        now=C[i+1][j+1]
        dp[i+1][j+1]=min(abs(dp[i][j+1]-now),abs(dp[i+1][j]-now))

print(dp[h][w])

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
input=sys.stdin.readline
h,w=map(int,input().split())
red=[list(map(int,input().split()))+[0] for i in range(h)]+[[0 for i in range(w+1)]]
blue=[list(map(int,input().split()))+[0] for i in range(h)]+[[0 for i in range(w+1)]]
field = [[None]*(w+1) for i in range(h+1)]
    for i in range(h):
        for j in range(w):
            field[i][j] = np.zeros(6500, np.bool)
for i in range(h):
    for j in range(w):
        for f in range(6401):
            if field[i][j][f]:
                field[i][j+1][f+abs(red[i][j+1]-blue[i][j+1])]=True
                field[i][j+1][abs(f-abs(red[i][j+1]-blue[i][j+1]))]=True
                field[i+1][j][f+abs(red[i+1][j]-blue[i+1][j])]=True
                field[i+1][j][abs(f-abs(red[i+1][j]-blue[i+1][j]))]=True
for i in range(6500):
    if field[h-1][w-1][i]:print(i);exit()

Submission status: Runtime Error

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

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