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
sa=[]
aa=[]
bb=[]
h,w=map(int,input().split())
for i in range(h):
	a=list(map(int,input().split()))
	aa.append(a)
for i in range(h):
	b=list(map(int,input().split()))
	bb.append(b)
for i in range(h):
	ttt=[]
	for j in range(w):
		ttt.append(abs(aa[i][j]-bb[i][j]))
	sa.append(ttt)
dp=[[[] for _ in range(w)]for _ in range(h)]
dp[0][0].append(sa[0][0])
for i in range(h-1):
	for j in range(len(dp[i][0])):
		if dp[i][0][j]+sa[i+1][0]<=80:
			dp[i+1][0].append(dp[i][0][j]+sa[i+1][0])
		if abs(dp[i][0][j]-sa[i+1][0])<=80:
			dp[i+1][0].append(abs(dp[i][0][j]-sa[i+1][0]))
		dp[i+1][0]=set(dp[i+1][0])
		dp[i+1][0]=list(dp[i+1][0])
for i in range(w-1):
	for j in range(len(dp[0][i])):
		if dp[0][i][j]+sa[0][i+1]<=10000:
			dp[0][i+1].append(dp[0][i][j]+sa[0][i+1])
		if abs(dp[0][i][j]-sa[0][i+1])<=10000:
			dp[0][i+1].append(abs(dp[0][i][j]-sa[0][i+1]))
		dp[0][i+1]=set(dp[0][i+1])
		dp[0][i+1]=list(dp[0][i+1])
for i in range(h-1):
	for k in range(w-1):
		for j in range(len(dp[i][k+1])):
			if dp[i][k+1][j]+sa[i+1][k+1]<=10000:
				dp[i+1][k+1].append(dp[i][k+1][j]+sa[i+1][k+1])
			if abs(dp[i][k+1][j]-sa[i+1][k+1])<=10000:
				dp[i+1][k+1].append(abs(dp[i][k+1][j]-sa[i+1][k+1]))
		for j in range(len(dp[i+1][k])):
			if dp[i+1][k][j]+sa[i+1][k+1]<=10000:
				dp[i+1][k+1].append(dp[i+1][k][j]+sa[i+1][k+1])
			if abs(dp[i+1][k][j]-sa[i+1][k+1])<=10000:
				dp[i+1][k+1].append(abs(dp[i+1][k][j]-sa[i+1][k+1]))
		dp[i+1][k+1]=set(dp[i+1][k+1])
		dp[i+1][k+1]=list(dp[i+1][k+1])
print(min(dp[-1][-1]))

Submission status: Time Limit Exceeded

Solution code:
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

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 = [[set() for j in range(w+1)]for i in range(h+1)]
DP[0][0].add((0,0))
for i in range(h+1):
    for j in range(w+1):
        for s,t in DP[i][j]:
            if i < h and j<w:
                q = b[i][j]-a[i][j]
                DP[i+1][j].add((s+q,t))
                DP[i+1][j].add((s,t+q))
                DP[i][j+1].add((s+q,t))
                DP[i][j+1].add((s,t+q))
s = DP[h-1][w] | DP[h][w-1]
ans = float("inf")
for i,j in s:
    ans = min(ans, abs(i-j))

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)]
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],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(i-c[x-1][y-1])
                if i+c[x-1][y-1]<=80*(h+w-x-y+1):
                    d[x][y].add(i+c[x-1][y-1])
print(abs(min(d[h][w],key=abs)))

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

dp = [[set() for j in range(w)] for i in range(h)]
dp[0][0].add(c[0][0])
for j in range(1, w):
  for num in dp[0][j-1]:
    dp[0][j].add(abs(c[0][j] - num))
    dp[0][j].add(c[0][j] + num)
for i in range(1, h):
  for num in dp[i-1][0]:
    dp[i][0].add(abs(c[i][0] - num))
    dp[i][0].add(c[i][0] + num)
for i in range(1, h):
  for j in range(1, w):
    for num in dp[i][j-1]:
      dp[i][j].add(abs(c[i][j] - num))
      dp[i][j].add(c[i][j] + num)
    for num in dp[i-1][j]:
      dp[i][j].add(abs(c[i][j] - num))
      dp[i][j].add(c[i][j] + num)
print(min(list(dp[-1][-1])))

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

    dp1 = [[set() for j in range(W)] for i in range(H)]
    dp2 = [[set() for j in range(W)] for i in range(H)]

    dist = H+W-3
    d1, d2 = (dist+1)//2, dist//2
#    print('d1:', d1, '/ d2:', d2)

    A, B = Ass[0][0], Bss[0][0]
    dp1[0][0] = set([abs(A-B)])
    for d in range(d1):
#        print('d:', d)
        for i in range(d+1):
            j = d-i
#            print((i, j))
            if 0 <= i+1 <= H-1 and 0 <= j <= W-1:
                A, B = Ass[i+1][j], Bss[i+1][j]
                for diff in dp1[i][j]:
                    dp1[i+1][j].add(abs(diff+A-B))
                    dp1[i+1][j].add(abs(diff+B-A))
            if 0 <= i <= H-1 and 0 <= j+1 <= W-1:
                A, B = Ass[i][j+1], Bss[i][j+1]
                for diff in dp1[i][j]:
                    dp1[i][j+1].add(abs(diff+A-B))
                    dp1[i][j+1].add(abs(diff+B-A))
#    for dpi in dp1:
#        print(dpi)
#    print()

    A, B = Ass[-1][-1], Bss[-1][-1]
    dp2[-1][-1] = set([abs(A-B)])
    for d in range(d2):
        for i0 in range(d+1):
            j0 = d-i0
            i, j = H-1-i0, W-1-j0
            if 0 <= i-1 <= H-1 and 0 <= j <= W-1:
                A, B = Ass[i-1][j], Bss[i-1][j]
                for diff in dp2[i][j]:
                    dp2[i-1][j].add(abs(diff+A-B))
                    dp2[i-1][j].add(abs(diff+B-A))
            if 0 <= i <= H-1 and 0 <= j-1 <= W-1:
                A, B = Ass[i][j-1], Bss[i][j-1]
                for diff in dp2[i][j]:
                    dp2[i][j-1].add(abs(diff+A-B))
                    dp2[i][j-1].add(abs(diff+B-A))
#    for dpi in dp2:
#        print(dpi)
#    print()

    ans = float('inf')
    d = d1
    for i in range(d+1):
        j = d-i
        if 0 <= i+1 <= H-1 and 0 <= j <= W-1:
            for diff1 in dp1[i][j]:
                for diff2 in dp2[i+1][j]:
                    diff = abs(diff1-diff2)
                    ans = min(ans, diff)
        if 0 <= i <= H-1 and 0 <= j+1 <= W-1:
            for diff1 in dp1[i][j]:
                for diff2 in dp2[i][j+1]:
                    diff = abs(diff1-diff2)
                    ans = min(ans, diff)

    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)]
g=[[0]*w for _ in range(h)]
import sys
sys.setrecursionlimit(10**9)
for i in range(h):
    for j in range(w):
        g[i][j]=abs(a[i][j]-b[i][j])
c=g[0][0]
dyx=[(1,0),(0,1)]
ans=[float("inf")]
def dfs(y,x,c):
    if y==h-1 and x==w-1:
        ans[0]=min(ans[0],min(abs(c+g[y][x]),abs(c-g[y][x])))
    for dy,dx in dyx:
        ny=y+dy
        nx=x+dx
        if 0<=ny<h and 0<=nx<w:
            dfs(ny,nx,c+g[y][x])
            dfs(ny,nx,c-g[y][x])
dfs(0,0,c)
print(ans[0])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, heapq, collections, bisect,copy
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
sys.setrecursionlimit(10**7)
inf = float('inf')
mod = 10**9+7
ans = inf ;count = 0 ;pro = 1

h,w=map(int,input().split())
A=[tuple(map(int,input().split())) for i in range(h)]
B=[tuple(map(int,input().split())) for i in range(h)]
a=[set() for j in range(w)]
dp=[copy.deepcopy(a) for i in range(h)]
dp[0][0].add(abs(A[0][0]-B[0][0]))
for i in range(h):
    for j in range(w):
        d=abs(A[i][j]-B[i][j])
        if i-1>=0:
            for si in dp[i-1][j]:
                if si+d<=6500:
                    dp[i][j].add(si+d)
                if abs(si-d)<=6500:
                    dp[i][j].add(abs(si-d))
        if j-1>=0:
            for si in dp[i][j-1]:
                if si+d <= 6500:
                    dp[i][j].add(si+d)
                if abs(si-d) <= 6500:
                    dp[i][j].add(abs(si-d))
ans=min(dp[h-1][w-1])
print(ans)
# for di in dp:
#     print(di)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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 = np.zeros((h,w),dtype="int")
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 = 6600
m = 0
 
M = np.zeros((h,w,l),dtype="int")
N = np.zeros((h,w),dtype="int")
N[0][0] = C[0][0]
 
s = 0
Q = [[0, 0]]
 
M[0][0][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(min(N[i][j]+1, l)):
            if M[i][j][ii] == 1:
                if abs(ii+C[i+1][j]) < l:
                    M[i+1][j][abs(ii+C[i+1][j])] = 1
                if abs(ii-C[i+1][j]) < l:
                    M[i+1][j][abs(ii-C[i+1][j])] = 1
        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 range(min(N[i][j]+1, l)):
            if M[i][j][ii] == 1:
                if abs(ii+C[i][j+1]) < l:
                    M[i][j+1][abs(ii+C[i][j+1])] = 1
                if abs(ii-C[i][j+1]) < l:
                    M[i][j+1][abs(ii-C[i][j+1])] = 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])
 
ans = 10**5
for i in range(len(M[-1][-1])):
    if M[-1][-1][i] == 1:
        ans = i
        break
print(ans)

Submission status: Time Limit Exceeded

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

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

    xss = [[int(x) for x in input().split()] for _ in range(h)]
    yss = [[int(y) for y in input().split()] for _ in range(h)]
    uss = [[x - y for x, y in zip(xs, ys)] for xs, ys in zip(xss, yss)]

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

    dp[0][0].add(uss[0][0])
    dp[0][0].add(-uss[0][0])

    for i in range(1, w):
        for d in dp[0][i-1]:
            dp[0][i].add(d + uss[0][i])
            dp[0][i].add(d - uss[0][i])
    for i in range(1, h):
        for d in dp[i-1][0]:
            dp[i][0].add(d + uss[i][0])
            dp[i][0].add(d - uss[i][0])
    
    for i in range(1, h):
        for j in range(1, w):
            for d in dp[i-1][j]:
                dp[i][j].add(d + uss[i][j])
                dp[i][j].add(d - uss[i][j])
            for d in dp[i][j-1]:
                dp[i][j].add(d + uss[i][j])
                dp[i][j].add(d - uss[i][j])
    ans = sorted(abs(d) for d in dp[-1][-1])
    print(ans[0])

main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    def dfs(i=0, j=0, s=-1):
        if s==-1:s=cc[0][0]
        if (i, j) == (h - 1, w - 1):
            return s
        res = inf
        for di, dj in [(1, 0), (0, 1)]:
            ni, nj = i + di, j + dj
            if ni == h or nj == w: continue
            res = min(res, abs(dfs(ni, nj, s + cc[ni][nj])))
            res = min(res, abs(dfs(ni, nj, s - cc[ni][nj])))
        return res

    inf = 10 ** 16
    h, w = MI()
    aa = LLI(h)
    bb = LLI(h)
    cc = [[a - b for a, b in zip(ar, br)] for ar, br in zip(aa, bb)]
    #p2D(cc)
    print(dfs())
main()

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
A_ = []
B_ = []
for i in range(H):
  As = list(map(int, input().split()))
  A_.append(As)
for i in range(H):
  Bs = list(map(int, input().split()))
  B_.append(Bs)
A = []
for i in range(H):
  l = []
  for j in range(W):
    l.append(abs(A_[i][j]-B_[i][j]))
  A.append(l)
#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(0, H):
  for j in range(0, W):
    a = A[i][j]
    if i > 0:
      for c in C[i-1][j]:
        C[i][j].add(c+a)
        C[i][j].add(abs(c-a))
    if j > 0:
      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:
H,W = map(int,input().split())
A = [list(map(int,input().split())) for _ in [0]*H]
B = [list(map(int,input().split())) for _ in [0]*H]


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

d = [[set() for _ in [0]*W] for _ in [0]*H]
d[0][0] = {C[0][0]}

for i in range(H):
    for j in range(W):
        for n in d[i][j]:
            if i+1<H:
                c = C[i+1][j]
                d[i+1][j].add(n+c)
                d[i+1][j].add(abs(n-c))
            if j+1<W:
                c = C[i][j+1]
                d[i][j+1].add(n+c)
                d[i][j+1].add(abs(n-c))
ans = min(abs(o) for o in d[-1][-1])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
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(abs(k+a[i][j]))
                tmp.add(abs(k-a[i][j]))
        if j!=0:
            for k in dp[i][j-1]:
                tmp.add(abs(k+a[i][j]))
                tmp.add(abs(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(min(ls))

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline

ri = lambda: int(input())
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]

h, w = ril()
ls0 = rils(h)
ls1 = rils(h)

nums = [[set() for _ in range(w)] for _ in range(h)]
nums[0][0].add(abs(ls0[0][0] - ls1[0][0]))
for i in range(h):
    for j in range(w):
        x = abs(ls0[i][j] - ls1[i][j])
        if i > 0 and j > 0:
            s = nums[i - 1][j] | nums[i][j - 1]
            for y in s:
                nums[i][j].add(abs(x + y))
                nums[i][j].add(abs(x - y))
        elif i > 0:
            for y in nums[i - 1][j]:
                nums[i][j].add(abs(x + y))
                nums[i][j].add(abs(x - y))
        elif j > 0:
            for y in nums[i][j - 1]:
                nums[i][j].add(abs(x + y))
                nums[i][j].add(abs(x - y))
print(min(nums[h - 1][w - 1]))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque

def solve(H: int, W: int, A: "List[List[int]]", B: "List[List[int]]"):
    state = [[[0 for d in range(6401)] for w in range(W)] for h in range(H)]
    grid = [[abs(A[h][w]-B[h][w]) for w in range(W)] for h in range(H)]
    todo = deque()
    for d in range(6401):
        state[H-1][W-1][d] = min(abs(d-grid[H-1][W-1]), abs(d+grid[H-1][W-1]))
    done = set((H-1, W-1))
    todo.append((H-1, W-2))
    todo.append((H-2, W-1))

    while len(todo) > 0:
        h, w = todo.popleft()
        if (h, w) in done:
            continue
        for d in range(6401):
            res_c = 9999
            for diff in (abs(d-grid[h][w]), abs(d+grid[h][w])):
                if diff > 6400:
                    continue
                if h+1 < H:
                    res_c = min(res_c, state[h+1][w][diff])
                if w+1 < W:
                    res_c = min(res_c, state[h][w+1][diff])
            state[h][w][d] = res_c
        if h > 0:
            todo.append((h-1, w))
        if w > 0:
            todo.append((h, w-1))
        done.add((h, w))
    print(state[0][0][0])

    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    A = [[int(next(tokens)) for _ in range(W)] for _ in range(H)]  # type: "List[List[int]]"
    B = [[int(next(tokens)) for _ in range(W)] for _ in range(H)]  # type: "List[List[int]]"
    solve(H, W, A, B)

if __name__ == '__main__':
    main()

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 = [[abs(A[i][j] - B[i][j]) for j in range(W)] for i in range(H)]

# [print(c_i) for c_i in c]

dp = [[[0 for _ in range(90)] for _ in range(W)] for _ in range(H)]
dp[0][0][c[0][0]] = 1

q = deque([(0, 0)])
while q:
    tx, ty = q.popleft()
    tdp = dp[ty][tx]

    for dx, dy in [(0, 1), (1, 0)]:
        nx, ny = tx+dx, ty+dy
        if not (0 <= nx < W and 0 <= ny < H):
            continue
        nc = c[ny][nx]
        for i, m in enumerate(tdp):
            if m == 0:
                continue
            if abs(i-nc) <= 80:
                dp[ny][nx][abs(i-nc)] = 1
            if abs(i+nc) <= 80:
                dp[ny][nx][abs(i+nc)] = 1
            # print((nx, ny), dp[ny][nx])
        q.append((nx, ny))
        # print((nx, ny))

# [[print(j, i, dp_j) for j, dp_j in enumerate(dp_i)] for i, dp_i in enumerate(dp)]

print(dp[H-1][W-1].index(1))

Submission status: Time Limit Exceeded

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

A_list = []
for _ in range(H):
	A_list.append(list(map(int, input().split())))

B_list = []
for _ in range(H):
	B_list.append(list(map(int, input().split())))

values = None
for h in range(H):
	new_values = []
	for w in range(W):
		prev_values = set()
		if h == 0 and w == 0:
			prev_values.add(0)
		else:
			if w > 0:
				prev_values |= new_values[w - 1]
			if h > 0:
				prev_values |= values[w]
		value = A_list[h][w] - B_list[h][w]
		new_set = set()
		for v in prev_values:
#			print(v, value)
			new_set.add(v + value)
			new_set.add(v - value)
		new_values.append(new_set)
	values = new_values
#	print(values)

print(min(map(abs, values[W - 1])))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, heapq, collections, bisect,copy
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
sys.setrecursionlimit(10**7)
inf = float('inf')
mod = 10**9+7
ans = inf ;count = 0 ;pro = 1

h,w=map(int,input().split())
A=[tuple(map(int,input().split())) for i in range(h)]
B=[tuple(map(int,input().split())) for i in range(h)]
a=[[] for j in range(w)]
dp=[copy.deepcopy(a) for i in range(h)]
dp[0][0].append(abs(A[0][0]-B[0][0]))
for i in range(h):
    for j in range(w):
        d=abs(A[i][j]-B[i][j])
        if i-1>=0:
            for si in dp[i-1][j]:
                dp[i][j].append(si+d)
                dp[i][j].append(abs(si-d))
        if j-1>=0:
            for si in dp[i][j-1]:
                dp[i][j].append(si+d)
                dp[i][j].append(abs(si-d))
ans=min(dp[h-1][w-1])
print(ans)
# for di in dp:
#     print(di)

Submission status: Time Limit Exceeded

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<=80*80:
                    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: 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)]
# abs(A - B)
S = [[abs(a - b) for a, b in zip(A[n], B[n])] for n in range(H)]

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

setS[0][0].add(S[0][0])

for i in range(H):
    for j in range(W):
        if i == 0 and j == 0:
           continue
        if i > 0:
            for a in list(setS[i-1][j]):
                if a + S[i][j] <= 80 * (160 - (i + j)):
                    setS[i][j].add(abs(a + S[i][j]))
                setS[i][j].add(abs(a - S[i][j]))
        if j > 0:
            for a in list(setS[i][j-1]):
                if a + S[i][j] <= 80 * (160 - (i + j)):
                    setS[i][j].add(abs(a + S[i][j]))
                setS[i][j].add(abs(a - S[i][j]))

print(min(setS[H-1][W-1]))

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)]
d=[[[0]*80*H*W for i in range(W+1)] for j in range(H+1)]
d[1][1][A[0][0]-B[0][0]]=d[1][1][B[0][0]-A[0][0]]=1
for h in range(H):
    for w in range(W):
        x=A[h][w]-B[h][w]
        for y in range(80*H*W):
            if d[h][w+1][y] or d[h+1][w][y]:
                d[h+1][w+1][(y+x)%(80*H*W)]=d[h+1][w+1][(y-x)%(80*H*W)]=1
for i in range(40*H*W):
    if d[H][W][i] or d[H][W][-i]:
        print(i)
        exit()

Submission status: Time Limit Exceeded

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<=80*80*40:
                    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: 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 = [[[0 for i in range(12801)] for _ in range(w)] for _ in range(h)]

dic[0][0][abl[i][j] + 6400] = 1
dic[0][0][-abl[i][j]+ 6400] = 1

for i in range(h):
    for j in range(w):
        for v, t in enumerate(dic[i][j]):
            if t == 1:
                if j + 1 < w:
                    if 0 <= v+abl[i][j+1] <= 12800:
                        dic[i][j+1][v+abl[i][j+1]] = 1
                    if 0 <= v-abl[i][j+1] <= 12800:
                        dic[i][j+1][v-abl[i][j+1]] = 1
                if i + 1 < h:
                    if 0 <=v+abl[i+1][j] <= 12800:
                        dic[i+1][j][v+abl[i+1][j]] = 1
                    if 0 <= v-abl[i+1][j] <= 12800:
                        dic[i+1][j][v-abl[i+1][j]] = 1

ans = float("inf")
for idx,i in enumerate(dic[-1][-1]):
    if i == 1:
        ans = min(ans, abs(idx-6401))
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 = [[abs(A[h][w]-B[h][w]) for w in range(W)] for h in range(H)]
    dp = [[[False for _ in range(6401)] for w in range(W)] for h in range(H)]

    dp[0][0][D[0][0]] = True

    for h in range(1,H):
        for i in range(6401):
            if dp[h-1][0][i]:
                dp[h][0][abs(i-D[h][0])] = True
                if i+D[h][0]<6401:
                    dp[h][0][i+D[h][0]] = True
    for w in range(1,W):
        for i in range(6401):
            if dp[0][w-1][i]:
                dp[0][w][abs(i-D[0][w])] = True
                if i+D[0][w]<6401:
                    dp[0][w][i+D[0][w]] = True

    for h in range(1,H):
        for w in range(1,W):
            for i in range(6401):
                if dp[h-1][w][i]:
                    dp[h][w][abs(i-D[h][w])] = True
                    if i+D[h][w]<6401:
                        dp[h][w][i+D[h][w]] = True
                if dp[h][w-1][i]:
                    dp[h][w][abs(i-D[h][w])] = True
                    if i+D[h][w]<6401:
                        dp[h][w][i+D[h][w]] = True

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

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+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 * 80 + 1
dp = [[False]*n for i in range(h*w)]
dp[0][diff[0][0]] = True

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

                if j+1 < w:
                    dp[k + 1][abs(cnt - tmp2)] = True 
                    if cnt + tmp2 < n:
                        dp[k + 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: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
def f():
    h,w=[int(j) for j in input().split()]
    a=[]
    b=[]
    for i in range(h):
        a.append([int(j) for j in input().split()])
    for i in range(h):
        b.append([int(j) for j in input().split()])
    l=[[] for i in range(h)]
    for i in range(h):
        for j in range(w):
            l[i].append(abs(a[i][j]-b[i][j]))
    ans=[[set() for j in range(w)] for i in range(h)]
    ans[0][0].add(l[0][0])
    for i in range(h):
        for j in range(w):
            for k in ans[i][j]:
                if i+1<h:
                    ans[i+1][j].add(k+l[i+1][j])
                    ans[i+1][j].add(k-l[i+1][j])
                if j+1<w:
                    ans[i][j+1].add(k+l[i][j+1])
                    ans[i][j+1].add(k-l[i][j+1])
    a=10**18
    for i in ans[h-1][w-1]:
        a=min(abs(i),a)
    print(a)

f()