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:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
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


import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


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


def read_float():
    return float(buff_readline())


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


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


def read_str_n():
    return readline().strip().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):
    C = [[a-b for a, b in zip(ar, br)] for ar, br in zip(A, B)]

    memo = [[set() for _ in range(W)] for __ in range(H)]
    memo[0][0].add(C[0][0])
    memo[0][0].add(-C[0][0])
    for i in range(H):
        for j in range(W):
            c = C[i][j]
            if i > 0:
                for d in memo[i-1][j]:
                    memo[i][j].add(d + c)
                    memo[i][j].add(d - c)
            if j > 0:
                for d in memo[i][j-1]:
                    memo[i][j].add(d + c)
                    memo[i][j].add(d - c)


    return min(map(abs, memo[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())
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=[[[False]*25601 for _ in range(w+1)]for _ in range(h+1)]
dp[0][1][12800]=True
for i in range(1,h+1):
    for j in range(1,w+1):
        t=c[i-1][j-1]
        for k in range(25601):
            if t<=k:dp[i][j][k]|=dp[i-1][j][k-t]|dp[i][j-1][k-t]
            if 25600>=t+k:dp[i][j][k]|=dp[i-1][j][k+t]|dp[i][j-1][k+t]
ans=10**20
for i in range(25601):
    if dp[h][w][i]:
        ans=min(ans,abs(12800-i))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

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

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

ans = 0
dp = [set() for _ in range(W+1)]
dp[0].add(0)
for i in range(H):
    ndp = [set() for _ in range(W+1)]
    for j in range(W):
        diff = A[i][j] - B[i][j]
        for prev in dp[j]:
            dp[j+1].add(prev + diff)
            dp[j+1].add(prev - diff)
            ndp[j].add(prev + diff)
            ndp[j].add(prev - diff)
    # print(dp)
    if i == H - 1:
        break
    dp = ndp

# print(dp)
ans = float("inf")
for v in dp[W]:
    ans = min(ans, abs(v))
print(ans)

Submission status: Time Limit Exceeded

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

# C: A-Bの絶対値を持つ
C = [[None]*W for _ in range(H)]
for i in range(H):
    for j in range(W):
        C[i][j] = abs(A[i][j]-B[i][j])

K = 80*(H+W-1)
dp = [[[0]*(K+1) for _ in range(W)] for _ in range(H)]
dp[0][0][C[0][0]] = 1

for i in range(H):
    for j in range(W):
        for k in range(K+1):
            if i and dp[i-1][j][k]:
                dp[i][j][k+C[i][j]] = 1
                dp[i][j][abs(k-C[i][j])] = 1
            if j and dp[i][j-1][k]:
                dp[i][j][k+C[i][j]] = 1
                dp[i][j][abs(k-C[i][j])] = 1

for k in range(K+1):
    res = dp[H-1][W-1][k]
    if res:
        print(k)
        exit()

Submission status: Time Limit Exceeded

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

# C: A-Bの絶対値を持つ
C = [[None]*W for _ in range(H)]
for i in range(H):
    for j in range(W):
        C[i][j] = abs(A[i][j]-B[i][j])

INF = 10**12
K = 2*80*(H+W-1)
dp = [[[0]*(K+1) for _ in range(W)] for _ in range(H)]# 答えから80*(H+W-1)を引く
dp[0][0][80*(H+W-1)+C[0][0]] = 1
dp[0][0][80*(H+W-1)-C[0][0]] = 1

for i in range(H):
    for j in range(W):
        for k in range(K+1):
            if i > 0 and dp[i-1][j][k] > 0:
                dp[i][j][k+C[i][j]] += dp[i-1][j][k]
                dp[i][j][k-C[i][j]] += dp[i-1][j][k]
            if j > 0 and dp[i][j-1][k] > 0:
                dp[i][j][k+C[i][j]] += dp[i][j-1][k]
                dp[i][j][k-C[i][j]] += dp[i][j-1][k]
ans = INF
for k in range(K+1):
    res = dp[H-1][W-1][k]
    if res > 0:
        ans = min(ans, abs(k-80*(H+W-1)))
print(ans)

Submission status: Time Limit Exceeded

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

# C: A-Bの絶対値を持つ
C = [[None]*W for _ in range(H)]
for i in range(H):
    for j in range(W):
        C[i][j] = abs(A[i][j]-B[i][j])
# print(C)
INF = 10**12
K = 2*80*(H+W-1)
dp = [[[0]*W for _ in range(H)] for _ in range(K+1)]# 答えから80*(H+W-1)を引く
dp[80*(H+W-1)+C[0][0]][0][0] = 1
dp[80*(H+W-1)-C[0][0]][0][0] = 1
# print(dp)

for i in range(H):
    for j in range(W):
        for k in range(K+1):
            if i > 0 and dp[k][i-1][j] > 0:
                dp[k+C[i][j]][i][j] += dp[k][i-1][j]
                dp[k-C[i][j]][i][j] += dp[k][i-1][j]
            if j > 0 and dp[k][i][j-1] > 0:
                dp[k+C[i][j]][i][j] += dp[k][i][j-1]
                dp[k-C[i][j]][i][j] += dp[k][i][j-1]
ans = INF
for k in range(K+1):
    res = dp[k][H-1][W-1]
    if res > 0:
        ans = min(ans, abs(k-80*(H+W-1)))
print(ans)

Submission status: Time Limit Exceeded

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

# C: A-Bの絶対値を持つ
C = [[None]*W for _ in range(H)]
for i in range(H):
    for j in range(W):
        C[i][j] = abs(A[i][j]-B[i][j])

ans = 10**12

def DFS(v, route):# vは現在地
    global ans
    if v == (H-1,W-1):# goal
        res = cal_diff(route+[C[H-1][W-1]])
        # print(res)
        ans = min(ans, res)
    else:
        c = C[v[0]][v[1]]
        if v[0] < H-1:
            DFS((v[0]+1,v[1]), route+[c])
        if v[1] < W-1:
            DFS((v[0],v[1]+1), route+[c])

def cal_diff(route):
    res = 0
    route.sort(reverse=True)
    for r in route:
        if abs(res+r) <= abs(res-r):
            res += r
        else:
            res -= r
    return abs(res)

DFS((0,0),[])
print(abs(ans))

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int, input().split())
al = []
bl = []

for _ in range(h):
    row = list(map(int, input().split()))
    al.append(row)

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


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

INF = 10**9
lim = (h+w)*80
# dp = [ [INF]*6400 for _ in range(h) ]
dp = [ [ [False]*(lim+1)  for _ in range(w) ] for _ in range(h) ]

dp[0][0][cl[0][0]] = True

for i in range(h):
    for j in range(w):
        for k in range(0,lim+1):
            if dp[i][j][k] == True:
                if i+1 < h:
                    v = cl[i+1][j]
                    dp[i+1][j][k+v] = True
                    dp[i+1][j][abs(k-v)] = True
                if j+1 < w:
                    v = cl[i][j+1]
                    dp[i][j+1][k+v] = True
                    dp[i][j+1][abs(k-v)] = True


for i,v in enumerate(dp[-1][-1]):
    if v == True:
        print(i)
        break

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
def input(): return sys.stdin.readline().rstrip()


def main():
    h, w = map(int, input().split())
    A = np.array([list(map(int, input().split()))
                  for i in range(h)], dtype=int)
    B = np.array([list(map(int, input().split()))
                  for i in range(h)], dtype=int)
    abss = np.abs(A-B)
    kmax = 280
    dp = np.zeros((h, w, kmax), dtype=int)
    dp[0][0][abss[0][0]] = 1
    for i in range(h):
        for j in range(w):
            for k in range(kmax):
                if dp[i][j][k] == 1:
                    if i != h-1:
                        dp[i+1][j][abs(k-abss[i+1][j])] = 1
                        if k+abss[i+1][j] < kmax:
                            dp[i+1][j][k+abss[i+1][j]] = 1
                    if j != w-1:
                        dp[i][j+1][abs(k-abss[i][j+1])] = 1
                        if k+abss[i][j+1] < kmax:
                            dp[i][j+1][k+abss[i][j+1]] = 1
    for k in range(kmax):
        if dp[-1][-1][k] == 1:
            print(k)
            break


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
def input(): return sys.stdin.readline().rstrip()


def main():
    h, w = map(int, input().split())
    A = np.array([list(map(int, input().split()))
                  for i in range(h)], dtype=int)
    B = np.array([list(map(int, input().split()))
                  for i in range(h)], dtype=int)
    abss = np.abs(A-B)
    kmax = 400
    dp = np.zeros((h, w, kmax), dtype=int)
    dp[0][0][abss[0][0]] = 1
    for i in range(h):
        for j in range(w):
            for k in range(kmax):
                if dp[i][j][k] == 1:
                    if i != h-1:
                        dp[i+1][j][abs(k-abss[i+1][j])] = 1
                        if k+abss[i+1][j] < kmax:
                            dp[i+1][j][k+abss[i+1][j]] = 1
                    if j != w-1:
                        dp[i][j+1][abs(k-abss[i][j+1])] = 1
                        if k+abss[i][j+1] < kmax:
                            dp[i][j+1][k+abss[i][j+1]] = 1
    for k in range(kmax):
        if dp[-1][-1][k] == 1:
            print(k)
            break


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
def input(): return sys.stdin.readline().rstrip()


def main():
    h, w = map(int, input().split())
    A = np.array([list(map(int, input().split()))
                  for i in range(h)], dtype=int)
    B = np.array([list(map(int, input().split()))
                  for i in range(h)], dtype=int)
    abss = np.abs(A-B)
    dp = np.zeros((h, w, 800), dtype=int)
    kmax = 800
    dp[0][0][abss[0][0]] = 1
    for i in range(h):
        for j in range(w):
            for k in range(kmax):
                if dp[i][j][k] == 1:
                    if i != h-1:
                        dp[i+1][j][abs(k-abss[i+1][j])] = 1
                        if k+abss[i+1][j] < kmax:
                            dp[i+1][j][k+abss[i+1][j]] = 1
                    if j != w-1:
                        dp[i][j+1][abs(k-abss[i][j+1])] = 1
                        if k+abss[i][j+1] < kmax:
                            dp[i][j+1][k+abss[i][j+1]] = 1
    for k in range(kmax):
        if dp[-1][-1][k] == 1:
            print(k)
            break


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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


def solve(H: int, W: int, A: "List[List[int]]", B: "List[List[int]]"):
    from itertools import chain
    dp = [[set() for _ in range(W+1)] for _ in range(H+1)]
    dp[0][0].add(0)
    for h in range(H):
        for w in range(W):
            d = A[h][w] - B[h][w]
            for v in dp[h][w]:
                dp[h+1][w].add(v+d)
                dp[h+1][w].add(v-d)
                dp[h][w+1].add(v+d)                                            
                dp[h][w+1].add(v-d)
    return min(map(abs, chain(dp[H-1][W], dp[H][W-1])))

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
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]]"
    print(solve(H, W, A, B))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Time Limit Exceeded

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


def solve(H: int, W: int, A: "List[List[int]]", B: "List[List[int]]"):
    from collections import defaultdict
    from itertools import chain
    dp = [[defaultdict(int) for _ in range(W+1)] for _ in range(H+1)]
    dp[0][0][0] = 1
    for h in range(H):
        for w in range(W):
            d = A[h][w] - B[h][w]
            for k, v in dp[h][w].items():
                dp[h+1][w][k+d] += v
                dp[h+1][w][k-d] += v
                dp[h][w+1][k+d] += v
                dp[h][w+1][k-d] += v
    return min(map(abs, chain(dp[H-1][W].keys(), dp[H][W-1].keys())))

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
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]]"
    print(solve(H, W, A, B))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
A = []
B = []
for _ in range(H):
    A.append(list(map(int, input().split())))
for _ in range(H):
    B.append(list(map(int, input().split())))
d = [[0]*W for _ in range(H)]
for h in range(H):
    for w in range(W):
        d[h][w] = abs(A[h][w]-B[h][w])

dp = [[[] for _ in range(W)] for _ in range(H)]
dp[0][0].append(d[0][0])
for h in range(H):
    for w in range(W):
        if h < H-1:
            dp[h+1][w] += list(map(lambda x: x+d[h+1][w], dp[h][w]))
            dp[h+1][w] += list(map(lambda x: abs(x-d[h+1][w]), dp[h][w]))
        if w < W-1:
            dp[h][w+1] += list(map(lambda x: x+d[h][w+1], dp[h][w]))
            dp[h][w+1] += list(map(lambda x: abs(x-d[h][w+1]), dp[h][w]))
print(min(dp[-1][-1]))

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
A = []
B = []
for _ in range(H):
    A.append(list(map(int, input().split())))
for _ in range(H):
    B.append(list(map(int, input().split())))
d = [[0]*W for _ in range(H)]
for h in range(H):
    for w in range(W):
        d[h][w] = abs(A[h][w]-B[h][w])

dp = [[set() for _ in range(W)] for _ in range(H)]
dp[0][0].add(d[0][0])
for h in range(H):
    for w in range(W):
        if h < H-1:
            dp[h+1][w] |= set(map(lambda x: x+d[h+1][w], dp[h][w]))
            dp[h+1][w] |= set(map(lambda x: abs(x-d[h+1][w]), dp[h][w]))
        if w < W-1:
            dp[h][w+1] |= set(map(lambda x: x+d[h][w+1], dp[h][w]))
            dp[h][w+1] |= set(map(lambda x: abs(x-d[h][w+1]), dp[h][w]))
print(min(dp[-1][-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)]

ab = [[0]*w for i in range(h)]
for ch in range(h):
    for cw in range(w):
        ab[ch][cw] = abs(a[ch][cw] - b[ch][cw])

ab0 = ab[0][0]
size = 80*(h+w)
dp = [[set([]) for ww in range(w)] for hh in range(h)]
dp[0][0] = {ab0, -ab0}
for ch in range(h):
    for cw in range(w):
        if ch < h-1:
            for ci in dp[ch][cw]:
                dp[ch+1][cw].add(ci + ab[ch+1][cw])
                dp[ch+1][cw].add(ci - ab[ch+1][cw])
        if cw < w-1:
            for ci in dp[ch][cw]:
                dp[ch][cw+1].add(ci + ab[ch][cw+1])
                dp[ch][cw+1].add(ci - ab[ch][cw+1])

ans = list({abs(i) for i in dp[h-1][w-1]})
print(min(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)]

ab = [[0]*w for i in range(h)]
for ch in range(h):
    for cw in range(w):
        ab[ch][cw] = abs(a[ch][cw] - b[ch][cw])

ab0 = ab[0][0]
size = 80*(h+w)
dp = [[set([]) for ww in range(w)] for hh in range(h)]
dp[0][0] = {ab0, -ab0}
for ch in range(h):
    for cw in range(w):
        if ch < h-1:
            for ci in dp[ch][cw]:
                dp[ch+1][cw].add(ci + ab[ch+1][cw])
                dp[ch+1][cw].add(ci - ab[ch+1][cw])
        if cw < w-1:
            for ci in dp[ch][cw]:
                dp[ch][cw+1].add(ci + ab[ch][cw+1])
                dp[ch][cw+1].add(ci - ab[ch][cw+1])

for i in range(1 + size//2):
    for j in [1, -1]:
        if i*j in dp[h-1][w-1]:
            print(i)
            exit()

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

ab = [[0]*w for i in range(h)]
for ch in range(h):
    for cw in range(w):
        ab[ch][cw] = abs(a[ch][cw] - b[ch][cw])

ab0 = ab[0][0]
size = 80*(h+w)
dp = [[set([]) for ww in range(w)] for hh in range(h)]
dp[0][0] = {ab0, -ab0}
for ch in range(h):
    for cw in range(w):
        if ch < h-1:
            for ci in dp[ch][cw]:
                dp[ch+1][cw].add(ci + ab[ch+1][cw])
                dp[ch+1][cw].add(ci - ab[ch+1][cw])
        if cw < w-1:
            for ci in dp[ch][cw]:
                dp[ch][cw+1].add(ci + ab[ch][cw+1])
                dp[ch][cw+1].add(ci - ab[ch][cw+1])

for i in range(1 + size//2):
    for j in [1, -1]:
        if i*j in dp[h-1][w-1]:
            print(i)
            exit()

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

ab = [[0]*w for i in range(h)]
for ch in range(h):
    for cw in range(w):
        ab[ch][cw] = abs(a[ch][cw] - b[ch][cw])

ab0 = ab[0][0]
size = 80*((h+w)*2)
dp = [[[False]*(1+size) for ww in range(w)] for hh in range(h)]
dp[0][0][size//2 + ab0] = True # size//2が0に相当
dp[0][0][size//2 - ab0] = True
for ch in range(h):
    for cw in range(w):
        for ck in range(1 + size): 
            if dp[ch][cw][ck]:
                if ch < h-1:
                    dp[ch+1][cw][ck + ab[ch+1][cw]] = True
                    dp[ch+1][cw][ck - ab[ch+1][cw]] = True
                if cw < w-1:
                    dp[ch][cw+1][ck + ab[ch][cw+1]] = True
                    dp[ch][cw+1][ck - ab[ch][cw+1]] = True

for i in range(1 + size//2):
    for j in [1, -1]:
        if dp[h-1][w-1][size//2 + i*j]:
            print(i)
            exit()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

a = np.array(a)
b = np.array(b)
ab = abs(a - b)
ab0 = ab[0][0]
size = 80*h*w 
dp = np.zeros((h, w, 1 + size), dtype='bool')
dp[0][0][size//2 + ab0] = True # size//2が0に相当
dp[0][0][size//2 - ab0] = True
for ch in range(h):
    for cw in range(w):
        for ck in range(1 + size): 
            if dp[ch][cw][ck]:
                if ch < h-1:
                    dp[ch+1][cw][ck + ab[ch+1][cw]] = True
                    dp[ch+1][cw][ck - ab[ch+1][cw]] = True
                if cw < w-1:
                    dp[ch][cw+1][ck + ab[ch][cw+1]] = True
                    dp[ch][cw+1][ck - ab[ch][cw+1]] = True

for i in range(1 + size//2):
    for j in [1, -1]:
        if dp[h-1][w-1][size//2 + i*j]:
            print(i)
            exit()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import bisect
import heapq


def input():
    return sys.stdin.readline().rstrip()


def main():
    H, W = map(int, input().split())
    M = 80
    A = [[0] * W for _ in range(H)]
    K = M * (H + W) + 1
    for i in range(H):
        a = list(map(int, input().split()))
        A[i] = a

    for i in range(H):
        b = list(map(int, input().split()))
        for j in range(W):
            A[i][j] -= b[j]

    dp = [[[False] * K for i in range(W)] for i in range(H)]
    # dp[i][j][k]
    dp[0][0][abs(A[0][0])] = True

    for i in range(H):
        for j in range(W):
            if i != 0:
                for k in range(K):
                    if dp[i - 1][j][k] is True:
                        dp[i][j][abs(k - A[i][j])] = True
                        dp[i][j][abs(k + A[i][j])] = True

            if j != 0:
                for k in range(K):
                    if dp[i][j - 1][k] == True:
                        dp[i][j][abs(k - A[i][j])] = True
                        dp[i][j][abs(k + A[i][j])] = True


    for k in range(K):
        if dp[H-1][W-1][k] ==True:
            print(k)
            exit()

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


h,w = list(map(int, input().split()))
n = h*w
a = [None]*h
b = [None]*h
for i in range(h):
    a[i] = list(map(int, input().split()))
for i in range(h):
    b[i] = list(map(int, input().split()))
# for i in range(h):
#     for j in range(h):
dp = [[None]*(w) for _ in range(h)]
# mask = 1<<6400

dp[0][0] = set([a[0][0]-b[0][0], b[0][0]-a[0][0]])
for i in range(h):
    for j in range(w):
        if i==j==0:
            continue
        v =abs(a[i][j]-b[i][j])
        s = set()
        if i>0:
            for item in dp[i-1][j]:
                s.add(item+v)
                s.add(item-v)
        if j>0:
            for item in dp[i][j-1]:
                s.add(item+v)
                s.add(item-v)
        dp[i][j] = s
ans = min(abs(item) for item in dp[h-1][w-1])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys

    def LI():
        return list(map(int, sys.stdin.readline().rstrip().split()))  # 空白あり

    H, W = LI()
    A = [[0] * (W + 1)] + [[0] + LI() for i in range(H)]
    B = [[0] * (W + 1)] + [[0] + LI() for i in range(H)]
    C = [[abs(A[i][j] - B[i][j]) for j in range(W + 1)] for i in range(H + 1)]

    m = max(max(C[i]) for i in range(H+1))
    M = m*((H+W+1)//2)

    dp = {}
    for i in range(1,H+1):
        for j in range(1,W+1):
            if i == 1 and j == 1:
                dp[(1,1)] = {C[1][1]}
            else:
                dp[(i,j)] = set([])

    # dp[(i,j)] = (i,j)に至ったときに偏りとして有り得る数のset

    for i in range(1, H + 1):
        for j in range(1, W + 1):
            if i != H and j != W:
                for k in dp[(i, j)]:
                    if k <= M:
                        dp[(i + 1, j)].add(abs(k + C[i + 1][j]))
                        dp[(i + 1, j)].add(abs(k - C[i + 1][j]))
                        dp[(i, j + 1)].add(abs(k + C[i][j + 1]))
                        dp[(i, j + 1)].add(abs(k - C[i][j + 1]))
            elif i == H and j != W:
                for k in dp[(i, j)]:
                    if k <= M:
                        dp[(i, j + 1)].add(abs(k + C[i][j + 1]))
                        dp[(i, j + 1)].add(abs(k - C[i][j + 1]))
            elif i != H and j == W:
                for k in dp[(i, j)]:
                    if k <= M:
                        dp[(i + 1, j)].add(abs(k + C[i + 1][j]))
                        dp[(i + 1, j)].add(abs(k - C[i + 1][j]))
            else:
                continue

    l = list(dp[(H, W)])
    print(min(l))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys

    def LI():
        return list(map(int, sys.stdin.readline().rstrip().split()))  # 空白あり

    H, W = LI()
    A = [[0] * (W + 1)] + [[0] + LI() for i in range(H)]
    B = [[0] * (W + 1)] + [[0] + LI() for i in range(H)]
    C = [[abs(A[i][j] - B[i][j]) for j in range(W + 1)] for i in range(H + 1)]

    m = max(max(C[i]) for i in range(H+1))
    M = m*((H+W+1)//2)

    dp = {}
    for i in range(1,H+1):
        for j in range(1,W+1):
            if i == 1 and j == 1:
                dp[(1,1)] = {C[1][1]}
            else:
                dp[(i,j)] = set([])

    # dp[(i,j)] = (i,j)に至ったときに偏りとして有り得る数のset

    for i in range(1, H + 1):
        for j in range(1, W + 1):
            if i != H and j != W:
                for k in dp[(i, j)]:
                    if k <= M:
                        dp[(i + 1, j)].add(abs(k + C[i + 1][j]))
                        dp[(i + 1, j)].add(abs(k - C[i + 1][j]))
                        dp[(i, j + 1)].add(abs(k + C[i][j + 1]))
                        dp[(i, j + 1)].add(abs(k - C[i][j + 1]))
            elif i == H and j != W:
                for k in dp[(i, j)]:
                    if k <= M:
                        dp[(i, j + 1)].add(abs(k + C[i][j + 1]))
                        dp[(i, j + 1)].add(abs(k - C[i][j + 1]))
            elif i != H and j == W:
                for k in dp[(i, j)]:
                    if k <= M:
                        dp[(i + 1, j)].add(abs(k + C[i + 1][j]))
                        dp[(i + 1, j)].add(abs(k - C[i + 1][j]))
            else:
                continue

    l = list(dp[(H, W)])
    print(min(l))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys

    def LI():
        return list(map(int, sys.stdin.readline().rstrip().split()))  # 空白あり

    H, W = LI()
    A = [[0] * (W + 1)] + [[0] + LI() for i in range(H)]
    B = [[0] * (W + 1)] + [[0] + LI() for i in range(H)]
    C = [[A[i][j] - B[i][j] for j in range(W + 1)] for i in range(H + 1)]

    dp = {}
    for i in range(1,H+1):
        for j in range(1,W+1):
            if i == 1 and j == 1:
                dp[(1,1)] = {C[1][1]}
            else:
                dp[(i,j)] = set([])

    # dp[(i,j)] = (i,j)に至ったときに偏りとして有り得る数のset

    for i in range(1, H + 1):
        for j in range(1, W + 1):
            if i != H and j != W:
                for k in dp[(i, j)]:
                    dp[(i + 1, j)].add(abs(k + C[i + 1][j]))
                    dp[(i + 1, j)].add(abs(k - C[i + 1][j]))
                    dp[(i, j + 1)].add(abs(k + C[i][j + 1]))
                    dp[(i, j + 1)].add(abs(k - C[i][j + 1]))
            elif i == H and j != W:
                for k in dp[(i, j)]:
                    dp[(i, j + 1)].add(abs(k + C[i][j + 1]))
                    dp[(i, j + 1)].add(abs(k - C[i][j + 1]))
            elif i != H and j == W:
                for k in dp[(i, j)]:
                    dp[(i + 1, j)].add(abs(k + C[i + 1][j]))
                    dp[(i + 1, j)].add(abs(k - C[i + 1][j]))
            else:
                continue

    l = list(dp[(H, W)])
    print(min(l))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys

    def LI():
        return list(map(int, sys.stdin.readline().rstrip().split()))  # 空白あり

    H, W = LI()
    A = [[0] * (W + 1)] + [[0] + LI() for i in range(H)]
    B = [[0] * (W + 1)] + [[0] + LI() for i in range(H)]
    C = [[A[i][j] - B[i][j] for j in range(W + 1)] for i in range(H + 1)]

    from collections import defaultdict

    dp = defaultdict(set)

    # dp[(i,j)] = (i,j)に至ったときに偏りとして有り得る数のset

    dp[(1, 1)] = {C[1][1]}

    for i in range(1, H + 1):
        for j in range(1, W + 1):
            if i != H and j != W:
                for k in dp[(i, j)]:
                    dp[(i + 1, j)].add(abs(k + C[i + 1][j]))
                    dp[(i + 1, j)].add(abs(k - C[i + 1][j]))
                    dp[(i, j + 1)].add(abs(k + C[i][j + 1]))
                    dp[(i, j + 1)].add(abs(k - C[i][j + 1]))
            elif i == H and j != W:
                for k in dp[(i, j)]:
                    dp[(i, j + 1)].add(abs(k + C[i][j + 1]))
                    dp[(i, j + 1)].add(abs(k - C[i][j + 1]))
            elif i != H and j == W:
                for k in dp[(i, j)]:
                    dp[(i + 1, j)].add(abs(k + C[i + 1][j]))
                    dp[(i + 1, j)].add(abs(k - C[i + 1][j]))
            else:
                continue

    l = list(dp[(H, W)])
    print(min(l))

if __name__ == '__main__':
    main()