Problem:


Score : 500 points

Problem Statement

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

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

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

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

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

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

Find the minimum unbalancedness possible.

Constraints

2 \leq H \leq 80

2 \leq W \leq 80

0 \leq A_{ij} \leq 80

0 \leq B_{ij} \leq 80

All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print the minimum unbalancedness possible.

Sample Input 1

2 2
1 2
3 4
3 4
2 1

Sample Output 1

0

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

Sample Input 2

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

Sample Output 2

2



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


Sample output:
0

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
MAX_VAL = 9000
OFFSET = MAX_VAL // 2
 
h, w = [int(item) for item in input().split()]
a = []
b = []
for i in range(h):
    line = [int(item) for item in input().split()] + [0]
    a.append(line)
a.append([0] * (w + 1))
for i in range(h):
    line = [int(item) for item in input().split()] + [0]
    b.append(line)
b.append([0] * (w + 1))
 
# dp[height][width][bias]
dp = [[[0] * MAX_VAL for _ in range(w+1)] for _ in range(h+1)] 
dp[0][0][OFFSET + a[0][0] - b[0][0]] = 1
dp[0][0][OFFSET + b[0][0] - a[0][0]] = 1
for i in range(h):
    for j in range(w):
        diffr = a[i][j+1] - b[i][j+1]
        diffd = a[i+1][j] - b[i+1][j]
        for k in range(85, MAX_VAL - 85):
            if dp[i][j][k] == 0:
                continue
            # Move right
            dp[i][j+1][k+diffr] = 1
            dp[i][j+1][k-diffr] = 1
            # Move down
            dp[i+1][j][k+diffd] = 1
            dp[i+1][j][k-diffd] = 1
ans = 10**9
for i, item in enumerate(dp[h-1][w-1]):
    if item == 1:
        ans = min(ans, abs(i - OFFSET))
print(ans)

Submission status: Wrong Answer

Solution code:
import copy
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=[[0]*w for i in range(h)]
for i in range(h):
  for j in range(w):
    c[i][j]=abs(a[i][j]-b[i][j])
dp=[[[] for i in range(w)] for j in range(h)]
dp[0][0].append(c[0][0])
for i in range(h):
  for j in range(w):
    if i<h-1:
      l=copy.copy(dp[i][j])
      for k in range(len(l)):
        if -80<=l[k]+c[i+1][j] and l[k]+c[i+1][j]<=80:
          l.append(l[k]+c[i+1][j])
        if -80<=l[k]-c[i+1][j] and l[k]+c[i+1][j]<=80:
          l.append(l[k]-c[i+1][j])
      l=list(set(l))
      dp[i+1][j]=l
    if j<w-1:
      l=copy.copy(dp[i][j])
      for k in range(len(l)):
        if -80<=l[k]+c[i][j+1]<=80:
          l.append(l[k]+c[i][j+1])
        if -80<=l[k]-c[i][j+1]<=80:
          l.append(l[k]-c[i][j+1])
      l=list(set(l))
      dp[i][j+1]=l
for i in range(len(dp[h-1][w-1])):
  dp[h-1][w-1][i]=abs(dp[h-1][w-1][i])
print(min(dp[h-1][w-1]))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
h,w=map(int,input().split())
a=[]
for i in range(h):
    a.append(list(map(int,input().split())))
b=[]
for i in range(h):
    b.append(list(map(int,input().split())))
dp=[[set([]) for i in range(w)] for j in range(h)]
dp[0][0].add(a[0][0]-b[0][0])
dp[0][0].add(b[0][0]-a[0][0])
for i in range(h):
    for j in range(w):
        if i==j==0:
            continue
        if i==0:
            for k in dp[i][j-1]:
                dp[i][j].add(abs(k+a[i][j]-b[i][j]))
                dp[i][j].add(abs(k+b[i][j]-a[i][j]))
        elif j==0:
            for k in dp[i-1][j]:
                dp[i][j].add(abs(k+a[i][j]-b[i][j]))
                dp[i][j].add(abs(k+b[i][j]-a[i][j]))
        else:
            for k in (dp[i][j-1]|dp[i-1][j]):
                if k<=100:
                    dp[i][j].add(abs(k+a[i][j]-b[i][j]))
                    dp[i][j].add(abs(k+b[i][j]-a[i][j]))             
#dp[h-1][w-1]
ans=10**10
for i in dp[h-1][w-1]:
    ans=min(ans,abs(i))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
h, w = map(int, input().split())
graph = []
for i in range(h):
    a = list(map(int, sys.stdin.readline().split()))
    graph.append(a)
for i in range(h):
    b = list(map(int, sys.stdin.readline().split()))
    for j in range(w):
        graph[i][j] = abs(graph[i][j] - b[j])
result = [[set()]*w for _ in range(h)]
result[0][0].add(graph[0][0])
for i in range(1, h+w-1):
    for j in range(max(0, i-(w-1)), min(i+1, h)):
        ps = set()
        if j > 0:
            for k in result[j-1][i-j]:
                em = abs(k - graph[j][i-j])
                ps.add(em)
                eu = k + graph[j][i-j]
                if k <= 80 * 3:
                    ps.add(eu)
        if i-j > 0:
            for k in result[j][i-j-1]:
                em = abs(k - graph[j][i-j])
                ps.add(em)
                eu = k + graph[j][i-j]
                if k <= 80 * 3:
                    ps.add(eu)
        result[j][i-j] = ps
print(min(result[h-1][w-1]))

Submission status: Wrong Answer

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def build_grid(H, W, intv, _type, space=True, padding=False):
    # 入力がスペース区切りかどうか
    if space:
        _input = lambda: input().split()
    else:
        _input = lambda: input()
    _list = lambda: list(map(_type, _input()))
    # 余白の有無
    if padding:
        offset = 1
    else:
        offset = 0
    grid = list2d(H+offset*2, W+offset*2, intv)
    for i in range(offset, H+offset):
        row = _list()
        for j in range(offset, W+offset):
            grid[i][j] = row[j-offset]
    return grid

H, W = MAP()
MAXV = 80 ** 2 // 2

grid1 =build_grid(H, W, 0, int)
grid2 =build_grid(H, W, 0, int)
grid = list2d(H+1, W+1, 0)
for i in range(H):
    for j in range(W):
        grid[i+1][j+1] = abs(grid1[i][j]-grid2[i][j])

dp = list3d(H+1, W+1, MAXV+1, 0)
dp[1][1][grid[1][1]] = 1
for i in range(1, H+1):
    for j in range(1, W+1):
        v = grid[i][j]
        for k in range(MAXV+1):
            dp[i][j][k] |= dp[i-1][j][abs(k-v)]
            if k+v <= MAXV:
                dp[i][j][k] |= dp[i-1][j][k+v]
            dp[i][j][k] |= dp[i][j-1][abs(k-v)]
            if k+v <= MAXV:
                dp[i][j][k] |= dp[i][j-1][k+v]
ans = INF
for k in range(MAXV+1):
    if dp[H][W][k]:
        ans = min(ans, k)
print(ans)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
A = list(list(map(int, input().split())) for _ in range(H))
B = list(list(map(int, input().split())) for _ in range(H))

point = [[A[i][j]-B[i][j] for j in range(W)] for i in range(H)]

pos = [0,0]
score = 0
first_pass = True
while(pos[0]!=H-1 or pos[1]!=W-1):
    #print("(x,y)=(%d,%d)"%(pos[1],pos[0]))
    if first_pass is True:
        first_pass = False
    else:
        if pos[0] == H-1:
            pos[1] += 1
        elif pos[1] == W-1:
            pos[0] += 1
        else:
            if abs(point[pos[0]][pos[1]+1]) < abs(point[pos[0]+1][pos[1]]):
                pos[1] += 1
            else:
                pos[0] += 1
    score += point[pos[0]][pos[1]]
print(score)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
G = [list(map(int, input().split())) for i in range(H)]
for h in range(H):
    row = list(map(int, input().split()))
    for w in range(W):
        G[h][w] = abs(G[h][w] - row[w])


# dp[h][w] :=  G[h][w]にたどり着いた時の総和の最小値
dp = [[float('inf')] * W for i in range(H)]
dx = [[''] * W for i in range(H)]
dp[0][0] = G[0][0]


direction = [[0, 1], [1, 0]]
for nh in range(H):
    for nw in range(W):
        for i, (dh, dw) in enumerate(direction):
            if not((0 <= nh + dh < H) and (0 <= nw + dw < W)):
                continue
            if dp[nh + dh][nw + dw] > dp[nh][nw] + G[nh][nw]:
                dp[nh + dh][nw + dw] = dp[nh][nw] + G[nh][nw]
                dx[nh + dh][nw + dw] = i


X = []
h, w = H - 1, W - 1
while (h != 0) or (w != 0):
    X.append(G[h][w])
    if dx[h][w] == 0:
        w -= 1
    else:
        h -= 1
X.append(G[0][0])

X.sort()
ans = sum(X)
S = sum(X)

for x in X:
    if abs(abs(S - x) - x) < ans:
        ans = abs(abs(S - x) - x)

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
import os
import sys

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

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


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

grid = [[0] * W for _ in range(H)]
for h, w in itertools.product(range(H), range(W)):
    grid[h][w] = A[h][w] - B[h][w]

# 符号をどっちにするか選べる
dp = [[set() for _ in range(W)] for _ in range(H)]
dp[0][0] = {grid[0][0] % 160, -(grid[0][0]) % 160}
for h, w in itertools.product(range(H), range(W)):
    g = grid[h][w]
    s = dp[h][w]
    if h - 1 >= 0:
        for c in dp[h - 1][w]:
            s.add((c + g) % 160)
            s.add((c - g) % 160)
    if w - 1 >= 0:
        for c in dp[h][w - 1]:
            s.add((c + g) % 160)
            s.add((c - g) % 160)
# print(grid)
# print(dp)
ans = INF
for s in dp[-1][-1]:
    ans = min(ans, s)
    ans = min(ans, (-s) % 160)
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
H,W=map(int,input().split())
a = [[] for _ in range(H)]
for i in range(H):
    a[i] = list(map(int, input().split()))
b = [[] for _ in range(H)]
for i in range(H):
    b[i] = list(map(int, input().split()))
#print(a)
#print(b)
for i in range(H):
    for j in range(W):
        a[i][j] =abs(a[i][j]-b[i][j])
#print(a)
dp = [[set() for _ in range(W)] for _ in range(H)]
dp[0][0].add(a[0][0])
dp[0][0].add(-a[0][0])
for i in range(H):
    for j in range(W):
        tmp = set()
        if i!=0:
            for k in dp[i-1][j]:
                tmp.add(k+a[i][j])
                tmp.add(k-a[i][j])
        if j!=0:
            for k in dp[i][j-1]:
                tmp.add(k+a[i][j])
                tmp.add(k-a[i][j])
        if i>0 or j>0:
            dp[i][j] = tmp
        #print(tmp)
#print(dp[H-1][W-1])
ls = list(dp[H-1][W-1])
res = np.abs(np.asarray(ls)).argmin()
print(ls[res])

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) : {abs(A[0][0]-B[0][0])}}

cap = 1200

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(x for x in chain((abs(v+d) for v in dp[(x-1,y)]),
                            (abs(v-d) for v in dp[(x-1,y)]),
                            (abs(v+d) for v in dp[(x,y-1)]),
                            (abs(v-d) for v in dp[(x,y-1)]),) if x < cap)
        elif x > 0:
            ns = set(x for x in chain((abs(v+d) for v in dp[(x-1,y)]),
                            (abs(v-d) for v in dp[(x-1,y)]),) if x < cap)
        elif y > 0:
            ns = set(x for x in chain((abs(v+d) for v in dp[(x,y-1)]),
                            (abs(v-d) for v in dp[(x,y-1)]),) if x < cap)
        else:
            ns = set()

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

print(min(dp[(W-1,H-1)]))

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


def div(s):
    s.sort(reversed=True)
    a = []
    b = []
    total_a = 0
    total_b = 0
    for v in a:
        if total_a < total_b:
            total_a += v
            a.append(v)
        else:
            total_b += v
            b.append(v)
    return (a, b)


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]:
        if e <= 160:
            sets[i][0].add(e + c[i][0])
            sets[i][0].add(abs(e - c[i][0]))
for i in range(1, w):
    new_set = set()
    for e in sets[0][i - 1]:
        if e <= 160:
            sets[0][i].add(e+c[0][i])
            sets[0][i].add(abs(e-c[0][i]))

for i in range(1, h):
    for j in range(1, w):
        for e in sets[i-1][j]:
            if e <= 160:
                sets[i][j].add(e+c[i][j])
                sets[i][j].add(abs(e-c[i][j]))
        for e in sets[i][j-1]:
            if e <= 160:
                sets[i][j].add(e+c[i][j])
                sets[i][j].add(abs(e-c[i][j]))
print(min(sets[h-1][w-1]))

Submission status: Wrong Answer

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def build_grid(H, W, intv, _type, space=True, padding=False):
    # 入力がスペース区切りかどうか
    if space:
        _input = lambda: input().split()
    else:
        _input = lambda: input()
    _list = lambda: list(map(_type, _input()))
    # 余白の有無
    if padding:
        offset = 1
    else:
        offset = 0
    grid = list2d(H+offset*2, W+offset*2, intv)
    for i in range(offset, H+offset):
        row = _list()
        for j in range(offset, W+offset):
            grid[i][j] = row[j-offset]
    return grid

H, W = MAP()
MAXV = 80 ** 2 // 2

grid1 =build_grid(H, W, 0, int)
grid2 =build_grid(H, W, 0, int)
grid = list2d(H+1, W+1, 0)
for i in range(H):
    for j in range(W):
        grid[i+1][j+1] = abs(grid1[i][j]-grid2[i][j])

dp = list3d(H+1, W+1, MAXV+1, 0)
dp[1][1][grid[1][1]] = 1
for i in range(1, H+1):
    for j in range(1, W+1):
        v = grid[i][j]
        for k in range(MAXV+1):
            dp[i][j][abs(k-v)] |= dp[i-1][j][k]
            if k+v <= MAXV:
                dp[i][j][k+v] |= dp[i-1][j][k]
            dp[i][j][abs(k-v)] |= dp[i][j-1][k]
            if k+v <= MAXV:
                dp[i][j][k+v] |= dp[i][j-1][k]
ans = INF
for k in range(MAXV+1):
    if dp[H][W][k]:
        ans = min(ans, k)
print(ans)

Submission status: Wrong Answer

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

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

A=[list(map(int,input().split())) for i in range(H)]
B=[list(map(int,input().split())) for i in range(H)]

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

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

DP=[[[] for i in range(W+1)] for i in range(H+1)]

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

MID=(H+W-2)//2

def next(i,j,t):
    RET=[]
    lim=80*(MID-abs(t-MID)+2)
    if i+j<=lim:
        RET.append(i+j)

    if abs(i-j)<=lim:
        RET.append(abs(i-j))

    return RET

for i in range(H):
    for j in range(W):
        for k in set(DP[i][j]):
            if i+j<=MID:
                DP[i+1][j].append(k+SA[i+1][j])
                DP[i][j+1].append(abs(k-SA[i+1][j]))
            else:
                DP[i+1][j].extend(next(k,SA[i+1][j],i+j))
                DP[i][j+1].extend(next(k,SA[i][j+1],i+j))
                
print(min(DP[H-1][W-1]))

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


def div(s):
    s.sort(reversed=True)
    a = []
    b = []
    total_a = 0
    total_b = 0
    for v in a:
        if total_a < total_b:
            total_a += v
            a.append(v)
        else:
            total_b += v
            b.append(v)
    return (a, b)


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]:
        if e <= 80:
            sets[i][0].add(e + c[i][0])
            sets[i][0].add(abs(e - c[i][0]))
for i in range(1, w):
    new_set = set()
    for e in sets[0][i - 1]:
        if e <= 80:
            sets[0][i].add(e+c[0][i])
            sets[0][i].add(abs(e-c[0][i]))

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

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)]
D = [[abs(A[h][w] - B[h][w]) for w in range(W)] for h in range(H)]
DP = [[0] * W for _ in range(H)]

DP[0][0], FIN = abs(D[0][0] - D[H - 1][W - 1]), D[H - 1][W - 1]
for w in range(1, W):
    DP[0][w] = min(abs(abs((DP[0][w - 1] - FIN if DP[0][w - 1] >= FIN else DP[0][w - 1] + FIN) - D[0][w]) - FIN),
                   abs(abs((DP[0][w - 1] - FIN if DP[0][w - 1] >= FIN else DP[0][w - 1] + FIN) + D[0][w]) - FIN))
for h in range(1, H):
    DP[h][0] = min(abs(abs((DP[h - 1][0] - FIN if DP[h - 1][0] >= FIN else DP[h - 1][0] + FIN) - D[h][0]) - FIN),
                   abs(abs((DP[h - 1][0] - FIN if DP[h - 1][0] >= FIN else DP[h - 1][0] + FIN) + D[h][0]) - FIN))

for h in range(1, H):
    for w in range(1, W):
        DP[h][w] = min(abs(abs((DP[h][w - 1] - FIN if DP[h][w - 1] >= FIN else DP[h][w - 1] + FIN) - D[h][w]) - FIN),
                       abs(abs((DP[h][w - 1] - FIN if DP[h][w - 1]
                                >= FIN else DP[h][w - 1] + FIN) + D[h][w]) - FIN),
                       abs(abs((DP[h - 1][w] - FIN if DP[h - 1][w]
                                >= FIN else DP[h - 1][w] + FIN) - D[h][w]) - FIN),
                       abs(abs((DP[h - 1][w] - FIN if DP[h - 1][w] >= FIN else DP[h - 1][w] + FIN) + D[h][w]) - FIN))

print(min(DP[H - 1][W - 2], DP[H - 2][W - 1]))

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
a = [list(map(int, input().split())) for i in range(h)]
b = [list(map(int, input().split())) for i in range(h)]
diff = [[0]*(w+1) for i in range(h+1)]

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

n = 80 * 60 + 1
dp = [[False]*n for i in range(h*w)]
dp[0][diff[0][0]] = True

for i in range(h):
    for j in range(w):
        for cnt in range(n):
            if dp[i*w + j][cnt]:
                tmp1 = diff[i+1][j]
                tmp2 = diff[i][j+1]
                if i+1 < h:
                    dp[(i+1)*w + j][abs(cnt - tmp1)] = True
                    if cnt + tmp1 < n:
                        dp[(i+1)*w + j][cnt + tmp1] = True

                if j+1 < w:
                    dp[i*w + j+1][abs(cnt - tmp2)] = True 
                    if cnt + tmp2 < n:
                        dp[i*w + j+1][cnt + tmp2] = True

for i, boo in enumerate(dp[w*h - 1][0:81]):
    if boo:
        print(i)
        exit()
print(a[10*9])

Submission status: Wrong Answer

Solution code:
import itertools
import copy
def main():
    h,w = map(int,input().split())
    a = [tuple(map(int,input().split())) for _ in range(h)]
    b = [tuple(map(int,input().split())) for _ in range(h)]

    ans = 10**9
    x = 0
    y = 0
    aa = a[y][x]
    bb = b[y][x]
    rb = [(abs(aa-bb),sorted([aa,bb]))]
    for i in range(h+w-2):
        t = []
        if x+1 <= w-1:
            aa = a[y][x+1]
            bb = b[y][x+1]
            t.append((abs(aa-bb),sorted([aa,bb]),x+1,y))
        if y+1 <= h-1:
            aa = a[y+1][x]
            bb = b[y+1][x]
            t.append((abs(aa-bb),sorted([aa,bb]),x,y+1))
        tm = sorted(t)[0]
        x = tm[-2]
        y = tm[-1]
        rb.append((tm[0],tm[1]))
    rb = sorted(rb,reverse=True)
    for i in range(len(rb)):
        p = rb.pop(-1)
        if not p[0] == 0:
            rb.append(p)
            break
    tr = 0
    tb = 0
    lrb = len(rb)
    odd = lrb%2
    for j in range(lrb-odd):
        if j %2 == 0:
            tr += rb[j][1][0]
            tb += rb[j][1][1]
        else:
            tr += rb[j][1][1]
            tb += rb[j][1][0]
    if odd == 1:
        tr,tb = min([tr,tb])+max(rb[-1][1]),max([tr,tb])+min(rb[-1][1])
    ans = min([ans,abs(tr-tb)])
    print(ans)
    
if __name__ == '__main__':
    main()

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] * 1601  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(1601):
            if C[i-1][0][j]:
                if abs(j + A[i][0]) <= 1600:
                    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(1601):
            if C[0][j-1][i]:
                if abs(i + A[0][j]) <= 1600:
                    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(1601):

            if C[i-1][j][k]:
                if abs(k + A[i][j]) <= 1600:
                    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]) <= 1600:
                    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(1601):

    if C[-1][-1][i]:
        ans = min(ans,i)
    
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)]
c=[[abs(a[i][j]-b[i][j])for j in range(w)]for i in range(h)]
d=[[set()for i in range(w+1)]for j in range(h+1)]
d[1][1]=set([c[0][0]])
for x in range(1,h+1):
    for y in range(1,w+1):
        if not (x==1 and y==1):
            a=d[x-1][y]|d[x][y-1]
            for i in a:
                d[x][y].add(abs(i-c[x-1][y-1]))
print(min(d[h][w]))

Submission status: Wrong Answer

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

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

    dp = [[[False]*2001 for j in range(w)] for i in range(h)]

    dp[0][0][abs(a[0][0]-b[0][0])] = True



    for i in range(1,h):
        for k in range(2001):
            if abs(k-abs(a[i][0]-b[i][0])) <= 2000 and dp[i-1][0][abs(k-abs(a[i][0]-b[i][0]))]:
                dp[i][0][k] = True
            elif abs(k+abs(a[i][0]-b[i][0])) <= 2000 and dp[i-1][0][abs(k+abs(a[i][0]-b[i][0]))]:
                dp[i][0][k] = True

    for j in range(1,w):
        for k in range(2001):
            if abs(k-abs(a[0][j]-b[0][j])) <= 2000 and dp[0][j-1][abs(k-abs(a[0][j]-b[0][j]))]:
                dp[0][j][k] = True
            elif abs(k+abs(a[0][j]-b[0][j])) <= 2000 and dp[0][j-1][abs(k+abs(a[0][j]-b[0][j]))]:
                dp[0][j][k] = True


    for i in range(1,h):
        for j in range(1,w):
            for k in range(2001):
                if abs(k-abs(a[i][j]-b[i][j])) <= 2000 and dp[i][j-1][abs(k-abs(a[i][j]-b[i][j]))]:
                    dp[i][j][k] = True
                elif abs(k+abs(a[i][j]-b[i][j])) <= 2000 and dp[i][j-1][abs(k+abs(a[i][j]-b[i][j]))]:
                    dp[i][j][k] = True
                elif abs(k-abs(a[i][j]-b[i][j])) <= 2000 and dp[i-1][j][abs(k-abs(a[i][j]-b[i][j]))]:
                    dp[i][j][k] = True
                elif abs(k+abs(a[i][j]-b[i][j])) <= 2000 and dp[i-1][j][abs(k+abs(a[i][j]-b[i][j]))]:
                    dp[i][j][k] = True
    res = 2001
    for k in range(2001):
        if dp[-1][-1][k]:
            res = min(res,k)

    print(res)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
h, w = map(int,input().split())
A = [list(map(int,input().split())) for i in range(h)]
B = [list(map(int,input().split())) for i in range(h)]

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

V = [[2] * w for i in range(h)]
for i in range(h):
    V[i][0] -= 1
for i in range(w):
    V[0][i] -= 1

l = 5000
m = 0

M = [[set() for i in range(w)] for j in range(h)]
N = [[0 for i in range(w)] for j in range(h)]
N[0][0] = C[0][0]

s = 0
Q = [[0, 0]]

M[0][0].add(C[0][0])
# M[0][0][m-C[0][0]] = 1

while len(Q) > s:
    i = Q[s][0]
    j = Q[s][1]
    if i+1 < h:
        for ii in M[i][j]:
            if abs(ii+C[i+1][j]) < l:
                M[i+1][j].add(abs(ii+C[i+1][j]))
            if abs(ii-C[i+1][j]) < l:
                M[i+1][j].add(abs(ii-C[i+1][j]))
        V[i+1][j] -= 1
        # print(N[i+1][j], N[i][j] + C[i+1][j])
        N[i+1][j] = max(N[i+1][j], N[i][j] + C[i+1][j])
        if V[i+1][j]==0:
            Q.append([i+1,j])
    if j+1 < w:
        for ii in M[i][j]:
            if abs(ii+C[i][j+1]) < l:
                M[i][j+1].add(abs(ii+C[i][j+1]))
            if abs(ii-C[i][j+1]) < l:
                M[i][j+1].add(abs(ii-C[i][j+1]))
        V[i][j+1] -= 1
        N[i][j+1] = max(N[i][j+1], N[i][j] + C[i][j+1])
        if V[i][j+1]==0:
            Q.append([i,j+1])
        
    
    s += 1

# print(M[-1][-1])

print(min(M[-1][-1]))

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
B = [list(map(int, input().split())) for _ in range(H)]
C = [[0]*W for _ in range(H)]
for i in range(H):
    for j in range(W):
        C[i][j] = A[i][j]-B[i][j]
M = 80*(H+W)
dp = [[set() for i in range(W)] for j in range(H)]
c = C[0][0]
dp[0][0].add(c)
for s in range(1, H+W):
    for b in range(max(s-H+1, 0), min(s, W)):
        a = s-b
        c = C[a][b]
        if a>=1:
            for i in dp[a-1][b]:
                dp[a][b].add(abs(i+c))
                dp[a][b].add(abs(i-c))

        if b>=1:
            for i in dp[a][b-1]:
                dp[a][b].add(abs(i+c))
                dp[a][b].add(abs(i-c))
ans = min(dp[-1][-1])
print(ans)

Submission status: Wrong Answer

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

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

max_f = [[0] * (w+1) for _ in range(h+1)]
min_f = [[0] * (w+1 )for _ in range(h+1)]
# dp[height][width][bias]
dp = [[[0] * MAX_VAL for _ in range(w+1)] for _ in range(h+1)] 
max_f[0][0] = abs(a[0][0] - b[0][0])
min_f[0][0] = -abs(a[0][0] - b[0][0])

dp[0][0][OFFSET + a[0][0] - b[0][0]] = 1
dp[0][0][OFFSET + b[0][0] - a[0][0]] = 1
for i in range(h):
    for j in range(w):
        diffr = a[i][j+1] - b[i][j+1]
        diffd = a[i+1][j] - b[i+1][j]
        max_f[i][j+1] = max_f[i][j] + diffr
        min_f[i][j+1] = min_f[i][j] - diffr
        max_f[i+1][j] = max_f[i][j] + diffd
        min_f[i+1][j] = min_f[i][j] - diffd
        for k in range(OFFSET + min_f[i][j] - 1, OFFSET + max_f[i][j] + 1):
            if dp[i][j][k] == 0:
                continue
            # Move right
            dp[i][j+1][k+diffr] = 1
            dp[i][j+1][k-diffr] = 1
            # Move down
            dp[i+1][j][k+diffd] = 1
            dp[i+1][j][k-diffd] = 1
ans = 10**9
for i, item in enumerate(dp[h-1][w-1]):
    if item == 1:
        ans = min(ans, abs(i - OFFSET))
print(ans)

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
a = [list(map(int, input().split())) for i in range(h)]
b = [list(map(int, input().split())) for i in range(h)]
diff = [[0]*(w+1) for i in range(h+1)]

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

n = 80 + 1
dp = [[False]*n for i in range(h*w)]
dp[0][diff[0][0]] = True

for i in range(h):
    for j in range(w):
        for cnt in range(n):
            if dp[i*w + j][cnt]:
                tmp1 = diff[i+1][j]
                tmp2 = diff[i][j+1]
                if i+1 < h:
                    dp[(i+1)*w + j][abs(cnt - tmp1)] = True

                if j+1 < w:
                    dp[i*w + j+1][abs(cnt - tmp2)] = True 

for i, boo in enumerate(dp[w*h - 1][0:81]):
    if boo:
        print(i)
        exit()
print(a[10*9])