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())) 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
dp = [[[False]*5000 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(5000):
      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] < 5000:
            dp[i][j][x+g[i-1][j-1]] |= True
for x in range(5000):
  if dp[h][w][x]:
    print(x)
    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)]
diff = [[0]*w for i in range(h)]
for i in range(h):
    for j in range(w):
        diff[i][j] = abs(a[i][j] - b[i][j])

n = 80 * 32 + 1
dp = [[[False]*n for i in range(w)] for i in range(h)]
dp[0][0][diff[0][0]] = True

for i in range(h):
    for j in range(w):
        for cnt in range(n):
            if dp[i][j][cnt]:
                if i+1 < h and cnt + diff[i+1][j] < 80 * 32 + 1:
                    dp[i+1][j][cnt + diff[i+1][j]] = True
                    dp[i+1][j][abs(cnt - diff[i+1][j])] = True
                if j+1 < w and cnt + diff[i][j+1] < 80 * 32 + 1:
                    dp[i][j+1][cnt + diff[i][j+1]] = True
                    dp[i][j+1][abs(cnt - diff[i][j+1])] = True 

for i, boo in enumerate(dp[h-1][w-1]):
    if boo:
        print(i)
        exit()
print(a[10*9])

Submission status: Wrong Answer

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
dp = [[[False]*1000 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(1000):
      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] < 1000:
            dp[i][j][x+g[i-1][j-1]] |= True
for x in range(1000):
  if dp[h][w][x]:
    print(x)
    break

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################


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

def calc(n):
    return n + (H+W-1)*80

d = [[[False]*(2*(H+W-1)*80+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:
            d[i][j][calc(A[i][j]-B[i][j])] = True
            d[i][j][calc(-A[i][j]+B[i][j])] = True
        elif j==0:
            for k in range((i+j)*160):
                if d[i-1][j][k]:
                    d[i][j][k+A[i][j]-B[i][j]] = True
                    d[i][j][k-A[i][j]+B[i][j]] = True
        elif i==0:
            for k in range((i+j)*160):
                if d[i][j-1][k]:
                    d[i][j][k+A[i][j]-B[i][j]] = True
                    d[i][j][k-A[i][j]+B[i][j]] = True
        else:
            for k in range((i+j)*160):
                if d[i-1][j][k]:
                    d[i][j][k+A[i][j]-B[i][j]] = True
                    d[i][j][k-A[i][j]+B[i][j]] = True
            for k in range((i+j)*160):
                if d[i][j-1][k]:
                    d[i][j][k+A[i][j]-B[i][j]] = True
                    d[i][j][k-A[i][j]+B[i][j]] = True

ans = 2*(H+W-1)*80+50
for i in range(2*(H+W-1)*80+1):
    if d[H-1][W-1][i]:
        now = abs(i-(H+W-1)*80)
        if ans>now:
            ans = now
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 = [[] 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)
        if j:
            for d in dp2[j-1]:
                dp2[j].add(d+c)
                dp2[j].add(d-c)
    dp = dp2

ans = float('inf')
for a in dp[-1]:
    ans = min(ans, abs(a))
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


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

grid = [[0] * W for _ in range(H)]
for h, w in itertools.product(range(H), range(W)):
    grid[h][w] = A[h][w] - B[h][w]

LIMIT = 2000
# 符号をどっちにするか選べる
dp = [[set() for _ in range(W)] for _ in range(H)]
dp[0][0] = {grid[0][0], -grid[0][0]}
for h, w in itertools.product(range(H), range(W)):
    g = grid[h][w]
    s = dp[h][w]
    if h - 1 >= 0:
        for c in dp[h - 1][w]:
            if abs(c + g) <= LIMIT:
                s.add(abs(c + g))
            if abs(c - g) <= LIMIT:
                s.add(abs(c - g))
    if w - 1 >= 0:
        for c in dp[h][w - 1]:
            if abs(c + g) <= LIMIT:
                s.add(abs(c + g))
            if abs(c - g) <= LIMIT:
                s.add(abs(c - g))

ans = INF
for s in dp[-1][-1]:
    ans = min(ans, abs(s))

print(ans)

Submission status: Wrong Answer

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)]
diff = [[abs(aij - bij) for aij, bij in zip(ai, bi)] for ai, bi in zip(a, b)]

memo = [[[None] * 161 for x in range(w)] for y in range(h)]
def doit(x, y, d):
    if x < 0 or y < 0 or d > 160:
        return False
    if x == 0 and y == 0:
        return d == diff[0][0]
    if memo[y][x][d] is None:
        memo[y][x][d] = (doit(x - 1, y, abs(d + diff[y][x])) or
                         doit(x - 1, y, abs(d - diff[y][x])) or
                         doit(x, y - 1, abs(d + diff[y][x])) or
                         doit(x, y - 1, abs(d - diff[y][x])))
    return memo[y][x][d]

for ret in range(161):
    if doit(w - 1, h - 1, ret):
        print(ret)
        break

Submission status: Wrong Answer

Solution code:
import bisect
import collections
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)]

q = collections.deque()

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

q. append((0, 0))
s = []
while(q):
    i, j = q.popleft()
    s.append(C[i][j])
    if i == H-1 and j == W - 1:
        break
    if i == H - 1:
        q.append((i, j+1))
    elif j == W - 1:
        q.append((i+1, j))
    else:
        if C[i+1][j] <= C[i][j+1]:
            q.append((i+1, j))
        else:
            q.append((i, j+1))
s.sort()
ss = [0]*(len(s) + 1)
sums = 0
for i in range(len(s)):
    ss[i+1] = ss[i] + s[i]
    sums += s[i]
id = bisect.bisect_left(ss, s[i] // 2)
if id != 0 and id != len(ss) - 1:
    print(min([abs(sums - ss[id]*2), abs(sums - ss[id-1]*2), abs(sums - ss[id+1]*2)]))
elif id == 0:
    print(min([abs(sums - ss[id]*2), abs(sums - ss[id+1]*2)]))
else:
    print(min([abs(sums - ss[id]*2), abs(sums - ss[id-1]*2)]))
# print(abs(red - blue))

Submission status: Wrong Answer

Solution code:
from itertools import chain

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

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

dp = {(0,0) : {abs(A[0][0]-B[0][0])}}

cap = 700

for t in range(1,H+W-1):
    ndp = dict()
    for x in range(max(0,t-H+1), min(t+1,W)):
        y = t-x
        d = A[y][x]-B[y][x]
        if x > 0 and y > 0:
            ns = set(x for x in chain((abs(v+d) for v in dp[(x-1,y)]),
                            (abs(v-d) for v in dp[(x-1,y)]),
                            (abs(v+d) for v in dp[(x,y-1)]),
                            (abs(v-d) for v in dp[(x,y-1)]),) if x < cap)
        elif x > 0:
            ns = set(x for x in chain((abs(v+d) for v in dp[(x-1,y)]),
                            (abs(v-d) for v in dp[(x-1,y)]),) if x < cap)
        elif y > 0:
            ns = set(x for x in chain((abs(v+d) for v in dp[(x,y-1)]),
                            (abs(v-d) for v in dp[(x,y-1)]),) if x < cap)
        else:
            ns = set()

        ndp[(x,y)] = ns
    dp = ndp

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

Submission status: Wrong Answer

Solution code:
import itertools
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


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

grid = [[0] * W for _ in range(H)]
for h, w in itertools.product(range(H), range(W)):
    grid[h][w] = A[h][w] - B[h][w]

LIMIT = 160
# 符号をどっちにするか選べる
dp = [[set() for _ in range(W)] for _ in range(H)]
dp[0][0] = {grid[0][0], -grid[0][0]}
for h, w in itertools.product(range(H), range(W)):
    g = grid[h][w]
    s = dp[h][w]
    if h - 1 >= 0:
        for c in dp[h - 1][w]:
            if abs(c + g) <= LIMIT:
                s.add(abs(c + g))
            if abs(c - g) <= LIMIT:
                s.add(abs(c - g))
    if w - 1 >= 0:
        for c in dp[h][w - 1]:
            if abs(c + g) <= LIMIT:
                s.add(abs(c + g))
            if abs(c - g) <= LIMIT:
                s.add(abs(c - g))

ans = INF
for s in dp[-1][-1]:
    ans = min(ans, abs(s))

print(ans)

Submission status: Wrong Answer

Solution code:
H, W = list(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 = 641


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

DP = [[[0] * M for _ in range(W)] for _ in range(H)]

def nasu(t):
  if t >= 0 and t < M:
    return True
  else:
    return False

DP[0][0][D[0][0]] = 1
for i in range(H + W):
  for j in range(H):
    if i - j >= W: continue
    x = i - j
    y = j
    if x < 0: continue
    if x - 1 >= 0:
      for k in range(M):
        if DP[y][x - 1][k] == 1:
          t = k + D[y][x]
          if nasu(t):
            DP[y][x][t] = 1
          t = abs(k - D[y][x])
          if nasu(t):
            DP[y][x][t] = 1
    if y - 1 >= 0:
      for k in range(M):
        if DP[y - 1][x][k] == 1:
          t = k + D[y][x]
          if nasu(t):
            DP[y][x][t] = 1
          t = abs(k - D[y][x])
          if nasu(t):
            DP[y][x][t] = 1

for i in range(M):
  if DP[-1][-1][i] == 1:
    print(i)
    break

Submission status: Wrong Answer

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

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

    dp = [[[False]*2000 for j in range(w)] for i in range(h)]

    dp[0][0][1000+a[0][0]-b[0][0]] = True
    dp[0][0][1000-a[0][0]+b[0][0]] = True


    for i in range(1,h):
        for k in range(2000):
            if 0 <= k+a[i][0]-b[i][0] <= 1999 and dp[i-1][0][k+a[i][0]-b[i][0]]:
                dp[i][0][k] = True
            elif 0 <= k-a[i][0]+b[i][0] <= 1999 and dp[i-1][0][k-a[i][0]+b[i][0]]:
                dp[i][0][k] = True

    for j in range(1,w):
        for k in range(2000):
            if 0 <= k+a[0][j]-b[0][j] <= 1999 and dp[0][j-1][k+a[0][j]-b[0][j]]:
                dp[0][j][k] = True
            elif 0 <= k-a[0][j]+b[0][j] <= 1999 and dp[0][j-1][k-a[0][j]+b[0][j]]:
                dp[0][j][k] = True       


    for i in range(1,h):
        for j in range(1,w):
            for k in range(2000):
                if 0 <= k+a[i][j]-b[i][j] <= 1999 and dp[i-1][j][k+a[i][j]-b[i][j]]:
                    dp[i][j][k] = True
                elif 0 <= k+a[i][j]-b[i][j] <= 1999 and dp[i][j-1][k+a[i][j]-b[i][j]]:
                    dp[i][j][k] = True
                elif 0 <= k-a[i][j]+b[i][j] <= 1999 and dp[i-1][j][k-a[i][j]+b[i][j]]:
                    dp[i][j][k] = True
                elif 0 <= k-a[i][j]+b[i][j] <= 1999 and dp[i][j-1][k-a[i][j]+b[i][j]]:
                    dp[i][j][k] = True

    res = 10**9
    for k in range(2000):
        if dp[-1][-1][k]:
            res = min(res,abs(1000-k))

    print(res)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from itertools import chain

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

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

dp = {(0,0) : {abs(A[0][0]-B[0][0])}}

cap = 400

for t in range(1,H+W-1):
    ndp = dict()
    for x in range(max(0,t-H+1), min(t+1,W)):
        y = t-x
        d = A[y][x]-B[y][x]
        if x > 0 and y > 0:
            ns = set(x for x in chain((abs(v+d) for v in dp[(x-1,y)]),
                            (abs(v-d) for v in dp[(x-1,y)]),
                            (abs(v+d) for v in dp[(x,y-1)]),
                            (abs(v-d) for v in dp[(x,y-1)]),) if x < cap)
        elif x > 0:
            ns = set(x for x in chain((abs(v+d) for v in dp[(x-1,y)]),
                            (abs(v-d) for v in dp[(x-1,y)]),) if x < cap)
        elif y > 0:
            ns = set(x for x in chain((abs(v+d) for v in dp[(x,y-1)]),
                            (abs(v-d) for v in dp[(x,y-1)]),) if x < cap)
        else:
            ns = set()

        ndp[(x,y)] = ns
    dp = ndp

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

Submission status: Wrong Answer

Solution code:
H, W = list(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 = [[0] * W for _ in range(H)]
for i in range(H):
  for j in range(W):
    D[i][j] = abs(B[i][j] - A[i][j])

DP = [[[0] * 81 for _ in range(W)] for _ in range(H)]

def nasu(t):
  if t >= 0 and t < 81:
    return True
  else:
    return False

DP[0][0][D[0][0]] = 1
for i in range(H + W):
  for j in range(H):
    if i - j >= W: continue
    x = i - j
    y = j
    if x < 0: continue
    if x - 1 >= 0:
      for k in range(81):
        if DP[y][x - 1][k] == 1:
          t = k + D[y][x]
          if nasu(t):
            DP[y][x][t] = 1
          t = abs(k - D[y][x])
          if nasu(t):
            DP[y][x][t] = 1
    if y - 1 >= 0:
      for k in range(81):
        if DP[y - 1][x][k] == 1:
          t = k + D[y][x]
          if nasu(t):
            DP[y][x][t] = 1
          t = abs(k - D[y][x])
          if nasu(t):
            DP[y][x][t] = 1

for i in range(81):
  if DP[-1][-1][i] == 1:
    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)]

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

V = [[2] * w for i in range(h)]
for i in range(h):
    V[i][0] -= 1
for i in range(w):
    V[0][i] -= 1

l = 3500
m = 0

M = [[[0] * l for i in range(w)] for j in range(h)]



s = 0
Q = [[0, 0]]

M[0][0][C[0][0]] = 1
# M[0][0][m-C[0][0]] = 1

while len(Q) > s:
    i = Q[s][0]
    j = Q[s][1]
    if i+1 < h:
        for ii in range(l):
            if M[i][j][ii] == 1:
                if abs(ii+C[i+1][j]) < l:
                    M[i+1][j][abs(ii+C[i+1][j])] = 1
                if abs(ii-C[i+1][j]) < l:
                    M[i+1][j][abs(ii-C[i+1][j])] = 1
        V[i+1][j] -= 1
        if V[i+1][j]==0:
            Q.append([i+1,j])
    if j+1 < w:
        for ii in range(l):
            if M[i][j][ii] == 1:
                if abs(ii+C[i][j+1]) < l:
                    M[i][j+1][abs(ii+C[i][j+1])] = 1
                if abs(ii-C[i][j+1]) < l:
                    M[i][j+1][abs(ii-C[i][j+1])] = 1
        V[i][j+1] -= 1
        if V[i][j+1]==0:
            Q.append([i,j+1])
        
    
    s += 1

# print(M[-1][-1])

ans = 10**5
for i in range(len(M[-1][-1])):
    if M[-1][-1][i] == 1:
        ans = min(ans, abs(i-m))
print(ans)

Submission status: Wrong Answer

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

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

    dp = [[[False]*400 for j in range(w)] for i in range(h)]

    dp[0][0][200+a[0][0]-b[0][0]] = True
    dp[0][0][200-a[0][0]+b[0][0]] = True


    for i in range(1,h):
        for k in range(400):
            if 0 <= k+a[i][0]-b[i][0] <= 399 and dp[i-1][0][k+a[i][0]-b[i][0]]:
                dp[i][0][k] = True
            elif 0 <= k-a[i][0]+b[i][0] <= 399 and dp[i-1][0][k-a[i][0]+b[i][0]]:
                dp[i][0][k] = True

    for j in range(1,w):
        for k in range(400):
            if 0 <= k+a[0][j]-b[0][j] <= 399 and dp[0][j-1][k+a[0][j]-b[0][j]]:
                dp[0][j][k] = True
            elif 0 <= k-a[0][j]+b[0][j] <= 399 and dp[0][j-1][k-a[0][j]+b[0][j]]:
                dp[0][j][k] = True       


    for i in range(1,h):
        for j in range(1,w):
            for k in range(400):
                if 0 <= k+a[i][j]-b[i][j] <= 399 and dp[i-1][j][k+a[i][j]-b[i][j]]:
                    dp[i][j][k] = True
                elif 0 <= k+a[i][j]-b[i][j] <= 399 and dp[i][j-1][k+a[i][j]-b[i][j]]:
                    dp[i][j][k] = True
                elif 0 <= k-a[i][j]+b[i][j] <= 399 and dp[i-1][j][k-a[i][j]+b[i][j]]:
                    dp[i][j][k] = True
                elif 0 <= k-a[i][j]+b[i][j] <= 399 and dp[i][j-1][k-a[i][j]+b[i][j]]:
                    dp[i][j][k] = True

    res = 10**9
    for k in range(400):
        if dp[-1][-1][k]:
            res = min(res,abs(200-k))

    print(res)

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)]
diff = [[0]*w for i in range(h)]
for i in range(h):
    for j in range(w):
        diff[i][j] = abs(a[i][j] - b[i][j])

n = 80 * 20 + 1
dp = [[[False]*n for i in range(w)] for i in range(h)]
dp[0][0][diff[0][0]] = True

for i in range(h):
    for j in range(w):
        for cnt in range(n):
            if dp[i][j][cnt]:
                if i+1 < h and cnt + diff[i+1][j] < 80 * 20 + 1:
                    dp[i+1][j][cnt + diff[i+1][j]] = True
                    dp[i+1][j][abs(cnt - diff[i+1][j])] = True
                if j+1 < w and cnt + diff[i][j+1] < 80 * 20 + 1:
                    dp[i][j+1][cnt + diff[i][j+1]] = True
                    dp[i][j+1][abs(cnt - diff[i][j+1])] = True 

for i, boo in enumerate(dp[h-1][w-1]):
    if boo:
        print(i)
        exit()
print(a[10*9])

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
b = [list(map(int, input().split())) for _ in range(n)]
dp = [[set() for _ in range(m)] for _ in range(n)]
dp[0][0].add(abs(a[0][0] - b[0][0]))
for i in range(n):
	for j in range(m):
		if not i and not j:
			continue
		if i:
			for k in dp[i - 1][j]:
				if abs(k + a[i][j] - b[i][j]) <= 400:
					dp[i][j].add(abs(k + a[i][j] - b[i][j]))
				if abs(k - a[i][j] + b[i][j]) <= 400:
					dp[i][j].add(abs(k - a[i][j] + b[i][j]))
		if j:
			for k in dp[i][j - 1]:
				if abs(k + a[i][j] - b[i][j]) <= 400:
					dp[i][j].add(abs(k + a[i][j] - b[i][j]))
				if abs(k - a[i][j] + b[i][j]) <= 400:
					dp[i][j].add(abs(k - a[i][j] + b[i][j]))
print(min(dp[n - 1][m - 1]))

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

V = [[2] * w for i in range(h)]
for i in range(h):
    V[i][0] -= 1
for i in range(w):
    V[0][i] -= 1

l = 3205
m = 0

M = [[[0] * l for i in range(w)] for j in range(h)]



s = 0
Q = [[0, 0]]

M[0][0][C[0][0]] = 1
# M[0][0][m-C[0][0]] = 1

while len(Q) > s:
    i = Q[s][0]
    j = Q[s][1]
    if i+1 < h:
        for ii in range(l):
            if M[i][j][ii] == 1:
                if abs(ii+C[i+1][j]) < l:
                    M[i+1][j][abs(ii+C[i+1][j])] = 1
                if abs(ii-C[i+1][j]) < l:
                    M[i+1][j][abs(ii-C[i+1][j])] = 1
        V[i+1][j] -= 1
        if V[i+1][j]==0:
            Q.append([i+1,j])
    if j+1 < w:
        for ii in range(l):
            if M[i][j][ii] == 1:
                if abs(ii+C[i][j+1]) < l:
                    M[i][j+1][abs(ii+C[i][j+1])] = 1
                if abs(ii-C[i][j+1]) < l:
                    M[i][j+1][abs(ii-C[i][j+1])] = 1
        V[i][j+1] -= 1
        if V[i][j+1]==0:
            Q.append([i,j+1])
        
    
    s += 1

# print(M[-1][-1])

ans = 10**5
for i in range(len(M[-1][-1])):
    if M[-1][-1][i] == 1:
        ans = min(ans, abs(i-m))
print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
b = [list(map(int, input().split())) for _ in range(n)]
dp = [[set() for _ in range(m)] for _ in range(n)]
dp[0][0].add(abs(a[0][0] - b[0][0]))
for i in range(n):
	for j in range(m):
		if not i and not j:
			continue
		if i:
			for k in dp[i - 1][j]:
				if abs(k + a[i][j] - b[i][j]) <= 100:
					dp[i][j].add(abs(k + a[i][j] - b[i][j]))
				if abs(k - a[i][j] + b[i][j]) <= 100:
					dp[i][j].add(abs(k - a[i][j] + b[i][j]))
		if j:
			for k in dp[i][j - 1]:
				if abs(k + a[i][j] - b[i][j]) <= 100:
					dp[i][j].add(abs(k + a[i][j] - b[i][j]))
				if abs(k - a[i][j] + b[i][j]) <= 100:
					dp[i][j].add(abs(k - a[i][j] + b[i][j]))
print(min(dp[n - 1][m - 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)]
diff = [[0]*w for i in range(h)]
for i in range(h):
    for j in range(w):
        diff[i][j] = abs(a[i][j] - b[i][j])

n = 80 * 10
dp = [[[False]*n for i in range(w)] for i in range(h)]
dp[0][0][diff[0][0]] = True

for i in range(h):
    for j in range(w):
        for cnt in range(n):
            if dp[i][j][cnt]:
                if i+1 < h and cnt + diff[i+1][j] < 80 * 10:
                    dp[i+1][j][cnt + diff[i+1][j]] = True
                    dp[i+1][j][abs(cnt - diff[i+1][j])] = True
                if j+1 < w and cnt + diff[i][j+1] < 80 * 10:
                    dp[i][j+1][cnt + diff[i][j+1]] = True
                    dp[i][j+1][abs(cnt - diff[i][j+1])] = True 

for i, boo in enumerate(dp[h-1][w-1]):
    if boo:
        print(i)
        exit()
print(a[10*9])

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
data1 = [list(map(int,input().split())) for _ in range(h)]
data2 = [list(map(int,input().split())) for _ in range(h)]

data = []
for i in range(h):
    d = []
    for j in range(w):
        d.append(data1[i][j]-data2[i][j])
    data.append(d)

y = 2000
dp = [[[False for i in range(y)] for j in range(w)] for k in range(h)]

dp[0][0][abs(data[0][0])] = True

for i in range(h):
    for j in range(w):
        if i == 0 and j == 0:
            continue
        if i > 0:
            for k in range(y):
                if dp[i-1][j][k]:
                    if abs(k - abs(data[i][j])) < y:
                        dp[i][j][abs(k-abs(data[i][j]))] = True
                    if abs(k + abs(data[i][j])) < y:
                        dp[i][j][abs(k+abs(data[i][j]))] = True
        if j > 0:
            for k in range(y):
                if dp[i][j-1][k]:
                    if abs(k - abs(data[i][j])) < y:
                        dp[i][j][abs(k-abs(data[i][j]))] = True
                    if abs(k + abs(data[i][j])) < y:
                        dp[i][j][abs(k+abs(data[i][j]))] = True


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

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
data1 = [list(map(int,input().split())) for _ in range(h)]
data2 = [list(map(int,input().split())) for _ in range(h)]

data = []
for i in range(h):
    d = []
    for j in range(w):
        d.append(data1[i][j]-data2[i][j])
    data.append(d)

y = 1001
dp = [[[False for i in range(y)] for j in range(w)] for k in range(h)]

dp[0][0][abs(data[0][0])] = True

for i in range(h):
    for j in range(w):
        if i == 0 and j == 0:
            continue
        if i > 0:
            for k in range(y):
                if dp[i-1][j][k]:
                    if abs(k - abs(data[i][j])) < y:
                        dp[i][j][abs(k-abs(data[i][j]))] = True
                    if abs(k + abs(data[i][j])) < y:
                        dp[i][j][abs(k+abs(data[i][j]))] = True
        if j > 0:
            for k in range(y):
                if dp[i][j-1][k]:
                    if abs(k - abs(data[i][j])) < y:
                        dp[i][j][abs(k-abs(data[i][j]))] = True
                    if abs(k + abs(data[i][j])) < y:
                        dp[i][j][abs(k+abs(data[i][j]))] = True


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

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

V = [[2] * w for i in range(h)]
for i in range(h):
    V[i][0] -= 1
for i in range(w):
    V[0][i] -= 1

M = [[[0] * 200 for i in range(w)] for j in range(h)]

l = 200
m = 100

s = 0
Q = [[0, 0]]

M[0][0][m+C[0][0]] = 1
M[0][0][m-C[0][0]] = 1

while len(Q) > s:
    i = Q[s][0]
    j = Q[s][1]
    if i+1 < h:
        for ii in range(l):
            if M[i][j][ii] == 1:
                if ii+C[i+1][j] < l:
                    M[i+1][j][ii+C[i+1][j]] = 1
                if ii-C[i+1][j] >= 0:
                    M[i+1][j][ii-C[i+1][j]] = 1
        V[i+1][j] -= 1
        if V[i+1][j]==0:
            Q.append([i+1,j])
    if j+1 < w:
        for ii in range(l):
            if M[i][j][ii] == 1:
                if ii+C[i][j+1] < l:
                    M[i][j+1][ii+C[i][j+1]] = 1
                if ii-C[i][j+1] >= 0:
                    M[i][j+1][ii-C[i][j+1]] = 1
        V[i][j+1] -= 1
        if V[i][j+1]==0:
            Q.append([i,j+1])
        
    
    s += 1

# print(M[-1][-1])

ans = 10**5
for i in range(len(M[-1][-1])):
    if M[-1][-1][i] == 1:
        ans = min(ans, abs(i-m))
print(ans)

Submission status: Wrong Answer

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

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

    dp = [[[False]*200 for j in range(w)] for i in range(h)]

    dp[0][0][100+a[0][0]-b[0][0]] = True
    dp[0][0][100-a[0][0]+b[0][0]] = True


    for i in range(1,h):
        for k in range(200):
            if 0 <= k+a[i][0]-b[i][0] <= 199 and dp[i-1][0][k+a[i][0]-b[i][0]]:
                dp[i][0][k] = True
            elif 0 <= k-a[i][0]+b[i][0] <= 199 and dp[i-1][0][k-a[i][0]+b[i][0]]:
                dp[i][0][k] = True

    for j in range(1,w):
        for k in range(200):
            if 0 <= k+a[0][j]-b[0][j] <= 199 and dp[0][j-1][k+a[0][j]-b[0][j]]:
                dp[0][j][k] = True
            elif 0 <= k-a[0][j]+b[0][j] <= 199 and dp[0][j-1][k-a[0][j]+b[0][j]]:
                dp[0][j][k] = True       


    for i in range(1,h):
        for j in range(1,w):
            for k in range(200):
                if 0 <= k+a[i][j]-b[i][j] <= 199 and dp[i-1][j][k+a[i][j]-b[i][j]]:
                    dp[i][j][k] = True
                elif 0 <= k+a[i][j]-b[i][j] <= 199 and dp[i][j-1][k+a[i][j]-b[i][j]]:
                    dp[i][j][k] = True
                elif 0 <= k-a[i][j]+b[i][j] <= 199 and dp[i-1][j][k-a[i][j]+b[i][j]]:
                    dp[i][j][k] = True
                elif 0 <= k-a[i][j]+b[i][j] <= 199 and dp[i][j-1][k-a[i][j]+b[i][j]]:
                    dp[i][j][k] = True

    res = 2000
    for k in range(200):
        if dp[-1][-1][k]:
            res = min(res,abs(100-k))

    print(res)

if __name__ == '__main__':
    main()