Problem:


Score : 500 points

Problem Statement

We have a grid with H horizontal rows and W vertical columns. Let (i,j) denote the square at the i-th row from the top and the j-th column from the left.

The square (i, j) has two numbers A_{ij} and B_{ij} written on it.

First, for each square, Takahashi paints one of the written numbers red and the other blue.

Then, he travels from the square (1, 1) to the square (H, W). In one move, he can move from a square (i, j) to the square (i+1, j) or the square (i, j+1). He must not leave the grid.

Let the unbalancedness be the absolute difference of the sum of red numbers and the sum of blue numbers written on the squares along Takahashi's path, including the squares (1, 1) and (H, W).

Takahashi wants to make the unbalancedness as small as possible by appropriately painting the grid and traveling on it.

Find the minimum unbalancedness possible.

Constraints

2 \leq H \leq 80

2 \leq W \leq 80

0 \leq A_{ij} \leq 80

0 \leq B_{ij} \leq 80

All values in input are integers.

Input

Input is given from Standard Input in the following format:

H W
A_{11} A_{12} \ldots A_{1W}
:
A_{H1} A_{H2} \ldots A_{HW}
B_{11} B_{12} \ldots B_{1W}
:
B_{H1} B_{H2} \ldots B_{HW}

Output

Print the minimum unbalancedness possible.

Sample Input 1

2 2
1 2
3 4
3 4
2 1

Sample Output 1

0

By painting the grid and traveling on it as shown in the figure below, the sum of red numbers and the sum of blue numbers are 3+3+1=7 and 1+2+4=7, respectively, for the unbalancedness of 0.

Sample Input 2

2 3
1 10 80
80 10 1
1 2 3
4 5 6

Sample Output 2

2



Sample input:
2 2
1 2
3 4
3 4
2 1


Sample output:
0

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
A=[]
x=[0]*(W+2)
A.append(x)
for i in range(H):
    a=list(map(int,input().split()))
    A.append([0]+a+[0])
A.append(x)
#print(A)

for i in range(H):
    b=list(map(int,input().split()))
    for j in range(W):
        A[i+1][j+1] = abs(A[i+1][j+1]-b[j])
        
#print(A)

L=[[set() for i in range(W+2)] for j in range(H+2)]
L[1][1].add(abs(A[1][1]))
#print(L)
#print(L[0][0])
for i in range(1,H+1):
    for j in range(1,W+1):
        L[i][j]=list(L[i][j])
        for x in L[i][j]:
            if abs(x+A[i][j+1])<=3200:
                L[i][j+1].add(abs(x+A[i][j+1]))
            if abs(x-A[i][j+1])<=3200:
                L[i][j+1].add(abs(x-A[i][j+1]))
            if abs(x+A[i+1][j])<=3200:
                L[i+1][j].add(abs(x+A[i+1][j]))
            if abs(x-A[i+1][j])<=3200:
                L[i+1][j].add(abs(x-A[i+1][j]))
#print(L)

ans=10**5
L[H][W]=list(L[H][W])
for k in L[H][W]:
    if k<ans:
        ans=k
print(ans)

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
A=[]
x=[0]*(W+2)
A.append(x)
for i in range(H):
    a=list(map(int,input().split()))
    A.append([0]+a+[0])
A.append(x)
#print(A)

for i in range(H):
    b=list(map(int,input().split()))
    for j in range(W):
        A[i+1][j+1] = abs(A[i+1][j+1]-b[j])
        
#print(A)

L=[[{} for i in range(W+2)] for j in range(H+2)]
L[1][1][A[1][1]]=1
L[1][1][-A[1][1]]=1
#print(L)
#print(L[0][0])
for i in range(1,H+1):
    for j in range(1,W+1):
        for x,y in L[i][j].items():
            #print(x+A[i][j+1])
            if abs(x+A[i][j+1]) not in L[i][j+1] and abs(x+A[i][j+1])<=2000:
                L[i][j+1][abs(x+A[i][j+1])]=1
            if abs(x-A[i][j+1]) not in L[i][j+1] and abs(x-A[i][j+1])<=2000:
                L[i][j+1][abs(x-A[i][j+1])]=1
            if abs(x+A[i+1][j]) not in L[i+1][j] and abs(x+A[i+1][j])<=2000:
                L[i+1][j][abs(x+A[i+1][j])]=1
            if abs(x-A[i+1][j]) not in L[i+1][j] and abs(x-A[i+1][j])<=2000:
                L[i+1][j][abs(x-A[i+1][j])]=1
#print(L)

ans=10**5
for k,v in L[H][W].items():
    if abs(k)<ans:
        ans=abs(k)
print(ans)

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
A=[]
x=[0]*(W+2)
A.append(x)
for i in range(H):
    a=list(map(int,input().split()))
    A.append([0]+a+[0])
A.append(x)
#print(A)

for i in range(H):
    b=list(map(int,input().split()))
    for j in range(W):
        A[i+1][j+1] = abs(A[i+1][j+1]-b[j])
        
#print(A)

L=[[{} for i in range(W+2)] for j in range(H+2)]
L[1][1][A[1][1]]=1
L[1][1][-A[1][1]]=1
#print(L)
#print(L[0][0])
for i in range(1,H+1):
    for j in range(1,W+1):
        for x,y in L[i][j].items():
            #print(x+A[i][j+1])
            if abs(x+A[i][j+1]) not in L[i][j+1] and abs(x+A[i][j+1])<=1000:
                L[i][j+1][abs(x+A[i][j+1])]=1
            if abs(x-A[i][j+1]) not in L[i][j+1] and abs(x-A[i][j+1])<=1000:
                L[i][j+1][abs(x-A[i][j+1])]=1
            if abs(x+A[i+1][j]) not in L[i+1][j] and abs(x+A[i+1][j])<=1000:
                L[i+1][j][abs(x+A[i+1][j])]=1
            if abs(x-A[i+1][j]) not in L[i+1][j] and abs(x-A[i+1][j])<=1000:
                L[i+1][j][abs(x-A[i+1][j])]=1
#print(L)

ans=10**5
for k,v in L[H][W].items():
    if abs(k)<ans:
        ans=abs(k)
print(ans)

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
A=[]
x=[0]*(W+2)
A.append(x)
for i in range(H):
    a=list(map(int,input().split()))
    A.append([0]+a+[0])
A.append(x)
#print(A)

for i in range(H):
    b=list(map(int,input().split()))
    for j in range(W):
        A[i+1][j+1] = abs(A[i+1][j+1]-b[j])
        
#print(A)

L=[[{} for i in range(W+2)] for j in range(H+2)]
L[1][1][A[1][1]]=1
L[1][1][-A[1][1]]=1
#print(L)
#print(L[0][0])
for i in range(1,H+1):
    for j in range(1,W+1):
        for x,y in L[i][j].items():
            #print(x+A[i][j+1])
            if x+A[i][j+1] not in L[i][j+1] and abs(x+A[i][j+1])<=640:
                L[i][j+1][x+A[i][j+1]]=1
            if x-A[i][j+1] not in L[i][j+1] and abs(x-A[i][j+1])<=640:
                L[i][j+1][x-A[i][j+1]]=1
            if x+A[i+1][j] not in L[i+1][j] and abs(x+A[i+1][j])<=640:
                L[i+1][j][x+A[i+1][j]]=1
            if x-A[i+1][j] not in L[i+1][j] and abs(x-A[i+1][j])<=640:
                L[i+1][j][x-A[i+1][j]]=1
#print(L)

ans=10**5
for k,v in L[H][W].items():
    if abs(k)<ans:
        ans=abs(k)
print(ans)

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
A=[]
x=[0]*(W+2)
A.append(x)
for i in range(H):
    a=list(map(int,input().split()))
    A.append([0]+a+[0])
A.append(x)
#print(A)

for i in range(H):
    b=list(map(int,input().split()))
    for j in range(W):
        A[i+1][j+1] = abs(A[i+1][j+1]-b[j])
        
#print(A)

L=[[{} for i in range(W+2)] for j in range(H+2)]
L[1][1][A[1][1]]=1
L[1][1][-A[1][1]]=1
#print(L)
#print(L[0][0])
for i in range(1,H+1):
    for j in range(1,W+1):
        for x,y in L[i][j].items():
            #print(x+A[i][j+1])
            if x+A[i][j+1] not in L[i][j+1] and abs(x+A[i][j+1])<=320:
                L[i][j+1][x+A[i][j+1]]=1
            if x-A[i][j+1] not in L[i][j+1] and abs(x-A[i][j+1])<=320:
                L[i][j+1][x-A[i][j+1]]=1
            if x+A[i+1][j] not in L[i+1][j] and abs(x+A[i+1][j])<=320:
                L[i+1][j][x+A[i+1][j]]=1
            if x-A[i+1][j] not in L[i+1][j] and abs(x-A[i+1][j])<=320:
                L[i+1][j][x-A[i+1][j]]=1
#print(L)

ans=10**5
for k,v in L[H][W].items():
    if abs(k)<ans:
        ans=abs(k)
print(ans)

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
A=[]
x=[0]*(W+2)
A.append(x)
for i in range(H):
    a=list(map(int,input().split()))
    A.append([0]+a+[0])
A.append(x)
#print(A)

for i in range(H):
    b=list(map(int,input().split()))
    for j in range(W):
        A[i+1][j+1] = abs(A[i+1][j+1]-b[j])
        
#print(A)

L=[[{} for i in range(W+2)] for j in range(H+2)]
L[1][1][A[1][1]]=1
L[1][1][-A[1][1]]=1
#print(L)
#print(L[0][0])
for i in range(1,H+1):
    for j in range(1,W+1):
        for x,y in L[i][j].items():
            #print(x+A[i][j+1])
            if x+A[i][j+1] not in L[i][j+1] and abs(x+A[i][j+1])<=160:
                L[i][j+1][x+A[i][j+1]]=1
            if x-A[i][j+1] not in L[i][j+1] and abs(x-A[i][j+1])<=160:
                L[i][j+1][x-A[i][j+1]]=1
            if x+A[i+1][j] not in L[i+1][j] and abs(x+A[i+1][j])<=160:
                L[i+1][j][x+A[i+1][j]]=1
            if x-A[i+1][j] not in L[i+1][j] and abs(x-A[i+1][j])<=160:
                L[i+1][j][x-A[i+1][j]]=1
#print(L)

ans=10**5
for k,v in L[H][W].items():
    if abs(k)<ans:
        ans=abs(k)
print(ans)

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
A=[]
x=[0]*(W+2)
A.append(x)
for i in range(H):
    a=list(map(int,input().split()))
    A.append([0]+a+[0])
A.append(x)
#print(A)

for i in range(H):
    b=list(map(int,input().split()))
    for j in range(W):
        A[i+1][j+1] = abs(A[i+1][j+1]-b[j])
        
#print(A)

L=[[{} for i in range(W+2)] for j in range(H+2)]
L[1][1][A[1][1]]=1
L[1][1][-A[1][1]]=1
#print(L)
#print(L[0][0])
for i in range(1,H+1):
    for j in range(1,W+1):
        for x,y in L[i][j].items():
            #print(x+A[i][j+1])
            if x+A[i][j+1] not in L[i][j+1] and abs(x+A[i][j+1])<=80:
                L[i][j+1][x+A[i][j+1]]=1
            if x-A[i][j+1] not in L[i][j+1] and abs(x-A[i][j+1])<=80:
                L[i][j+1][x-A[i][j+1]]=1
            if x+A[i+1][j] not in L[i+1][j] and abs(x+A[i+1][j])<=80:
                L[i+1][j][x+A[i+1][j]]=1
            if x-A[i+1][j] not in L[i+1][j] and abs(x-A[i+1][j])<=80:
                L[i+1][j][x-A[i+1][j]]=1
#print(L)

ans=10**5
for k,v in L[H][W].items():
    if abs(k)<ans:
        ans=abs(k)
print(ans)

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
A=[]
x=[0]*(W+2)
A.append(x)
for i in range(H):
    a=list(map(int,input().split()))
    A.append([0]+a+[0])
A.append(x)
#print(A)

for i in range(H):
    b=list(map(int,input().split()))
    for j in range(W):
        A[i+1][j+1] = abs(A[i+1][j+1]-b[j])
        
#print(A)

L=[[{} for i in range(W+2)] for j in range(H+2)]
L[1][1][A[1][1]]=1
L[1][1][-A[1][1]]=1
#print(L)
#print(L[0][0])
for i in range(1,H+1):
    for j in range(1,W+1):
        for x,y in L[i][j].items():
            #print(x+A[i][j+1])
            if x+A[i][j+1] not in L[i][j+1] and abs(x+A[i][j+1])<=80:
                L[i][j+1][x+A[i][j+1]]=1
            if x-A[i][j+1] not in L[i][j+1] and abs(x-A[i][j+1])<=80:
                L[i][j+1][x-A[i][j+1]]=1
            if x+A[i+1][j] not in L[i+1][j] and abs(x+A[i+1][j])<=80:
                L[i+1][j][x+A[i+1][j]]=1
            if x-A[i+1][j] not in L[i+1][j] and abs(x-A[i+1][j])<=80:
                L[i+1][j][x-A[i+1][j]]=1
print(L)

ans=10**5
for k,v in L[H][W].items():
    if abs(k)<ans:
        ans=abs(k)
print(ans)

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
A=[]
x=[0]*(W+2)
A.append(x)
for i in range(H):
    a=list(map(int,input().split()))
    A.append([0]+a+[0])
A.append(x)
#print(A)

for i in range(H):
    b=list(map(int,input().split()))
    for j in range(W):
        A[i+1][j+1] = abs(A[i+1][j+1]-b[j])
        
#print(A)

L=[[{} for i in range(W+2)] for j in range(H+2)]
L[0][0][0]=1
#print(L)
#print(L[0][0])
for i in range(H+1):
    for j in range(W+1):
        for x,y in L[i][j].items():
            #print(x+A[i][j+1])
            if x+A[i][j+1] not in L[i][j+1]:
                L[i][j+1][x+A[i][j+1]]=1
            if x-A[i][j+1] not in L[i][j+1]:
                L[i][j+1][x-A[i][j+1]]=1
            if x+A[i+1][j] not in L[i+1][j]:
                L[i+1][j][x+A[i+1][j]]=1
            if x-A[i+1][j] not in L[i+1][j]:
                L[i+1][j][x-A[i+1][j]]=1
#print(L)

ans=10**5
for k,v in L[H][W].items():
    if abs(k)<ans:
        ans=abs(k)
print(ans)

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
A=[]
x=[0]*(W+2)
A.append(x)
for i in range(H):
    a=list(map(int,input().split()))
    A.append([0]+a+[0])
A.append(x)
#print(A)

for i in range(H):
    b=list(map(int,input().split()))
    for j in range(W):
        A[i+1][j+1] = abs(A[i+1][j+1]-b[j])
        
#print(A)

L=[[{} for i in range(W+2)] for j in range(H+2)]
L[0][0][0]=1
#print(L)
#print(L[0][0])
for i in range(H+1):
    for j in range(W+1):
        for x in L[i][j].keys():
            #print(x+A[i][j+1])
            if x+A[i][j+1] not in L[i][j+1]:
                L[i][j+1][x+A[i][j+1]]=1
            if x-A[i][j+1] not in L[i][j+1]:
                L[i][j+1][x-A[i][j+1]]=1
            if x+A[i+1][j] not in L[i+1][j]:
                L[i+1][j][x+A[i+1][j]]=1
            if x-A[i+1][j] not in L[i+1][j]:
                L[i+1][j][x-A[i+1][j]]=1
#print(L)

ans=10**5
for k,v in L[H][W].items():
    if abs(k)<ans:
        ans=abs(k)
print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
a = [[0 for j in range(m)] for i in range(n)]
for i in range(n):
  ai = list(map(int, input().split()))
  for j in range(m):
     a[i][j] += ai[j]
for i in range(n):
  bi = list(map(int, input().split()))
  for j in range(m):
     a[i][j] = abs(a[i][j] - bi[j])
      
v = 240
dp = [[[False for j in range(m)] for i in range(n)] for k in range(v)]
dp[a[0][0]][0][0] = True
for i in range(1,n):
  for k in range(v):
    dp[k][i][0] |= dp[abs(k - a[i][0])][i-1][0]
    if k + a[i][0] < v:
      dp[k][i][0] |= dp[k + a[i][0]][i-1][0]

for j in range(1,m):
  for k in range(v):
    dp[k][0][j] |= dp[abs(k - a[0][j])][0][j-1]
    if k + a[0][j] < v:
      dp[k][0][j] |= dp[k + a[0][j]][0][j-1]

for i in range(1,n):
  for j in range(1,m):
    for k in range(v):
      dp[k][i][j] |= dp[abs(k - a[i][j-1])][i][j-1]
      dp[k][i][j] |= dp[abs(k - a[i-1][j])][i-1][j]
      if k + a[i][j] < v:
        dp[k][i][j] |= dp[k + a[i][j]][i][j-1]
        dp[k][i][j] |= dp[k + a[i][j]][i-1][j]

for k in range(v):
  if dp[k][n-1][m-1]:
    print(k)
    break

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
a = [[0 for j in range(m)] for i in range(n)]
for i in range(n):
  ai = list(map(int, input().split()))
  for j in range(m):
     a[i][j] += ai[j]
for i in range(n):
  bi = list(map(int, input().split()))
  for j in range(m):
     a[i][j] = abs(a[i][j] - bi[j])
      
v = 160
dp = [[[False for j in range(m)] for i in range(n)] for k in range(v)]
dp[a[0][0]][0][0] = True
for i in range(1,n):
  for k in range(v):
    dp[k][i][0] |= dp[abs(k - a[i][0])][i-1][0]
    if k + a[i][0] < v:
      dp[k][i][0] |= dp[k + a[i][0]][i-1][0]

for j in range(1,m):
  for k in range(v):
    dp[k][0][j] |= dp[abs(k - a[0][j])][0][j-1]
    if k + a[0][j] < v:
      dp[k][0][j] |= dp[k + a[0][j]][0][j-1]

for i in range(1,n):
  for j in range(1,m):
    for k in range(v):
      dp[k][i][j] |= dp[abs(k - a[i][j-1])][i][j-1]
      dp[k][i][j] |= dp[abs(k - a[i-1][j])][i-1][j]
      if k + a[i][j] < v:
        dp[k][i][j] |= dp[k + a[i][j]][i][j-1]
        dp[k][i][j] |= dp[k + a[i][j]][i-1][j]

for k in range(v):
  if dp[k][n-1][m-1]:
    print(k)
    break

Submission status: Wrong Answer

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

A = [list(map(int, input().split())) for _ in range(H)]
B = [list(map(int, input().split())) for _ in range(H)]
Diff = [[0] * (W + 1) for _ in range(H + 1)]
M = 0
for i in range(H):
    for j in range(W):
        m = abs(A[i][j] - B[i][j])
        Diff[i][j] = m
        M += m

dp = [[0] * (W + 1) for _ in range(H + 1)]
dp[0][0] |= (1 << Diff[i][j])

for i in range(0, H):
    for j in range(0, W):
        dp[i + 1][j] |= (dp[i][j] << Diff[i][j])
        dp[i + 1][j] |= (dp[i][j] >> Diff[i][j])
        dp[i][j + 1] |= (dp[i][j] << Diff[i][j])
        dp[i][j + 1] |= (dp[i][j] >> Diff[i][j])

a = dp[H - 1][W - 1]
ans = 0
for k in range(M + 1):
    if (a >> k) & 1:
        ans = k
        break

print(k)

Submission status: Wrong Answer

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

A = [list(map(int, input().split())) for _ in range(H)]
B = [list(map(int, input().split())) for _ in range(H)]
Diff = [[0] * (W + 1) for _ in range(H + 1)]
for i in range(H):
    for j in range(W):
        Diff[i][j] = abs(A[i][j] - B[i][j])

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

for i in range(0, H):
    for j in range(0, W):
        for k in range(161):
            if dp[i][j][k]:
                if k + Diff[i + 1][j] <= 160:
                    dp[i + 1][j][k + Diff[i + 1][j]] = 1
                dp[i + 1][j][abs(k - Diff[i + 1][j])] = 1
                if k + Diff[i][j + 1] <= 160:
                    dp[i][j + 1][k + Diff[i][j + 1]] = 1
                dp[i][j + 1][abs(k - Diff[i][j + 1])] = 1

for k in range(161):
    if dp[H - 1][W - 1][k] == 1:
        ans = k
        break

print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(H, W, A, B):
    M = [[a-b for a, b in zip(ar, br)] for ar, br in zip(A, B)]

    dp = [[set() for _ in range(W)] for __ in range(H)]
    dp[0][0].add(M[0][0])
    for i in range(H):
        for j in range(W):
            for k, l in [(-1, 0), (0, -1)]:
                for v in dp[i+k][j+l]:
                    dp[i][j].add(abs(v+M[i][j]))
                    # dp[i][j].add(v-M[i][j])
    # for r in M:
    #     print(r)

    # for r in dp:
    #     print(r)

    return min(map(abs, dp[H-1][W-1]))


def main():
    H, W = read_int_n()
    A = [read_int_n() for _ in range(H)]
    B = [read_int_n() for _ in range(H)]
    print(slv(H, W, A, B))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(H, W, A, B):
    M = [[a-b for a, b in zip(ar, br)] for ar, br in zip(A, B)]

    dp = [[set() for _ in range(W)] for __ in range(H)]
    dp[0][0].add(M[0][0])
    for i in range(H):
        for j in range(W):
            for k, l in [(-1, 0), (0, -1)]:
                for v in dp[i+k][j+l]:
                    dp[i][j].add(v+M[i][j])
                    # dp[i][j].add(v-M[i][j])
    # for r in M:
    #     print(r)

    # for r in dp:
    #     print(r)

    return min(map(abs, dp[H-1][W-1]))


def main():
    H, W = read_int_n()
    A = [read_int_n() for _ in range(H)]
    B = [read_int_n() for _ in range(H)]
    print(slv(H, W, A, B))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np
HW = list(map(int, input().split()))
H = HW[0]
W = HW[1]
A = np.empty((H, W), dtype=np.int64)
B = np.empty((H, W), dtype=np.int64)
for i in range(H):
  A[i] = np.fromstring(input(), dtype = np.int64, sep = ' ')
for i in range(H):
  B[i] = np.fromstring(input(), dtype = np.int64, sep = ' ')

C = np.abs(A - B)
D = np.full((H, W), 0, dtype=int)
D[0][0] = (2**C[0][0])

for i in range(0, H):
  for j in range(0, W):
    t1 = 0
    t2 = 0
    if i > 0:
      t1 = (D[i-1][j] >> C[i][j])|(D[i-1][j] << C[i][j])
    if j > 0:
      t2 = (D[i][j-1] >> C[i][j])|(D[i][j-1] << C[i][j])
    D[i][j] = D[i][j] | t1 | t2

res = format(D[H-1][W-1], 'b')
print(len(res) - res.rfind('1') - 1)

Submission status: Wrong Answer

Solution code:
import numpy as np
HW = list(map(int, input().split()))
H = HW[0]
W = HW[1]
A = np.empty((H, W), dtype=np.int64)
B = np.empty((H, W), dtype=np.int64)
for i in range(H):
  A[i] = np.fromstring(input(), dtype = np.int64, sep = ' ')
for i in range(H):
  B[i] = np.fromstring(input(), dtype = np.int64, sep = ' ')

C = np.abs(A - B)
D = np.full((H, W), 0, dtype=int)
D[0][0] = (2**C[0][0])

for i in range(0, H):
  for j in range(0, W):
    if i > 0:
      D[i][j] = (D[i-1][j] >> C[i][j])|(D[i-1][j] << C[i][j])
    if j > 0:
      D[i][j] = (D[i][j-1] >> C[i][j])|(D[i][j-1] << C[i][j])

res = format(D[H-1][W-1], 'b')
print(len(res) - res.rfind('1') - 1)

Submission status: Wrong Answer

Solution code:
import numpy as np
H, W = map(int, input().split())
As = []
Bs = []
for i in range(H):
	As.append(list(map(int, input().split())))
for i in range(H):
	Bs.append(list(map(int, input().split())))
As = np.array(As)
Bs = np.array(Bs)
absolute = abs(As - Bs)

val = []
for h in range(H):

	for w in range(W):

		if h == 0 and w == 0:
			val.append(absolute[h][w])

		if h == H - 1 and w == W - 1:
			break

		for j in range(len(val)):
			v = val.pop(0)
			print(v)
			if w == W - 1 and h != H - 1:
				nextDis = absolute[h+1][w]
				val.append(v + nextDis)
				val.append(abs(v - nextDis))
			elif h == H - 1 and w != W - 1:
				nextDis = absolute[h][w+1]
				val.append(v + nextDis)
				val.append(abs(v - nextDis))
			else:
				nextDis = absolute[h+1][w]
				val.append(v + nextDis)
				val.append(abs(v - nextDis))
				nextDis = absolute[h][w+1]
				val.append(v + nextDis)
				val.append(abs(v - nextDis))
else:
	print("Ans", min(val))

Submission status: Wrong Answer

Solution code:
import numpy as np
H, W = map(int, input().split())
As = []
Bs = []
for i in range(H):
	As.append(list(map(int, input().split())))
for i in range(H):
	Bs.append(list(map(int, input().split())))
As = np.array(As)
Bs = np.array(Bs)
absolute = abs(As - Bs)

val = []
DP = [[[False] * (1+80*(W+H-1)) for w in range(W)] for h in range(H)]
for h in range(H):

	for w in range(W):

		if h == 0 and w == 0:
			DP[h][w][absolute[h][w]] = True
			val.append(absolute[h][w])

		for j in range(len(val)):
			v = val.pop(0)
			print(v)
			if w == W - 1 and h != H - 1:
				nextDis = absolute[h+1][w]
				DP[h+1][w][v + nextDis] = True 
				DP[h+1][w][abs(v - nextDis)] = True
				val.append(v + nextDis)
				val.append(abs(v - nextDis))
			elif h == H - 1 and w != W - 1:
				nextDis = absolute[h][w+1]
				DP[h][w+1][v + nextDis] = True 
				DP[h][w+1][abs(v - nextDis)] = True
				val.append(v + nextDis)
				val.append(abs(v - nextDis))
			elif h == H - 1 and w == W - 1:
				continue
			else:
				nextDis = absolute[h+1][w]
				DP[h+1][w][v + nextDis] = True 
				DP[h+1][w][abs(v - nextDis)] = True
				val.append(v + nextDis)
				val.append(abs(v - nextDis))
				nextDis = absolute[h][w+1]
				DP[h][w+1][v + nextDis] = True 
				DP[h][w+1][abs(v - nextDis)] = True
				val.append(v + nextDis)
				val.append(abs(v - nextDis))
else:
	print("Ans", DP[H - 1][W - 1].index(True))

Submission status: Wrong Answer

Solution code:
def solve():
    from sys import stdin
    f_i = stdin
    
    H, W = map(int, f_i.readline().split())
    A = tuple(tuple(map(int, f_i.readline().split())) for i in range(H))
    B = tuple(tuple(map(int, f_i.readline().split())) for i in range(H))
    
    dp1 = [set() for i in range(W)]
    dp1[0].add(0)
    for A_i, B_i in zip(A, B):
        dp2 = [set() for i in range(W)]
        diff = A_i[0] - B_i[0]
        for pre_bias in dp1[0]:
            bias = pre_bias + diff
            if -320 <= bias <= 320:
                dp2[0].add(bias)
            bias = pre_bias - diff
            if -320 <= bias <= 320:
                dp2[0].add(bias)
        for j, t in enumerate(zip(A_i[1:], B_i[1:]), start=1):
            A_ij, B_ij = t
            diff = A_ij - B_ij
            for pre_bias in dp1[j]:
                bias = pre_bias + diff
                if -320 <= bias <= 320:
                    dp2[j].add(bias)
                bias = pre_bias - diff
                if -320 <= bias <= 320:
                    dp2[j].add(bias)
            for pre_bias in dp2[j-1]:
                bias = pre_bias + diff
                if -320 <= bias <= 320:
                    dp2[j].add(bias)
                bias = pre_bias - diff
                if -320 <= bias <= 320:
                    dp2[j].add(bias)
        dp1 = dp2
    
    ans = min(abs(x) for x in dp2[-1])
    print(ans)

solve()

Submission status: Wrong Answer

Solution code:
def solve():
    from sys import stdin
    f_i = stdin
    
    H, W = map(int, f_i.readline().split())
    A = tuple(tuple(map(int, f_i.readline().split())) for i in range(H))
    B = tuple(tuple(map(int, f_i.readline().split())) for i in range(H))
    
    dp1 = [set() for i in range(W)]
    dp1[0].add(0)
    for A_i, B_i in zip(A, B):
        dp2 = [set() for i in range(W)]
        diff = A_i[0] - B_i[0]
        for pre_bias in dp1[0]:
            bias = pre_bias + diff
            if -160 <= bias <= 160:
                dp2[0].add(bias)
            bias = pre_bias - diff
            if -160 <= bias <= 160:
                dp2[0].add(bias)
        for j, t in enumerate(zip(A_i[1:], B_i[1:]), start=1):
            A_ij, B_ij = t
            diff = A_ij - B_ij
            for pre_bias in dp1[j]:
                bias = pre_bias + diff
                if -160 <= bias <= 160:
                    dp2[j].add(bias)
                bias = pre_bias - diff
                if -160 <= bias <= 160:
                    dp2[j].add(bias)
            for pre_bias in dp2[j-1]:
                bias = pre_bias + diff
                if -160 <= bias <= 160:
                    dp2[j].add(bias)
                bias = pre_bias - diff
                if -160 <= bias <= 160:
                    dp2[j].add(bias)
        dp1 = dp2
    
    ans = min(abs(x) for x in dp2[-1])
    print(ans)

solve()

Submission status: Wrong Answer

Solution code:
def solve():
    from sys import stdin
    f_i = stdin
    
    H, W = map(int, f_i.readline().split())
    A = tuple(tuple(map(int, f_i.readline().split())) for i in range(H))
    B = tuple(tuple(map(int, f_i.readline().split())) for i in range(H))
    
    dp1 = [set() for i in range(W)]
    dp1[0].add(0)
    for A_i, B_i in zip(A, B):
        dp2 = [set() for i in range(W)]
        diff = A_i[0] - B_i[0]
        for pre_bias in dp1[0]:
            bias = pre_bias + diff
            if -80 <= bias <= 80:
                dp2[0].add(bias)
            bias = pre_bias - diff
            if -80 <= bias <= 80:
                dp2[0].add(bias)
        for j, t in enumerate(zip(A_i[1:], B_i[1:]), start=1):
            A_ij, B_ij = t
            diff = A_ij - B_ij
            for pre_bias in dp1[j]:
                bias = pre_bias + diff
                if -80 <= bias <= 80:
                    dp2[j].add(bias)
                bias = pre_bias - diff
                if -80 <= bias <= 80:
                    dp2[j].add(bias)
            for pre_bias in dp2[j-1]:
                bias = pre_bias + diff
                if -80 <= bias <= 80:
                    dp2[j].add(bias)
                bias = pre_bias - diff
                if -80 <= bias <= 80:
                    dp2[j].add(bias)
        dp1 = dp2
    
    ans = min(abs(x) for x in dp2[-1])
    print(ans)

solve()

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    h,w = LI()
    a = [LI() for _ in range(h)]
    b = [LI() for _ in range(h)]
    c = [[abs(a[i][j]-b[i][j]) for j in range(w)] for i in range(h)]

    r = [[set() for j in range(w)] for i in range(h)]
    r[0][0].add(c[0][0])
    ma = 40*80
    for i in range(h):
        for j in range(w):
            s = r[i][j]
            t = c[i][j]
            if i > 0:
                for k in r[i-1][j]:
                    if k < ma:
                        s.add(k+t)
                    if k > -ma:
                        s.add(k-t)
            if j > 0:
                for k in r[i][j-1]:
                    if k < ma:
                        s.add(k+t)
                    if k > -ma:
                        s.add(k-t)

    return min(map(abs, r[-1][-1]))


print(main())

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys

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)

D=[(1,0),(0,1)]

for r in range(H):
    for c in range(W):
        for dr,dc in D: #横に1つ移動か、下に1つ移動
            if r+dr<H and c+dc<W:   #移動しようとするマスが存在するならばif文内の処理を行う
                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)

print 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 <= 500}

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