Problem:


Score : 500 points

Problem Statement

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

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

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

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

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

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

Find the minimum unbalancedness possible.

Constraints

2 \leq H \leq 80

2 \leq W \leq 80

0 \leq A_{ij} \leq 80

0 \leq B_{ij} \leq 80

All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print the minimum unbalancedness possible.

Sample Input 1

2 2
1 2
3 4
3 4
2 1

Sample Output 1

0

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

Sample Input 2

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

Sample Output 2

2



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


Sample output:
0

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

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

pdp = [set() for _ in range(W)]
pdp[0] = set([0])
for y in range(H) :
    ndp = [set() for _ in range(W)]
    for x in range(W) :
        s = set([i + A[y][x] - B[y][x] for i in pdp[x]] + [i + B[y][x] - A[y][x] for i in pdp[x]])
        if y < H - 1 :
            for i in pdp[x] :
                ndp[x] |= s
        if x < W - 1 :
            for i in pdp[x] :
                pdp[x+1] |= s
    
    if y == H - 1 :
        ret = float('inf')
        for i in pdp[-1] :
            ret = min(ret, abs(i + A[H-1][W-1] - B[H-1][W-1]))
            ret = min(ret, abs(i + B[H-1][W-1] - A[H-1][W-1]))
        print(ret)
    pdp = ndp

Submission status: Time Limit Exceeded

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 = [[] for i in range(H)]
for i in range(H):
    for j in range(W):
        
        C[i].append({})

#print (C)

for i in range(H):

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

        for j in C[i-1][0]:
            C[i][0] [abs(j - A[i][0])] = 1
            C[i][0] [abs(j + A[i][0])] = 1

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

#print (C)

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

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

        for k in C[i-1][j]:
            C[i][j] [abs(k + A[i][j])] = 1
            C[i][j] [abs(k - A[i][j])] = 1
        for k in C[i][j-1]:
            C[i][j] [abs(k + A[i][j])] = 1
            C[i][j] [abs(k - A[i][j])] = 1

ans = float("inf")   
for i in C[-1][-1]:

    ans = min(ans,i)
    
print (ans)

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
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)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    h,w = LI()
    a = LIR(h)
    b = LIR(h)
    for i in range(h):
        for j in range(w):
            a[i][j] -= b[i][j]
            if a[i][j] < 0:
                a[i][j] *= -1
    M = 160*(5+((h+w)>>1))
    m = -M
    f = defaultdict(lambda : set({}))
    f[(0,0)].add(a[0][0])
    d = [(0,1),(1,0)]
    for y in range(h):
        for x in range(w):
            for t in f[(y,x)]:
                for dy,dx in d:
                    ny = y+dy
                    nx = x+dx
                    if 0 <= ny < h and 0 <= nx < w:
                        nt = t-a[ny][nx]
                        if m <= nt <= M:
                            f[(ny,nx)].add(nt)
                        nt = t+a[ny][nx]
                        if m <= nt <= M:
                            f[(ny,nx)].add(nt)
    ans = min([abs(i) for i in f[(h-1,w-1)]])
    print(ans)
    return

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

Submission status: Time Limit Exceeded

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=[[[]for i in range(w+1)]for j in range(h+1)]
def f(x,y):
    if x==1 and y==1:
        d[1][1]=list(set([-c[0][0],c[0][0]]))
    else:
        a=set(d[x-1][y]+d[x][y-1])
        e=set()
        for i in a:
            e.add(i-c[x-1][y-1])
            e.add(i+c[x-1][y-1])
        d[x][y]=list(e)
    if x!=h:
        f(x+1,y)
    if y!=w:
        f(x,y+1)
f(1,1)
print(abs(min(d[h][w],key=abs)))

Submission status: Time Limit Exceeded

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

def solve():
    H, W = map(int, input().split())
    Ass = [tuple(map(int, input().split())) for _ in range(H)]
    Bss = [tuple(map(int, input().split())) for _ in range(H)]

    dp = [[set() for j in range(W)] for i in range(H)]
    A, B = Ass[0][0], Bss[0][0]
    dp[0][0] = set([(A, B), (B, A)])

    for i in range(H):
        for j in range(W):
            if i < H-1:
                A, B = Ass[i+1][j], Bss[i+1][j]
                for x, y in dp[i][j]:
                    dp[i+1][j].add((x+A, y+B))
                    dp[i+1][j].add((x+B, y+A))
            if j < W-1:
                A, B = Ass[i][j+1], Bss[i][j+1]
                for x, y in dp[i][j]:
                    dp[i][j+1].add((x+A, y+B))
                    dp[i][j+1].add((x+B, y+A))

    ans = float('inf')
    for x, y in dp[-1][-1]:
        score = abs(x-y)
        ans = min(ans, score)

    #for dpi in dp:
    #    print(dpi)
    print(ans)


solve()

Submission status: Time Limit Exceeded

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

arr = [set() for _ in range(W)]
arr[0].add(0)
for y in range(H):
    nextarr = [set() for _ in range(W)]
    Ay = A[y]
    By = B[y]
    for x in range(W):
        nextset = nextarr[x]
        d = Ay[x] - By[x]
        for n in arr[x]:
            nextset.add(n+d)
            nextset.add(n-d)
        if x >= 1:
            for n in nextarr[x-1]:
                nextset.add(n+d)
                nextset.add(n-d)
    arr = nextarr
print(min([abs(d) for d in arr[-1]]))

Submission status: Time Limit Exceeded

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


D = [[0] * W for _ in range(H)]
for i in range(H):
  for j in range(W):
    D[i][j] = abs(B[i][j] - A[i][j])

DP = [[[0] * M for _ in range(W)] for _ in range(H)]

def nasu(t):
  if t >= 0 and t < M:
    return True
  else:
    return False

DP[0][0][D[0][0]] = 1
for i in range(H + W):
  for j in range(H):
    if i - j >= W: continue
    x = i - j
    y = j
    if x < 0: continue
    if x - 1 >= 0:
      for k in range(M):
        if DP[y][x - 1][k] == 1:
          t = k + D[y][x]
          if nasu(t):
            DP[y][x][t] = 1
          t = abs(k - D[y][x])
          if nasu(t):
            DP[y][x][t] = 1
    if y - 1 >= 0:
      for k in range(M):
        if DP[y - 1][x][k] == 1:
          t = k + D[y][x]
          if nasu(t):
            DP[y][x][t] = 1
          t = abs(k - D[y][x])
          if nasu(t):
            DP[y][x][t] = 1

for i in range(M):
  if DP[-1][-1][i] == 1:
    print(i)
    break

Submission status: Time Limit Exceeded

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]

LIMIT = 80 * 80
# 符号をどっちにするか選べる
dp = [[set() for _ in range(W)] for _ in range(H)]
dp[0][0] = {grid[0][0], -grid[0][0]}
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]:
            if abs(c + g) <= LIMIT:
                s.add(abs(c + g))
            if abs(c - g) <= LIMIT:
                s.add(abs(c - g))
    if w - 1 >= 0:
        for c in dp[h][w - 1]:
            if abs(c + g) <= LIMIT:
                s.add(abs(c + g))
            if abs(c - g) <= LIMIT:
                s.add(abs(c - g))

ans = INF
for s in dp[-1][-1]:
    ans = min(ans, abs(s))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
import bisect
 
mod = 10**9+7
 
def I(): return(int(sys.stdin.readline()))
def LI(): return([int(x) for x in sys.stdin.readline().split()])
def S(): return(list(sys.stdin.readline())[:-1])
 
def main():
    H,W = LI()
    A = [LI() for _ in range(H)]
    B = [LI() for _ in range(H)]
    D = [[A[h][w]-B[h][w] for w in range(W)] for h in range(H)]
    dp = [[[False for _ in range(26000)] for w in range(W)] for h in range(H)]

    dp[0][0][D[0][0]+13000] = True

    for h in range(H):
        for w in range(W):
            if(h>0):
                for i in range(26000):
                    if dp[h-1][w][i]:
                        dp[h][w][i+D[h][w]] = True
                        dp[h][w][i-D[h][w]] = True
            if(w>0):
                for i in range(26000):
                    if dp[h][w-1][i]:
                        dp[h][w][i+D[h][w]] = True
                        dp[h][w][i-D[h][w]] = True

    ans = 30000
    for i in range(26000):
        if dp[H-1][W-1][i]:
            ans = min(ans,abs(i-13000))
    return(ans)
 
if __name__ == "__main__":
    print(main())

Submission status: Time Limit Exceeded

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]*4000 for j in range(w)] for i in range(h)]

    dp[0][0][2000+a[0][0]-b[0][0]] = True
    dp[0][0][2000-a[0][0]+b[0][0]] = True


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

    for j in range(1,w):
        for k in range(4000):
            if 0 <= k+a[0][j]-b[0][j] <= 3999 and dp[0][j-1][k+a[0][j]-b[0][j]]:
                dp[0][j][k] = True
            elif 0 <= k-a[0][j]+b[0][j] <= 3999 and dp[0][j-1][k-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(4000):
                if 0 <= k+a[i][j]-b[i][j] <= 3999 and dp[i-1][j][k+a[i][j]-b[i][j]]:
                    dp[i][j][k] = True
                elif 0 <= k+a[i][j]-b[i][j] <= 3999 and dp[i][j-1][k+a[i][j]-b[i][j]]:
                    dp[i][j][k] = True
                elif 0 <= k-a[i][j]+b[i][j] <= 3999 and dp[i-1][j][k-a[i][j]+b[i][j]]:
                    dp[i][j][k] = True
                elif 0 <= k-a[i][j]+b[i][j] <= 3999 and dp[i][j-1][k-a[i][j]+b[i][j]]:
                    dp[i][j][k] = True

    res = 10**9
    for k in range(4000):
        if dp[-1][-1][k]:
            res = min(res,abs(2000-k))

    print(res)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

Solution code:
from collections import deque
from copy import copy

row, column = map(int, input().split())
map1 = [list(map(int, input().split())) for _ in range(row)]
map2 = [list(map(int, input().split())) for _ in range(row)]

n1 = map1[0][0]
n2 = map2[0][0]
queue = deque([(0, 0, n1, n2), (0, 0, n2, n1)])
ansque = deque()

def bfs(queue):
    while True:
        nextqueue = deque()
        while queue:
            posr, posc, red, blue = queue.popleft()
            if (posr, posc) == (row - 1, column - 1):
                ansque.append(abs(red - blue))
            for dr, dc in zip([1, 0], [0, 1]):
                nextr = posr + dr
                nextc = posc + dc
                if 0 <= nextr < row and 0 <= nextc < column:
                    n1 = map1[nextr][nextc]
                    n2 = map2[nextr][nextc]
                    nextqueue.append((nextr, nextc, red + n1, blue + n2))
                    nextqueue.append((nextr, nextc, red + n2, blue + n1))
        if nextqueue:
            queue = copy(nextqueue)
        else:
            return ansque

print(min(bfs(queue)))

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
	return sys.stdin.readline()[:-1]

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 for _ in range(W)] for _ in range(H)]
for h in range(H):
	for w in range(W):
		c[h][w] = abs(a[h][w] - b[h][w])

#print(*c, sep="\n")
s = [[set() for _ in range(W)] for _ in range(H)]
s[0][0].add(c[0][0])
for h in range(H):
	for w in range(W):
		for x in s[h][w]:
			if h < H-1:
				s[h+1][w].add(x + c[h+1][w])
				s[h+1][w].add(abs(x - c[h+1][w]))
			if w < W-1:
				s[h][w+1].add(x + c[h][w+1])
				s[h][w+1].add(abs(x - c[h][w+1]))

ans = 100000
for x in s[H-1][W-1]:
	ans = min(ans, abs(x))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################


H,W = II()
A = []
B = []
for i in range(H):
    A.append(III())
for i in range(H):
    B.append(III())

def calc(n):
    return n + (H+W-1)*80

d = [[[False]*(2*(H+W-1)*80+1) for _ in range(W)] for _ in range(H)]
for i in range(H):
    for j in range(W):
        if i==0 and j==0:
            d[i][j][calc(A[i][j]-B[i][j])] = True
            d[i][j][calc(-A[i][j]+B[i][j])] = True
        elif j==0:
            for k in range(2*(H+W-1)*80+1):
                if d[i-1][j][k]:
                    d[i][j][k+A[i][j]-B[i][j]] = True
                    d[i][j][k-A[i][j]+B[i][j]] = True
        elif i==0:
            for k in range(2*(H+W-1)*80+1):
                if d[i][j-1][k]:
                    d[i][j][k+A[i][j]-B[i][j]] = True
                    d[i][j][k-A[i][j]+B[i][j]] = True
        else:
            for k in range(2*(H+W-1)*80+1):
                if d[i-1][j][k]:
                    d[i][j][k+A[i][j]-B[i][j]] = True
                    d[i][j][k-A[i][j]+B[i][j]] = True
            for k in range(2*(H+W-1)*80+1):
                if d[i][j-1][k]:
                    d[i][j][k+A[i][j]-B[i][j]] = True
                    d[i][j][k-A[i][j]+B[i][j]] = True

ans = float('inf')
for i in range(2*(H+W-1)*80+1):
    if d[H-1][W-1][i]:
        now = abs(i-(H+W-1)*80)
        if ans>now:
            ans = now
print(ans)

Submission status: Time Limit Exceeded

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

bl = []
for _ in range(h):
    b = list(map(int,input().split()))
    bl.append(b)

abl = [[0 for _ in range(w)] for _ in range(h)]
for i in range(h):
    for j in range(w):
        abl[i][j] = al[i][j] - bl[i][j]

from collections import defaultdict
dic = defaultdict(set)

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

ans = float("inf")
for i in dic[(h-1, w-1)]:
    ans = min(abs(i), ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
A = []
for i in range(H):
  As = list(map(int, input().split()))
  A.append(As)
for i in range(H):
  As = A[i]
  Bs = list(map(int, input().split()))
  for j in range(W):
    A[i][j] = abs(As[j]-Bs[j])
#print(A)
C = [[set() for j in range(W)] for i in range(H)]
C[0][0].add(A[0][0])
for i in range(1, H):
  a = A[i][0]
  for c in C[i-1][0]:
    C[i][0].add(c+a)
    C[i][0].add(abs(c-a))
for j in range(1, W):
  a = A[0][j]
  for c in C[0][j-1]:
    C[0][j].add(c+a)
    C[0][j].add(abs(c-a))
for i in range(1, H):
  for j in range(1, W):
    a = A[i][j]
    for c in C[i-1][j]:
      C[i][j].add(c+a)
      C[i][j].add(abs(c-a))
    for c in C[i][j-1]:
      C[i][j].add(c+a)
      C[i][j].add(abs(c-a))
#print(C)
r = min(C[-1][-1])
print(r)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

h, w = list(map(int, input().split()))

field = [[None] * w for _ in range(h)]
aaa = [list(map(int, input().split())) for _ in range(h)]
bbb = [list(map(int, input().split())) for _ in range(h)]
aaa = np.array(aaa, dtype=np.int64)
bbb = np.array(bbb, dtype=np.int64)
diff = abs(aaa - bbb)

offset = 15000
can = np.zeros(30001, dtype=np.int64)
can[diff[0][0] + offset] = 1
field[0][0] = can


def merge_new_can(d, can, prev_can):
    if d == 0:
        can |= prev_can
    else:
        can[d:] |= prev_can[:-d]
        can[:-d] |= prev_can[d:]


for j in range(1, w):
    d = diff[0][j]
    prev_can = field[0][j - 1]
    can = np.zeros(30001, dtype=np.int64)
    merge_new_can(d, can, prev_can)
    field[0][j] = can

for i in range(1, h):
    d = diff[i][0]
    prev_can = field[i - 1][0]
    can = np.zeros(30001, dtype=np.int64)
    merge_new_can(d, can, prev_can)
    field[i][0] = can

for i in range(1, h):
    for j in range(1, w):
        d = diff[i][j]
        can = np.zeros(30001, dtype=np.int64)
        prev_can1 = field[i][j - 1]
        prev_can2 = field[i - 1][j]
        merge_new_can(d, can, prev_can1)
        merge_new_can(d, can, prev_can2)
        field[i][j] = can

goal = field[-1][-1]
goal[15001:] |= goal[:15000][::-1]
goal = goal[15000:]
print(np.argmax(goal))

Submission status: Time Limit Exceeded

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

bl = []
for _ in range(h):
    b = list(map(int,input().split()))
    bl.append(b)

abl = [[0 for _ in range(w)] for _ in range(h)]
for i in range(h):
    for j in range(w):
        abl[i][j] = al[i][j] - bl[i][j]

from collections import defaultdict
dic = defaultdict(set)

dic[(0,0)].add(abl[0][0])
dic[(0,0)].add(-abl[0][0])
for i in range(h):
    for j in range(w):
        for v in dic[(i,j)]:
            if j + 1 < w:
                dic[(i,j+1)].add(v+abl[i][j+1])
                dic[(i,j+1)].add(v-abl[i][j+1])
            if i + 1 < h:
                dic[(i+1,j)].add(v+abl[i+1][j])
                dic[(i+1,j)].add(v-abl[i+1][j])

ans = float("inf")
for i in dic[(h-1, w-1)]:
    ans = min(abs(i), ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
INF = 10**10

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

C = [[abs(a - b) for a, b in zip(rowA, rowB)] for rowA, rowB in zip(A, B)]

ans = INF
que = deque([(0, 0, 0)])
while que:
    cost, h, w = que.popleft()

    for c in (C[h][w], -C[h][w]):
        newCost = cost + c
        if h == H - 1 and w == W - 1:
            ans = min(ans, abs(newCost))
            continue

        if h < H - 1:
            que.append((newCost, h + 1, w))
        if w < W - 1:
            que.append((newCost, h, w + 1))

print(ans)

Submission status: Time Limit Exceeded

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

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
        a,b = A[y][x], B[y][x]
        d = a-b
        ns = set()
        if x > 0:
            s = dp[(x-1,y)]
            ns |= set(chain((abs(v+d) for v in s),
                            (abs(v-d) for v in s)))
        if y > 0:
            s = dp[(x,y-1)]
            ns |= set(chain((abs(v+d) for v in s),
                            (abs(v-d) for v in s)))
        ndp[(x,y)] = ns
    dp = ndp

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    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=[[[] for _ in range(w)] for _ in range(h)]
    dp[-1][-1].append(A[-1][-1]-B[-1][-1])
    dp[-1][-1].append(-A[-1][-1]+B[-1][-1])

    from itertools import product
    for i,j in product(range(h-1,-1,-1),range(w-1,-1,-1)):
        p=A[i][j]-B[i][j]
        if(i+1<h):
            for x in dp[i+1][j]:
                dp[i][j].append(x+p)
                dp[i][j].append(x-p)
        if(j+1<w):
            for x in dp[i][j+1]:
                dp[i][j].append(x+p)
                dp[i][j].append(x-p)

    print(min(*(abs(x) for x in dp[0][0])))
resolve()

Submission status: Time Limit Exceeded

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 for i in range(h)]
for i in range(h):
    for j in range(w):
        diff[i][j] = abs(a[i][j] - b[i][j])

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

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

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

Submission status: Time Limit Exceeded

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)
dp[0][0].add(-c)
for s in range(1, H+W):
    for b in range(W):
        a = s-b
        if a<0 or a>=H:
            continue
        c = C[a][b]
        if a>=1:
            for i in dp[a-1][b]:
                dp[a][b].add(i+c)
                dp[a][b].add(i-c)

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

Submission status: Time Limit Exceeded

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 for i in range(h)]
for i in range(h):
    for j in range(w):
        diff[i][j] = abs(a[i][j] - b[i][j])

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

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

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

Submission status: Time Limit Exceeded

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 = 3505*2
m = 3505

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



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

M[0][0][m+C[0][0]] = 1
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 range(l):
            if M[i][j][ii] == 1:
                if ii+C[i+1][j] < l:
                    M[i+1][j][ii+C[i+1][j]] = 1
                if ii-C[i+1][j] >= 0:
                    M[i+1][j][ii-C[i+1][j]] = 1
        V[i+1][j] -= 1
        if V[i+1][j]==0:
            Q.append([i+1,j])
    if j+1 < w:
        for ii in range(l):
            if M[i][j][ii] == 1:
                if ii+C[i][j+1] < l:
                    M[i][j+1][ii+C[i][j+1]] = 1
                if ii-C[i][j+1] >= 0:
                    M[i][j+1][ii-C[i][j+1]] = 1
        V[i][j+1] -= 1
        if V[i][j+1]==0:
            Q.append([i,j+1])
        
    
    s += 1

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

ans = 10**5
for i in range(len(M[-1][-1])):
    if M[-1][-1][i] == 1:
        ans = min(ans, abs(i-m))
print(ans)

Submission status: Time Limit Exceeded

Solution code:

# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline 
readlines = sys.stdin.readlines

#n = int(input())
h,w = [int(i) for i in readline().split()]

a = [[int(i) for i in readline().split()] for _ in range(h)]
b = [[int(i) for i in readline().split()] for _ in range(h)]


dp = [set() for _ in range(w)]
dp[0] = set([0])

#print(dp)
for i in range(h):
    ndp = [set() for _ in range(w)]
    for j in range(w):
        v = a[i][j] - b[i][j]
        #print(v)
        for c in dp[j]:
            ndp[j].add(abs(c+v))
            ndp[j].add(abs(c-v))
        if j:
            for c in ndp[j-1]:
                ndp[j].add(abs(c+v))
                ndp[j].add(abs(c-v))

    dp = ndp
    #print(dp)
    

print(min(dp[j]))

Submission status: Time Limit Exceeded

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]

LIMIT = 80 * 40 * 40
# 符号をどっちにするか選べる
dp = [[set() for _ in range(W)] for _ in range(H)]
dp[0][0] = {grid[0][0], -grid[0][0]}
for h, w in itertools.product(range(H), range(W)):
    g = grid[h][w]
    if h - 1 >= 0:
        for c in dp[h - 1][w]:
            if -LIMIT <= c + g <= LIMIT:
                dp[h][w].add(c + g)
            if -LIMIT <= c - g <= LIMIT:
                dp[h][w].add(c - g)
    if w - 1 >= 0:
        for c in dp[h][w - 1]:
            if -LIMIT <= c + g <= LIMIT:
                dp[h][w].add(c + g)
            if -LIMIT <= c - g <= LIMIT:
                dp[h][w].add(c - g)

ans = INF
for s in dp[-1][-1]:
    ans = min(ans, abs(s))

print(ans)

Submission status: Time Limit Exceeded

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 for i in range(H)]

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)] for i in range(H)]

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

def next(i,j):
    RET=[]
    if i+j<=6400:
        RET.append(i+j)
    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+1<H:
                DP[i+1][j].extend(next(k,SA[i+1][j]))
            if j+1<W:
                DP[i][j+1].extend(next(k,SA[i][j+1]))
                
print(min(DP[-1][-1]))