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:
def solve():
    import numpy as np
    from sys import stdin
    f_i = stdin
    
    H, W = map(int, f_i.readline().split())
    A = tuple(tuple(map(int, f_i.readline().split())) for i in range(H))
    B = tuple(tuple(map(int, f_i.readline().split())) for i in range(H))
    
    max_bias = 80 * (W - 1) * (H - 1)
    dp1 = np.full((W, max_bias), False)
    dp1[0][0] = True
    for A_i, B_i in zip(A, B):
        dp2 = np.full((W, max_bias), False)
        diff = A_i[0] - B_i[0]
        for pre_bias in np.where(dp1[0] == True):
            dp2[0][abs(pre_bias + diff)] = True
            dp2[0][abs(pre_bias - diff)] = True
        
        for j, t in enumerate(zip(A_i[1:], B_i[1:]), start=1):
            A_ij, B_ij = t
            diff = A_ij - B_ij
            for pre_bias in np.where(dp1[j] == True):
                dp2[j][abs(pre_bias + diff)] = True
                dp2[j][abs(pre_bias - diff)] = True
            for pre_bias in np.where(dp2[j-1] == True):
                dp2[j][abs(pre_bias + diff)] = True
                dp2[j][abs(pre_bias - diff)] = True
        dp1 = dp2
    
    print(np.where(dp2[-1] == True)[0][0])#
 
solve()

Submission status: Time Limit Exceeded

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

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

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


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


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


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


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


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


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


def mt(f):
    import time

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

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

    return wrap


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

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

    # for r in dp:
    #     print(r)

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


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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

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


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


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


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


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


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


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


def mt(f):
    import time

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

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

    return wrap


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

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

    # for r in dp:
    #     print(r)

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


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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
As = []
Bs = []
for i in range(H):
	As.append(list(map(int, input().split())))
for i in range(H):
	Bs.append(list(map(int, input().split())))

mem = [[[False] * 12801 for w in range(W)] for h in range(H)]
mem[0][0][abs(As[0][0] - Bs[0][0])] = True
for h in range(H):

	for w in range(W):

		for k in range(12801):
			if mem[h][w][k]:
				if h < H - 1:
					mem[h + 1][w][k + abs(As[h + 1][w] - Bs[h + 1][w])] = True
					mem[h + 1][w][abs(k - abs(As[h + 1][w] - Bs[h + 1][w]))] = True
				if w < W - 1:
					mem[h][w + 1][k + abs(As[h][w + 1] - Bs[h][w + 1])] = True
					mem[h][w + 1][abs(k - abs(As[h][w + 1] - Bs[h][w + 1]))] = True

else:
	for k in range(12801):
		if mem[h][w][k]:
			print(k)
			exit()

Submission status: Time Limit Exceeded

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

solve()

Submission status: Time Limit Exceeded

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

solve()

Submission status: Time Limit Exceeded

Solution code:
# E - Balanced Path

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

assert all(len(row) == W for row in A)
assert all(len(row) == W for row in B)

# そのマスを通過したときの赤・青の差 (の絶対値)
table = [[set() for j in range(W)] for i in range(H)]

table[0][0].add(abs(A[0][0] - B[0][0]))

for i in range(H):
    for j in range(W):
        prev  = table[i - 1][j] if i > 0 else set()
        prev |= table[i][j - 1] if j > 0 else set()
        for pdiff in prev:
            diff = A[i][j] - B[i][j]
            table[i][j].add(abs(pdiff + diff))
            table[i][j].add(abs(pdiff - diff))

m = min(diff for diff in table[H - 1][W - 1])
print(m)

Submission status: Time Limit Exceeded

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

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

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


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

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

            for k in ks:
                if k < ma:
                    s.add(k+t)
                if k > -ma:
                    s.add(k-t)

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


print(main())

Submission status: Time Limit Exceeded

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

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

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


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

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

            for k in ks:
                if k < ma:
                    s.add(k+t)
                if k > -ma:
                    s.add(k-t)

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


print(main())

Submission status: Time Limit Exceeded

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

H,W = map(int,input().split())
#差分だけで良い，これを*1 or -1していく
diff = [list(map(int, input().split())) for _ in range(H)]

for i in range(H):
    B = list(map(int,input().split()))
    for j in range(W):
        diff[i][j] = abs(diff[i][j] - B[j])
        
 # i,jマスにおいて，偏りがkになれるかどうかでDP
K = 4001 #適当
kk = int((K-1)/2)
dp = [[[False]*K for _ in range(W)] for _ in range(H)]
 
dp[0][0][kk+diff[0][0]] = True
dp[0][0][kk-diff[0][0]] = True
 
for i in range(H):
    for j in range(W):
        a= min((i+j)*80,kk)
        for k in range(kk-a,kk+a+1):
            if i-1>=0:
                if k+diff[i][j]<K:
                    if dp[i-1][j][k+diff[i][j]]:
                        dp[i][j][k] =True
                if k-diff[i][j]>=0:
                    if dp[i-1][j][k-diff[i][j]]:
                        dp[i][j][k] =True
            if j-1>=0:
                if k+diff[i][j]<K:
                    if dp[i][j-1][k+diff[i][j]]:
                        dp[i][j][k] =True
                if k-diff[i][j]>=0:
                    if dp[i][j-1][k-diff[i][j]]:
                        dp[i][j][k] =True
ans = K

for k in range(K):
    if dp[-1][-1][k]:
        ans = min(ans,abs(k-kk))
print(ans)

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)]
 
#差分だけで良い，これを*1 or -1していく
diff = [[0]*W for _ in range(H)]
for i in range(H):
    for j in range(W):
        diff[i][j] = abs(A[i][j] - B[i][j])
        
 # i,jマスにおいて，偏りがkになれるかどうかでDP
K = 6401 #適当
kk = int((K-1)/2)
dp = [[[False]*K for _ in range(W)] for _ in range(H)]
 
dp[0][0][kk+diff[0][0]] = True
dp[0][0][kk-diff[0][0]] = True
 

for i in range(H):
    for j in range(W):
        a= min((i+j)*80,kk)
        for k in range(kk-a,kk+a+1):
            if i-1>=0:
                if k+diff[i][j]<K:
                    if dp[i-1][j][k+diff[i][j]]:
                        dp[i][j][k] =True
                if k-diff[i][j]>=0:
                    if dp[i-1][j][k-diff[i][j]]:
                        dp[i][j][k] =True
            if j-1>=0:
                if k+diff[i][j]<K:
                    if dp[i][j-1][k+diff[i][j]]:
                        dp[i][j][k] =True
                if k-diff[i][j]>=0:
                    if dp[i][j-1][k-diff[i][j]]:
                        dp[i][j][k] =True
ans = K


for k in range(K):
    if dp[H-1][W-1][k]:
        ans = min(ans,abs(k-kk))
print(ans)

Submission status: Time Limit Exceeded

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

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

for h in range(H):
    for w in range(W):
        A[h][w]=abs(A[h][w]-B[h][w])

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

#初期化
r,c=0,0
val=A[r][c]
dp[r][c].add(val)
dp[r][c].add(val*-1)

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

for r in range(H):
    for c in range(W):
        for dr,dc in D: #横に1つ移動か、下に1つ移動
            if r+dr<H and c+dc<W:   #移動しようとするマスが存在するならばif文内の処理を行う
                next_r=r+dr
                next_c=c+dc
                next_val=A[next_r][next_c]
                for j in dp[r][c]:
                    dp[next_r][next_c].add(j+next_val)
                    dp[next_r][next_c].add(j+next_val*-1)

print min(map(lambda x: abs(x), dp[H-1][W-1]))

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

#差分だけで良い，これを*1 or -1していく
diff = [[0]*W for _ in range(H)]
for i in range(H):
    for j in range(W):
        diff[i][j] = abs(A[i][j] - B[i][j])

#i,jマスにおいて，偏りがkになれるかどうかでDP
K = 4001 #適当
kk = int((K-1)/2)
dp = [[[False]*K for _ in range(W)] for _ in range(H)]

dp[0][0][kk+diff[0][0]] = True
dp[0][0][kk-diff[0][0]] = True

                 

for i in range(H):
    for j in range(W):
        for k in range(K):
            if i-1>=0:
                if k+diff[i][j]<K:
                    if dp[i-1][j][k+diff[i][j]]:
                        dp[i][j][k] =True
                if k-diff[i][j]>=0:
                    if dp[i-1][j][k-diff[i][j]]:
                        dp[i][j][k] =True
            if j-1>=0:
                if k+diff[i][j]<K:
                    if dp[i][j-1][k+diff[i][j]]:
                        dp[i][j][k] =True
                if k-diff[i][j]>=0:
                    if dp[i][j-1][k-diff[i][j]]:
                        dp[i][j][k] =True

ans = K
for k in range(K):
    if dp[H-1][W-1][k]:
        ans = min(ans,abs(k-kk))

print(ans)

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


#差分だけで良い，これを*1 or -1していく
diff = [[0]*W for _ in range(H)]
for i in range(H):
    for j in range(W):
        diff[i][j] = abs(A[i][j] - B[i][j])

#i,jマスにおいて，偏りがkになれるかどうかでDP
K = 6401 #適当,[-3200,3200]
kk = int((K-1)/2)
dp = [[[False]*K for _ in range(W)] for _ in range(H)]

dp[0][0][kk+diff[0][0]] = True
dp[0][0][kk-diff[0][0]] = True

for i in range(H):
    for j in range(W):
        for k in range(K):
            if i-1>=0:
                if k+diff[i][j]<K:
                    if dp[i-1][j][k+diff[i][j]]:
                        dp[i][j][k] =True
                if k-diff[i][j]>=0:
                    if dp[i-1][j][k-diff[i][j]]:
                        dp[i][j][k] =True
            if j-1>=0:
                if k+diff[i][j]<K:
                    if dp[i][j-1][k+diff[i][j]]:
                        dp[i][j][k] =True
                if k-diff[i][j]>=0:
                    if dp[i][j-1][k-diff[i][j]]:
                        dp[i][j][k] =True

ans = K
for k in range(K):
    if dp[H-1][W-1][k]:
        ans = min(ans,abs(k-kk))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, raw_input().split())
A = []
B = []
for h in range(H):
    A_hj = map(int, raw_input().split())
    A.append(A_hj)
for h in range(H):
    B_hj = map(int, raw_input().split())
    B.append(B_hj)

dp = [[set() for _ in range(W)] for _ in range(H)]
dp[0][0] = {abs(A[0][0] - B[0][0])}
for i in range(H):
    for j in range(W):
        if i == 0 and j == 0: continue
        d = abs(A[i][j] - B[i][j])
        possible = set()
        if i-1 >= 0:
            for diff in dp[i-1][j]:
                possible.add(abs(diff+d))
                possible.add(abs(diff-d))
        if j-1 >= 0:
            for diff in dp[i][j-1]:
                possible.add(abs(diff+d))
                possible.add(abs(diff-d))
        dp[i][j] = {d for d in possible if d <= 6400}

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque
H,W=map(int, sys.stdin.readline().split())

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

for h in range(H):
    for w in range(W):
        A[h][w]=abs(A[h][w]-B[h][w])

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

Center=80*80      #中心地のセット マイナスの値もセットできるようにbitsetのゼロを80*80+1桁目に置く

#初期化
r,c=0,0
val=A[r][c]
dp[r][c]=1<<val+Center

q=deque()
q.append((0,0))
D=[(1,0),(0,1)]
Visit={}    #訪問済みの頂点にフラグ1を立てる
Visit[(0,0)]=1

while q:
    r,c=q.popleft()
    for dr,dc in D:
        if r+dr<H and c+dc<W:
            next_r=r+dr
            next_c=c+dc
            next_val=A[next_r][next_c]
            dp[next_r][next_c]|=dp[r][c]<<next_val
            dp[next_r][next_c]|=dp[r][c]>>next_val
            Visit[(next_r,next_c)]=1    #次の頂点をキューに入れたら、訪問済みに印をつける
            q.append((next_r,next_c))

ans=float("inf")
for i in range(80*80*2):
    bit=dp[H-1][W-1]>>i&1
    if bit==1:
        ans=min(ans,abs(i-Center))

print ans

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque
H,W=map(int, sys.stdin.readline().split())

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

for h in range(H):
    for w in range(W):
        A[h][w]=abs(A[h][w]-B[h][w])

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

Center=80*80      #中心地のセット マイナスの値もセットできるようにbitsetのゼロを80*80+1桁目に置く

#初期化
r,c=0,0
val=A[r][c]
dp[r][c]=1<<val+Center

q=deque()
q.append((0,0))
D=[(1,0),(0,1)]
Visit={}    #訪問済みの頂点にフラグ1を立てる
Visit[(0,0)]=1

while q:
    r,c=q.popleft()
    for dr,dc in D:
        if r+dr<H and c+dc<W:
            next_r=r+dr
            next_c=c+dc
            next_val=A[next_r][next_c]
            dp[next_r][next_c]|=dp[r][c]<<next_val
            dp[next_r][next_c]|=dp[r][c]>>next_val
            q.append((next_r,next_c))
            Visit[(next_r,next_c)]=1    #次の頂点をキューに入れたら、訪問済みに印をつける

ans=float("inf")
for i in range(80*80*2):
    bit=dp[H-1][W-1]>>i&1
    if bit==1:
        ans=min(ans,abs(i-Center))

print ans

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque
H,W=map(int, sys.stdin.readline().split())

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

for h in range(H):
    for w in range(W):
        A[h][w]=abs(A[h][w]-B[h][w])

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

Center=80*80      #中心地のセット マイナスの値もセットできるようにbitsetのゼロを80*80+1桁目に置く

#初期化
r,c=0,0
val=A[r][c]
dp[r][c]=1<<val+Center

q=deque()
q.append((0,0))
D=[(1,0),(0,1)]

while q:
    r,c=q.popleft()
    for dr,dc in D:
        if r+dr<H and c+dc<W:
            next_r=r+dr
            next_c=c+dc
            next_val=A[next_r][next_c]
            dp[next_r][next_c]|=dp[r][c]<<next_val
            dp[next_r][next_c]|=dp[r][c]>>next_val
            q.append((next_r,next_c))

ans=float("inf")
for i in range(80*80*2):
    bit=dp[H-1][W-1]>>i&1
    if bit==1:
        ans=min(ans,abs(i-Center))

print ans

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
h, w = map(int, input().split())
grid = []
bias_inf = 2000
for i in range(h):
    k = list(map(int, input().split()))
    grid.append(k)
for i in range(h):
    k = list(map(int, input().split()))
    for j in range(w):
        grid[i][j] = abs(grid[i][j] - k[j])

dp = [[[False for i in range(-bias_inf,bias_inf)] for j in range(w)] for k in range(h)]
dp[0][0][0 - grid[0][0]] = True
dp[0][0][0 + grid[0][0]] = True
for i in range(h):
    for j in range(w):
        for k in range(-bias_inf,bias_inf):
            if i == h-1 and j == w-1:
                break
            if dp[i][j][k]:
                if i != h-1 and j != w-1:
                    dp[i][j+1][k + grid[i][j+1]] = True
                    dp[i+1][j][k + grid[i+1][j]] = True
                    dp[i][j+1][k - grid[i][j+1]] = True
                    dp[i+1][j][k - grid[i+1][j]] = True
                elif j == w-1:
                    dp[i+1][j][k - grid[i+1][j]] = True
                    dp[i+1][j][k + grid[i+1][j]] = True
                else:
                    dp[i][j+1][k - grid[i][j+1]] = True
                    dp[i][j+1][k + grid[i][j+1]] = True
ans = bias_inf
for i in range(-bias_inf,bias_inf):
    if dp[-1][-1][i]:
        ans = min(ans, abs(i))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
input = sys.stdin.readline
h, w = map(int, input().split())
grid = []
bias_inf = 2000
for i in range(h):
    k = list(map(int, input().split()))
    grid.append(k)
for i in range(h):
    k = list(map(int, input().split()))
    for j in range(w):
        grid[i][j] = abs(grid[i][j] - k[j])

dp = np.full((h,w,bias_inf*2), False)
dp[0][0][0 - grid[0][0]] = True
dp[0][0][0 + grid[0][0]] = True
for i in range(h):
    for j in range(w):
        for k in range(-bias_inf,bias_inf):
            if i == h-1 and j == w-1:
                break
            if dp[i][j][k]:
                if i == h-1:
                    dp[i][j+1][k - grid[i][j+1]] = True
                    dp[i][j+1][k + grid[i][j+1]] = True
                elif j == w-1:
                    dp[i+1][j][k - grid[i+1][j]] = True
                    dp[i+1][j][k + grid[i+1][j]] = True
                else:
                    dp[i][j+1][k + grid[i][j+1]] = True
                    dp[i+1][j][k + grid[i+1][j]] = True
                    dp[i][j+1][k - grid[i][j+1]] = True
                    dp[i+1][j][k - grid[i+1][j]] = True
ans = bias_inf
for i in range(-bias_inf,bias_inf):
    if dp[-1][-1][i]:
        ans = min(ans, abs(i))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
h, w = map(int, input().split())
grid = []
bias_inf = 2000
for i in range(h):
    k = list(map(int, input().split()))
    grid.append(k)
for i in range(h):
    k = list(map(int, input().split()))
    for j in range(w):
        grid[i][j] = abs(grid[i][j] - k[j])

dp = [[[False for i in range(-bias_inf,bias_inf)] for j in range(w)] for k in range(h)]
dp[0][0][0 - grid[0][0]] = True
dp[0][0][0 + grid[0][0]] = True
for i in range(h):
    for j in range(w):
        for k in range(-bias_inf,bias_inf):
            if i == h-1 and j == w-1:
                break
            if dp[i][j][k]:
                if i == h-1:
                    dp[i][j+1][k - grid[i][j+1]] = True
                    dp[i][j+1][k + grid[i][j+1]] = True
                elif j == w-1:
                    dp[i+1][j][k - grid[i+1][j]] = True
                    dp[i+1][j][k + grid[i+1][j]] = True
                else:
                    dp[i][j+1][k + grid[i][j+1]] = True
                    dp[i+1][j][k + grid[i+1][j]] = True
                    dp[i][j+1][k - grid[i][j+1]] = True
                    dp[i+1][j][k - grid[i+1][j]] = True
ans = bias_inf
for i in range(-bias_inf,bias_inf):
    if dp[-1][-1][i]:
        ans = min(ans, abs(i))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
grid = []
bias_inf = 2000
for i in range(h):
    k = list(map(int, input().split()))
    grid.append(k)
for i in range(h):
    k = list(map(int, input().split()))
    for j in range(w):
        grid[i][j] = abs(grid[i][j] - k[j])

dp = [[[False for i in range(-bias_inf,bias_inf)] for j in range(w)] for k in range(h)]
dp[0][0][0 - grid[0][0]] = True
dp[0][0][0 + grid[0][0]] = True
for i in range(h):
    for j in range(w):
        for k in range(-bias_inf,bias_inf):
            if i == h-1 and j == w-1:
                break
            if dp[i][j][k]:
                if i == h-1:
                    dp[i][j+1][k - grid[i][j+1]] = True
                    dp[i][j+1][k + grid[i][j+1]] = True
                elif j == w-1:
                    dp[i+1][j][k - grid[i+1][j]] = True
                    dp[i+1][j][k + grid[i+1][j]] = True
                else:
                    dp[i][j+1][k + grid[i][j+1]] = True
                    dp[i+1][j][k + grid[i+1][j]] = True
                    dp[i][j+1][k - grid[i][j+1]] = True
                    dp[i+1][j][k - grid[i+1][j]] = True
ans = bias_inf
for i in range(-bias_inf,bias_inf):
    if dp[-1][-1][i]:
        ans = min(ans, abs(i))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque
H,W=map(int, sys.stdin.readline().split())

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

for h in range(H):
    for w in range(W):
        A[h][w]=abs(A[h][w]-B[h][w])

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

#初期化
r,c=0,0
val=A[r][c]
dp[r][c].add(val)

q=deque()
q.append((0,0))
D=[(1,0),(0,1)]

while q:
    r,c=q.popleft()
    for dr,dc in D:
        if r+dr<H and c+dc<W:
            next_r=r+dr
            next_c=c+dc
            next_val=A[next_r][next_c]
            for j in dp[r][c]:
                dp[next_r][next_c].add(abs(j+next_val))
                dp[next_r][next_c].add(abs(j+next_val*-1))
            q.append((next_r,next_c))

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque
H,W=map(int, sys.stdin.readline().split())

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

for h in range(H):
    for w in range(W):
        A[h][w]=abs(A[h][w]-B[h][w])

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

#初期化
r,c=0,0
val=A[r][c]
dp[r][c].add(val)
dp[r][c].add(val*-1)

q=deque()
q.append((0,0))
D=[(1,0),(0,1)]

while q:
    r,c=q.popleft()
    for dr,dc in D:
        if r+dr<H and c+dc<W:
            next_r=r+dr
            next_c=c+dc
            next_val=A[next_r][next_c]
            for j in dp[r][c]:
                dp[next_r][next_c].add(j+next_val)
                dp[next_r][next_c].add(j+next_val*-1)
            q.append((next_r,next_c))


print min(map(lambda x: abs(x), dp[H-1][W-1]))

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
n = (h + w) * 80
diff = [list(map(int, input().split())) for _ in range(h)]
for i in range(h):
    for j, b in enumerate(list(map(int, input().split()))):
        diff[i][j] = abs(diff[i][j] - b)
dp = [[0] * (w+1) for i in range(h+1)]
for i in range(h+1): dp[i][0] = -1
for i in range(w+1): dp[0][i] = -1
dp[1][1] = 1 << diff[0][0]

for i in range(1, h+1):
    for j in range(1, w+1):
        d = diff[i-1][j-1]
        for k in range(n):
            if (dp[i-1][j] != -1 and dp[i-1][j] >> k & 1) or (dp[i][j-1] != -1 and dp[i][j-1] >> k & 1):
                dp[i][j] |= 1 << abs(k+d)
                dp[i][j] |= 1 << abs(k-d)

ans = float("inf")
for i in range(n):
    if dp[h][w] >> i & 1:
        ans = min(ans, i)
print(ans)