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: Time Limit Exceeded

Solution code:
import sys
def main():
    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)]

    S = (80+80)*80//2
    dp = [[[0]*(S+1) for _ in range(W)] for __ in range(H)]
    dp[0][0][abs(A[0][0] - B[0][0])] = 1
    for i in range(H):
        for j in range(W):
            for s in range(S+1):
                for ni,nj in [(i,j+1),(i+1,j)]:
                    if ni >= H or nj >= W: continue
                    t = abs(A[ni][nj] - B[ni][nj])
                    if s+t <= S:
                        dp[ni][nj][s+t] |= dp[i][j][s]
                    dp[ni][nj][abs(s-t)] |= dp[i][j][s]
    for s in range(S+1):
        if dp[H-1][W-1][s]:
            print(s)
            break

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def main():
    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)]

    S = (80+80)*80//2
    dp = [[[0]*(S+1) for _ in range(W)] for __ in range(H)]
    dp[0][0][abs(A[0][0] - B[0][0])] = 1
    for i in range(H):
        for j in range(W):
            for s in range(S+1):
                if i < H-1:
                    ni = i + 1
                    nj = j
                    t = abs(A[ni][nj] - B[ni][nj])
                    ns = s + t
                    if ns <= S:
                        dp[ni][nj][ns] |= dp[i][j][s]
                    ns = abs(s - t)
                    dp[ni][nj][ns] |= dp[i][j][s]
                if j < W-1:
                    ni = i
                    nj = j + 1
                    t = abs(A[ni][nj] - B[ni][nj])
                    ns = s + t
                    if ns <= S:
                        dp[ni][nj][ns] |= dp[i][j][s]
                    ns = abs(s - t)
                    dp[ni][nj][ns] |= dp[i][j][s]
    for s in range(S+1):
        if dp[H-1][W-1][s]:
            print(s)
            break

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def main():
    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)]

    dp = [[set() for _ in range(W)] for __ in range(H)]
    dp[0][0].add(abs(A[0][0] - B[0][0]))
    for i in range(H):
        for j in range(W):
            for s in dp[i][j]:
                for ni,nj in [(i,j+1),(i+1,j)]:
                    if ni >= H or nj >= W: continue
                    t = abs(A[ni][nj] - B[ni][nj])
                    if s+t <= 80*80:
                        dp[ni][nj].add(s + t)
                    dp[ni][nj].add(abs(s - t))
    print(min(dp[H-1][W-1]))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

C = [[0]*w for _ in range(h)]
for i in range(h):
    for j in range(w):
        C[i][j] = abs(A[i][j]-B[i][j])

D = 80*80
dp = [[[0]*D for i in range(w)] for j in range(h)]
dp[0][0][C[0][0]] = 1
for i in range(h):
    for j in range(w):
        if i+1< h:
            for k in range(D):
                if dp[i][j][k] != 0:
                    if k+C[i+1][j] < D:
                        dp[i+1][j][k+C[i+1][j]] = 1
                    dp[i+1][j][abs(k-C[i+1][j])] = 1
        if j+1<w:
            for k in range(D):
                if dp[i][j][k] != 0:
                    if k+C[i][j+1] < D:
                        dp[i][j+1][k+C[i][j+1]] = 1
                    dp[i][j+1][abs(k-C[i][j+1])] = 1

for i in range(D):
    if dp[-1][-1][i] != 0:
        print(i)
        exit()

Submission status: Time Limit Exceeded

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

C = [[0]*w for _ in range(h)]
for i in range(h):
    for j in range(w):
        C[i][j] = abs(A[i][j]-B[i][j])

D = 80*160
dp = [[[0]*D for i in range(w)] for j in range(h)]
dp[0][0][C[0][0]] = 1
for i in range(h):
    for j in range(w):
        if i+1< h:
            for k in range(D):
                if dp[i][j][k] != 0:
                    dp[i+1][j][k+C[i+1][j]] = 1
                    dp[i+1][j][abs(k-C[i+1][j])] = 1
        if j+1<w:
            for k in range(D):
                if dp[i][j][k] != 0:
                    dp[i][j+1][k+C[i][j+1]] = 1
                    dp[i][j+1][abs(k-C[i][j+1])] = 1

for i in range(D):
    if dp[-1][-1][i] != 0:
        print(i)
        exit()

Submission status: Time Limit Exceeded

Solution code:
import sys
def main():
    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)]

    S = (80+80)*80
    dp = [[[0]*(S+1) for _ in range(W)] for __ in range(H)]
    dp[0][0][abs(A[0][0] - B[0][0])] = 1
    for i in range(H):
        for j in range(W):
            for s in range((i+j+1)*80+1):
                if i < H-1:
                    ni = i + 1
                    nj = j
                    t = abs(A[ni][nj] - B[ni][nj])
                    ns = s + t
                    if ns <= S:
                        dp[ni][nj][ns] |= dp[i][j][s]
                    ns = abs(s - t)
                    dp[ni][nj][ns] |= dp[i][j][s]
                if j < W-1:
                    ni = i
                    nj = j + 1
                    t = abs(A[ni][nj] - B[ni][nj])
                    ns = s + t
                    if ns <= S:
                        dp[ni][nj][ns] |= dp[i][j][s]
                    ns = abs(s - t)
                    dp[ni][nj][ns] |= dp[i][j][s]
    for s in range(S+1):
        if dp[H-1][W-1][s]:
            print(s)
            break

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def main():
    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)]

    S = (80+80)*80
    dp = [[[0]*(S+1) for _ in range(W)] for __ in range(H)]
    dp[0][0][abs(A[0][0] - B[0][0])] = 1
    for i in range(H):
        for j in range(W):
            for s in range(S+1):
                if i < H-1:
                    ni = i + 1
                    nj = j
                    t = abs(A[ni][nj] - B[ni][nj])
                    ns = s + t
                    if ns <= S:
                        dp[ni][nj][ns] |= dp[i][j][s]
                    ns = abs(s - t)
                    dp[ni][nj][ns] |= dp[i][j][s]
                if j < W-1:
                    ni = i
                    nj = j + 1
                    t = abs(A[ni][nj] - B[ni][nj])
                    ns = s + t
                    if ns <= S:
                        dp[ni][nj][ns] |= dp[i][j][s]
                    ns = abs(s - t)
                    dp[ni][nj][ns] |= dp[i][j][s]
    for s in range(S+1):
        if dp[H-1][W-1][s]:
            print(s)
            break

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def main():
    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)]

    dp = [[set() for _ in range(W)] for __ in range(H)]
    dp[0][0].add(abs(A[0][0] - B[0][0]))
    for i in range(H):
        for j in range(W):
            for s in dp[i][j]:
                for ni,nj in [(i,j+1),(i+1,j)]:
                    if ni >= H or nj >= W: continue
                    dp[ni][nj].add(s + abs(A[ni][nj] - B[ni][nj]))
                    dp[ni][nj].add(abs(s - abs(A[ni][nj] - B[ni][nj])))
    print(min(dp[H-1][W-1]))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

C = [[0]*w for _ in range(h)]
for i in range(h):
    for j in range(w):
        C[i][j] = abs(A[i][j]-B[i][j])

d = 80*(h+w-1)
D = 2*d+1
dp = [[[0]*D for i in range(w)] for j in range(h)]
dp[0][0][d+C[0][0]] = 1
for i in range(h):
    for j in range(w):
        if i+1< h:
            for k in range(D):
                if dp[i][j][k] != 0:
                    dp[i+1][j][k+C[i+1][j]] = 1
                    dp[i+1][j][k-C[i+1][j]] = 1
        if j+1<w:
            for k in range(D):
                if dp[i][j][k] != 0:
                    dp[i][j+1][k+C[i][j+1]] = 1
                    dp[i][j+1][k-C[i][j+1]] = 1
ans = d
for i in range(d, D):
    if dp[-1][-1][i] != 0:
        ans = min(ans, i-d)
for i in reversed(range(d)):
    if dp[-1][-1][i] != 0:
        ans = min(ans, d-i)
print(ans)

Submission status: Time Limit Exceeded

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

C = [[0]*w for _ in range(h)]
for i in range(h):
    for j in range(w):
        C[i][j] = abs(A[i][j]-B[i][j])

d = 80*160+1
D = 2*d+1
dp = [[[0]*D for i in range(w)] for j in range(h)]
dp[0][0][d+C[0][0]] = 1
for i in range(h):
    for j in range(w):
        if i+1< h:
            for k in range(D):
                if dp[i][j][k] != 0:
                    dp[i+1][j][k+C[i+1][j]] = 1
                    dp[i+1][j][k-C[i+1][j]] = 1
        if j+1<w:
            for k in range(D):
                if dp[i][j][k] != 0:
                    dp[i][j+1][k+C[i][j+1]] = 1
                    dp[i][j+1][k-C[i][j+1]] = 1
ans = d
for i in range(d, D):
    if dp[-1][-1][i] != 0:
        ans = min(ans, i-d)
for i in reversed(range(d)):
    if dp[-1][-1][i] != 0:
        ans = min(ans, d-i)
print(ans)

Submission status: Time Limit Exceeded

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

dp = [[[False] * 12801 for j in range(W)] for _ in range(H)]
dp[0][0][C[0][0]] = True
for i in range(H):
    for j in range(W):
        if i == j == 0:
            continue
        for n in range(12801):
            if i > 0 and dp[i-1][j][n] or j > 0 and dp[i][j-1][n]:
                dp[i][j][abs(n-C[i][j])] = True
                dp[i][j][abs(n+C[i][j])] = True

for n in range(12801):
    if dp[H-1][W-1][n]:
        print(n)
        break

Submission status: Time Limit Exceeded

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

dp = [[None] * W for _ in range(H)]
dp[0][0] = {C[0][0]}
for i in range(H):
    for j in range(W):
        if i == j == 0:
            continue
        st = set()
        if i > 0:
            st |= dp[i-1][j]
        if j > 0:
            st |= dp[i][j-1]
        nst = set()
        for n in st:
            nst.add(abs(n-C[i][j]))
            nst.add(abs(n+C[i][j]))
        dp[i][j] = nst

ans = list(dp[H-1][W-1])
ans.sort()
print(ans[0])

Submission status: Time Limit Exceeded

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

memo = {}
def dfs(i, j):
    if i < 0 or i >= H or j < 0 or j >= W:
        return set()
    if i == j == 0:
        return {C[i][j]}
    if (i, j) in memo:
        return memo[(i, j)]
    st = dfs(i, j-1) | dfs(i-1, j)
    ret = set()
    for n in st:
        ret.add(abs(n-C[i][j]))
        ret.add(abs(n+C[i][j]))
    memo[(i, j)] = ret
    return ret

ans = list(dfs(H-1, W-1))
ans.sort()
print(ans[0])

Submission status: Time Limit Exceeded

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

dp = [[set() for _ in range(w)] for _ in range(h)]
dp[0][0].add(a[0][0] - b[0][0])


for i in range(h):
    for j in range(w):
        ad = a[i][j] - b[i][j]
        for k in dp[i - 1][j]:
            dp[i][j].add(k + ad)
            dp[i][j].add(k - ad)
        for k in dp[i][j-1]:
            dp[i][j].add(k + ad)
            dp[i][j].add(k - ad)

print(abs(min(dp[-1][-1], key=abs)))

Submission status: Time Limit Exceeded

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

dp = [[set() for _ in range(w)] for _ in range(h)]
dp[0][0].add(a[0][0] - b[0][0])
dp[0][0].add(-a[0][0] + b[0][0])


for i in range(h):
    for j in range(w):
        ad = a[i][j] - b[i][j]
        for k in dp[i - 1][j]:
            dp[i][j].add(k + ad)
            dp[i][j].add(k - ad)
        for k in dp[i][j-1]:
            dp[i][j].add(k + ad)
            dp[i][j].add(k - ad)

print(abs(min(dp[-1][-1], key=abs)))

Submission status: Time Limit Exceeded

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

dp = [[set() for _ in range(w)] for _ in range(h)]
dp[0][0].add(a[0][0] - b[0][0])
dp[0][0].add(-a[0][0] + b[0][0])


for i in range(h):
    for j in range(w):
        for k in dp[i - 1][j]:
            dp[i][j].add(k + a[i][j] - b[i][j])
            dp[i][j].add(k - a[i][j] + b[i][j])
        for k in dp[i][j-1]:
            dp[i][j].add(k + a[i][j] - b[i][j])
            dp[i][j].add(k - a[i][j] + b[i][j])

print(abs(min(dp[-1][-1], key=abs)))

Submission status: Time Limit Exceeded

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

dp = [[set() for _ in range(w)] for _ in range(h)]
dp[0][0].add(a[0][0] - b[0][0])
dp[0][0].add(-a[0][0] + b[0][0])


for i in range(h):
    for j in range(w):
        for k in dp[i - 1][j] | dp[i][j-1]:
            dp[i][j].add(k + a[i][j] - b[i][j])
            dp[i][j].add(k - a[i][j] + b[i][j])

print(abs(min(dp[-1][-1], key=abs)))

Submission status: Time Limit Exceeded

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

dp = [[[False] * (160 * 160) for _ in range(w)] for _ in range(h)]
dp[0][0][a[0][0] - b[0][0]] = True
dp[0][0][-a[0][0] + b[0][0]] = True


for i in range(h):
    for j in range(w):
        for k in range(-160 * 80, 160 * 80):
            if dp[i - 1][j][k] or dp[i][j-1][k]:
                dp[i][j][k + a[i][j] - b[i][j]] = True
                dp[i][j][k - a[i][j] + b[i][j]] = True
ans = 10**9
for i in range(-160 * 80, 160 * 80):
    if dp[-1][-1][i]:
        ans = min(ans, abs(i))

print(ans)

Submission status: Time Limit Exceeded

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

A = [tuple(map(int, input().split())) for _ in range(H)]
B = [tuple(map(int, input().split())) for _ in range(H)]
C = [[abs(i-j) for i, j in zip(a, b)] for a, b in zip(A, B)]

dmax = max([j for i in C for j in i])
vmax = (H+W) * dmax

dp = [[[0]*(vmax+1) for _ in range(W)] for _ in range(H)]
dp[0][0][C[0][0]] = 1

for i in range(H):
    for j in range(W):
        for k in range(vmax+1):
            if i+1<H:
                k1, k2 = k+C[i+1][j], abs(k-C[i+1][j])
                if k1<=vmax:
                    dp[i+1][j][k1] |= dp[i][j][k]
                if k2<=vmax:
                    dp[i+1][j][k2] |= dp[i][j][k]

            if j+1<W:
                k1, k2 = k+C[i][j+1], abs(k-C[i][j+1])
                if k1<=vmax:
                    dp[i][j+1][k1] |= dp[i][j][k]
                if k2<=vmax:
                    dp[i][j+1][k2] |= dp[i][j][k]

print(dp[H-1][W-1].index(1))

Submission status: Time Limit Exceeded

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

d = [[0]*(W+1) for _ in range(H+1)]
vmax = (H+W)*80
dp = [[[False]*(vmax+1) for _ in range(W+1)] for _ in range(H+1)]
dp[1][1][0] = True

for i in range(H):
    for j, n in enumerate(map(int, input().split())):
        d[i+1][j+1] = n
    
for i in range(H):
    for j, n in enumerate(map(int, input().split())):
        d[i+1][j+1] -= n

for i in range(1, H+1):
    for j in range(1, W+1):
        for k in range(vmax+1):
            if i>1:
                if 0<=k-d[i-1][j]<=vmax:
                    dp[i][j][k] |= dp[i-1][j][k-d[i-1][j]]
                if 0<=k+d[i-1][j]<=vmax:
                    dp[i][j][k] |= dp[i-1][j][k+d[i-1][j]]
            if j>1:
                if 0<=k-d[i][j-1]<=vmax:
                    dp[i][j][k] |= dp[i][j-1][k-d[i][j-1]]
                if 0<=k+d[i][j-1]<=vmax:
                    dp[i][j][k] |= dp[i][j-1][k+d[i][j-1]]

v = d[H][W]
ans = vmax
for i,j in enumerate(dp[H][W]):
    if not j:continue
    ans = min(ans, abs(i+v), abs(i-v))

print(ans)

Submission status: Time Limit Exceeded

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

d = [[0]*(W+1) for _ in range(H+1)]
vmax = (H+W)*80
dp = [[[False]*(vmax+1) for _ in range(W+1)] for _ in range(H+1)]
dp[1][1][0] = True

for i in range(H):
    for j, n in enumerate(map(int, input().split())):
        d[i+1][j+1] = n
for i in range(H):
    for j, n in enumerate(map(int, input().split())):
        d[i+1][j+1] -= n
        d[i+1][j+1] = abs(d[i+1][j+1])

for i in range(1, H+1):
    for j in range(1, W+1):
        v1 = d[i-1][j]
        v2 = d[i][j-1]
        d1 = dp[i-1][j]
        d2 = dp[i][j-1]

        for k in range(v1, vmax+1):
            dp[i][j][k] |= d1[k-v1] 
        for k in range(0, vmax-v1+1):
            dp[i][j][k] |= d1[k+v1]
        for k in range(v2, vmax+1):
            dp[i][j][k] |= d2[k-v2]
        for k in range(0, vmax-v2+1):
            dp[i][j][k] |= d2[k+v2]

v = d[H][W]
ans = vmax
for i,j in enumerate(dp[H][W]):
    if not j:continue
    ans = min(ans, abs(i+v), abs(i-v))

print(ans)

Submission status: Time Limit Exceeded

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

d = [[0]*(W+1) for _ in range(H+1)]
vmax = H*W*80
dp = [[[False]*(vmax+1) for _ in range(W+1)] for _ in range(H+1)]
dp[1][1][0] = True

for i in range(H):
    for j, n in enumerate(map(int, input().split())):
        d[i+1][j+1] = n
for i in range(H):
    for j, n in enumerate(map(int, input().split())):
        d[i+1][j+1] -= n
        d[i+1][j+1] = abs(d[i+1][j+1])

for i in range(1, H+1):
    for j in range(1, W+1):
        v1 = d[i-1][j]
        v2 = d[i][j-1]
        d1 = dp[i-1][j]
        d2 = dp[i][j-1]

        for k in range(v1, vmax+1):
            dp[i][j][k] |= d1[k-v1] 
        for k in range(0, vmax-v1+1):
            dp[i][j][k] |= d1[k+v1]
        for k in range(v2, vmax+1):
            dp[i][j][k] |= d2[k-v2]
        for k in range(0, vmax-v2+1):
            dp[i][j][k] |= d2[k+v2]

v = d[H][W]
ans = vmax
for i,j in enumerate(dp[H][W]):
    if not j:continue
    ans = min(ans, abs(i+v), abs(i-v))

print(ans)

Submission status: Time Limit Exceeded

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

d = [[0]*(W+1) for _ in range(H+1)]
vmax = H*W*80
dp = [[[False]*(vmax+1) for _ in range(W+1)] for _ in range(H+1)]
dp[1][1][0] = True

for i in range(H):
    for j, n in enumerate(map(int, input().split())):
        d[i+1][j+1] = n
for i in range(H):
    for j, n in enumerate(map(int, input().split())):
        d[i+1][j+1] -= n

for i in range(1, H+1):
    for j in range(1, W+1):
        v1 = d[i-1][j]
        v2 = d[i][j-1]
        d1 = dp[i-1][j]
        d2 = dp[i][j-1]

        for k in range(max(0, v1), min(vmax, vmax+v1)+1):
            if d1[k-v1]:
                dp[i][j][k] = True
    
        for k in range(max(0, -v1), min(vmax, vmax-v1)+1):
            if d1[k+v1]:
                dp[i][j][k] = True

        for k in range(max(0, v2), min(vmax, vmax+v2)+1):
            if d2[k-v2]:
                dp[i][j][k] = True

        for k in range(max(0, -v2), min(vmax, vmax-v2)+1):
            if d2[k+v2]:
                dp[i][j][k] = True

v = d[H][W]
ans = vmax
for i,j in enumerate(dp[H][W]):
    if not j:continue
    ans = min(ans, abs(i+v), abs(i-v))

print(ans)

Submission status: Time Limit Exceeded

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

d = [[0]*(W+1) for _ in range(H+1)]
vmax = H*W*80
dp = [[[False]*(vmax+1) for _ in range(W+1)] for _ in range(H+1)]
dp[1][1][0] = True

for i in range(H):
    for j, n in enumerate(map(int, input().split())):
        d[i+1][j+1] = n
for i in range(H):
    for j, n in enumerate(map(int, input().split())):
        d[i+1][j+1] -= n

for i in range(1, H+1):
    for j in range(1, W+1):
        v1 = d[i-1][j]
        v2 = d[i][j-1]
        d1 = dp[i-1][j]
        d2 = dp[i][j-1]

        for k in range(min(0, v1), min(vmax, vmax+v1)+1):
            if d1[k-v1]:
                dp[i][j][k] = True
    
        for k in range(min(0, -v1), min(vmax, vmax-v1)+1):
            if d1[k+v1]:
                dp[i][j][k] = True

        for k in range(min(0, v2), min(vmax, vmax+v2)+1):
            if d2[k-v2]:
                dp[i][j][k] = True

        for k in range(min(0, -v2), min(vmax, vmax-v2)+1):
            if d2[k+v2]:
                dp[i][j][k] = True

v = d[H][W]
ans = vmax
for i,j in enumerate(dp[H][W]):
    if not j:continue
    ans = min(ans, abs(i+v), abs(i-v))

print(ans)

Submission status: Time Limit Exceeded

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

d = [[0]*(W+1) for _ in range(H+1)]
vmax = H*W*80
dp = [[[False]*(vmax+1) for _ in range(W+1)] for _ in range(H+1)]
dp[1][1][0] = True

for i in range(H):
    for j, n in enumerate(map(int, input().split())):
        d[i+1][j+1] = n
    
for i in range(H):
    for j, n in enumerate(map(int, input().split())):
        d[i+1][j+1] -= n

for i in range(1, H+1):
    for j in range(1, W+1):
        for k in range(vmax+1):
            if 0<=k-d[i-1][j]<=vmax and dp[i-1][j][k-d[i-1][j]]:
                dp[i][j][k] = True
                continue
            if 0<=k+d[i-1][j]<=vmax and dp[i-1][j][k+d[i-1][j]]:
                dp[i][j][k] = True
                continue
            if 0<=k-d[i][j-1]<=vmax and dp[i][j-1][k-d[i][j-1]]:
                dp[i][j][k] = True
                continue
            if 0<=k+d[i][j-1]<=vmax and dp[i][j-1][k+d[i][j-1]]:
                dp[i][j][k] = True
                continue

v = d[H][W]
ans = vmax
for i,j in enumerate(dp[H][W]):
    if not j:continue
    ans = min(ans, abs(i+v), abs(i-v))

print(ans)

Submission status: Time Limit Exceeded

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

d = [[0]*(W+1) for _ in range(H+1)]
vmax = H*W*80
dp = [[[False]*(vmax+1) for _ in range(W+1)] for _ in range(H+1)]
dp[1][1][0] = True

for i in range(H):
    for j, n in enumerate(map(int, input().split())):
        d[i+1][j+1] = n
    
for i in range(H):
    for j, n in enumerate(map(int, input().split())):
        d[i+1][j+1] -= n

for i in range(1, H+1):
    for j in range(1, W+1):
        for k in range(vmax+1):
            if i>1:
                if 0<=k-d[i-1][j]<=vmax:
                    dp[i][j][k] |= dp[i-1][j][k-d[i-1][j]]
                if 0<=k+d[i-1][j]<=vmax:
                    dp[i][j][k] |= dp[i-1][j][k+d[i-1][j]]
            if j>1:
                if 0<=k-d[i][j-1]<=vmax:
                    dp[i][j][k] |= dp[i][j-1][k-d[i][j-1]]
                if 0<=k+d[i][j-1]<=vmax:
                    dp[i][j][k] |= dp[i][j-1][k+d[i][j-1]]

v = d[H][W]
ans = vmax
for i,j in enumerate(dp[H][W]):
    if not j:continue
    ans = min(ans, abs(i+v), abs(i-v))

print(ans)

Submission status: Time Limit Exceeded

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

d = [[0]*(W+1) for _ in range(H+1)]
vmax = 12800
dp = [[[False]*(vmax+1) for _ in range(W+1)] for _ in range(H+1)]
dp[1][1][0] = True

for i in range(H):
    for j, n in enumerate(map(int, input().split())):
        d[i+1][j+1] = n
    
for i in range(H):
    for j, n in enumerate(map(int, input().split())):
        d[i+1][j+1] -= n

for i in range(1, H+1):
    for j in range(1, W+1):
        for k in range(vmax+1):
            if i>1 and 0<=k-d[i-1][j]<=vmax:
                dp[i][j][k] |= dp[i-1][j][k-d[i-1][j]]
            if i>1 and 0<=k+d[i-1][j]<=vmax:
                dp[i][j][k] |= dp[i-1][j][k+d[i-1][j]]
            if j>1 and 0<=k-d[i][j-1]<=vmax:
                dp[i][j][k] |= dp[i][j-1][k-d[i][j-1]]
            if j>1 and 0<=k+d[i][j-1]<=vmax:
                dp[i][j][k] |= dp[i][j-1][k+d[i][j-1]]

v = d[H][W]
ans = vmax
for i,j in enumerate(dp[H][W]):
    if not j:continue
    ans = min(ans, abs(i+v), abs(i-v))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int, input().split())
A=[]
B=[]
for _ in range(H):
    A.append(list(map(int, input().split())))
for _ in range(H):
    B.append(list(map(int, input().split())))
M=[[[] for _ in range(W)] for _ in range(H)]
m=0
for i in range(H):
    for j in range(W):
        M[i][j]=abs(A[i][j]-B[i][j])
        m=max(M[i][j],m)
r=m*(H+W)
dp=[[[False for _ in range(r+1)] for _ in range(W)] for _ in range(H)]
dp[0][0][abs(A[0][0]-B[0][0])]=True
for i in range(H):
    for j in range(W):
        if i==0 and j==0: continue
        for k in range(r+1):
            if i==0:
                if k+M[i][j] <= r:
                    if dp[i][j-1][abs(k-M[i][j])] or dp[i][j-1][k+M[i][j]]:
                        dp[i][j][k]=True
                else:
                    if dp[i][j-1][abs(k-M[i][j])]:
                        dp[i][j][k]=True
            elif j==0:
                if k+M[i][j] <= r:
                    if dp[i-1][j][abs(k-M[i][j])] or dp[i-1][j][k+M[i][j]]:
                        dp[i][j][k]=True
                else:
                    if dp[i-1][j][abs(k-M[i][j])]:
                        dp[i][j][k]=True
            elif k+M[i][j] <= r:
                if dp[i][j-1][abs(k-M[i][j])] or dp[i][j-1][k+M[i][j]] or dp[i-1][j][abs(k-M[i][j])] or dp[i-1][j][k+M[i][j]]:
                    dp[i][j][k]=True
            else:
                if dp[i][j-1][abs(k-M[i][j])] or dp[i-1][j][abs(k-M[i][j])]:
                    dp[i][j][k]=True
for i in range(r+1):
    if dp[H-1][W-1][i]:
        print(i)
        break

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int, input().split())
A=[]
B=[]
for _ in range(H):
    A.append(list(map(int, input().split())))
for _ in range(H):
    B.append(list(map(int, input().split())))
M=[[[] for _ in range(W)] for _ in range(H)]
m=0
for i in range(H):
    for j in range(W):
        M[i][j]=abs(A[i][j]-B[i][j])
        m=max(M[i][j],m)
r=m*(H+W)
dp=[[[False for _ in range(r+1)] for _ in range(W)] for _ in range(H)]
dp[0][0][abs(A[0][0]-B[0][0])]=True
for i in range(H):
    for j in range(W):
        if i==0 and j==0: continue
        for k in range(r+1):
            if i==0:
                if k+M[i][j] <= r:
                    if dp[i][j-1][abs(k-M[i][j])] or dp[i][j-1][k+M[i][j]]:
                        dp[i][j][k]=True
                else:
                    if dp[i][j-1][abs(k-M[i][j])]:
                        dp[i][j][k]=True
            elif j==0:
                if k+M[i][j] <= r:
                    if dp[i-1][j][abs(k-M[i][j])] or dp[i-1][j][k+M[i][j]]:
                        dp[i][j][k]=True
                else:
                    if dp[i-1][j][abs(k-M[i][j])]:
                        dp[i][j][k]=True
            elif k+M[i][j] <= r:
                if dp[i][j-1][abs(k-M[i][j])] or dp[i][j-1][k+M[i][j]] or dp[i-1][j][abs(k-M[i][j])] or dp[i-1][j][k+M[i][j]]:
                    dp[i][j][k]=True
            else:
                if dp[i][j-1][abs(k-M[i][j])] or dp[i-1][j][abs(k-M[i][j])]:
                    dp[i][j][k]=True
for i in range(r+1):
    if dp[H-1][W-1][i]:
        print(i)
        break

Submission status: Time Limit Exceeded

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

def main():
    H,W = map(int,input().split())
    p = [[0 for _ in range(W)] for _ in range(H)]
    point = [[[] for _ in range(W)] for _ in range(H)]
    
    for i in range(H):
        a = list(map(int,input().split()))
        for j,num in enumerate(a):
            p[i][j] += num
    
    for i in range(H):
        b = list(map(int,input().split()))
        for j,num in enumerate(b):
            p[i][j] -= num

    point[0][0].append(p[0][0])
    q = deque([(0,0)])
    while q:
        x,y = q.popleft()
        dx,dy = [1,0],[0,1]
        for i in range(2):
            nx,ny = x+dx[i],y+dy[i]
            if (0<=nx<H and 0<=ny<W):
                for num in point[x][y]:
                    point[nx][ny].append(num+p[nx][ny])
                    point[nx][ny].append(num-p[nx][ny])
                point[nx][ny] = list(set(point[nx][ny]))
                q.append((nx,ny))
    
    point[-1][-1].sort(key=lambda x:abs(x))
    print(abs(point[-1][-1][0]))

if __name__ == "__main__":
    main()