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

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

for w in range(W):
    for h in range(H):
        if w:
            pvw = dp[h][w - 1]
        else:
            pvw = set()
        if h:
            pvh = dp[h - 1][w]
        else:
            pvh = set()

        pv = pvh | pvw
        if w == 0 & h == 0:
            pv = set([0])

        for c in pv:
            dp[h][w].add(c + abs(A[h][w] - B[h][w]))
            dp[h][w].add(abs(c - abs(A[h][w] - B[h][w])))
print(min(dp[H - 1][W - 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 _ in range(H)]
B = [list(map(int, input().split())) for _ in range(H)]
C = [[0]*W for _ in range(H)]
for i in range(H):
    for j in range(W):
        C[i][j] = A[i][j]-B[i][j]
M = 80*(H+W)
dp = [[set() for i in range(W)] for j in range(H)]
c = C[0][0]
dp[0][0].add(c)
for s in range(1, H+W):
    for b in range(max(s-H+1, 0), min(s, W)):
        a = s-b
        c = C[a][b]
        if a>=1:
            for i in dp[a-1][b]:
                dp[a][b].add(abs(i+c))
                dp[a][b].add(abs(i-c))

        if b>=1:
            for i in dp[a][b-1]:
                dp[a][b].add(abs(i+c))
                dp[a][b].add(abs(i-c))
ans = min(dp[-1][-1])
print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdout
printn = lambda x: stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

M = 2001
K = 1000
h,w = inm()
dp = [ [[0]*M for j in range(w)] for i in range(h) ]

a = []
b = []
for i in range(h):
    a.append(inl())
for i in range(h):
    b.append(inl())

dp[0][0][a[0][0]-b[0][0]+K] = 1
dp[0][0][-a[0][0]+b[0][0]+K] = 1

for i in range(1,h):
    for u in range(M):
        if dp[i-1][0][u]==0:
            continue
        x = u + a[i][0] - b[i][0]
        y = u - a[i][0] + b[i][0]
        if 0 <= x < M:
            dp[i][0][x] = 1
        if 0 <= y < M:
            dp[i][0][y] = 1

for j in range(1,w):
    for u in range(M):
        if dp[0][j-1][u]==0:
            continue
        x = u + a[0][j] - b[0][j]
        y = u - a[0][j] + b[0][j]
        if 0 <= x < M:
            dp[0][j][x] = 1
        if 0 <= y < M:
            dp[0][j][y] = 1

for i in range(1,h):
  for j in range(1,w):
    for u in range(M):
        if dp[i][j-1][u]==0 and dp[i-1][j][u]==0:
            continue
        x = u + a[i][j] - b[i][j]
        y = u - a[i][j] + b[i][j]
        if 0 <= x < M:
            dp[i][j][x] = 1
        if 0 <= y < M:
            dp[i][j][y] = 1

if DBG:
    for i in range(h):
        for j in range(w):
            print("i {} j {}".format(i,j))
            print(dp[i][j][992:1009])
            print("")

mn = 999999999
for u in range(M):
    if dp[h-1][w-1][u]==1 and abs(u-K)<mn:
        mn = abs(u-K)
print(mn)

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) : {(A[0][0]-B[0][0])%160, (B[0][0]-A[0][0])%160}}


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(k%160 for k in chain((v+d for v in dp[(x-1,y)]),
                            (v-d for v in dp[(x-1,y)]),
                            (v+d for v in dp[(x,y-1)]),
                            (v-d for v in dp[(x,y-1)]),))
        elif x > 0:
            ns = set(k%160 for k in chain((v+d for v in dp[(x-1,y)]),
                            (v-d for v in dp[(x-1,y)]),))
        elif y > 0:
            ns = set(k%160 for k in chain((v+d for v in dp[(x,y-1)]),
                            (v-d for v in dp[(x,y-1)]),))
        else:
            ns = set()

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

print(min(chain(dp[(W-1,H-1)], (160-v for v in dp[(W-1,H-1)] ))))

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

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

for w in range(W):
    for h in range(H):
        if w:
            pvw = dp[h][w - 1]
        else:
            pvw = set()
        if h:
            pvh = dp[h - 1][w]
        else:
            pvh = set()

        pv = pvh | pvw
        if w == 0 & h == 0:
            pv = set([0])

        for c in pv:
            dp[h][w].add(abs(c + A[h][w]))
            dp[h][w].add(abs(c - A[h][w]))
            dp[h][w].add(abs(c + B[h][w]))
            dp[h][w].add(abs(c - B[h][w]))
print(min(dp[H - 1][W - 1]))

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)]
D = [[abs(A[h][w] - B[h][w]) for w in range(W)] for h in range(H)]
DP = [[0] * W for _ in range(H)]

DP[0][0], FIN = D[0][0], D[H - 1][W - 1]
for w in range(1, W):
    if abs(abs(D[0][w] - DP[0][w - 1]) - FIN) < abs(abs(D[0][w] + DP[0][w - 1]) - FIN):
        DP[0][w] = abs(D[0][w] - DP[0][w - 1])
    else:
        DP[0][w] = abs(D[0][w] + DP[0][w - 1])
for h in range(1, H):
    if abs(abs(D[h][0] - DP[h - 1][0]) - FIN) < abs(abs(D[h][0] + DP[h - 1][0]) - FIN):
        DP[h][0] = abs(D[h][0] - DP[h - 1][0])
    else:
        DP[h][0] = abs(D[h][0] + DP[h - 1][0])

for h in range(1, H):
    for w in range(1, W):
        mini = min(abs(abs(D[h][w] - DP[h][w - 1]) - FIN),
                   abs(abs(D[h][w] + DP[h][w - 1]) - FIN),
                   abs(abs(D[h][w] - DP[h - 1][w]) - FIN),
                   abs(abs(D[h][w] + DP[h - 1][w]) - FIN))
        if mini == abs(abs(D[h][w] - DP[h][w - 1]) - FIN):
            DP[h][w] = abs(D[h][w] - DP[h][w - 1])
        elif mini == abs(abs(D[h][w] + DP[h][w - 1]) - FIN):
            DP[h][w] = abs(D[h][w] + DP[h][w - 1])
        elif mini == abs(abs(D[h][w] - DP[h - 1][w]) - FIN):
            DP[h][w] = abs(D[h][w] - DP[h - 1][w])
        elif mini == abs(abs(D[h][w] + DP[h - 1][w]) - FIN):
            DP[h][w] = abs(D[h][w] + DP[h - 1][w])

print(min(abs(DP[h - 1][w - 2] - FIN), abs(DP[h - 2][w - 1] - FIN)))

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) : {(A[0][0]-B[0][0])%160, (B[0][0]-A[0][0])%160}}


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(k%160 for k in chain((v+d for v in dp[(x-1,y)]),
                            (v-d for v in dp[(x-1,y)]),
                            (v+d for v in dp[(x,y-1)]),
                            (v-d for v in dp[(x,y-1)]),))
        elif x > 0:
            ns = set(k%160 for k in chain((v+d for v in dp[(x-1,y)]),
                            (v-d for v in dp[(x-1,y)]),))
        elif y > 0:
            ns = set(k%160 for k in chain((v+d for v in dp[(x,y-1)]),
                            (v-d for v in dp[(x,y-1)]),))
        else:
            ns = set()

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

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

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) : {A[0][0]-B[0][0], B[0][0]-A[0][0]}}

cap = 1000000

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%160 for x in chain((v+d for v in dp[(x-1,y)]),
                            (v-d for v in dp[(x-1,y)]),
                            (v+d for v in dp[(x,y-1)]),
                            (v-d for v in dp[(x,y-1)]),) if x < cap)
        elif x > 0:
            ns = set(x%160 for x in chain((v+d for v in dp[(x-1,y)]),
                            (v-d for v in dp[(x-1,y)]),) if x < cap)
        elif y > 0:
            ns = set(x%160 for x in chain((v+d for v in dp[(x,y-1)]),
                            (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 sys

input = sys.stdin.readline

ri = lambda: int(input())
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]

h, w = ril()
ls0 = rils(h)
ls1 = rils(h)

nums = [[set() for _ in range(w)] for _ in range(h)]
nums[0][0].add(abs(ls0[0][0] - ls1[0][0]))
for i in range(h):
    for j in range(w):
        x = abs(ls0[i][j] - ls1[i][j])
        if i > 0:
            for y in nums[i - 1][j]:
                z = abs(x + y)
                if z <= 40 * 81:
                    nums[i][j].add(z)
                nums[i][j].add(abs(x - y))
        if j > 0:
            for y in nums[i][j - 1]:
                z = abs(x + y)
                if z <= 40 * 81:
                    nums[i][j].add(z)
                nums[i][j].add(abs(x - y))
print(min(nums[h - 1][w - 1]))

Submission status: Wrong Answer

Solution code:
import math

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def bitlist(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

#a = list(map(int, input().split()))

h,w = list(map(int, input().split()))
mapa1 = []
mapa2 = []

for i in range(h):
    mapa1.append(list(map(int, input().split())))

for i in range(h):
    mapa2.append(list(map(int, input().split())))
    
mapa=[[0 for i in range(w)] for j in range(h)]
for i in range(h):
    for j in range(w):
        mapa[i][j] = abs(mapa1[i][j]-mapa2[i][j])

ans = 9999999999
#print(mapa1)
dp = [[[0 for k in range(161)] for j in range(w)] for i in range(h)]

dp[0][0][mapa1[0][0]+80]=1
dp[0][0][-mapa2[0][0]+80]=1
#print(dp[0][0])

for jj in range(w-1):
    j = jj+1
    for k in range(161):
        if(dp[0][j-1][k]==1):
            v1 = k - 80  + mapa1[0][j]
            if(-80 <= v1 and v1 <= 80):
                dp[0][j][v1+80] = 1
            v2 = k - 80 - mapa2[0][j]
            if(-80 <= v2 and v2 <= 80):
                dp[0][j][v2+80] = 1
#print(dp[0][2])
for ii in range(h-1):
    i = ii+1
    for k in range(161):
        if(dp[ii][0][k]==1):
            v3 = k - 80  + mapa1[i][0]
            if(-80 <= v3 and v3 <= 80):
                dp[i][j][v3+80] = 1
            v4 = k - 80 - mapa2[i][0]
            if(-80 <= v4 and v4 <= 80):
                dp[i][j][v4+80] = 1
    
    for jj in range(w-1):
        j = jj+1
        for k in range(161):
            if(dp[i][j-1][k]==1):
                v1 = k - 80  + mapa1[i][j]
                if(-80 <= v1 and v1 <= 80):
                    dp[i][j][v1+80] = 1
                v2 = k - 80 - mapa2[i][j]
                if(-80 <= v2 and v2 <= 80):
                    dp[i][j][v2+80] = 1
            if(dp[i-1][j][k]==1):
                v3 = k - 80  + mapa1[i][j]
                if(-80 <= v3 and v3 <= 80):
                    dp[i][j][v3+80] = 1
                v4 = k - 80 - mapa2[i][j]
                if(-80 <= v4 and v4 <= 80):
                    dp[i][j][v4+80] = 1

ans = 9999999

for i in range(161):
    val = dp[h-1][w-1][i]
    vall = abs(i-80)
    if(vall<ans and val==1):
        ans = vall
print(ans)

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) : {A[0][0]-B[0][0]}}

cap = 1000000

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%160 for x in chain((v+d for v in dp[(x-1,y)]),
                            (v-d for v in dp[(x-1,y)]),
                            (v+d for v in dp[(x,y-1)]),
                            (v-d for v in dp[(x,y-1)]),) if x < cap)
        elif x > 0:
            ns = set(x%160 for x in chain((v+d for v in dp[(x-1,y)]),
                            (v-d for v in dp[(x-1,y)]),) if x < cap)
        elif y > 0:
            ns = set(x%160 for x in chain((v+d for v in dp[(x,y-1)]),
                            (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 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())


d = [[set() 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].add(abs(A[i][j]-B[i][j]))
        elif j==0:
            for k in d[i-1][j]:
                d[i][j].add(abs(k+A[i][j]-B[i][j]))
                d[i][j].add(abs(-k+A[i][j]-B[i][j]))
        elif i==0:
            for k in d[i][j-1]:
                d[i][j].add(abs(k+A[i][j]-B[i][j]))
                d[i][j].add(abs(-k+A[i][j]-B[i][j]))
        else:
            for k in d[i-1][j]:
                if abs(k+A[i][j]-B[i][j])<=(H+W-1):
                    d[i][j].add(abs(k+A[i][j]-B[i][j]))
                if abs(-k+A[i][j]-B[i][j])<=(H+W-1):
                    d[i][j].add(abs(-k+A[i][j]-B[i][j]))
            for k in d[i][j-1]:
                if abs(k+A[i][j]-B[i][j])<=(H+W-1):
                    d[i][j].add(abs(k+A[i][j]-B[i][j]))
                if abs(-k+A[i][j]-B[i][j])<=(H+W-1):
                    d[i][j].add(abs(-k+A[i][j]-B[i][j]))

ans = 2*(H+W-1)*80+1
for i in d[H-1][W-1]:
        now = i
        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 _ in range(h)]
b=[list(map(int,input().split())) for _ in range(h)]
g=[[0]*w for _ in range(h)]
import sys
sys.setrecursionlimit(10**9)
for i in range(h):
    for j in range(w):
        g[i][j]=abs(a[i][j]-b[i][j])
c=g[0][0]
dyx=[(1,0),(0,1)]
ans=[float("inf")]
def dfs(y,x,c):
    if y==h-1 and x==w-1:
        ans[0]=min(ans[0],min(abs(c+g[y][x]),abs(c-g[y][x])))
    for dy,dx in dyx:
        ny=y+dy
        nx=x+dx
        if 0<=ny<h and 0<=nx<w:
            dfs(ny,nx,min(abs(c+g[y][x]),abs(c-g[y][x])))

dfs(0,0,c)
print(ans[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)]

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

for w in range(W):
    for h in range(H):
        if w:
            pvw = dp[h][w - 1]
        else:
            pvw = set([0])
        if h:
            pvh = dp[h - 1][w]
        else:
            pvh = set([0])
        pv = pvh | pvw

        for c in pv:
            dp[h][w].add(abs(c + A[h][w]))
            dp[h][w].add(abs(c - A[h][w]))
            dp[h][w].add(abs(c + B[h][w]))
            dp[h][w].add(abs(c - B[h][w]))
print(min(dp[H - 1][W - 1]))

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 = 1000000

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%160 for x in chain((v+d for v in dp[(x-1,y)]),
                            (v-d for v in dp[(x-1,y)]),
                            (v+d for v in dp[(x,y-1)]),
                            (v-d for v in dp[(x,y-1)]),) if x < cap)
        elif x > 0:
            ns = set(x%160 for x in chain((v+d for v in dp[(x-1,y)]),
                            (v-d for v in dp[(x-1,y)]),) if x < cap)
        elif y > 0:
            ns = set(x%160 for x in chain((v+d for v in dp[(x,y-1)]),
                            (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 = map(int, input().split())
A = []
for _ in range(H):
    A.append(list(map(int, input().split())))
B = []
C = []
for y in range(H):
    B.append(list(map(int, input().split())))
    C.append(list(abs(a-b) for (a, b) in zip(A[y], B[y])))
VMAX = 640+1
dp = [[[0] * VMAX for _ in range(W)] for _ in range(H)]
dp[0][0][C[0][0]] = 1
for y in range(H):
    for x in range(W):
        if y==0 and x==0:
            continue
        for v in range(VMAX):
            if y-1 >= 0 and dp[y-1][x][v]:
                if abs(v+C[y][x]) < VMAX:
                    dp[y][x][abs(v+C[y][x])] = 1
                dp[y][x][abs(v-C[y][x])] = 1
            if x-1 >= 0 and dp[y][x-1][v]:
                if abs(v+C[y][x]) < VMAX:
                    dp[y][x][abs(v+C[y][x])] = 1
                dp[y][x][abs(v-C[y][x])] = 1
ans = -1
for v in range(VMAX):
    if dp[-1][-1][v]:
        ans = v
        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=[[abs(a[i][j]-b[i][j])for j in range(w)]for i in range(h)]
d=[[set()for i in range(w+1)]for j in range(h+1)]
d[1][1]=set([-c[0][0],c[0][0]])
for x in range(1,h+1):
    for y in range(1,w+1):
        if not (x==1 and y==1):
            a=d[x-1][y]|d[x][y-1]
            for i in a:
                d[x][y].add(i-c[x-1][y-1])
                if i+c[x-1][y-1]<=80:
                    d[x][y].add(i+c[x-1][y-1])
print(abs(min(d[h][w],key=abs)))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
def f():
    h,w=[int(j) for j in input().split()]
    a=[]
    b=[]
    for i in range(h):
        a.append([int(j) for j in input().split()])
    for i in range(h):
        b.append([int(j) for j in input().split()])
    l=[[] for i in range(h)]
    for i in range(h):
        for j in range(w):
            l[i].append(abs(a[i][j]-b[i][j]))
    ans=[[set() for j in range(w)] for i in range(h)]
    ans[0][0].add(l[0][0])
    for i in range(h):
        for j in range(w):
            for k in ans[i][j]:
                if i+1<h:
                    if -2000<k+l[i+1][j]<2000:
                        ans[i+1][j].add(k+l[i+1][j])
                    if -2000<k-l[i+1][j]<2000:
                        ans[i+1][j].add(k-l[i+1][j])
                if j+1<w:
                    if -2000<k+l[i][j+1]<2000:
                        ans[i][j+1].add(k+l[i][j+1])
                    if -2000<k-l[i][j+1]<2000:
                        ans[i][j+1].add(k-l[i][j+1])
    a=10**18
    for i in ans[h-1][w-1]:
        a=min(abs(i),a)
    print(a)

f()

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)]
# abs(A - B)
S = [[abs(a - b) for a, b in zip(A[n], B[n])] for n in range(H)]

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

setS[0][0].add(S[0][0])

for i in range(H):
    for j in range(W):
        if i == 0 and j == 0:
           continue
        if i > 0:
            for a in list(setS[i-1][j]):
                # if a + S[i][j] <= 80 * (160 - (i + j)):
                #     setS[i][j].add(abs(a + S[i][j]))
                SET1 = set([abs(a - S[i][j]) for a in setS[i-1][j]])
                SET2 = set([a + S[i][j] for a in setS[i-1][j] if a + S[i][j] <= 80 * (160 - (i + j))])
                # setS[i][j].add(abs(a - S[i][j]))
                setS[i][j] = SET1.union(SET2)
        if j > 0:
            for a in list(setS[i][j-1]):
                # if a + S[i][j] <= 80 * (160 - (i + j)):
                #     setS[i][j].add(abs(a + S[i][j]))
                # setS[i][j].add(abs(a - S[i][j]))
                SET1 = set([abs(a - S[i][j]) for a in setS[i][j-1]])
                SET2 = set([a + S[i][j] for a in setS[i][j-1] if a + S[i][j] <= 80 * (160 - (i + j))])
                setS[i][j] = SET1.union(SET2)

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

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
sa=[]
aa=[]
bb=[]
h,w=map(int,input().split())
for i in range(h):
	a=list(map(int,input().split()))
	aa.append(a)
for i in range(h):
	b=list(map(int,input().split()))
	bb.append(b)
for i in range(h):
	ttt=[]
	for j in range(w):
		ttt.append(abs(aa[i][j]-bb[i][j]))
	sa.append(ttt)
dp=[[[] for _ in range(w)]for _ in range(h)]
dp[0][0].append(sa[0][0])
for i in range(h-1):
	for j in range(len(dp[i][0])):
		if dp[i][0][j]+sa[i+1][0]<=80:
			dp[i+1][0].append(dp[i][0][j]+sa[i+1][0])
		if abs(dp[i][0][j]-sa[i+1][0])<=80:
			dp[i+1][0].append(abs(dp[i][0][j]-sa[i+1][0]))
		dp[i+1][0]=set(dp[i+1][0])
		dp[i+1][0]=list(dp[i+1][0])
for i in range(w-1):
	for j in range(len(dp[0][i])):
		if dp[0][i][j]+sa[0][i+1]<=100:
			dp[0][i+1].append(dp[0][i][j]+sa[0][i+1])
		if abs(dp[0][i][j]-sa[0][i+1])<=100:
			dp[0][i+1].append(abs(dp[0][i][j]-sa[0][i+1]))
		dp[0][i+1]=set(dp[0][i+1])
		dp[0][i+1]=list(dp[0][i+1])
for i in range(h-1):
	for k in range(w-1):
		for j in range(len(dp[i][k+1])):
			if dp[i][k+1][j]+sa[i+1][k+1]<=100:
				dp[i+1][k+1].append(dp[i][k+1][j]+sa[i+1][k+1])
			if abs(dp[i][k+1][j]-sa[i+1][k+1])<=100:
				dp[i+1][k+1].append(abs(dp[i][k+1][j]-sa[i+1][k+1]))
		for j in range(len(dp[i+1][k])):
			if dp[i+1][k][j]+sa[i+1][k+1]<=100:
				dp[i+1][k+1].append(dp[i+1][k][j]+sa[i+1][k+1])
			if abs(dp[i+1][k][j]-sa[i+1][k+1])<=100:
				dp[i+1][k+1].append(abs(dp[i+1][k][j]-sa[i+1][k+1]))
		dp[i+1][k+1]=set(dp[i+1][k+1])
		dp[i+1][k+1]=list(dp[i+1][k+1])
print(min(dp[-1][-1]))

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
A = []
for _ in range(H):
    A.append(list(map(int, input().split())))
B = []
C = []
for y in range(H):
    B.append(list(map(int, input().split())))
    C.append(list(abs(a-b) for (a, b) in zip(A[y], B[y])))
VMAX = 320+1
dp = [[[0] * VMAX for _ in range(W)] for _ in range(H)]
dp[0][0][C[0][0]] = 1
for y in range(H):
    for x in range(W):
        if y==0 and x==0:
            continue
        for v in range(VMAX):
            if y-1 >= 0 and dp[y-1][x][v]:
                if abs(v+C[y][x]) < VMAX:
                    dp[y][x][abs(v+C[y][x])] = 1
                dp[y][x][abs(v-C[y][x])] = 1
            if x-1 >= 0 and dp[y][x-1][v]:
                if abs(v+C[y][x]) < VMAX:
                    dp[y][x][abs(v+C[y][x])] = 1
                dp[y][x][abs(v-C[y][x])] = 1
ans = -1
for v in range(VMAX):
    if dp[-1][-1][v]:
        ans = v
        break
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    def dfs(i=0, j=0, s=-1):
        if s==-1:s=cc[0][0]
        if (i, j) == (h - 1, w - 1):
            return s
        if (i,j,s) in memo:return memo[(i,j,s)]
        res = inf
        for di, dj in [(1, 0), (0, 1)]:
            ni, nj = i + di, j + dj
            if ni == h or nj == w: continue
            res = min(res, abs(dfs(ni, nj, s + cc[ni][nj])))
            res = min(res, abs(dfs(ni, nj, s - cc[ni][nj])))
        memo[(i,j,s)]=res
        return res
    memo={}

    inf = 10 ** 16
    h, w = MI()
    aa = LLI(h)
    bb = LLI(h)
    cc = [[a - b for a, b in zip(ar, br)] for ar, br in zip(aa, bb)]
    #p2D(cc)
    print(dfs())
main()

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]*3600 for j in range(w)] for i in range(h)]

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


    for i in range(1,h):
        for k in range(3600):
            if 0 <= k+a[i][0]-b[i][0] <= 3599 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] <= 3599 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(3600):
            if 0 <= k+a[0][j]-b[0][j] <= 3599 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] <= 3599 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(3600):
                if 0 <= k+a[i][j]-b[i][j] <= 3599 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] <= 3599 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] <= 3599 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] <= 3599 and dp[i][j-1][k-a[i][j]+b[i][j]]:
                    dp[i][j][k] = True

    res = 1800
    for k in range(3600):
        if dp[-1][-1][k]:
            res = min(res,abs(1800-k))

    print(res)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline

ri = lambda: int(input())
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]

h, w = ril()
ls0 = rils(h)
ls1 = rils(h)

nums = [[set() for _ in range(w)] for _ in range(h)]
nums[0][0].add(abs(ls0[0][0] - ls1[0][0]))
for i in range(h):
    for j in range(w):
        x = abs(ls0[i][j] - ls1[i][j])
        if i > 0 and j > 0:
            s = nums[i - 1][j] | nums[i][j - 1]
            for y in s:
                z = abs(x + y)
                if z <= 40 * 81:
                    nums[i][j].add(z)
                nums[i][j].add(abs(x - y))
        elif i > 0:
            for y in nums[i - 1][j]:
                nums[i][j].add(abs(x + y))
                nums[i][j].add(abs(x - y))
        elif j > 0:
            for y in nums[i][j - 1]:
                nums[i][j].add(abs(x + y))
                nums[i][j].add(abs(x - y))
print(min(nums[h - 1][w - 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 = [[abs(a[i][j] - b[i][j]) for j in range(w)] for i in range(h)]


sets = [[set() for j in range(w)] for i in range(h)]
sets[0][0].add(c[0][0])
for i in range(1, h):
    for e in sets[i - 1][0]:
        if e <= 80:
            sets[i][0].add(e + c[i][0])
            sets[i][0].add(abs(e - c[i][0]))
for i in range(1, w):
    for e in sets[0][i - 1]:
        if e <= 80:
            sets[0][i].add(e+c[0][i])
            sets[0][i].add(abs(e-c[0][i]))
for i in range(1, h):
    for j in range(1, w):
        for e in sets[i-1][j]:
            if e <= 80:
                sets[i][j].add(e+c[i][j])
                sets[i][j].add(abs(e - c[i][j]))
        for e in sets[i][j-1]:
            if e <= 80:
                sets[i][j].add(e+c[i][j])
                sets[i][j].add(abs(e-c[i][j]))

print(min(sets[h - 1][w - 1]))