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:
import sys
def input():
    return sys.stdin.readline()[:-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)]
d=[[0 for i in range(w)] for j in range(h)]
maxd=1
for i in range(h):
    for j in range(w):
        d[i][j] = abs(a[i][j]-b[i][j])
        maxd=max(maxd,d[i][j])
dp=[[0 for j in range(w)] for k in range(h)]
c=20000
dp[0][0] |= 1 << c+d[0][0]
for i in range(h):
    for j in range(w):
        if i+1<h:
            dp[i+1][j] |= dp[i][j] << d[i+1][j]
            dp[i+1][j] |= dp[i][j] >> d[i+1][j]
        if j+1<w:
            dp[i][j+1] |= dp[i][j] << d[i][j+1]
            dp[i][j+1] |= dp[i][j] >> d[i][j+1]
m=1000000
cnt = 0
for x in bin(dp[h-1][w-1])[2:][::-1]:
    m=min(m,abs(cnt-c))
    cnt+=1
print(m)

Submission status: Wrong Answer

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

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

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

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

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

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

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

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

Submission status: Wrong Answer

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

A = []

for i in range(H):

    a = list(map(int,input().split()))
    A.append(a)

B = []

for i in range(H):

    b = list(map(int,input().split()))
    B.append(b)

for i in range(H):
    for j in range(W):

        A[i][j] = abs(A[i][j] - B[i][j])

C = [[[False] * 3201  for i in range(W)] for j in range(H)]


for i in range(H):

    if i == 0:
        C[i][0][A[i][0]] = True
    else:

        for j in range(3201):
            if C[i-1][0][j]:
                if abs(j + A[i][0]) <= 3200:
                    C[i][0] [abs(j + A[i][0])] = True
                C[i][0] [abs(j - A[i][0])] = True

for j in range(W):
    if j == 0:
        continue
    else:
        for i in range(3201):
            if C[0][j-1][i]:
                if abs(i + A[0][j]) <= 3200:
                    C[0][j] [abs(i + A[0][j])] = True
                C[0][j] [abs(i - A[0][j])] = True

#print (C)

for i in range(H-1):
    i += 1

    for j in range(W-1):
        j += 1

        for k in range(3201):

            if C[i-1][j][k]:
                if abs(k + A[i][j]) <= 3200:
                    C[i][j] [abs(k + A[i][j])] = 1   
                C[i][j] [abs(k - A[i][j])] = 1

            if C[i][j-1][k]:                
                if abs(k + A[i][j]) <= 3200:
                    C[i][j] [abs(k + A[i][j])] = 1
                C[i][j] [abs(k - A[i][j])] = 1

#print (C)
ans = float("inf")   
for i in range(3201):

    if C[-1][-1][i]:
        ans = min(ans,i)
    
print (ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

H,W = map(int,input().split())

A = np.array(tuple(tuple(map(int,input().split())) for _ in range(H)))
B = np.array(tuple(tuple(map(int,input().split())) for _ in range(H)))

D = np.abs(A-B)
del A,B

if W > H:
    W,H = H,W
    D = D.T

L = D.max()*(H+W-1)+1
dp0 = np.zeros((W,L), dtype=bool)
dp1 = np.zeros_like(dp0)

dp1[0,D[0,0]] = True
for y in range(H):
    for x,d in enumerate(D[y]):
        dp1[x,d:] |= dp0[x,:L-d]
        dp1[x,:L-d] |= dp0[x,d:]
        dp1[x,:d] |= dp0[x,d:0:-1]
        dp1[x,d:] |= dp1[x-1,:L-d]
        dp1[x,:L-d] |= dp1[x-1,d:]
        dp1[x,:d] |= dp1[x-1,d:0:-1]
    dp0,dp1 = dp1, dp0
    dp1[-1] = False

print(next(i for i,v in enumerate(dp0[-1]) if v))

Submission status: Wrong Answer

Solution code:
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines

#mod=10**9+7
# rstrip().decode('utf-8')
# map(int,input().split())
#import numpy as np

def main():
	h,w=map(int,input().split())
	
	G=[[0]*w for i in range(h)]
	
	for i in range(h):
		A=list(map(int,input().split()))
		for j in range(w):
			G[i][j]+=A[j]
	for i in range(h):
		B = list(map(int, input().split()))
		for j in range(w):
			G[i][j] =abs(G[i][j]-B[j])
	M=(h+w)*80

	
	li=[[[0]*M for i in range(w)] for j in range(h)]

	
	li[0][0][G[0][0]]=1
	for i in range(h):
		for j in range(w):
			for k in range(M):

				if li[i][j][k]==1:
					if i<h-1:
						li[i + 1][j][abs(k - G[i][j])] = 1
						li[i + 1][j][abs(k + G[i][j])] = 1
					if j<w-1:
						li[i][j + 1][abs(k - G[i][j])] = 1
						li[i][j + 1][abs(k + G[i][j])] = 1

	
	for i in range(M):
		if li[h-1][w-1][i]==1:
			print(i-1)
			exit(0)
	
if __name__ == "__main__":
	main()

Submission status: Wrong Answer

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

data = []
for i in range(h):
    d = []
    for j in range(w):
        d.append(data1[i][j]-data2[i][j])
    data.append(d)

y = 3000
dp = [[[False for i in range(y)] for j in range(w)] for k in range(h)]

dp[0][0][abs(data[0][0])] = True

for i in range(h):
    for j in range(w):
        if i == 0 and j == 0:
            continue
        if i > 0:
            for k in range(y):
                if dp[i-1][j][k]:
                    if abs(k - abs(data[i][j])) < y:
                        dp[i][j][abs(k-abs(data[i][j]))] = True
                    if abs(k + abs(data[i][j])) < y:
                        dp[i][j][abs(k+abs(data[i][j]))] = True
        if j > 0:
            for k in range(y):
                if dp[i][j-1][k]:
                    if abs(k - abs(data[i][j])) < y:
                        dp[i][j][abs(k-abs(data[i][j]))] = True
                    if abs(k + abs(data[i][j])) < y:
                        dp[i][j][abs(k+abs(data[i][j]))] = True


for k in range(y):
    if dp[h-1][w-1][k]:
        print(k)
        exit()

Submission status: Wrong Answer

Solution code:
import itertools
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


# int で bitset をします
# https://twitter.com/armeria_betrue/status/1203681298826452993

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

A = np.array(A, dtype=int)
B = np.array(B, dtype=int)
grid = np.abs(A - B)

dp = np.zeros((H, W), dtype=object)
# 下から n ビットめが 1 ならそこまでで絶対値 n を作れる
dp[0][0] = 1 << grid[0][0]
for h, w in itertools.product(range(H), range(W)):
    if h - 1 >= 0:
        dp[h][w] |= dp[h - 1][w] << grid[h][w]
        dp[h][w] |= dp[h - 1][w] >> grid[h][w]
    if w - 1 >= 0:
        dp[h][w] |= dp[h][w - 1] << grid[h][w]
        dp[h][w] |= dp[h][w - 1] >> grid[h][w]

i = 0
n = dp[-1][-1] % (1 << 81)
while True:
    if n & 1:
        print(i)
        break
    n >>= 1
    i += 1

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

h, w = [ int(v) for v in input().split() ]

diff = [[ 0 for i in range(w)] for j in range(h)]
diff2 = [ [ set([]) for i in range(w)] for j in range(h)]
for i in range(h):
    line = [ int(v) for v in input().split() ]
    for j, v in  enumerate(line):
        diff[i][j] = v

for i in range(h):
    line = [ int(v) for v in input().split() ]
    for j, v in  enumerate(line):
        diff[i][j] = abs(v - diff[i][j])

for i in range(h):
    for j in range(w):
        if i == 0:
            if j == 0:
                diff2[0][0].add(diff[i][j])
            else:
                for k in diff2[i][j-1]:
                    
                    if 0 <= k + diff[i][j] <= 320:
                        diff2[i][j].add(k + diff[i][j])
                    if 0 <= abs(diff[i][j] - k) <= 320:
                        diff2[i][j].add(abs(diff[i][j] - k))
        else:
            for k in diff2[i-1][j]:
                if 0 <= k + diff[i][j] <= 320:
                    diff2[i][j].add(k + diff[i][j])
                if 0 <= abs(diff[i][j] - k) <= 320:
                    diff2[i][j].add(abs(diff[i][j] - k))
            
            if j != 0:
                for k in diff2[i][j-1]:
                    if 0 <= k + diff[i][j] <= 320:
                        diff2[i][j].add(k + diff[i][j])
                    if 0 <= abs(diff[i][j] - k) <= 320:
                        diff2[i][j].add(abs(diff[i][j] - k))

print(min(list(diff2[-1][-1])))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
#ABC147 E

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

h,w = LI()
a = [LI() for _ in range(h)]
b = [LI() for _ in range(h)]

ans = inf
for i in range(2):
    dp1 = [[inf]*w for _ in range(h)] #赤
    dp2 = [[inf]*w for _ in range(h)] #青
    if i == 0:
        dp1[0][0] = a[0][0]
        dp2[0][0] = b[0][0]
    else:
        dp1[0][0] = b[0][0]
        dp2[0][0] = a[0][0]
    for i in range(h):
        for j in range(w):
            if i+1 < h:
                s = dp1[i][j] + a[i+1][j]
                t = dp1[i][j] + b[i+1][j]
                u = dp2[i][j] + a[i+1][j]
                v = dp2[i][j] + b[i+1][j]
                if abs(s-v) > abs(t-u):
                    dp1[i+1][j] = min(dp1[i+1][j],dp1[i][j] + b[i+1][j])
                    dp2[i+1][j] = min(dp2[i+1][j],dp2[i][j] + a[i+1][j])
                else:
                    dp1[i+1][j] = min(dp1[i+1][j],dp1[i][j] + a[i+1][j])
                    dp2[i+1][j] = min(dp2[i+1][j],dp2[i][j] + b[i+1][j])
            if j+1 < w: 
                s = dp1[i][j] + a[i][j+1]
                t = dp1[i][j] + b[i][j+1]
                u = dp2[i][j] + a[i][j+1]
                v = dp2[i][j] + b[i][j+1]
                if abs(s-v) > abs(t-u):
                    dp1[i][j+1] = min(dp1[i][j+1],dp1[i][j] + b[i][j+1])
                    dp2[i][j+1] = min(dp2[i][j+1],dp2[i][j] + a[i][j+1])
                else:
                    dp1[i][j+1] = min(dp1[i][j+1],dp1[i][j] + a[i][j+1])
                    dp2[i][j+1] = min(dp2[i][j+1],dp2[i][j] + b[i][j+1])
    ans = min(ans,abs(dp1[-1][-1] - dp2[-1][-1]))
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
H, W = map(int,input().split())

A = np.array([input().split() for _ in range(H)], dtype=int)
B = np.array([input().split() for _ in range(H)], dtype=int)
C = np.abs(A-B)

dp = np.zeros((H,W,1000), dtype=bool) # マス(i,j)までの経路の偏りのとり得る値

dp[0,0,C[0,0]] = True

for h in range(H):
  for w in range(W):
    idx = np.zeros(0, dtype=int)
    if h > 0: idx = np.r_[idx, np.where(dp[h-1,w])[0]]
    if w > 0: idx = np.r_[idx, np.where(dp[h,w-1])[0]]
    idx = np.r_[idx + C[h,w], idx - C[h,w]]
    idx = np.abs(idx)
    idx = np.unique(idx)
    idx = idx[idx < 1000]
    dp[h,w][idx] = True

print(np.where(dp[H-1,W-1])[0].min())

Submission status: Wrong Answer

Solution code:
import sys
import math
import bisect
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop


def LI(): return [int(x) for x in sys.stdin.readline().split()]


def I(): return int(sys.stdin.readline())


def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res


def IR(n):
    return [I() for i in range(n)]


# A
def A():
    a, b, c = LI()
    if a + b + c >= 22:
        print("bust")
    else:
        print("win")
    return


# B
def B():
    s = S()
    ans = 0
    for i in range(len(s) // 2):
        if s[i] != s[-i - 1]:
            ans += 1
    print(ans)
    return


# C
def C():
    n = I()
    res = [[0] * n for i in range(n)]
    ans = 0
    for i in range(n):
        a = I()
        for j in range(a):
            x, y = LI()
            if y == 0:
                res[i][x - 1] = 1
    while (1):
        max_num = 0
        max_ind = -1
        for i in range(n):
            num = 0
            for j in range(n):
                if i == j:
                    num += sum(res[i])
                else:
                    if res[j][i] == 1:
                        num += 1
            if num > max_num:
                max_num = num
                max_ind = i
        if max_ind == -1:
            print(n - ans)
            return
        else:
            ans += 1
            res[max_ind] = [0] * n
            for i in range(n):
                res[i][max_ind] = 0
    return


# D
def D():
    return


# E
def E():
    h, w = LI()
    a = [LI() for i in range(h)]
    b = [LI() for i in range(h)]
    dp = [[[0] * 100 for i in range(w)] for i in range(h)]
    dp[0][0][abs(a[0][0] - b[0][0])] = 1
    for i in range(1, h):
        for num in range(100):
            if dp[i - 1][0][num] == 1:
                if abs(num + abs(a[i][0] - b[i][0])) < 100:
                    dp[i][0][abs(num + abs(a[i][0] - b[i][0]))] = 1
                dp[i][0][abs(num - abs(a[i][0] - b[i][0]))] = 1
    for i in range(1, w):
        for num in range(100):
            if dp[0][i - 1][num] == 1:
                if abs(num + abs(a[0][i] - b[0][i])) < 100:
                    dp[0][i][abs(num + abs(a[0][i] - b[0][i]))] = 1
                dp[0][i][abs(num - abs(a[0][i] - b[0][i]))] = 1
    for i in range(1, h):
        for j in range(1, w):
            for num in range(100):
                if dp[i - 1][j][num] == 1:
                    if abs(num + abs(a[i][j] - b[i][j])) < 100:
                        dp[i][j][abs(num + abs(a[i][j] - b[i][j]))] = 1
                    dp[i][j][abs(num - abs(a[i][j] - b[i][j]))] = 1
                if dp[i][j - 1][num] == 1:
                    if abs(num + abs(a[i][j] - b[i][j])) < 100:
                        dp[i][j][abs(num + abs(a[i][j] - b[i][j]))] = 1
                    dp[i][j][abs(num - abs(a[i][j] - b[i][j]))] = 1
    for i in range(100):
        if dp[h-1][w-1][i] == 1:
            print(i)
            break
    return


# F
def F():
    return

# Solve
if __name__ == "__main__":
    E()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

h, w = [ int(v) for v in input().split() ]

diff = [[ 0 for i in range(w)] for j in range(h)]
diff2 = [ [ set([]) for i in range(w)] for j in range(h)]
for i in range(h):
    line = [ int(v) for v in input().split() ]
    for j, v in  enumerate(line):
        diff[i][j] = v

for i in range(h):
    line = [ int(v) for v in input().split() ]
    for j, v in  enumerate(line):
        diff[i][j] = abs(v - diff[i][j])

for i in range(h):
    for j in range(w):
        if i == 0:
            if j == 0:
                diff2[0][0].add(diff[i][j])
            else:
                for k in diff2[i][j-1]:
                    
                    if 0 <= k + diff[i][j] <= 160:
                        diff2[i][j].add(k + diff[i][j])
                    if 0 <= abs(diff[i][j] - k) <= 160:
                        diff2[i][j].add(abs(diff[i][j] - k))
        else:
            for k in diff2[i-1][j]:
                if 0 <= k + diff[i][j] <= 160:
                    diff2[i][j].add(k + diff[i][j])
                if 0 <= abs(diff[i][j] - k) <= 160:
                    diff2[i][j].add(abs(diff[i][j] - k))
            
            if j != 0:
                for k in diff2[i][j-1]:
                    if 0 <= k + diff[i][j] <= 160:
                        diff2[i][j].add(k + diff[i][j])
                    if 0 <= abs(diff[i][j] - k) <= 160:
                        diff2[i][j].add(abs(diff[i][j] - k))

print(min(list(diff2[-1][-1])))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
H, W = [int(x) for x in input().strip().split()]
A = [[0] * (W+1) for h in range(H+1)]
B = [[0] * (W+1) for h in range(H+1)]
for h in range(H):
    A[h+1] = [0] + [int(x) for x in input().strip().split()]

for h in range(H):
    B[h+1] = [0] + [int(x) for x in input().strip().split()]

MM = [[{} for w in range(W+1)] for h in range(H+1)]
print(A)
print(B)
print(MM)
for w in range(W+1):
    for h in range(H+1):
        if w == 0 or h == 0:
            MM[h][w][0] = 1
            continue
        for a in MM[h-1][w]:
            MM[h][w][a+A[h][w]-B[h][w]] = 1
            MM[h][w][a+B[h][w]-A[h][w]] = 1
        for a in MM[h][w-1]:
            MM[h][w][a+A[h][w]-B[h][w]] = 1
            MM[h][w][a+B[h][w]-A[h][w]] = 1
print(min([abs(key) for key in MM[H][W].keys()]))

Submission status: Wrong Answer

Solution code:
from itertools import product

H, W = map(int, input().split())
grid_A = [list(map(int, input().split())) for _ in range(H)]
grid_B = [list(map(int, input().split())) for _ in range(H)]
diff = []
M = 0
for A, B in zip(grid_A, grid_B):
    temp = [abs(a - b) for a, b in zip(A, B)]
    M = max(max(temp), M)
    diff.append(temp)
dp = [[[False]*((H+W)*(M+1)) for _ in range(W)] for _ in range(H)]
dp[0][0][diff[0][0]] = True
for i, j in product(range(H), range(W)):
    for m in range(M+1):
        if dp[i][j][m]:
            if i + 1 < H:
                d = diff[i+1][j]
                dp[i+1][j][m + d] = True
                dp[i+1][j][abs(m - d)] = True
            if j + 1 < W:
                d = diff[i][j+1]
                dp[i][j+1][m + d] = True
                dp[i][j+1][abs(m - d)] = True
for i in range(M+1):
    if dp[H-1][W-1][i]:
        print(i)
        break

Submission status: Wrong Answer

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

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

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

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

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

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

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

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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline

h, w = map(int, input().split())
grid = [None for _ in range(h)]
poss = [[set() for x in range(w)] for y in range(h)]
tmp = [map(int, input().split()) for _ in range(h * 2)]
for i, (l1, l2) in enumerate(zip(tmp, tmp[h:])):
	grid[i] = [abs(x - y) for x, y in zip(l1, l2)]
poss[0][0].add(-grid[0][0])
poss[0][0].add(grid[0][0])
for i in range(h):
	for j, m in enumerate(grid[i][:-1]):
		for c in poss[i][j]:
			poss[i][j + 1].add(c - m)
			poss[i][j + 1].add(c + m)
	if i == h - 1:
		break
	for j, m in enumerate(grid[i + 1]):
		for c in poss[i][j]:
			poss[i + 1][j].add(c - m)
			poss[i + 1][j].add(c + m)
print(min(abs(x) for x in poss[-1][-1]))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

def main():
    H, W = map(int, input().split())
    P = W+1
    A = [list(map(int, input().split())) for _ in range(H)]
    B = [list(map(int, input().split())) for _ in range(H)]
    L = 80*80*4
    mid = L//2
    dp = [[False]*(L+1) for _ in range((W+1)*(H+1))]
    for h in range(H+1):
        dp[h*P][mid] = True
    for w in range(H+1):
        dp[w][mid] = True
    
    for l in range(L+1):
        for h in range(H):
            for w in range(W):
                c = A[h][w] - B[h][w]
                if 0 <= l-c <= L:
                    dp[(h+1)*P+w+1][l] = dp[h*P+w+1][l-c] or dp[(h+1)*P+w][l-c]
                if 0 <= l+c <= L:
                    dp[(h+1)*P+w+1][l] = dp[(h+1)*P+w+1][l] or dp[h*P+w+1][l+c] or dp[(h+1)*P+w][l+c]
    ans = 10**9
    for l in range(L+1):
        if dp[H*P+W][l]:
            ans = min(abs(l-mid), ans)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

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

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

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

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

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

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

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

Submission status: Wrong Answer

Solution code:
import bisect
import collections
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)]

q = collections.deque()

C = [[abs(A[i][j] - B[i][j]) for j in range(W)] for i in range(H)]
M = 0
for i in range(H):
    for j in range(W):
        M = max(C[i][j], M)

dp = [[[False]*((M*(H+W)) + 1) for j in range(W)] for i in range(H)]

for i in range(H):
    for j in range(W):
        if i == 0:
            if j == 0:
                dp[i][j][C[i][j]] = True
            else:
                for m in range(M+1):
                    if dp[i][j-1][m]:
                        dp[i][j][abs(m - C[i][j])] = True
                        dp[i][j][m+C[i][j]] = True

        else:
            if j != 0:
                for m in range(M+1):
                    if dp[i][j-1][m]:
                        dp[i][j][abs(m - C[i][j])] = True
                        dp[i][j][m+C[i][j]] = True

            for m in range(M+1):
                if dp[i-1][j][m]:
                    dp[i][j][abs(m - C[i][j])] = True
                    dp[i][j][m+C[i][j]] = True
for i in range((M*(H+W))+1):
    if dp[H-1][W-1][i]:
        print(i)
        break

Submission status: Wrong Answer

Solution code:
H, W=map(int, input().split())
maxK=81
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=[[[0 for _ in range(maxK+1)] for _ in range(W+1)] for _ in range(H+1)]
dp[1][1][C[0][0]]=1
for i in range(1, H+1):
    for j in range(1, W+1):
        for k in range(maxK):
            if dp[i-1][j][k]==1 or dp[i][j-1][k]==1:
                k_candidate1, k_candidate2=abs(k-C[i-1][j-1]), abs(k+C[i-1][j-1])
                if k_candidate1<maxK:
                    dp[i][j][k_candidate1]=1
                if k_candidate2<maxK:
                    dp[i][j][k_candidate2]=1
for k in range(maxK):
    if dp[H][W][k]==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)]

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

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

        diff = abs(A[h][w] - B[h][w])

        for c in pv:
            if c < (H + W) * 80:
                dp[h][w].add(c + diff)
                dp[h][w].add(abs(c - diff))
print(min(dp[H - 1][W - 1]))

Submission status: Wrong Answer

Solution code:
from itertools import chain

H,W = map(int,input().split())

A = tuple(tuple(map(int,input().split())) for _ in range(H))
B = tuple(tuple(map(int,input().split())) for _ in range(H))

dp = {(0,0) : {(A[0][0]-B[0][0])%200, (B[0][0]-A[0][0])%200}}


for t in range(1,H+W-1):
    ndp = dict()
    for x in range(max(0,t-H+1), min(t+1,W)):
        y = t-x
        d = A[y][x]-B[y][x]
        if x > 0 and y > 0:
            ns = set(k%200 for k in chain((v+d for v in dp[(x-1,y)]),
                            (v-d for v in dp[(x-1,y)]),
                            (v+d for v in dp[(x,y-1)]),
                            (v-d for v in dp[(x,y-1)]),))
        elif x > 0:
            ns = set(k%200 for k in chain((v+d for v in dp[(x-1,y)]),
                            (v-d for v in dp[(x-1,y)]),))
        elif y > 0:
            ns = set(k%200 for k in chain((v+d for v in dp[(x,y-1)]),
                            (v-d for v in dp[(x,y-1)]),))
        else:
            ns = set()

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

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

Submission status: Wrong Answer

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

nums = []
for i in range(2):

    rows = []
    for j in range(h):
        rows.append([int(k) for k in input().split()])
    nums.append(rows)

a = nums[0]
b = nums[1]

table = []
for hi in range(h):

    rows = []
    for wi in range(w):
        rows.append(tuple([a[hi][wi], b[hi][wi]]))
    table.append(rows)


current = [0, 0]
diff = 0


def get_diff_of_cell(x, y):
    cell = table[x][y]
    return abs(cell[0] - cell[1])


def calc_diff(diff_of_cell):
    return (-1 if diff >= 0 else 1) * diff_of_cell


while current != [h - 1, w - 1]:

    right = get_diff_of_cell(current[0], current[1] + 1) if current[1] < w - 1 else float("inf")
    down = get_diff_of_cell(current[0] + 1, current[1]) if current[0] < h - 1 else float("inf")

    if right < down:
        current[1] += 1
        diff += calc_diff(right)
    else:
        current[0] += 1
        diff += calc_diff(down)

print(abs(diff))

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())

a = [list(map(int, input().split())) for i in range(h)]
b = [list(map(int, input().split())) for i in range(h)]

c = [[abs(a[i][j] - b[i][j]) for j in range(w)] for i in range(h)]

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

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

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

Submission status: Wrong Answer

Solution code:
from itertools import chain

H,W = map(int,input().split())

A = tuple(tuple(map(int,input().split())) for _ in range(H))
B = tuple(tuple(map(int,input().split())) for _ in range(H))

dp = {(0,0) : {(A[0][0]-B[0][0])%160, (B[0][0]-A[0][0])%160}}


for t in range(1,H+W-1):
    ndp = dict()
    for x in range(max(0,t-H+1), min(t+1,W)):
        y = t-x
        d = A[y][x]-B[y][x]
        if x > 0 and y > 0:
            ns = set(k%160 for k in chain((v+d for v in dp[(x-1,y)]),
                            (v-d for v in dp[(x-1,y)]),
                            (v+d for v in dp[(x,y-1)]),
                            (v-d for v in dp[(x,y-1)]),))
        elif x > 0:
            ns = set(k%160 for k in chain((v+d for v in dp[(x-1,y)]),
                            (v-d for v in dp[(x-1,y)]),))
        elif y > 0:
            ns = set(k%160 for k in chain((v+d for v in dp[(x,y-1)]),
                            (v-d for v in dp[(x,y-1)]),))
        else:
            ns = set()

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

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