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:
#!/usr/bin/env python3
import sys
from collections import deque

def solve(H: int, W: int, A: "List[List[int]]", B: "List[List[int]]"):
    state = [[[0 for d in range(641)] for w in range(W)] for h in range(H)]
    grid = [[abs(A[h][w]-B[h][w]) for w in range(W)] for h in range(H)]
    todo = deque()
    for d in range(641):
        state[H-1][W-1][d] = min(abs(d-grid[H-1][W-1]), abs(d+grid[H-1][W-1]))
    done = set((H-1, W-1))
    todo.append((H-1, W-2))
    todo.append((H-2, W-1))

    while len(todo) > 0:
        h, w = todo.popleft()
        if (h, w) in done:
            continue
        for d in range(641):
            res_c = 9999
            for diff in (abs(d-grid[h][w]), abs(d+grid[h][w])):
                if diff > 640:
                    continue
                if h+1 < H:
                    res_c = min(res_c, state[h+1][w][diff])
                if w+1 < W:
                    res_c = min(res_c, state[h][w+1][diff])
            state[h][w][d] = res_c
        if h > 0:
            todo.append((h-1, w))
        if w > 0:
            todo.append((h, w-1))
        done.add((h, w))
    print(state[0][0][0])

    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    A = [[int(next(tokens)) for _ in range(W)] for _ in range(H)]  # type: "List[List[int]]"
    B = [[int(next(tokens)) for _ in range(W)] for _ in range(H)]  # type: "List[List[int]]"
    solve(H, W, A, B)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
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)
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(i+c)
                dp[a][b].add(i-c)

        if b>=1:
            for i in dp[a][b-1]:
                dp[a][b].add(i+c)
                dp[a][b].add(i-c)
ans = min(abs(i) for i in dp[-1][-1])
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 = 5000


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(min(M, 80 * i)):
        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(min(M, 80 * i)):
        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:
#!/usr/bin/env python3
import sys
from collections import deque

def solve(H: int, W: int, A: "List[List[int]]", B: "List[List[int]]"):
    state = [[[0 for d in range(161)] for w in range(W)] for h in range(H)]
    grid = [[abs(A[h][w]-B[h][w]) for w in range(W)] for h in range(H)]
    todo = deque()
    for d in range(161):
        state[H-1][W-1][d] = min(abs(d-grid[H-1][W-1]), abs(d+grid[H-1][W-1]))
    done = set((H-1, W-1))
    todo.append((H-1, W-2))
    todo.append((H-2, W-1))

    while len(todo) > 0:
        h, w = todo.popleft()
        if (h, w) in done:
            continue
        for d in range(161):
            res_c = 9999
            for diff in (abs(d-grid[h][w]), abs(d+grid[h][w])):
                if diff > 160:
                    continue
                if h+1 < H:
                    res_c = min(res_c, state[h+1][w][diff])
                if w+1 < W:
                    res_c = min(res_c, state[h][w+1][diff])
            state[h][w][d] = res_c
        if h > 0:
            todo.append((h-1, w))
        if w > 0:
            todo.append((h, w-1))
        done.add((h, w))
    print(state[0][0][0])

    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    A = [[int(next(tokens)) for _ in range(W)] for _ in range(H)]  # type: "List[List[int]]"
    B = [[int(next(tokens)) for _ in range(W)] for _ in range(H)]  # type: "List[List[int]]"
    solve(H, W, A, B)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    grid = dict() #絶対値
    dist = dict()
    for h in range(H):
        grid[h] = dict()
        dist[h] = dict()
        for w in range(W):
            grid[h][w] = 0
            dist[h][w] = 1000000000000000000

    for h in range(H):
        A = [int(a) for a in input().split()]
        for w in range(W):
            grid[h][w] = A[w]
    for h in range(H):
        B = [int(b) for b in input().split()]
        for w in range(W):
            grid[h][w] = abs(grid[h][w] - B[w])

    q = deque()
    q.append((0, 0, grid[0][0]))
    while q:
        r, c, score = q.popleft()
        if score ** 2 < dist[r][c] ** 2:
            dist[r][c] = score
            if r + 1 < H:
                q.append((r+1, c, score + grid[r+1][c]))
                q.append((r+1, c, score - grid[r+1][c]))
            if c + 1 < W:
                q.append((r, c+1, score + grid[r][c+1]))
                q.append((r, c+1, score - grid[r][c+1]))

    print(abs(dist[H-1][W-1]))

    return 0

if __name__ == "__main__":
    solve()

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)]
dmin = [[0]*W for _ in range(H)]
dmax = [[0]*W for _ in range(H)]

for i in range(H):
    for j in range(W):
        if i==0 and j==0:
            a = calc(A[i][j]-B[i][j])
            b = calc(-A[i][j]+B[i][j])
            d[i][j][a] = True
            d[i][j][b] = True
            if a>=b:
                dmin[0][0] = b
                dmax[0][0] = a
            else:
                dmin[0][0] = a
                dmax[0][0] = b                
        elif j==0:
            for k in range(dmin[i-1][j], dmax[i-1][j]+1):
                nowmax = 0
                nowmin = 2*(H+W-1)*80
                if d[i-1][j][k]:
                    a = k+A[i][j]-B[i][j]
                    b = k-A[i][j]+B[i][j]
                    d[i][j][a] = True
                    d[i][j][b] = True
                    if min(a,b)<nowmin:
                        nowmin = min(a,b)
                    if max(a,b)>nowmax:
                        nowmax = max(a,b)
                dmin[i][j] = nowmin
                dmax[i][j] = nowmax
        elif i==0:
            for k in range(dmin[i][j-1], dmax[i][j-1]+1):
                nowmax = 0
                nowmin = 2*(H+W-1)*80
                if d[i][j-1][k]:
                    a = k+A[i][j]-B[i][j]
                    b = k-A[i][j]+B[i][j]
                    d[i][j][a] = True
                    d[i][j][b] = True
                    if min(a,b)<nowmin:
                        nowmin = min(a,b)
                    if max(a,b)>nowmax:
                        nowmax = max(a,b)
                dmin[i][j] = nowmin
                dmax[i][j] = nowmax
        else:
            for k in range(dmin[i-1][j], dmax[i-1][j]+1):
                nowmax = 0
                nowmin = 2*(H+W-1)*80
                if d[i-1][j][k]:
                    a = k+A[i][j]-B[i][j]
                    b = k-A[i][j]+B[i][j]
                    d[i][j][a] = True
                    d[i][j][b] = True
                    if min(a,b)<nowmin:
                        nowmin = min(a,b)
                    if max(a,b)>nowmax:
                        nowmax = max(a,b)
                dmin[i][j] = nowmin
                dmax[i][j] = nowmax
            for k in range(dmin[i][j-1], dmax[i][j-1]+1):
                nowmax = 0
                nowmin = 2*(H+W-1)*80
                if d[i][j-1][k]:
                    a = k+A[i][j]-B[i][j]
                    b = k-A[i][j]+B[i][j]
                    d[i][j][a] = True
                    d[i][j][b] = True
                    if min(a,b)<nowmin:
                        nowmin = min(a,b)
                    if max(a,b)>nowmax:
                        nowmax = max(a,b)
                dmin[i][j] = min(nowmin,dmin[i][j])
                dmax[i][j] = max(nowmax,dmax[i][j])                

ans = 2*(H+W-1)*80+1
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:
#!/usr/bin/env python3
import sys
from collections import deque

def solve(H: int, W: int, A: "List[List[int]]", B: "List[List[int]]"):
    state = [[[0 for d in range(81)] for w in range(W)] for h in range(H)]
    grid = [[abs(A[h][w]-B[h][w]) for w in range(W)] for h in range(H)]
    todo = deque()
    for d in range(81):
        state[H-1][W-1][d] = min(abs(d-grid[H-1][W-1]), abs(d+grid[H-1][W-1]))
    done = set((H-1, W-1))
    todo.append((H-1, W-2))
    todo.append((H-2, W-1))

    while len(todo) > 0:
        h, w = todo.popleft()
        if (h, w) in done:
            continue
        for d in range(81):
            res_c = 9999
            for diff in (abs(d-grid[h][w]), abs(d+grid[h][w])):
                if diff > 80:
                    continue
                if h+1 < H:
                    res_c = min(res_c, state[h+1][w][diff])
                if w+1 < W:
                    res_c = min(res_c, state[h][w+1][diff])
            state[h][w][d] = res_c
        if h > 0:
            todo.append((h-1, w))
        if w > 0:
            todo.append((h, w-1))
        done.add((h, w))
    print(state[0][0][0])

    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    A = [[int(next(tokens)) for _ in range(W)] for _ in range(H)]  # type: "List[List[int]]"
    B = [[int(next(tokens)) for _ in range(W)] for _ in range(H)]  # type: "List[List[int]]"
    solve(H, W, A, B)

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+1) for i in range(h+1)]

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+1)] for i in range(h+1)]
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 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 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][0:81]):
    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)]

arr = [set() for _ in range(W)]
arr[0].add(0)
for y in range(H):
    nextarr = [set() for _ in range(W)]
    Ay = A[y]
    By = B[y]
    for x in range(W):
        nextset = nextarr[x]
        d = Ay[x] - By[x]
        for n in arr[x]:
            if abs(n+d) <= 320:
                nextset.add(n+d)
            if abs(n-d) <= 320:
                nextset.add(n-d)
        if x >= 1:
            for n in nextarr[x-1]:
                if abs(n+d) <= 320:
                    nextset.add(n+d)
                if abs(n-d) <= 320:
                    nextset.add(n-d)
    arr = nextarr
print(min([abs(d) for d in arr[-1]]))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
MAX_VAL = 10000
OFFSET = MAX_VAL // 2

h, w = [int(item) for item in input().split()]
a = []
b = []
for i in range(h):
    line = [int(item) for item in input().split()] + [0]
    a.append(line)
a.append([0] * (w + 1))
for i in range(h):
    line = [int(item) for item in input().split()] + [0]
    b.append(line)
b.append([0] * (w + 1))

# dp[height][width][bias]
dp = [[[0] * MAX_VAL for _ in range(w+1)] for _ in range(h+1)] 
dp[0][0][OFFSET + a[0][0] - b[0][0]] = 1
dp[0][0][OFFSET + b[0][0] - a[0][0]] = 1
for i in range(h):
    for j in range(w):
        diffr = a[i][j+1] - b[i][j+1]
        diffd = a[i+1][j] - b[i+1][j]
        for k in range(85, MAX_VAL - 85):
            if dp[i][j][k] == 0:
                continue
            # Move right
            dp[i][j+1][k+diffr] = 1
            dp[i][j+1][k-diffr] = 1
            # Move down
            dp[i+1][j][k+diffd] = 1
            dp[i+1][j][k-diffd] = 1
ans = 10**9
for i, item in enumerate(dp[h-1][w-1]):
    if item == 1:
        ans = min(ans, abs(i - OFFSET))
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)]
diff = [[0]*(w+1) for i in range(h+1)]

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+1)] for i in range(h+1)]
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 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 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())
al = []
for _ in range(h):
    a = list(map(int,input().split()))
    al.append(a)

bl = []
for _ in range(h):
    b = list(map(int,input().split()))
    bl.append(b)

abl = [[0 for _ in range(w)] for _ in range(h)]
for i in range(h):
    for j in range(w):
        abl[i][j] = al[i][j] - bl[i][j]

from collections import defaultdict
dic = defaultdict(set)

dic[(0,0)].add(abl[0][0])
dic[(0,0)].add(-abl[0][0])
for i in range(h):
    for j in range(w):
        for v in dic[(i,j)]:
            if j + 1 < w:
                if -160 <= v+abl[i][j+1] <= 160:
                    dic[(i,j+1)].add(v+abl[i][j+1])
                if -160 <= v-abl[i][j+1] <= 160:
                    dic[(i,j+1)].add(v-abl[i][j+1])
            if i + 1 < h:
                if -160 <= v+abl[i+1][j] <= 160:
                    dic[(i+1,j)].add(v+abl[i+1][j])
                if -160 <= v-abl[i+1][j] <= 160:
                    dic[(i+1,j)].add(v-abl[i+1][j])

ans = float("inf")
for i in dic[(h-1, w-1)]:
    ans = min(abs(i), ans)
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)]

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

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

DP=[[] for i in range(W)]

DP[0]=[SA[0][0]]

for i in range(H):
    NDP=[[] for _ in range(W)]
    for j in range(W):
        for k in set(DP[j]):
            if k>=3000:
                continue
            if i+1<H:
                NDP[j].append(k+SA[i+1][j])
                NDP[j].append(abs(k-SA[i+1][j]))
                
            if j+1<W:
                DP[j+1].append(k+SA[i][j+1])
                DP[j+1].append(abs(k-SA[i][j+1]))

    if i==H-1:
        print(min(DP[-1]))
        break
    DP=NDP

Submission status: Wrong Answer

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

bl = []
for _ in range(h):
    b = list(map(int,input().split()))
    bl.append(b)

abl = [[0 for _ in range(w)] for _ in range(h)]
for i in range(h):
    for j in range(w):
        abl[i][j] = al[i][j] - bl[i][j]

from collections import defaultdict
dic = defaultdict(set)

dic[(0,0)].add(abl[0][0])
dic[(0,0)].add(-abl[0][0])
for i in range(h):
    for j in range(w):
        for v in dic[(i,j)]:
            if j + 1 < w:
                if -80 <= v+abl[i][j+1] <= 80:
                    dic[(i,j+1)].add(v+abl[i][j+1])
                if -80 <= v-abl[i][j+1] <= 80:
                    dic[(i,j+1)].add(v-abl[i][j+1])
            if i + 1 < h:
                if -80 <= v+abl[i+1][j] <= 80:
                    dic[(i+1,j)].add(v+abl[i+1][j])
                if - 80 <= v-abl[i+1][j] <= 80:
                    dic[(i+1,j)].add(v-abl[i+1][j])

ans = float("inf")
for i in dic[(h-1, w-1)]:
    ans = min(abs(i), ans)
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
MOD = 10**9 + 7
MAX_VAL = 6400
OFFSET = MAX_VAL // 2

h, w = [int(item) for item in input().split()]
a = []
b = []
for i in range(h):
    line = [int(item) for item in input().split()] + [0]
    a.append(line)
a.append([0] * (w + 1))
for i in range(h):
    line = [int(item) for item in input().split()] + [0]
    b.append(line)
b.append([0] * (w + 1))

# dp[height][width][bias]
dp = [[[0] * MAX_VAL for _ in range(w+1)] for _ in range(h+1)] 
dp[0][0][OFFSET + a[0][0] - b[0][0]] = 1
dp[0][0][OFFSET + b[0][0] - a[0][0]] = 1
for i in range(h):
    for j in range(w):
        diffra = a[i][j+1] - b[i][j+1]
        diffrb = b[i][j+1] - a[i][j+1]
        diffda = a[i+1][j] - b[i+1][j]
        diffdb = b[i+1][j] - a[i+1][j]
        for k in range(85, MAX_VAL - 85):
            if dp[i][j][k] == 0:
                continue
            # Move right
            dp[i][j+1][k+diffra] = 1
            dp[i][j+1][k+diffrb] = 1
            # Move down
            dp[i+1][j][k+diffda] = 1
            dp[i+1][j][k+diffdb] = 1
ans = 10**9
for i, item in enumerate(dp[h-1][w-1]):
    if item == 1:
        ans = min(ans, abs(i - OFFSET))
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]*3400 for j in range(w)] for i in range(h)]

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


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

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

    print(res)

if __name__ == '__main__':
    main()

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


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:
h,w = map(int,input().split())
arr1 = [list(map(int,input().split())) for _ in range(h)]
arr2 = [list(map(int,input().split())) for _ in range(h)]
arr = [[arr1[j][i]-arr2[j][i] for i in range(w)] for j in range(h)]

matrix = [[{0} for _ in range(w+1)] for _ in range(h+1)]
for i in range(h):
    for j in range(w):
        tmpset = matrix[i+1][j].union(matrix[i][j+1])
        redset = {e + arr[i][j] for e in tmpset}
        blueset = {e - arr[i][j] for e in tmpset}
        matrix[i+1][j+1] = redset.union(blueset)
        
sol = {abs(e) for e in matrix[h][w]}
print(min(sol))

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


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

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


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

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

    print(res)

if __name__ == '__main__':
    main()

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 = sum(range(81))
# 符号をどっちにするか選べる
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)