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: Wrong Answer

Solution code:
H, W = map(int, input().split())
A = [list(map(int, input().split()))+[0] for _ in range(H)]
B = [list(map(int, input().split()))+[0] for _ in range(H)]
A.append([0]*(W+1))
B.append([0]*(W+1))


dp = [[set([]) for _ in range(W+2)] for _ in range(H+2)]
diff = A[0][0] - B[0][0]
dp[0][0].add(diff)
dp[0][0].add(-diff)

# 配るDP
for h in range(H):
    for w in range(W):
        dif_r = abs(A[h + 1][w] - B[h + 1][w])
        dif_d = abs(A[h][w + 1] - B[h][w + 1])
        for val in dp[h][w]:
            if val + dif_r <= 100:
                dp[h+1][w].add(val+dif_r)
            if val - dif_r >= -100:
                dp[h+1][w].add(val-dif_r)
            if val + dif_d <= 100:
                dp[h][w+1].add(val+dif_d)
            if val - dif_d >= -100:
                dp[h][w+1].add(val-dif_d)

ans = 10 ** 9
for val in dp[H-1][W-1]:
    ans = min(ans, abs(val))

print(ans)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
A = [list(map(int, input().split()))+[0] for _ in range(H)]
B = [list(map(int, input().split()))+[0] for _ in range(H)]
A.append([0]*(W+1))
B.append([0]*(W+1))


dp = [[set([]) for _ in range(W+2)] for _ in range(H+2)]
diff = A[0][0] - B[0][0]
dp[0][0].add(diff)
dp[0][0].add(-diff)

# 配るDP
for h in range(H):
    for w in range(W):
        dif_r = abs(A[h + 1][w] - B[h + 1][w])
        dif_d = abs(A[h][w + 1] - B[h][w + 1])
        for val in dp[h][w]:
            if val + dif_r <= 80:
                dp[h+1][w].add(val+dif_r)
            if val - dif_r >= -80:
                dp[h+1][w].add(val-dif_r)
            if val + dif_d <= 80:
                dp[h][w+1].add(val+dif_d)
            if val - dif_d >= -80:
                dp[h][w+1].add(val-dif_d)

ans = 10 ** 9
for val in dp[H-1][W-1]:
    ans = min(ans, abs(val))

print(ans)

Submission status: Wrong Answer

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

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])
#for i in range(H):
#    print(AB[i])

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

dp[0][0] = 1 << (SIZE + AB[i][j]) | 1 << (SIZE - AB[i][j])
for i in range(H):
    for j in range(W):
        if i == H and j == W:
            continue
        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(H):
    print(list(map(lambda x: bin(x >> SIZE), dp[i])))
    
for i in range(SIZE):
    if (dp[-1][-1] >> (i + SIZE)) & 1:
        print(i)
        exit()

Submission status: Wrong Answer

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

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])
#for i in range(H):
#    print(AB[i])

SIZE = 20000
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):
        if i == H and j == W:
            continue
        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(H):
#    print(list(map(lambda x: bin(x >> SIZE), dp[i])))
    
for i in range(SIZE):
    if (dp[-1][-1] >> (i + SIZE)) & 1:
        print(i)
        exit()

Submission status: Wrong Answer

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

import numpy as np

h, w = map(int, input().split())
A = np.array([input().split() for _ in range(h)], dtype=np.int64)
B = np.array([input().split() for _ in range(h)], dtype=np.int64)
C = np.zeros((h+1, w+1), dtype=np.int64)
C[:h, :w] = abs(A-B)
U = C.sum()
dp = np.zeros((h+1, w+1, U+1), dtype=bool)
dp[0, 0, C[0, 0]] = True
for i in range(h):
  for j in range(w):
    c = C[i+1, j]
    dp[i+1, j, c:] |= dp[i, j, :U+1-c]
    dp[i+1, j, :c] |= dp[i, j, ::-1][U+1-c:]
    dp[i+1, j, :U+1-c] |= dp[i, j, c:]
    c = C[i, j+1]
    dp[i, j+1, c:] |= dp[i, j, :U+1-c]
    dp[i, j+1, :c] |= dp[i, j, ::-1][U+1-c:]
    dp[i, j+1, :U+1-c] |= dp[i, j, c:]
print(min(np.where(dp[h-1, w-1])[0]))

Submission status: Wrong Answer

Solution code:
print()

Submission status: Wrong Answer

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)) <= M: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: Wrong Answer

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)])
    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)]:
            key[(0,w)].add(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)]:
            key[(h,0)].add(k + abs(a - b))
            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)]:
                key[(h,w)].add(k + abs(a - b))
                key[(h,w)].add(abs(k - abs(a - b)))
            for k in key[(h,w-1)]:
                key[(h,w)].add(k + abs(a - b))
                key[(h,w)].add(abs(k - abs(a - b)))
    print(min(key[(H-1,W-1)]))
    return

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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)]
grid = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
  for j in range(w):
    grid[i][j] = abs(a[i][j]-b[i][j])
dp = [[0 for j in range(w)] for k in range(h)]
buf = (h+w)*80
for i in range(h):
  for j in range(w):
      t = grid[i][j]
      if i == j == 0:
        dp[i][j] = 1 << buf+t | 1 << buf-t
      if j > 0:
        dp[i][j] = dp[i][j] | dp[i][j-1] << t | dp[i][j-1] >> t
      if i > 0:
        dp[i][j] = dp[i][j] | dp[i-1][j] << t | dp[i-1][j] >> t
print(bin(dp[h-1][w-1]))
for i in range(buf):
  if (dp[h-1][w-1] & 1 << buf+i) or (dp[h-1][w-1] & 1 << buf-i):
    print(i)
    exit()

Submission status: Wrong Answer

Solution code:
import numpy as np
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)]
A_np = np.array(A)
B_np = np.array(B)
C_np = abs(A_np - B_np)
p_inf = float('inf') # 正の無限大
dp = [[p_inf] * (W+3) for i in range(H+3)]
for i in range(1,H+1):
  for j in range(1,W+1):
    if i == 1 and j == 1:
      #print("1")
      dp[i][j] = C_np[0][0]
    elif i == 1:
      #print("2")
      tmp_min = min(abs(dp[i][j-1]+C_np[i-1][j-1]),abs(dp[i][j-1]-C_np[i-1][j-1]))
      dp[i][j] = tmp_min
    elif j == 1:
      #print("3")
      tmp_min = min(abs(dp[i-1][j]+C_np[i-1][j-1]),abs(dp[i-1][j]-C_np[i-1][j-1]))
      dp[i][j] = tmp_min
    else:
      #print("4")
      tmp_min = min(abs(dp[i-1][j]+C_np[i-1][j-1]),abs(dp[i-1][j]-C_np[i-1][j-1]),abs(dp[i][j-1]+C_np[i-1][j-1]),abs(dp[i][j-1]-C_np[i-1][j-1]))
      dp[i][j] = tmp_min
print(dp[H][W])

Submission status: Wrong Answer

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)]
grid = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
  for j in range(w):
    grid[i][j] = abs(a[i][j]-b[i][j])
dp = [[[False for i in range(80*(h+w+1)+1)] for j in range(w)] for k in range(h)]
dp[0][0][grid[i][j]] = True
for j in range(1,w):
  for k in range(80*j+1):
    t = grid[0][j]
    dp[0][j][k] = dp[0][j][k] or dp[0][j-1][k+t] or dp[0][j-1][abs(k-t)]
for i in range(1,h):
  for k in range(80*i+1):
    t = grid[i][0]
    dp[i][0][k] = dp[i][0][k] or dp[i-1][0][k+t] or dp[i-1][0][abs(k-t)]
for i in range(1,h):
  for j in range(1,w):
    for k in range(80*(i+j)+1):
      t = grid[i][j]
      dp[i][j][k] = dp[i][j][k] or dp[i][j-1][k+t] or dp[i][j-1][abs(k-t)] or dp[i-1][j][k+t] or dp[i-1][j][abs(k-t)]
for i in range(12801):
  if dp[h-1][w-1][i]:
    print(i)
    break

Submission status: Wrong Answer

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)]
grid = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
  for j in range(w):
    grid[i][j] = abs(a[i][j]-b[i][j])
dp = [[[False for i in range(12881)] for j in range(w)] for k in range(h)]
dp[0][0][grid[i][j]] = True
for j in range(1,w):
  for k in range(80*j+1):
    t = grid[0][j]
    dp[0][j][k] = dp[0][j][k] or dp[0][j-1][k+t] or dp[0][j-1][abs(k-t)]
for i in range(1,h):
  for k in range(80*i+1):
    t = grid[i][0]
    dp[i][0][k] = dp[i][0][k] or dp[i-1][0][k+t] or dp[i-1][0][abs(k-t)]
for i in range(1,h):
  for j in range(1,w):
    for k in range(80*(i+j)+1):
      t = grid[i][j]
      dp[i][j][k] = dp[i][j][k] or dp[i][j-1][k+t] or dp[i][j-1][abs(k-t)] or dp[i-1][j][k+t] or dp[i-1][j][abs(k-t)]
for i in range(12801):
  if dp[h-1][w-1][i]:
    print(i)
    break

Submission status: Wrong Answer

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)]
grid = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
  for j in range(w):
    grid[i][j] = abs(a[i][j]-b[i][j])
dp = [[[False for i in range(12881)] for j in range(w)] for k in range(h)]
for i in range(h):
  for j in range(w):
    for k in range(80*(i+j)+1):
      t = grid[i][j]
      if i == j == 0 and t == k:
        dp[i][j][k] = True
      if j > 0:
        dp[i][j][k] = dp[i][j][k] or dp[i][j-1][k+t] or dp[i][j-1][abs(k-t)]
      if i > 0:
        dp[i][j][k] = dp[i][j][k] or dp[i-1][j][k+t] or dp[i-1][j][abs(k-t)]
for i in range(12801):
  if dp[h-1][w-1][i]:
    print(i)
    break

Submission status: Wrong Answer

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)]
grid = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
  for j in range(w):
    grid[i][j] = abs(a[i][j]-b[i][j])
dp = [[[0 for i in range(2881)] for j in range(w)] for k in range(h)]
for i in range(h):
  for j in range(w):
    for k in range(2801):
      t = grid[i][j]
      if i == j == 0 and t == k:
        dp[i][j][k] = 1
      if j > 0:
        dp[i][j][k] = dp[i][j][k] or dp[i][j-1][k+t] or dp[i][j-1][abs(k-t)]
      if i > 0:
        dp[i][j][k] = dp[i][j][k] or dp[i-1][j][k+t] or dp[i-1][j][abs(k-t)]
for i in range(2801):
  if dp[h-1][w-1][i] == 1:
    print(i)
    break

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    h,w = LI()
    a = [LI() for _ in range(h)]
    b = [LI() for _ in range(h)]
    mm = 80*80
    m = 1 << (mm+3)
    r = [[0]*w for _ in range(h)]
    c = abs(a[0][0] - b[0][0])
    r[0][0] |= (1 << (mm+1)) << c
    r[0][0] |= (1 << (mm+1)) >> c
    for i in range(h):
        for j in range(w):
            if i == 0 and j == 0:
                continue
            c = abs(a[i][j] - b[i][j])
            t = 0
            if i > 0:
                t |= (r[i-1][j] << c) % m
                t |= r[i-1][j] >> c
            if j > 0:
                t |= (r[i][j-1] << c) % m
                t |= r[i][j-1] >> c
            r[i][j] = t

    c = r[-1][-1]
    t = 100
    for i in range(mm+3):
        if (1<<i) & c > 0:
            k = abs(i-mm+1)
            if t > k:
                t = k

    return t


print(main())

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    h,w = LI()
    a = [LI() for _ in range(h)]
    b = [LI() for _ in range(h)]
    m = 1 << 163
    r = [[0]*w for _ in range(h)]
    c = abs(a[0][0] - b[0][0])
    r[0][0] |= (1 << 81) << c
    r[0][0] |= (1 << 81) >> c
    for i in range(h):
        for j in range(w):
            if i == 0 and j == 0:
                continue
            c = abs(a[i][j] - b[i][j])
            t = 0
            if i > 0:
                t |= (r[i-1][j] << c) % m
                t |= r[i-1][j] >> c
            if j > 0:
                t |= (r[i][j-1] << c) % m
                t |= r[i][j-1] >> c
            r[i][j] = t

    c = r[-1][-1]
    t = 100
    for i in range(163):
        if (1<<i) & c > 0:
            k = abs(i-81)
            if t > k:
                t = k

    return t


print(main())

Submission status: Wrong Answer

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

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(MAX_S):
                        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: Wrong Answer

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

C = [[] for i in range(H)]
for i,(arow,brow) in enumerate(zip(A,B)):
    for a,b in zip(arow,brow):
        d = abs(a-b)
        C[i].append(d)

dp = [set([0]) for i in range(W)]
for i,crow in enumerate(C):
    dp2 = [set() for j in range(W)]
    for j,(c,dpr) in enumerate(zip(C[i],dp)):
        for d in dpr:
            dp2[j].add(d+c)
            dp2[j].add(d-c)
    for j,c in enumerate(C[i]):
        if j==0: continue
        for d in dp2[j-1]:
            dp2[j].add(d+c)
            dp2[j].add(d-c)
    dp = dp2

print(min(abs(a) for a in dp[-1]))

Submission status: Wrong Answer

Solution code:
def main():
    H, W = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(H)]
    B = [list(map(int, input().split())) for _ in range(H)]
    dp = [[set() for _ in range(W+1)] for _ in range(2)]
    dp[0][1].add(abs(A[0][0] - B[0][0]))
    for i in range(H):
        dp[(i+1) & 1] = [set() for _ in range(W+1)]
        for j in range(W):
            diff = abs(A[i][j] - B[i][j])
            dp[(i+1) & 1][j+1] |= set(map(lambda x: x + diff, dp[i & 1][j+1]))
            dp[(i+1) & 1][j+1] |= set(map(lambda x: abs(x - diff), dp[i & 1][j+1]))
            dp[(i+1) & 1][j+1] |= set(map(lambda x: x + diff, dp[(i+1) & 1][j]))
            dp[(i+1) & 1][j+1] |= set(map(lambda x: abs(x - diff), dp[(i+1) & 1][j]))
    print(min(dp[H & 1][W]))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    H, W = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(H)]
    B = [list(map(int, input().split())) for _ in range(H)]
    dp = [[set() for _ in range(W+1)] for _ in range(2)]
    dp[0][1].add(abs(A[0][0] - B[0][0]))
    for i in range(H):
        dp[(i+1) & 1] = [set() for _ in range(W+1)]
        for j in range(W):
            diff = abs(A[i][j] - B[i][j])
            dp[(i+1) & 1][j+1] |= set(map(lambda x: abs(x + diff), dp[i & 1][j+1]))
            dp[(i+1) & 1][j+1] |= set(map(lambda x: abs(x - diff), dp[i & 1][j+1]))
            dp[(i+1) & 1][j+1] |= set(map(lambda x: abs(x + diff), dp[(i+1) & 1][j]))
            dp[(i+1) & 1][j+1] |= set(map(lambda x: abs(x - diff), dp[(i+1) & 1][j]))
    print(min(dp[H & 1][W]))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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*5

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

for h 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: Wrong Answer

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 h 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: Wrong Answer

Solution code:
H,W = map(int,input().split())

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

C = [[0]*W for 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*70

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

for h 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: Wrong Answer

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

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

d = [[{0} for i in range(w+1)]]
for i in range(h):
    d.append([{0}]+[set()for j in range(w)])


for i in range(1,h+1):
    for j in range(1,w+1):
        for x in d[i-1][j]:
            d[i][j].add(abs(x+c[i-1][j-1]))
            d[i][j].add(abs(x-c[i-1][j-1]))
        for x in d[i][j-1]:
            d[i][j].add(abs(x+c[i-1][j-1]))
            d[i][j].add(abs(x-c[i-1][j-1]))

print(min(map(abs,d[-1][-1])))

Submission status: Wrong Answer

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

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

d = [[{0} for i in range(w+1)]]
for i in range(h):
    d.append([{0}]+[set()for j in range(w)])


for i in range(1,h+1):
    for j in range(1,w+1):
        for x in d[i-1][j]:
            d[i][j].add(x+c[i-1][j-1])
            d[i][j].add(x-c[i-1][j-1])
        for x in d[i][j-1]:
            d[i][j].add(x + c[i - 1][j - 1])
            d[i][j].add(x - c[i - 1][j - 1])

print(min(map(abs,d[-1][-1])))

Submission status: Wrong Answer

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(2001)]
           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(1700):
                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(1701):
        if dp[h - 1][w - 1][i]:
            print(i)
            exit()


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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(1301)]
           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: Wrong Answer

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

diffs = []
for y in range(h):
    row = map(int, input().split())
    diffs.append(list(row))

for y in range(h):
    row = map(int, input().split())
    for x, b in zip(range(w), row):
        diffs[y][x] = abs(diffs[y][x] - b)

diffs = np.array(diffs)

m = np.max(diffs) * h * w
dp = [[0 for j in range(w)] for k in range(h)]
dp = np.array(dp)
dp[0][0] |= 1 << diffs[0][0]

for y in range(h):
    for x in range(w):
        diff = diffs[y][x]
        if not y == 0:
            dp[y][x] |= dp[y-1][x] << diff
            dp[y][x] |= dp[y-1][x] >> diff
        if not x == 0:
            dp[y][x] |= dp[y][x-1] << diff
            dp[y][x] |= dp[y][x-1] >> diff


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

Submission status: Wrong Answer

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

diffs = []
for y in range(h):
    row = map(int, input().split())
    diffs.append(list(row))

for y in range(h):
    row = map(int, input().split())
    for x, b in zip(range(w), row):
        diffs[y][x] = abs(diffs[y][x] - b)

diffs = np.array(diffs)

m = np.max(diffs) * h * w
dp = [[[False for i in range(m+1)] for j in range(w)]
      for k in range(h)]
dp = np.array(dp)
dp[0][0][diffs[0][0]] = True

for y in range(h):
    for x in range(w):
        for k in range(m):
            diff = diffs[y][x]
            kplus = min(k + diff, m)
            kminus = abs(k - diff)
            canGet = dp[y][x][k]
            if not y == 0:
                canGet = canGet or dp[y-1][x][kplus] or dp[y-1][x][kminus]
            if not x == 0:
                canGet = canGet or dp[y][x-1][kplus] or dp[y][x-1][kminus]

            dp[y][x][k] = canGet

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