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, raw_input().split())
A = []
B = []
for h in range(H):
    A_hj = map(int, raw_input().split())
    A.append(A_hj)
for h in range(H):
    B_hj = map(int, raw_input().split())
    B.append(B_hj)

dp = [[set() for _ in range(W)] for _ in range(H)]
dp[0][0] = {abs(A[0][0] - B[0][0])}
for i in range(H):
    for j in range(W):
        if i == 0 and j == 0: continue
        d = abs(A[i][j] - B[i][j])
        possible = set()
        if i-1 >= 0:
            for diff in dp[i-1][j]:
                possible.add(abs(diff+d))
                possible.add(abs(diff-d))
        if j-1 >= 0:
            for diff in dp[i][j-1]:
                possible.add(abs(diff+d))
                possible.add(abs(diff-d))
        dp[i][j] = {d for d in possible if d <= 100}

possible = dp[H-1][W-1]
print min(possible, key=lambda d: abs(d))

Submission status: Wrong Answer

Solution code:
H, W = map(int, raw_input().split())
A = []
B = []
for h in range(H):
    A_hj = map(int, raw_input().split())
    A.append(A_hj)
for h in range(H):
    B_hj = map(int, raw_input().split())
    B.append(B_hj)

dp = [[set() for _ in range(W)] for _ in range(H)]
dp[0][0] = {abs(A[0][0] - B[0][0])}
for i in range(H):
    for j in range(W):
        d = abs(A[i][j] - B[i][j])
        if i-1 >= 0:
            for diff in dp[i-1][j]:
                if diff+d <= 6400:
                    dp[i][j].add(diff+d)
                if diff-d >= -6400:
                    dp[i][j].add(diff-d)
        if j-1 >= 0:
            for diff in dp[i][j-1]:
                if diff+d <= 6400:
                    dp[i][j].add(diff+d)
                if diff-d >= -6400:
                    dp[i][j].add(diff-d)

possible = dp[H-1][W-1]
print min(possible, key=lambda d: abs(d))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque
H,W=map(int, sys.stdin.readline().split())

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

for h in range(H):
    for w in range(W):
        A[h][w]=abs(A[h][w]-B[h][w])

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

Center=80*80      #中心地のセット マイナスの値もセットできるようにbitsetのゼロを80*80+1桁目に置く

#初期化
r,c=0,0
val=A[r][c]
dp[r][c]=1<<val+Center

q=deque()
q.append((0,0))
D=[(1,0),(0,1)]

while q:
    r,c=q.popleft()
    for dr,dc in D:
        if r+dr<H and c+dc<W:
            next_r=r+dr
            next_c=c+dc
            q.append((next_r,next_c))

print 0

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque
H,W=map(int, sys.stdin.readline().split())

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

for h in range(H):
    for w in range(W):
        A[h][w]=abs(A[h][w]-B[h][w])

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

Center=80*80      #中心地のセット マイナスの値もセットできるようにbitsetのゼロを80*80+1桁目に置く

#初期化
r,c=0,0
val=A[r][c]
dp[r][c]=1<<val+Center

q=deque()
q.append((0,0))
D=[(1,0),(0,1)]


print 0

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque
H,W=map(int, sys.stdin.readline().split())

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

for h in range(H):
    for w in range(W):
        A[h][w]=abs(A[h][w]-B[h][w])

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

Center=80*80      #中心地のセット マイナスの値もセットできるようにbitsetのゼロを80*80+1桁目に置く

#初期化
r,c=0,0
val=A[r][c]
dp[r][c]=1<<val+Center

q=deque()
q.append((0,0))
D=[(1,0),(0,1)]

while q:
    r,c=q.popleft()
    for dr,dc in D:
        if r+dr<H and c+dc<W:
            next_r=r+dr
            next_c=c+dc
            next_val=A[next_r][next_c]
            q.append((next_r,next_c))

print 0

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque
H,W=map(int, sys.stdin.readline().split())

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

for h in range(H):
    for w in range(W):
        A[h][w]=abs(A[h][w]-B[h][w])

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

Center=80*80      #中心地のセット マイナスの値もセットできるようにbitsetのゼロを80*80+1桁目に置く

#初期化
r,c=0,0
val=A[r][c]
dp[r][c]=1<<val+Center

q=deque()
q.append((0,0))
D=[(1,0),(0,1)]

while q:
    r,c=q.popleft()
    for dr,dc in D:
        if r+dr<H and c+dc<W:
            next_r=r+dr
            next_c=c+dc
            next_val=A[next_r][next_c]
            dp[next_r][next_c]|=dp[r][c]<<next_val
            dp[next_r][next_c]|=dp[r][c]>>next_val
            q.append((next_r,next_c))

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


#差分だけで良い，これを*1 or -1していく
diff = [[0]*W for _ in range(H)]
for i in range(H):
    for j in range(W):
        diff[i][j] = abs(A[i][j] - B[i][j])

#i,jマスにおいて，偏りがkになれるかどうかでDP
K = 2001 #適当,[-1000,1000]
kk = int((K-1)/2)
dp = [[[False]*K for _ in range(W)] for _ in range(H)]

dp[0][0][kk+diff[0][0]] = True
dp[0][0][kk-diff[0][0]] = True

for i in range(H):
    for j in range(W):
        for k in range(K):
            if i-1>=0:
                if k+diff[i][j]<K:
                    if dp[i-1][j][k+diff[i][j]]:
                        dp[i][j][k] =True
                if k-diff[i][j]>=0:
                    if dp[i-1][j][k-diff[i][j]]:
                        dp[i][j][k] =True
            if j-1>=0:
                if k+diff[i][j]<K:
                    if dp[i][j-1][k+diff[i][j]]:
                        dp[i][j][k] =True
                if k-diff[i][j]>=0:
                    if dp[i][j-1][k-diff[i][j]]:
                        dp[i][j][k] =True

ans = K
for k in range(K):
    if dp[H-1][W-1][k]:
        ans = min(ans,abs(k-kk))

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


#差分だけで良い，これを*1 or -1していく
diff = [[0]*W for _ in range(H)]
for i in range(H):
    for j in range(W):
        diff[i][j] = abs(A[i][j] - B[i][j])

#i,jマスにおいて，偏りがkになれるかどうかでDP
K = 601 #適当,[-300,300]
kk = int((K-1)/2)
dp = [[[False]*K for _ in range(W)] for _ in range(H)]

dp[0][0][kk+diff[0][0]] = True
dp[0][0][kk-diff[0][0]] = True

for i in range(H):
    for j in range(W):
        for k in range(K):
            if i-1>=0:
                if k+diff[i][j]<K:
                    if dp[i-1][j][k+diff[i][j]]:
                        dp[i][j][k] =True
                if k-diff[i][j]>=0:
                    if dp[i-1][j][k-diff[i][j]]:
                        dp[i][j][k] =True
            if j-1>=0:
                if k+diff[i][j]<K:
                    if dp[i][j-1][k+diff[i][j]]:
                        dp[i][j][k] =True
                if k-diff[i][j]>=0:
                    if dp[i][j-1][k-diff[i][j]]:
                        dp[i][j][k] =True

ans = K
for k in range(K):
    if dp[H-1][W-1][k]:
        ans = min(ans,abs(k-kk))

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


#差分だけで良い，これを*1 or -1していく
diff = [[0]*W for _ in range(H)]
for i in range(H):
    for j in range(W):
        diff[i][j] = abs(A[i][j] - B[i][j])

#i,jマスにおいて，偏りがkになれるかどうかでDP
K = 201 #適当,[-100,100]
kk = int((K-1)/2)
dp = [[[False]*K for _ in range(W)] for _ in range(H)]

dp[0][0][kk+diff[0][0]] = True
dp[0][0][kk-diff[0][0]] = True

for i in range(H):
    for j in range(W):
        for k in range(K):
            if i-1>=0:
                if k+diff[i][j]<K:
                    if dp[i-1][j][k+diff[i][j]]:
                        dp[i][j][k] =True
                if k-diff[i][j]>=0:
                    if dp[i-1][j][k-diff[i][j]]:
                        dp[i][j][k] =True
            if j-1>=0:
                if k+diff[i][j]<K:
                    if dp[i][j-1][k+diff[i][j]]:
                        dp[i][j][k] =True
                if k-diff[i][j]>=0:
                    if dp[i][j-1][k-diff[i][j]]:
                        dp[i][j][k] =True

ans = K
for k in range(K):
    if dp[H-1][W-1][k]:
        ans = min(ans,abs(k-kk))

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
h, w = map(int, input().split())
grid = []
bias_inf = 1900
for i in range(h):
    k = list(map(int, input().split()))
    grid.append(k)
for i in range(h):
    k = list(map(int, input().split()))
    for j in range(w):
        grid[i][j] = abs(grid[i][j] - k[j])

dp = [[[False for i in range(-bias_inf,bias_inf)] for j in range(w)] for k in range(h)]
dp[0][0][0 - grid[0][0]] = True
dp[0][0][0 + grid[0][0]] = True
for i in range(h):
    for j in range(w):
        for k in range(-bias_inf,bias_inf):
            if i == h-1 and j == w-1:
                break
            if dp[i][j][k]:
                if i != h-1 and j != w-1:
                    dp[i][j+1][k + grid[i][j+1]] = True
                    dp[i+1][j][k + grid[i+1][j]] = True
                    dp[i][j+1][k - grid[i][j+1]] = True
                    dp[i+1][j][k - grid[i+1][j]] = True
                elif j == w-1:
                    dp[i+1][j][k - grid[i+1][j]] = True
                    dp[i+1][j][k + grid[i+1][j]] = True
                else:
                    dp[i][j+1][k - grid[i][j+1]] = True
                    dp[i][j+1][k + grid[i][j+1]] = True
ans = bias_inf
for i in range(-bias_inf,bias_inf):
    if dp[-1][-1][i]:
        ans = min(ans, abs(i))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
h, w = map(int, input().split())
grid = []
bias_inf = 1700
for i in range(h):
    k = list(map(int, input().split()))
    grid.append(k)
for i in range(h):
    k = list(map(int, input().split()))
    for j in range(w):
        grid[i][j] = abs(grid[i][j] - k[j])

dp = [[[False for i in range(-bias_inf,bias_inf)] for j in range(w)] for k in range(h)]
dp[0][0][0 - grid[0][0]] = True
dp[0][0][0 + grid[0][0]] = True
for i in range(h):
    for j in range(w):
        for k in range(-bias_inf,bias_inf):
            if i == h-1 and j == w-1:
                break
            if dp[i][j][k]:
                if i == h-1:
                    if k - grid[i][j+1] > -bias_inf:
                        dp[i][j+1][k - grid[i][j+1]] = True
                    if k + grid[i][j+1] < bias_inf:
                        dp[i][j+1][k + grid[i][j+1]] = True
                elif j == w-1:
                    if k - grid[i+1][j] > -bias_inf:
                        dp[i+1][j][k - grid[i+1][j]] = True
                    if k + grid[i+1][j] < bias_inf:
                        dp[i+1][j][k + grid[i+1][j]] = True
                else:
                    if k + grid[i][j+1] < bias_inf:
                        dp[i][j+1][k + grid[i][j+1]] = True
                    if k + grid[i+1][j] < bias_inf:
                        dp[i+1][j][k + grid[i+1][j]] = True
                    if k - grid[i][j+1] > -bias_inf: 
                        dp[i][j+1][k - grid[i][j+1]] = True
                    if k - grid[i+1][j] > -bias_inf:
                        dp[i+1][j][k - grid[i+1][j]] = True
ans = bias_inf
for i in range(-bias_inf,bias_inf):
    if dp[-1][-1][i]:
        ans = min(ans, abs(i))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
h, w = map(int, input().split())
grid = []
bias_inf = 1500
for i in range(h):
    k = list(map(int, input().split()))
    grid.append(k)
for i in range(h):
    k = list(map(int, input().split()))
    for j in range(w):
        grid[i][j] = abs(grid[i][j] - k[j])

dp = [[[False for i in range(-bias_inf,bias_inf)] for j in range(w)] for k in range(h)]
dp[0][0][0 - grid[0][0]] = True
dp[0][0][0 + grid[0][0]] = True
for i in range(h):
    for j in range(w):
        for k in range(-bias_inf,bias_inf):
            if i == h-1 and j == w-1:
                break
            if dp[i][j][k]:
                if i == h-1:
                    if k - grid[i][j+1] > -bias_inf:
                        dp[i][j+1][k - grid[i][j+1]] = True
                    if k + grid[i][j+1] < bias_inf:
                        dp[i][j+1][k + grid[i][j+1]] = True
                elif j == w-1:
                    if k - grid[i+1][j] > -bias_inf:
                        dp[i+1][j][k - grid[i+1][j]] = True
                    if k + grid[i+1][j] < bias_inf:
                        dp[i+1][j][k + grid[i+1][j]] = True
                else:
                    if k + grid[i][j+1] < bias_inf:
                        dp[i][j+1][k + grid[i][j+1]] = True
                    if k + grid[i+1][j] < bias_inf:
                        dp[i+1][j][k + grid[i+1][j]] = True
                    if k - grid[i][j+1] > -bias_inf: 
                        dp[i][j+1][k - grid[i][j+1]] = True
                    if k - grid[i+1][j] > -bias_inf:
                        dp[i+1][j][k - grid[i+1][j]] = True
ans = bias_inf
for i in range(-bias_inf,bias_inf):
    if dp[-1][-1][i]:
        ans = min(ans, abs(i))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
h, w = map(int, input().split())
grid = []
bias_inf = 1000
for i in range(h):
    k = list(map(int, input().split()))
    grid.append(k)
for i in range(h):
    k = list(map(int, input().split()))
    for j in range(w):
        grid[i][j] = abs(grid[i][j] - k[j])

dp = [[[False for i in range(-bias_inf,bias_inf)] for j in range(w)] for k in range(h)]
dp[0][0][0 - grid[0][0]] = True
dp[0][0][0 + grid[0][0]] = True
for i in range(h):
    for j in range(w):
        for k in range(-bias_inf,bias_inf):
            if i == h-1 and j == w-1:
                break
            if dp[i][j][k]:
                if i == h-1:
                    if k - grid[i][j+1] > -bias_inf:
                        dp[i][j+1][k - grid[i][j+1]] = True
                    if k + grid[i][j+1] < bias_inf:
                        dp[i][j+1][k + grid[i][j+1]] = True
                elif j == w-1:
                    if k - grid[i+1][j] > -bias_inf:
                        dp[i+1][j][k - grid[i+1][j]] = True
                    if k + grid[i+1][j] < bias_inf:
                        dp[i+1][j][k + grid[i+1][j]] = True
                else:
                    if k + grid[i][j+1] < bias_inf:
                        dp[i][j+1][k + grid[i][j+1]] = True
                    if k + grid[i+1][j] < bias_inf:
                        dp[i+1][j][k + grid[i+1][j]] = True
                    if k - grid[i][j+1] > -bias_inf: 
                        dp[i][j+1][k - grid[i][j+1]] = True
                    if k - grid[i+1][j] > -bias_inf:
                        dp[i+1][j][k - grid[i+1][j]] = True
ans = bias_inf
for i in range(-bias_inf,bias_inf):
    if dp[-1][-1][i]:
        ans = min(ans, abs(i))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
h, w = map(int, input().split())
grid = []
bias_inf = 2000
for i in range(h):
    k = list(map(int, input().split()))
    grid.append(k)
for i in range(h):
    k = list(map(int, input().split()))
    for j in range(w):
        grid[i][j] = abs(grid[i][j] - k[j])

dp = [[[False for i in range(-bias_inf,bias_inf)] for j in range(w)] for k in range(h)]
dp[0][0][0 - grid[0][0]] = True
dp[0][0][0 + grid[0][0]] = True
for i in range(h):
    for j in range(w):
        for k in range(-bias_inf,bias_inf):
            if i == h-1 and j == w-1:
                break
            if dp[i][j][k]:
                if i == h-1:
                    dp[i][j+1][k - grid[i][j+1]] = True
                    dp[i][j+1][k + grid[i][j+1]] = True
                elif j == w-1:
                    dp[i+1][j][k - grid[i+1][j]] = True
                    dp[i+1][j][k + grid[i+1][j]] = True
                else:
                    dp[i][j+1][k + grid[i][j+1]] = True
                    dp[i+1][j][k + grid[i+1][j]] = True
                    dp[i][j+1][k - grid[i][j+1]] = True
                    dp[i+1][j][k - grid[i+1][j]] = True
ans = bias_inf
ans = min([i for i in range(-bias_inf, bias_inf) if dp[-1][-1][i]] ,key = lambda x:abs(x))
print(ans)

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
grid = []
bias_inf = 1700
for i in range(h):
    k = list(map(int, input().split()))
    grid.append(k)
for i in range(h):
    k = list(map(int, input().split()))
    for j in range(w):
        grid[i][j] = abs(grid[i][j] - k[j])

dp = [[[False for i in range(-bias_inf,bias_inf)] for j in range(w)] for k in range(h)]
dp[0][0][0 - grid[0][0]] = True
dp[0][0][0 + grid[0][0]] = True
for i in range(h):
    for j in range(w):
        for k in range(-bias_inf,bias_inf):
            if i == h-1 and j == w-1:
                break
            if dp[i][j][k]:
                if i == h-1:
                    dp[i][j+1][k - grid[i][j+1]] = True
                    dp[i][j+1][k + grid[i][j+1]] = True
                elif j == w-1:
                    dp[i+1][j][k - grid[i+1][j]] = True
                    dp[i+1][j][k + grid[i+1][j]] = True
                else:
                    dp[i][j+1][k + grid[i][j+1]] = True
                    dp[i+1][j][k + grid[i+1][j]] = True
                    dp[i][j+1][k - grid[i][j+1]] = True
                    dp[i+1][j][k - grid[i+1][j]] = True
ans = bias_inf
for i in range(-bias_inf,bias_inf):
    if dp[-1][-1][i]:
        ans = min(ans, abs(i))
print(ans)

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
grid = []
bias_inf = 1500
for i in range(h):
    k = list(map(int, input().split()))
    grid.append(k)
for i in range(h):
    k = list(map(int, input().split()))
    for j in range(w):
        grid[i][j] = abs(grid[i][j] - k[j])

dp = [[[False for i in range(-bias_inf,bias_inf)] for j in range(w)] for k in range(h)]
dp[0][0][0 - grid[0][0]] = True
dp[0][0][0 + grid[0][0]] = True
for i in range(h):
    for j in range(w):
        for k in range(-bias_inf,bias_inf):
            if i == h-1 and j == w-1:
                break
            if dp[i][j][k]:
                if i == h-1:
                    dp[i][j+1][k - grid[i][j+1]] = True
                    dp[i][j+1][k + grid[i][j+1]] = True
                elif j == w-1:
                    dp[i+1][j][k - grid[i+1][j]] = True
                    dp[i+1][j][k + grid[i+1][j]] = True
                else:
                    dp[i][j+1][k + grid[i][j+1]] = True
                    dp[i+1][j][k + grid[i+1][j]] = True
                    dp[i][j+1][k - grid[i][j+1]] = True
                    dp[i+1][j][k - grid[i+1][j]] = True
ans = bias_inf
for i in range(-bias_inf,bias_inf):
    if dp[-1][-1][i]:
        ans = min(ans, abs(i))
print(ans)

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
grid = []
bias_inf = 1000
for i in range(h):
    k = list(map(int, input().split()))
    grid.append(k)
for i in range(h):
    k = list(map(int, input().split()))
    for j in range(w):
        grid[i][j] = abs(grid[i][j] - k[j])

dp = [[[False for i in range(-bias_inf,bias_inf)] for j in range(w)] for k in range(h)]
dp[0][0][0 - grid[0][0]] = True
dp[0][0][0 + grid[0][0]] = True
for i in range(h):
    for j in range(w):
        for k in range(-bias_inf,bias_inf):
            if i == h-1 and j == w-1:
                break
            if dp[i][j][k]:
                if i == h-1:
                    dp[i][j+1][k - grid[i][j+1]] = True
                    dp[i][j+1][k + grid[i][j+1]] = True
                elif j == w-1:
                    dp[i+1][j][k - grid[i+1][j]] = True
                    dp[i+1][j][k + grid[i+1][j]] = True
                else:
                    dp[i][j+1][k + grid[i][j+1]] = True
                    dp[i+1][j][k + grid[i+1][j]] = True
                    dp[i][j+1][k - grid[i][j+1]] = True
                    dp[i+1][j][k - grid[i+1][j]] = True
ans = bias_inf
for i in range(-bias_inf,bias_inf):
    if dp[-1][-1][i]:
        ans = min(ans, abs(i))
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque
H,W=map(int, sys.stdin.readline().split())

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

for h in range(H):
    for w in range(W):
        A[h][w]=abs(A[h][w]-B[h][w])

dp=[ [ {} for _ in range(W) ] for __ in range(H) ]

#初期化
r,c=0,0
val=A[r][c]
dp[r][c][val]=1
dp[r][c][val*-1]=1

q=deque()
q.append((0,0))
D=[(1,0),(0,1)]

while q:
    r,c=q.popleft()
    for dr,dc in D:
        if r+dr<H and c+dc<W:
            next_r=r+dr
            next_c=c+dc
            next_val=A[next_r][next_c]
            for j in dp[r][c]:
                dp[next_r][next_c][j+next_val]=1
                dp[next_r][next_c][j+next_val*-1]=1
            q.append((next_r,next_c))

#print "dp : ",dp
#print min(map(lambda x: abs(x), dp[H-1][W-1]))
print 0

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque
H,W=map(int, sys.stdin.readline().split())

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

for h in range(H):
    for w in range(W):
        A[h][w]=abs(A[h][w]-B[h][w])

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

#初期化
r,c=0,0
val=A[r][c]
dp[r][c].add(val)
dp[r][c].add(val*-1)

q=deque()
q.append((0,0))
D=[(1,0),(0,1)]

while q:
    r,c=q.popleft()
    print "r,c",r,c
    for dr,dc in D:
        if r+dr<H and c+dc<W:
            next_r=r+dr
            next_c=c+dc
            next_val=A[next_r][next_c]
            for j in dp[r][c]:
                dp[next_r][next_c].add(j+next_val)
                dp[next_r][next_c].add(j+next_val*-1)
            q.append((next_r,next_c))


#print min(map(lambda x: abs(x), dp[H-1][W-1]))
print 0

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
a=[]
for i in range(h):
    a.append(tuple(map(int,input().split())))
b=[]
for i in range(h):
    b.append(tuple(map(int,input().split())))
c=[[0]*w for i in range(h)]
for i in range(h):
    for j in range(w):
        c[i][j]=abs(b[i][j]-a[i][j])
num=(h+w)*80+1
dp=[[[0]*(num) for i in range(w)] for j in range(2)]
dp[0][0][0]=1
dp[0][0][c[0][0]]=1
t=0
for i in range(h):
    if i==0:
        for j in range(1,w):
            for k in range(num):
                if dp[t][j-1][k]==1:
                    dp[t][j][k+c[i][j]]=1
                    dp[t][j][abs(k-c[i][j])]=1
    else:
        for j in range(w):
            for k in range(num):
                if dp[1-t][j][k]==1:
                    dp[t][j][k+c[i][j]]=1
                    dp[t][j][abs(k-c[i][j])]=1
                if dp[t][j-1][k]==1 and j!=0:
                    dp[t][j][k+c[i][j]]=1
                    dp[t][j][abs(k-c[i][j])]=1

    t=1-t
for i in range(num):
    if dp[1-t][-1][i]==1:
        print(i)
        break

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
a=[]
for i in range(h):
    a.append(tuple(map(int,input().split())))
b=[]
for i in range(h):
    b.append(tuple(map(int,input().split())))
c=[[0]*w for i in range(h)]
for i in range(h):
    for j in range(w):
        c[i][j]=abs(b[i][j]-a[i][j])
num=2*80**2+1
dp=[[[0]*(num) for i in range(w)] for j in range(2)]
dp[0][0][0]=1
dp[0][0][c[0][0]]=1
t=0
for i in range(h):
    if i==0:
        for j in range(1,w):
            for k in range(num):
                if dp[t][j-1][k]==1:
                    dp[t][j][k+c[i][j]]=1
                    dp[t][j][abs(k-c[i][j])]=1
    else:
        for j in range(w):
            for k in range(num):
                if dp[1-t][j][k]==1:
                    dp[t][j][k+c[i][j]]=1
                    dp[t][j][abs(k-c[i][j])]=1
                if dp[t][j-1][k]==1 and j!=0:
                    dp[t][j][k+c[i][j]]=1
                    dp[t][j][abs(k-c[i][j])]=1

    t=1-t
for i in range(num):
    if dp[1-t][-1][i]==1:
        print(i)
        break

Submission status: Wrong Answer

Solution code:
def solve(h, w, A, B):
    center = 1000
    C = [[abs(A[r][c]-B[r][c]) for c in range(w)] for r in range(h)]
    dp = [[0]*w for r in range(h)]
    dp[0][0] = (1 << (center + C[0][0])) | (1 << (center - C[0][0]))
    for r in range(h):
        for c in range(w):
            if r > 0:
                dp[r][c] |= (dp[r-1][c] << C[r-1][c])
                dp[r][c] |= (dp[r-1][c] >> C[r-1][c])
            if c > 0:
                dp[r][c] |= (dp[r][c-1] << C[r][c-1])
                dp[r][c] |= (dp[r][c-1] >> C[r][c-1])
    mask = bin(dp[-1][-1] >> center)
    return mask[::-1].find("1") - 1

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)]
print(solve(h, w, A, B))

Submission status: Wrong Answer

Solution code:
def solve(h, w, A, B):
    center = (h+w) * 80
    C = [[abs(A[r][c]-B[r][c]) for c in range(w)] for r in range(h)]
    dp = [[0]*w for r in range(h)]
    dp[0][0] = (1 << (center + C[0][0])) | (1 << (center - C[0][0]))
    for r in range(h):
        for c in range(w):
            if r > 0:
                dp[r][c] |= (dp[r-1][c] << C[r-1][c])
                dp[r][c] |= (dp[r-1][c] >> C[r-1][c])
            if c > 0:
                dp[r][c] |= (dp[r][c-1] << C[r][c-1])
                dp[r][c] |= (dp[r][c-1] >> C[r][c-1])
    mask = bin(dp[-1][-1] >> center)
    return mask[::-1].find("1") - 1

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)]
print(solve(h, w, A, B))

Submission status: Wrong Answer

Solution code:
def run():
  ofs = 100
  H, W = map(int, input().split())
  dp = [[0 for w in range(W)] for h in range(H)]
  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)]
  dp[0][0] = (1 << ofs + c[0][0]) | (1 << ofs - c[0][0])
  for h in range(1, H):
    dp[h][0] = (dp[h-1][0] << c[h][0]) | (dp[h-1][0] >> c[h][0])
  for w in range(1, W):
    dp[0][w] = (dp[0][w-1] << c[0][w]) | (dp[0][w-1] >> c[0][w])
  for h in range(1, H):
    for w in range(1, W):
      v = c[h][w]
      dp[h][w] = (dp[h-1][w] << v) | (dp[h-1][w] >> v)
      dp[h][w] |= (dp[h][w-1] << v) | (dp[h][w-1] >> v)
  s = list(bin(dp[-1][-1] >> ofs))
  for i in range(len(s)):
    if s[-1-i] == '1':
      print(i)
      break

if __name__ == '__main__':
  run()

Submission status: Wrong Answer

Solution code:
print("2019/12/18 23:00 reference: maspy")

import sys
input = sys.stdin.buffer.readline
 
H,W = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
B = [list(map(int, input().split())) for _ in range(H)]
 
X = (H + W) * 80
# X点持った状態から始める

dp = [[0] * W for _ in range(H)]
d = abs(A[0][0] - B[0][0])
dp[0][0] = (1 << (X - d)) # 最上位桁
#print(bin(dp[0][0])[2::])

for h in range(H): # indexが何を表しているか分かりやすくする。
    for w, (a, b) in enumerate(zip(A[h], B[h])): # 二つの配列から取り出す。enumerateはもっと多用する。
        if h == w == 0:
            continue
        d = abs(a - b)
        x = 0
        if h != 0:
            x |= (dp[h-1][w] << d) # 素晴らしい。
            x |= (dp[h-1][w] >> d)
        if w != 0:
            x |= (dp[h][w-1] << d) 
            x |= (dp[h][w-1] >> d)
        dp[h][w] = x

dp = dp[-1][-1]
B = bin(dp)[2:]
#print("B:", B)

can_make = [i - X for i, b in enumerate(B[::-1]) if b == '1']
print("can_make:", can_make)

answer = min(x if x >= 0 else -x for x in can_make)
print(answer)

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

X = [[0] * W for i in range(H)]
for h in range(H):
    for w in range(W):
        X[h][w] = abs(A[h][w] - B[h][w])

# dp[h][w][x] := (h, w)の時点で差をxにできるか？
M = 1280
dp = [[[False] * (M + 1) for j in range(W)] for i in range(H)]
dp[0][0][X[0][0]] = True

for h in range(H):
    for w in range(W):
        for m in range(M):
            x = X[h][w]
            if (0 <= h - 1) and abs(m + X[h][w]) <= M:
                dp[h][w][m] = dp[h][w][m] or dp[h - 1][w][abs(m + x)]

            if (0 <= h - 1) and abs(m - X[h][w]) <= M:
                dp[h][w][m] = dp[h][w][m] or dp[h - 1][w][abs(m - x)]

            if (0 <= w - 1) and abs(m + X[h][w]) <= M:
                dp[h][w][m] = dp[h][w][m] or dp[h][w - 1][abs(m + x)]

            if (0 <= w - 1) and abs(m - X[h][w]) <= M:
                dp[h][w][m] = dp[h][w][m] or dp[h][w - 1][abs(m - x)]

ans = float('inf')
for x in range(M + 1):
    if dp[H - 1][W - 1][x]:
        ans = min(ans, x)

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


X = [[0] * W for i in range(H)]
for h in range(H):
    for w in range(W):
        X[h][w] = abs(A[h][w] - B[h][w])


# dp[h][w][x] := (h, w)の時点で差をxにできるか？
M = 2560
dp = [[[False] * (M + 1) for j in range(W)] for i in range(H)]
dp[0][0][X[0][0]] = True


for h in range(H):
    for w in range(W):
        for m in range(M):
            x = X[h][w]
            if (0 <= h - 1) and abs(m + X[h][w] <= M):
                dp[h][w][m] = dp[h][w][m] or dp[h - 1][w][abs(m + x)]

            if (0 <= h - 1) and abs(m - X[h][w] <= M):
                dp[h][w][m] = dp[h][w][m] or dp[h - 1][w][abs(m - x)]

            if (0 <= w - 1) and abs(m + X[h][w] <= M):
                dp[h][w][m] = dp[h][w][m] or dp[h][w - 1][abs(m + x)]

            if (0 <= w - 1) and abs(m + X[h][w] <= M):
                dp[h][w][m] = dp[h][w][m] or dp[h][w - 1][abs(m - x)]


ans = float('inf')
for x in range(M + 1):
    if dp[H - 1][W - 1][x]:
        ans = min(ans, x)

print(ans)