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 time
def input():
    return sys.stdin.readline()[:-1]
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)]
kata=[]
for i in range(h):
    tmp=[]
    for j in range(w):
        tmp.append(abs(a[i][j]-b[i][j]))
    kata.append(tmp)
# print(kata)
tmp=0
for i in range(h):
    tmp=max(tmp,max(kata[i]))
# print(tmp)

dp=[[[0 for i in range(tmp*(h+w)+1)] for j in range(w+1)] for k in range(h+1)]
dp[0][0][kata[0][0]]+=1
i=0
j=0
# print(dp)
while i+j!=h+w-2:
    # print(i,j)
    for k in range(tmp*(h+2)+1):
        if dp[i][j][k]!=0:
            if i+1!=h:
                dp[i+1][j][k+kata[i+1][j]]+=1
                dp[i+1][j][abs(k-kata[i+1][j])]+=1
            if j+1!=w:
                dp[i][j+1][k+kata[i][j+1]]+=1
                dp[i][j+1][abs(k-kata[i][j+1])]+=1
    i-=1
    j+=1
    if i<0:
        i=abs(i+j)+1
        j=0
    while i>=h:
        i-=1
        j+=1
    # time.sleep(1)
# print(dp[1][0])
# print(dp[0][1])
# print(dp[h-1][w-1])
for i in range(tmp*(h+w)+1):
    if dp[h-1][w-1][i]!=0:
        print(i)
        quit()

Submission status: Runtime Error

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    a=sorted([random.randint(0,5) for _ in range(n)])[::-1]
    return n,a

show_flg=False
show_flg=True

h,w=LI()
ans=0
a=[[0]*(1+w)]
b=[[0]*(1+w)]
for i in range(h):
    a.append([0]+LI())
for i in range(h):
    b.append([0]+LI())

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

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

for i in range(1,h+1):
    for j in range(1,w+1):
        d=a[i][j]-b[i][j]
        M=80*(160-i-j)
        m=-80*(160-i-j)

        for x in dp[i-1][j]:
            if m<=x+d<=M:dp[i][j].add(x+d)
            if m<=x-d<=M:dp[i][j].add(x-d)

        for x in dp[i][j-1]:
            if m<=x+d<=M:dp[i][j].add(x+d)
            if m<=x-d<=M:dp[i][j].add(x-d)

ans=min([abs(i) for i in dp[h][w]])

print(ans)

Submission status: Runtime Error

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    a=sorted([random.randint(0,5) for _ in range(n)])[::-1]
    return n,a

show_flg=False
show_flg=True

h,w=LI()
ans=0
a=[[0]*(1+w)]
b=[[0]*(1+w)]
for i in range(h):
    a.append([0]+LI())
for i in range(h):
    b.append([0]+LI())

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

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

for i in range(1,h+1):
    for j in range(1,w+1):
        d=a[i][j]-b[i][j]
        for x in dp[i-1][j]:
            M=80*(160-i-j)
            m=-80*(160-i-j)
            if m<=x+d<=M:dp[i][j].add(x+d)
            if m<=x-d<=M:dp[i][j].add(x-d)

        for x in dp[i][j-1]:
            if m<=x+d<=M:dp[i][j].add(x+d)
            if m<=x-d<=M:dp[i][j].add(x-d)

ans=min([abs(i) for i in dp[h][w]])

print(ans)

Submission status: Runtime Error

Solution code:
H, W = [int(x) for x in input().split()] A = [[0]*W for i in range(H)] for c in [1, -1]: for i in range(H): arr = [int(x) for x in input().split()] for j in range(W): A[i][j] += arr[j] * c M = 160*80 dp = [[0]*W for i 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] << a) | (dp[i][j] >> a) ans = M for i in range(2*M): if dp[H-1][W-1] & (1 << i) > 0: ans = min(ans, abs(M-i)) print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
i8 = np.int64
i4 = np.int32

def calc(dp1, dp2, k):
    dp2[k:] += dp1[:dp1.shape[0]-k]
    dp2[:dp2.shape[0]-k] += dp1[k:]

def solve(z, dp):
    zero = dp.shape[2] // 2
    dp[0, 0, zero + z[0, 0]] = 1
    dp[0, 0, zero - z[0, 0]] = 1
    for x in range(1, z.shape[1]):
        calc(dp[0, x - 1], dp[0, x], z[0, x])
    for y in range(1, z.shape[0]):
        calc(dp[y - 1, 0], dp[y, 0], z[y, 0])
        for x in range(1, z.shape[1]):
            calc(dp[y, x - 1], dp[y, x], z[y, x])
            calc(dp[y - 1, x], dp[y, x], z[y, x])
    for i in range(zero, dp.shape[2]):
        if dp[dp.shape[0] - 1, dp.shape[1] - 1, i] > 0:
            return i - zero
    return -1

def main2():
    stdin = open('/dev/stdin')
    H, W = map(int, stdin.readline().split())
    a = np.empty((H, W), i8)
    b = np.empty((H, W), i8)
    for i in range(H):
        for j, c in enumerate(map(int, stdin.readline().split())):
            a[i, j] = c
    for i in range(H):
        for j, c in enumerate(map(int, stdin.readline().split())):
            b[i, j] = c
    z = np.abs(a - b)
    if H > W:
        z = z.T.copy()
    dp = np.zeros((H, W, 80 * 80 * 80*2 + 1), i8)
    ans = solve(z, dp)
    print(ans)


main2()

Submission status: Runtime Error

Solution code:
import numpy as np
i8 = np.int64
i4 = np.int32

def calc(dp1, dp2, k):
    dp2[k:] += dp1[:-k]
    dp2[:-k] += dp1[k:]

def solve(z, dp):
    zero = dp.shape[2] // 2
    dp[0, 0, zero + z[0, 0]] = 1
    dp[0, 0, zero - z[0, 0]] = 1
    for x in range(1, z.shape[1]):
        calc(dp[0, x - 1], dp[0, x], z[0, x])
    for y in range(1, z.shape[0]):
        calc(dp[y - 1, 0], dp[y, 0], z[y, 0])
        for x in range(1, z.shape[1]):
            calc(dp[y, x - 1], dp[y, x], z[y, x])
            calc(dp[y - 1, x], dp[y, x], z[y, x])
    for i in range(zero, dp.shape[2]):
        if dp[dp.shape[0] - 1, dp.shape[1] - 1, i] > 0:
            return i - zero
    return -1


def main2():
    stdin = open('/dev/stdin')
    H, W = map(int, stdin.readline().split())
    a = np.empty((H, W), i8)
    b = np.empty((H, W), i8)
    for i in range(H):
        for j, c in enumerate(map(int, stdin.readline().split())):
            a[i, j] = c
    for i in range(H):
        for j, c in enumerate(map(int, stdin.readline().split())):
            b[i, j] = c
    z = np.abs(a - b)
    if H > W:
        z = z.T.copy()
    dp = np.zeros((H, W, 80 * 80 * 80*2 + 1), i8)
    ans = solve(z, dp)
    print(ans)

main2()

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import itertools
import numpy as np

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

X = (H + W) * 80
# X点持った状態から始める
dp = [[0] * W for _ in range(H)]
d = abs(A[0][0] - B[0][0])
dp[0][0] = np.zeros(X+X+1,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(X+X+1,np.bool)
        if h != 0:
            x[d:] |= dp[h-1][w][:-d]
            x[:-d] |= dp[h-1][w][d:]
        if w != 0:
            x[d:] |= dp[h][w-1][:-d]
            x[:-d] |= dp[h][w-1][d:]
        dp[h][w] = x

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

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

Submission status: Runtime Error

Solution code:
# problem E

H,W=map(int,input().split())
A=[]
for i in range(H):
    A.append(list(map(int,input().split())))
B=[]
for i in range(H):
    B.append(list(map(int,input().split())))
D=[[abs(A[i][j]-B[i][j]) for j in range(W)] for i in range(H)]
M=max([max(Di) for Di in D])
dmax=(H+W-1)*M+1

dp=[[[False for d in range(dmax)] for j in range(W)] for i in range(H)]
dp[0][0][D[0][0]]=True

for j in range(1,W):
    for d in range(j*M+1):
        if dp[0][j-1][d]:
            dp[0][j][d+D[0][j]]=True
            dp[0][j][abs(d-D[0][j])]=True

for i in range(1,H):
    for d in range(i*M+1):
        if dp[i-1][0][d]:
            dp[i][0][d+D[i][0]]=True
            dp[i][0][abs(d-D[i][0])]=True

for i in range(1,H):
    for j in range(1,W):
        for d in range((i+j)*M):
            if dp[i-1][j][d] or dp[i][j-1][d]:
                dp[i][j][d+D[i][j]]=True
                dp[i][j][abs(d-D[i][j])]=True

ans=min([d for d in range(dmax) if dp[H-1][W-1][d]])

print(ans)

Submission status: Runtime Error

Solution code:
# problem E

H,W=map(int,input().split())
A=[]
for i in range(H):
    A.append(list(map(int,input().split())))
B=[]
for i in range(H):
    B.append(list(map(int,input().split())))
D=[[abs(A[i][j]-B[i][j]) for j in range(W)] for i in range(H)]
M=max([max(Di) for Di in D])
dmax=(H+W-1)*M+1

dp=[[[False for d in range(dmax)] for j in range(W)] for i in range(H)]
dp[0][0][D[0][0]]=True

for j in range(1,W):
    for d in range(j*M+1):
        if dp[0][j-1][d]:
            dp[0][j][d+D[0][j]]=True
            dp[0][j][abs(d-D[0][j])]=True

for i in range(1,H):
    for d in range(i*M+1):
        if dp[i-1][0][d]:
            dp[i][0][d+D[i][0]]=True
            dp[i][0][abs(d-D[i][0])]=True

for i in range(1,H):
    for j in range(1,W):
        for d in range((i+j)*M):
            if dp[i-1][j][d]:
                dp[i][j][d+D[i][j]]=True
                dp[i][j][abs(d-D[i][j])]=True
            if dp[i][j-1][d]:
                dp[i][j][d+D[i][j]]=True
                dp[i][j][abs(d-D[i][j])]=True

ans=min([d for d in range(dmax) if dp[H-1][W-1][d]])

print(ans)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
def inpl(): return list(map(int, input().split()))

H, W = inpl()
A = [inpl() for _ in range(H)]
B = [inpl() for _ in range(W)]

DP = [[0 for _ in range(W+1)] for _ in range(H+1)]
DP[0][0] = 1 << 12800

for h in range(H):
    for w in range(W):
        d = abs(A[h][w] - B[h][w])
        DP[h+1][w] |= DP[h][w] >> d
        DP[h+1][w] |= DP[h][w] << d
        DP[h][w+1] |= DP[h][w] >> d
        DP[h][w+1] |= DP[h][w] << d
l = 1 << 12800
r = 1 << 12800
for i in range(12801):
    if (DP[-1][-2]& l) | (DP[-1][-2] & r):
        print(i)
        break
    l = l << 1
    r = r >> 1

Submission status: Runtime Error

Solution code:
def inpl(): return list(map(int, input().split()))

H, W = inpl()
A = [inpl() for _ in range(H)]
B = [inpl() for _ in range(W)]

DP = [[0 for _ in range(W+1)] for _ in range(H+1)]
DP[0][0] = 1 << 12800

for h in range(H):
    for w in range(W):
        d = abs(A[h][w] - B[h][w])
        DP[h+1][w] |= DP[h][w] >> d
        DP[h+1][w] |= DP[h][w] << d
        DP[h][w+1] |= DP[h][w] >> d
        DP[h][w+1] |= DP[h][w] << d
l = 1 << 12800
r = 1 << 12800
for i in range(12800):
    if (DP[-1][-2]& l) | (DP[-1][-2] & r):
        print(i)
        break
    l = l << 1
    r = r >> 1

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)]
g = [[0]*w for _ in range(h)]
for i in range(h):
  for j in range(w):
    g[i][j] = abs(a[i][j] - b[i][j])
a = b = 0
m = max(max(x) for x in g)*(h+w)//2 + 1
dp = [[[False]*m for _ in range(w+1)] for _ in range(h+1)]
dp[0][1][0] = True
dp[1][0][0] = True
for i in range(1,h+1):
  for j in range(1,w+1):
    for x in range(m):
      if dp[i-1][j][x] or dp[i][j-1][x]:
        dp[i][j][abs(x-g[i-1][j-1])] |= True
        if x + g[i-1][j-1] < 3000:
            dp[i][j][x+g[i-1][j-1]] |= True
for x in range(m):
  if dp[h][w][x]:
    print(x)
    break

Submission status: Runtime Error

Solution code:
H, W = map(int, input().split())
M = (H + W) * 80

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

dp = [[0] * W for _ in range(H)]
dp[0][0] = (1 << (M - abs(A[0][0] - B[0][0])))

for h in range(H):
    for w, (a, b) in enumerate(zip(A[h], B[h])):
        d = abs(a - b)
        if d == 0:
            continue
        mask = 0
        if h > 0:
            mask |= (dp[h - 1][w] << d)
            mask |= (dp[h - 1][w] >> d)
        if w > 0:
            mask |= (dp[h][w - 1] << d)
            mask |= (dp[h][w - 1] >> d)
        dp[h][w] |= mask

state = dp[-1][-1]
nums = []
for digit, b in enumerate(bin(state)[2:][:: -1]):
    if b == '1':
        nums.append(digit - M)
ans = min(abs(n) for n in nums)
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)]
g = [[0]*w for _ in range(h)]
for i in range(h):
  for j in range(w):
    g[i][j] = abs(a[i][j] - b[i][j])
a = b = 0
m = max(max(x) for x in g)*(h+w)
dp = [[[False]*m for _ in range(w+1)] for _ in range(h+1)]
dp[0][1][0] = True
dp[1][0][0] = True
for i in range(1,h+1):
  for j in range(1,w+1):
    for x in range(m):
      if dp[i-1][j][x] or dp[i][j-1][x]:
        dp[i][j][abs(x-g[i-1][j-1])] |= True
        if x + g[i-1][j-1] < 3000:
            dp[i][j][x+g[i-1][j-1]] |= True
for x in range(m):
  if dp[h][w][x]:
    print(x)
    break

Submission status: Runtime Error

Solution code:
H, W = map(int, input().split())
M = (H + W) * 80

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

dp = [[0] * W for _ in range(H)]
dp[0][0] |= (1 << (M - abs(A[0][0] - B[0][0])))

for h in range(H):
    for w, (a, b) in enumerate(zip(A[h], B[h])):
        d = abs(a - b)
        if d == 0:
            continue
        mask = 0
        if h > 0:
            mask |= (dp[h - 1][w] << d)
            mask |= (dp[h - 1][w] >> d)
        if w > 0:
            mask |= (dp[h][w - 1] << d)
            mask |= (dp[h][w - 1] >> d)
        dp[h][w] |= mask

state = dp[-1][-1]
nums = []
for digit, b in enumerate(bin(state)[2:][:: -1]):
    if b == '1':
        nums.append(M - digit)
ans = min(abs(n) for n in nums)
print(ans)

Submission status: Runtime Error

Solution code:
H, W = map(int, input().split())
M = (H + W) * 80

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

dp = [[0] * W for _ in range(H)]
dp[0][0] |= (1 << (M - abs(A[0][0] - B[0][0])))

for h in range(H):
    for w, (a, b) in enumerate(zip(A[h], B[h])):
        d = abs(a - b)
        if d == 0:
            continue
        mask = 0
        if h > 0:
            mask |= (dp[h - 1][w] << d)
            mask |= (dp[h - 1][w] >> d)
        if w > 0:
            mask |= (dp[h][w - 1] << d)
            mask |= (dp[h][w - 1] >> d)
        dp[h][w] = mask

state = dp[-1][-1]
nums = []
for digit, b in enumerate(bin(state)[2:][:: -1]):
    if b == '1':
        nums.append(M - digit)
ans = min(abs(n) for n in nums)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict
input = sys.stdin.readline

H, W = map(int, input().split())
M = (H + W) * 100

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

dp = [[0] * W for _ in range(H)]
dp[0][0] |= (1 << (M - abs(A[0][0] - B[0][0])))

for h in range(H):
    for w, (a, b) in enumerate(zip(A[h], B[h])):
        d = abs(a - b)
        if d == 0:
            continue
        mask = 0
        if h > 0:
            mask |= (dp[h - 1][w] << d)
            mask |= (dp[h - 1][w] >> d)
        if w > 0:
            mask |= (dp[h][w - 1] << d)
            mask |= (dp[h][w - 1] >> d)
        dp[h][w] = mask

state = dp[-1][-1]
nums = []
for digit, b in enumerate(bin(state)[2:][:: -1]):
    if b == '1':
        nums.append(M - digit)
ans = min(abs(n) for n in nums)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict
input = sys.stdin.readline

H, W = map(int, input().split())
M = (H + W) * 80

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

dp = [[0] * W for _ in range(H)]
dp[0][0] |= (1 << (M - abs(A[0][0] - B[0][0])))

for h in range(H):
    for w, (a, b) in enumerate(zip(A[h], B[h])):
        d = abs(a - b)
        if d == 0:
            continue
        mask = 0
        if h > 0:
            mask |= (dp[h - 1][w] << d)
            mask |= (dp[h - 1][w] >> d)
        if w > 0:
            mask |= (dp[h][w - 1] << d)
            mask |= (dp[h][w - 1] >> d)
        dp[h][w] |= mask

state = dp[-1][-1]
nums = []
for digit, b in enumerate(bin(state)[2:][:: -1]):
    if b == '1':
        nums.append(M - digit)
ans = min(abs(n) for n in nums)
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 = [[abs(a[i][j] - b[i][j]) for j in range(w)] for i in range(h)]

dp = [[0] * w for i in range(h)]
dp[0][0] = 1 << c[0][0]

for j in range(1, w):
  dp_str = bin(dp[0][j-1])[:1:-1]
  for num, flag in enumerate(dp_str):
    if flag == '1'
      dp[0][j] |= 1 << abs(c[0][j] - num)
      dp[0][j] |= 1 << c[0][j] + num
    
for i in range(1, h):
  dp_str = bin(dp[i-1][0])[:1:-1]
  for num, flag in enumerate(dp_str):
    if flag == '1'
      dp[i][0] |= 1 << abs(c[i][0] - num)
      dp[i][0] |= 1 << c[i][0] + num
    
for i in range(1, h):
  for j in range(1, w):
    dp_str = bin(dp[i][j-1])[:1:-1]
    for num, flag in enumerate(dp_str):
      if flag == '1'
        dp[i][j] |= 1 << abs(c[i][j] - num)
        dp[i][j] |= 1 << c[i][j] + num
    dp_str = bin(dp[i-1][j])[:1:-1]
    for num, flag in enumerate(dp_str):
      if flag == '1'
        dp[i][j] |= 1 << abs(c[i][j] - num)
        dp[i][j] |= 1 << c[i][j] + num
      
print(bin(dp[-1][-1])[::-1].index('1'))

Submission status: Runtime Error

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

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

D = [[abs(A[i][j]) - abs(B[i][j]) for j in range(W)] for i in range(H)]
R = 160*80
dp = [[[False for k in range(R)] for j in range(W)] for i in range(H)]
dp[0][0][D[0][0]] = True
for i in range(H):
	for j in range(W):
		for n in range(R):
			if not dp[i][j][n]:
				continue
			if j != W-1:
				d = D[i][j+1]
				dp[i][j+1][n+d] = True
				dp[i][j+1][abs(n-d)] = True
			if i != H-1:
				d = D[i+1][j]
				dp[i+1][j][n+d] = True
				dp[i+1][j][abs(n-d)] = True

h,w = H-1, W-1
for i in range(160*80):
	if dp[h][w][i]:
		print(i)
		exit()

Submission status: Runtime Error

Solution code:
#!/bin/bash
''':'
docker run --rm -it -v $(cd $(dirname $0) && pwd):/vo:ro pypy:3-2.4.0 /bin/bash -c "pypy3 /vo/$(basename $0) < /vo/g.inp"; exit $?
exit 0
'''
import sys

def _ia(): return [ int(x) for x in sys.stdin.readline().strip().split() ]

# read input
h,w = _ia()
ab = []
for _ in range(h): ab.append(_ia())
for i in range(h):
    r = ab[i]
    for j,bj in enumerate(_ia()):
        r[j] = abs(r[j] - bj)
    t = max(r)

# initialize
dp = [[None for _ in range(w)] for _ in range(h)]
dp[0][0] = {ab[0][0]}
hw1 = h + w - 1
for ij in range(1,hw1):
    iend = ( hw1 - ij ) * 80
    for i in range(min(ij+1,h)):
        j = ij - i
        if j>=w: continue
        #
        ref = set()
        if i>0: ref|= dp[i-1][j]
        if j>0: ref|= dp[i][j-1]
        #
        x = ab[i][j]
        nxt = dp[i][j] = set()
        for idx in ref:
            ix = abs(idx-x)
            if ix<iend: nxt.add(ix)
            ix = idx + x
            if ix<iend: nxt.add(ix)
            
# stdout
print(min(dp[h-1][w-1]))

Submission status: Runtime Error

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

h,w = LI()
a = [LI() for _ in range(h)]
b = [LI() for _ in range(h)]

lst = [[0]*w for _ in range(h)]
m = 0
for i in range(h):
    for j in range(w):
        lst[i][j] = abs(a[i][j] - b[i][j])
        m = max(m,abs(a[i][j] - b[i][j]))

dp = [[[0]*((h+w-1)*m) for _ in range(w)] for _ in range(h)]
dp[0][0][lst[0][0]] = 1
for i in range(h):
    for j in range(w):
        for k in range(m*(h+w-1)):
            if dp[i][j][k]:
                if i+1 < h:
                    if k+lst[i+1][j] < m*(h+w-1):
                        dp[i+1][j][k+lst[i+1][j]] = 1
                    if abs(k-lst[i+1][j]) < m*(h+w-1):
                        dp[i+1][j][abs(k-lst[i+1][j])] = 1
                if j+1 < w:
                    if k+lst[i][j+1] < m*(h+w-1):
                        dp[i][j+1][k+lst[i][j+1]] = 1
                    if abs(k-lst[i][j+1]) < m*(h+w-1):
                        dp[i][j+1][abs(k-lst[i][j+1])] = 1

ans = 10**10
for i in range(m*(h+w-1)):
    if dp[-1][-1][i]:
        ans = min(ans,i)
print(ans)

Submission status: Runtime Error

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

h,w = LI()
a = [LI() for _ in range(h)]
b = [LI() for _ in range(h)]

lst = [[0]*w for _ in range(h)]
m = 0
for i in range(h):
    for j in range(w):
        lst[i][j] = abs(a[i][j] - b[i][j])
        m = max(m,abs(a[i][j] - b[i][j]))

dp = [[[0]*(h+w)*m for _ in range(w)] for _ in range(h)]
dp[0][0][lst[0][0]] = 1
for i in range(h):
    for j in range(w):
        for k in range(m*(h+w)):
            if dp[i][j][k]:
                if i+1 < h:
                    if k+lst[i+1][j] < m*(h+w):
                        dp[i+1][j][k+lst[i+1][j]] = 1
                    dp[i+1][j][abs(k-lst[i+1][j])] = 1
                if j+1 < w:
                    if k+lst[i][j+1] < m*(h+w):
                        dp[i][j+1][k+lst[i][j+1]] = 1
                    dp[i][j+1][abs(k-lst[i][j+1])] = 1

ans = 10**10
for i in range(m*(h+w)):
    if dp[-1][-1][i]:
        ans = min(ans,i)
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)]

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

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

ZERO=1<<(H+W)
DP=[[1<<ZERO for i in range(W)] for j in range(H)]

DP[0][0]=1<<H+W+SA[0][0]

for i in range(H):
    for j in range(W):
        if i+1<H:
            DP[i+1][j]|=DP[i][j]<<SA[i+1][j]
            DP[i+1][j]|=DP[i][j]>>SA[i+1][j]

        if j+1<W:
            DP[i][j+1]|=DP[i][j]<<SA[i][j+1]
            DP[i][j+1]|=DP[i][j]>>SA[i][j+1]

ANS=1<<30
for i in range((H+W)*2+1):
    if 1<<i & DP[-1][-1]!=0:
        ANS=min(ANS,abs(i-H-W))

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

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

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

ZERO=1<<(H+W)
DP=[[1<<ZERO for i in range(W)] for i in range(H)]

DP[0][0]=1<<H+W+SA[0][0]

for i in range(H):
    for j in range(W):
        if i+1<H:
            DP[i+1][j]|=DP[i][j]<<SA[i+1][j]
            DP[i+1][j]|=DP[i][j]>>SA[i+1][j]

        if j+1<W:
            DP[i][j+1]|=DP[i][j]<<SA[i][j+1]
            DP[i][j+1]|=DP[i][j]>>SA[i][j+1]

ANS=1<<30
for i in range((H+W)*2+1):
    if 1<<i & DP[-1][-1]!=0:
        ANS=min(ANS,abs(i-H-W))

print(ANS)

Submission status: Runtime Error

Solution code:
H,W = map(int,input().split())
A = [list(map(int,input().split()))for _ in range(H)]
for i in range(H):
    b = list(map(int,input().split()))
    for j in range(W):
        A[i][j] = abs(A[i][j]-b[j])
NUM = 10
DP = [[[0]*NUM for i in range(W)]for j in range(H)]
DP[0][0][A[0][0]] = 1
i = 0
for j in range(W-1):
    a = A[i][j+1]
    for k in range(NUM):
        if DP[i][j][k] == 1:
            if 0 <= a-k < NUM:
                DP[i][j+1][a-k] = 1
            if 0 <= k-a < NUM:
                DP[i][j+1][k-a] = 1
            if 0 <= k+a < NUM:
                DP[i][j+1][k+a] = 1
j = 0
for i in range(H-1):
    a = A[i+1][j]
    for k in range(NUM):
        if DP[i][j][k] == 1:
            if 0 <= a-k < NUM:
                DP[i+1][j][a-k] = 1
            if 0 <= k-a < NUM:
                DP[i+1][j][k-a] = 1
            if 0 <= k+a < NUM:
                DP[i+1][j][k+a] = 1
for i in range(H-1):
    for j in range(W-1):
        a = A[i+1][j+1]
        for k in range(NUM):
            if DP[i+1][j][k] == 1:
                if 0 <= a-k < NUM:
                    DP[i+1][j+1][a-k] = 1
                if 0 <= k-a < NUM:
                    DP[i+1][j+1][k-a] = 1
                if 0 <= k+a < NUM:
                    DP[i+1][j+1][k+a] = 1
            if DP[i][j+1][k] == 1:
                if 0 <= a-k < NUM:
                    DP[i+1][j+1][a-k] = 1
                if 0 <= k-a < NUM:
                    DP[i+1][j+1][k-a] = 1
                if 0 <= k+a < NUM:
                    DP[i+1][j+1][k+a] = 1

print(DP[-1][-1].index(1))

Submission status: Runtime Error

Solution code:
H,W = map(int, input().split())
As = []
for i in range(H):
    As.append(list(map(int, input().split())))
diffs = []
for i in range(H):
    bs = list(map(int, input().split()))
    diffs.append([abs(a-b) for a,b in zip(As[i],bs)])

# 左右の対称性から、がんばったら80を超えることはなくないか？
M = 0
for i in range(H):
    for j in range(W):
        M = max(M, diffs[i][j])
M *= H + W    

# (i,j)において、偏りがkになることがあるか
diff_s = diffs[0][0]
# 初期値
dp = [[[False]*M for i in range(W)] for j in range(H)]
dp[0][0][diff_s] = True
# もらうDP
for i in range(H):
    for j in range(W):
        # 行方向
        if i+1 < H:
            d = diffs[i+1][j]
            for k in range(M):
                x = dp[i][j][k]
                if x:
                    if d + k < M:
                        dp[i+1][j][d+k] = x
                    dp[i+1][j][abs(d-k)] = x
        # 列方向
        if j+1 < W:
            d = diffs[i][j+1]
            for k in range(M):
                x = dp[i][j][k]
                if x:                
                    if d + k < M:                  
                        dp[i][j+1][d+k] = x
                    dp[i][j+1][abs(d-k)] = x
        # print(i,j,diffs[i][j],dp)

ans = 0
for i,b in enumerate(dp[i][j]):
    if b:
        print(i)
        exit()