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: Accepted

Solution code:
import numpy as np
i8 = np.int64
i4 = np.int32

def calc(dp1, dp2, k):
    dp2[k:] += dp1[:dp1.shape[0]-k]
    dp2[:dp2.shape[0]-k] += dp1[k:]

def solve(z, dp):
    zero = dp.shape[2] // 2
    dp[0, 0, zero + z[0, 0]] = 1
    dp[0, 0, zero - z[0, 0]] = 1
    for x in range(1, z.shape[1]):
        calc(dp[0, x - 1], dp[0, x], z[0, x])
    for y in range(1, z.shape[0]):
        calc(dp[y - 1, 0], dp[y, 0], z[y, 0])
        for x in range(1, z.shape[1]):
            calc(dp[y, x - 1], dp[y, x], z[y, x])
            calc(dp[y - 1, x], dp[y, x], z[y, x])
            if (x + y) % 50 == 0:
                dp[y, x] = dp[y, x] > 0
    for i in range(zero, dp.shape[2]):
        if dp[dp.shape[0] - 1, dp.shape[1] - 1, i] > 0:
            return i - zero
    return -1

def main2():
    stdin = open('/dev/stdin')
    H, W = map(int, stdin.readline().split())
    a = np.empty((H, W), i8)
    b = np.empty((H, W), i8)
    for i in range(H):
        for j, c in enumerate(map(int, stdin.readline().split())):
            a[i, j] = c
    for i in range(H):
        for j, c in enumerate(map(int, stdin.readline().split())):
            b[i, j] = c
    z = np.abs(a - b)
    dp = np.zeros((H, W, 80 * 80 *2 + 1), i8)
    ans = solve(z, dp)
    print(ans)


main2()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
H, W = map(int, input().split())
A, B = [None] * H, [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()))
C = [[abs(A[i][j] - B[i][j]) for j in range(W)] for i in range(H)]
dp = [[0 for j in range(W+1)] for i in range(H+1)]
dp[0][1] = 1
dp[1][0] = 1
for i in range(1, H+1):
    for j in range(1, W+1):
        d = C[i-1][j-1]
        x = int('0'+bin((dp[i-1][j]&(2**d-1))+2**d)[::-1][:d], 2)<<1
        y = int('0'+bin((dp[i][j-1]&(2**d-1))+2**d)[::-1][:d], 2)<<1
        dp[i][j] = (dp[i-1][j] >> d) | (dp[i-1][j] << d) | (dp[i][j-1] >> d) | (dp[i][j-1] << d) | x | y
for i, v in enumerate(bin(dp[H][W])[::-1]):
    if v == '1':
        print(i)
        break

Submission status: Accepted

Solution code:
import numpy as np
i8 = np.int64
i4 = np.int32

def calc(dp1, dp2, k):
    dp2[k:] += dp1[:dp1.shape[0]-k]
    dp2[:dp2.shape[0]-k] += dp1[k:]

def solve(z, dp):
    zero = dp.shape[2] // 2
    dp[0, 0, zero + z[0, 0]] = 1
    dp[0, 0, zero - z[0, 0]] = 1
    for x in range(1, z.shape[1]):
        calc(dp[0, x - 1], dp[0, x], z[0, x])
    for y in range(1, z.shape[0]):
        calc(dp[y - 1, 0], dp[y, 0], z[y, 0])
        for x in range(1, z.shape[1]):
            calc(dp[y, x - 1], dp[y, x], z[y, x])
            calc(dp[y - 1, x], dp[y, x], z[y, x])
            if (x + y) % 10 == 0:
                dp[y, x] = dp[y, x] > 0
    for i in range(zero, dp.shape[2]):
        if dp[dp.shape[0] - 1, dp.shape[1] - 1, i] > 0:
            return i - zero
    return -1

def main2():
    stdin = open('/dev/stdin')
    H, W = map(int, stdin.readline().split())
    a = np.empty((H, W), i8)
    b = np.empty((H, W), i8)
    for i in range(H):
        for j, c in enumerate(map(int, stdin.readline().split())):
            a[i, j] = c
    for i in range(H):
        for j, c in enumerate(map(int, stdin.readline().split())):
            b[i, j] = c
    z = np.abs(a - b)
    dp = np.zeros((H, W, 80 * 80 *2 + 1), i8)
    ans = solve(z, dp)
    print(ans)


main2()

Submission status: Accepted

Solution code:
M = 6400
mid = M//2
INF = 10**18

H,W = map(int, input().split())
As = []
for i in range(H):
    As.append(list(map(int, input().split())))
diffs = []
for i in range(H):
    bs = list(map(int, input().split()))
    diffs.append([abs(a-b) for a,b in zip(As[i],bs)])

# bitset高速化
# 初期値
dp = [[0]*W for j in range(H)]
dp[0][0] = 1 << (mid+diffs[0][0]) #プラスマイナス考慮して、下駄をはかせる
for i in range(H):
    for j in range(W):
        # 行方向
        if i+1 < H:
            d = diffs[i+1][j]
            dp[i+1][j] |= dp[i][j] >> d  
            dp[i+1][j] |= dp[i][j] << d  
        # 列方向
        if j+1 < W:
            d = diffs[i][j+1]
            dp[i][j+1] |= dp[i][j] >> d
            dp[i][j+1] |= dp[i][j] << d

ans = INF
for i in range(M):
    if dp[H-1][W-1] >> i & 1:
        # print(i-mid)
        ans = min(ans, abs(i-mid))
print(ans)

Submission status: Accepted

Solution code:
M = 6400*4
mid = M//2
INF = 10**18

H,W = map(int, input().split())
As = []
for i in range(H):
    As.append(list(map(int, input().split())))
diffs = []
for i in range(H):
    bs = list(map(int, input().split()))
    diffs.append([abs(a-b) for a,b in zip(As[i],bs)])

# bitset高速化
# 初期値
dp = [[0]*W for j in range(H)]
dp[0][0] = 1 << (mid+diffs[0][0]) #プラスマイナス考慮して、下駄をはかせる
for i in range(H):
    for j in range(W):
        # 行方向
        if i+1 < H:
            d = diffs[i+1][j]
            dp[i+1][j] |= dp[i][j] >> d  
            dp[i+1][j] |= dp[i][j] << d  
        # 列方向
        if j+1 < W:
            d = diffs[i][j+1]
            dp[i][j+1] |= dp[i][j] >> d
            dp[i][j+1] |= dp[i][j] << d

ans = INF
for i in range(M):
    if dp[H-1][W-1] >> i & 1:
        # print(i-mid)
        ans = min(ans, abs(i-mid))
print(ans)

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    H,W=MI()
    A=LLIN(H)
    B=LLIN(H)
    X=80*(H+W)
    can = [[0]*W for _ in range(H)]
    can[0][0] += 1<<(X-abs(A[0][0]-B[0][0]))
    for h in range(H):
        for w in range(W):
            absol = abs(A[h][w]-B[h][w])
            if h:
                can[h][w]|=can[h-1][w]<<absol
                can[h][w]|=can[h-1][w]>>absol
            if w:
                can[h][w]|=can[h][w-1]<<absol
                can[h][w]|=can[h][w-1]>>absol
    for i in range(160*(H+W)+5):
        if can[-1][-1] & ((1<<X<<i) | (1<<X>>i)):
            print(i)
            break

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
H, W = map(int, input().split())
A, B = [None] * H, [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()))
C = [[abs(A[i][j] - B[i][j]) for j in range(W)] for i in range(H)]
M = 80*(80+80)
dp = [[0 for j in range(W+1)] for i in range(H+1)]
dp[0][1] = 1
dp[1][0] = 1
for i in range(1, H+1):
    for j in range(1, W+1):
        d = C[i-1][j-1]
        if d != 0:
            x = int(bin((dp[i-1][j]&(2**d-1))+2**d)[::-1][:d], 2)<<1
            y = int(bin((dp[i][j-1]&(2**d-1))+2**d)[::-1][:d], 2)<<1
        else:
            x=y=0
        #print(bin(dp[i-1][j]), bin(dp[i-1][j]+(2**10)))
        dp[i][j] = (dp[i-1][j] >> d) | (dp[i-1][j] << d) | (dp[i][j-1] >> d) | (dp[i][j-1] << d) | x | y
        #print(i, j, d, bin(dp[i][j]))

for i, v in enumerate(bin(dp[H][W])[::-1]):
    if v == '1':
        print(i)
        break

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
A = [[int(a) for a in input().split()] for _ in range(H)]
B = [[int(a) for a in input().split()] for _ in range(H)]
C = [[A[i][j] - B[i][j] for j in range(W)] for i in range(H)]
X = [[0] * (W) for _ in range(H)]
X[0][0] = (1 << 80 + C[0][0]) | (1 << 80 - C[0][0])
for i in range(H):
    for j in range(W):
        if i:
            X[i][j] |= (X[i-1][j] << 80 + C[i][j]) | (X[i-1][j] << 80 - C[i][j])
        if j:
            X[i][j] |= (X[i][j-1] << 80 + C[i][j]) | (X[i][j-1] << 80 - C[i][j])
s = bin(X[-1][-1] + (1<<13000))
mi = 1<<100
for i in range(len(s)):
    if s[-i-1] == "1":
        mi = min(mi, abs(i-(H+W-1)*80))
print(mi)

Submission status: Accepted

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

def honya(y, d):
  t = (1 << d + 1) - 1
  t = y & t
  k = 0
  for i in range(d):
    k += t & 1
    t >>= 1
    k <<= 1
  return k

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

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

def nasu(x, y, d):
  t = (1 << (d + 1)) - 1 & y
  return (x | (y << d) | (y >> d) | honya(y, d)) & mask
  

mask = (1 << M) - 1
DP[0][0] = 1 << D[0][0]
for i in range(H):
  for j in range(W):
    if i + 1 < H:
      DP[i + 1][j] = nasu(DP[i + 1][j], DP[i][j], D[i + 1][j])
    if j + 1 < W:
      DP[i][j + 1] = nasu(DP[i][j + 1], DP[i][j], D[i][j + 1])

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

Submission status: Accepted

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 bin_out(aa):
    bb = [format(a, "b") for a in aa]
    print(bb)

def main():
    h, w = MI()
    aa = LLI(h)
    bb = LLI(h)
    max_val=6400
    zero = 1 << max_val
    dp = [0] * w
    dp[0] = zero
    #bin_out(dp)
    for i, (ar, br) in enumerate(zip(aa, bb)):
        for j, (a, b) in enumerate(zip(ar, br)):
            d = abs(a - b)
            if j > 0: dp[j] |= dp[j - 1]
            dp[j] = dp[j] << d | dp[j] >> d
        #bin_out(dp)
    goal = dp[-1]
    for ans in range(max_val + 1):
        if goal & zero << ans or goal & zero >> ans:
            print(ans)
            break

main()

Submission status: Accepted

Solution code:
def fold(x,m):
    y = 0
    for _ in range(m):
        y |= x&1
        y <<= 1
        x >>= 1
    return x|y

lmi = lambda: list(map(int, input().split()))

h,w = lmi()
a = [lmi() for _ in range(2*h)]
g = [[abs(a[i][j] - a[i+h][j]) for j in range(w)] for i in range(h)]
m = 12801
mask = (1<<m) - 1

dp = [0]*(w+1)
dp[0] = 1
for i in range(h):
  for j in range(w):
    cur,par = g[i][j],dp[j]|dp[j-1]
    dp[j] = par<<cur&mask|fold(par,cur)
for i in range(m):
  if dp[-2]&(1<<i):
    print(i)
    break

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import itertools
import numpy as np

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

X = (H + W) * 80
L = X + X + 1
# X点持った状態から始める
dp = [[0] * W for _ in range(H)]
d = abs(A[0][0] - B[0][0])
dp[0][0] = np.zeros(L,np.bool)
dp[0][0][X+d] = 1
for h in range(H):
    for w,(a,b) in enumerate(zip(A[h],B[h])):
        if h == w == 0:
            continue
        d = abs(a - b)
        x = np.zeros(L,np.bool)
        if h != 0:
            x[d:] |= dp[h-1][w][:L-d]
            x[:L-d] |= dp[h-1][w][d:]
        if w != 0:
            x[d:] |= dp[h][w-1][:L-d]
            x[:L-d] |= dp[h][w-1][d:]
        dp[h][w] = x

dp = dp[-1][-1]
can_make = np.where(dp)[0] - X

answer = np.abs(can_make).min()
print(answer)

Submission status: Accepted

Solution code:
def fold(x,m):
    y = 0
    for _ in range(m):
        y |= x&1
        y <<= 1
        x >>= 1
    return x|y

lmi = lambda: list(map(int, input().split()))

h,w = lmi()
a = [lmi() for _ in range(2*h)]
g = [[abs(a[i][j] - a[i+h][j]) for j in range(w)] for i in range(h)]

mask = (1<<12801) - 1

dp = [[0]*(w+1) for _ in range(h+1)]
dp[0][0] = 1
for i in range(h):
  for j in range(w):
    cur,par = g[i][j],dp[i][j]
    pos = (par<<cur)|fold(par,cur)
    pos &= mask
    dp[i+1][j] |= pos
    dp[i][j+1] |= pos
for i in range(12801):
  if dp[-1][-2]&(1<<i):
    print(i)
    break

Submission status: Accepted

Solution code:
def main():
  e=enumerate
  (h,w),*a=[list(map(int,t.split()))for t in open(0)]
  dp=[0]*w
  c=12800
  for i,a in e(zip(a,a[h:])):
    for j,(x,y)in e(zip(*a)):
      x=abs(x-y)
      t=0
      if j:t|=dp[j-1]<<x|dp[j-1]>>x
      if i:t|=dp[j]<<x|dp[j]>>x
      dp[j]=t if i+j else 2**c<<x
  *a,=map(int,(bin(dp[w-1])[2:]).zfill(c-~c))
  print([i for i,(f,g)in e(zip(a[c:],a[c::-1]))if f+g][0])
main()

Submission status: Accepted

Solution code:
H, W = [int(x) for x in input().split()]

A = [[0]*W for i in range(H)]
for c in [1, -1]:
    for i in range(H):
        arr = [int(x) for x in input().split()]
        for j in range(W):
            A[i][j] += arr[j] * c

M = 160*80
dp = [[0]*W for i in range(H)]
dp[0][0] = 1 << M
for i in range(H):
    for j in range(W):
        if i > 0:
            dp[i][j] |= dp[i-1][j]
        if j > 0:
            dp[i][j] |= dp[i][j-1]
        a = abs(A[i][j])
        dp[i][j] = (dp[i][j] << a) | (dp[i][j] >> a)

ans = M
for i in range(2*M):
    if dp[H-1][W-1] & (1 << i) > 0:
        ans = min(ans, abs(M-i))
print(ans)

Submission status: Accepted

Solution code:
e=enumerate
(h,w),*a=[list(map(int,t.split()))for t in open(0)]
dp=[0]*w
c=12800
for i,a in e(zip(a,a[h:])):
  for j,(x,y)in e(zip(*a)):
    x=abs(x-y)
    t=0
    if j:t|=dp[j-1]<<x|dp[j-1]>>x
    if i:t|=dp[j]<<x|dp[j]>>x
    dp[j]=t if i+j else 2**c<<x
*a,=map(int,(bin(dp[w-1])[2:]).zfill(c-~c))
print(min(i for i,(f,g)in e(zip(a[c:],a[c::-1]))if f+g))

Submission status: Accepted

Solution code:
e=enumerate
(h,w),*a=[list(map(int,t.split()))for t in open(0)]
dp=[0]*w
c=12800
for i,a in e(zip(a,a[h:])):
  for j,(x,y)in e(zip(*a)):
    x=abs(x-y)
    t=0
    if j:t|=dp[j-1]<<x|dp[j-1]>>x
    if i:t|=dp[j]<<x|dp[j]>>x
    dp[j]=t if i+j else 2**c<<x
*a,=map(int,(bin(dp[w-1])[2:]).zfill(25601))
print(min(i for i,(f,g)in e(zip(a[12800:],a[12800::-1]))if f+g))

Submission status: Accepted

Solution code:
e=enumerate
(h,w),*a=[list(map(int,t.split()))for t in open(0)]
dp=[0]*w
c=12800
for i,a in e(zip(a,a[h:])):
  for j,(x,y)in e(zip(*a)):
    x=abs(x-y)
    t=0
    if j:
      t|=dp[j-1]<<x
      t|=dp[j-1]>>x
    if i:
      t|=dp[j]<<x
      t|=dp[j]>>x
    dp[j]=t if i+j else 2**c<<x
*a,=map(int,(bin(dp[w-1])[2:]).zfill(25601))
print(min([i for i,f in e(a[12800:])if f]+[i for i,f in e(a[12800::-1])if f]))

Submission status: Accepted

Solution code:
e=enumerate
h,w=map(int,input().split())
a=[list(map(int,input().split()))for _ in range(h)]
b=[list(map(int,input().split()))for _ in range(h)]
dp=[0]*w
c=13000
for i,(a,b)in e(zip(a,b)):
  for j,(x,y)in e(zip(a,b)):
    x=abs(x-y)
    if i==j==0:
      dp[j]=2**c<<x
      continue
    t=0
    if j:
      t|=dp[j-1]<<x
      t|=dp[j-1]>>x
    if i:
      t|=dp[j]<<x
      t|=dp[j]>>x
    dp[j]=t
*a,=map(int,(bin(dp[w-1])[2:]).zfill(26001))
print(min([i for i,f in e(a[13000:])if f]+[i for i,f in e(a[13000::-1])if f]))

Submission status: Accepted

Solution code:
def inpl(): return list(map(int, input().split()))

H, W = inpl()
A = [inpl() for _ in range(H)]
B = [inpl() for _ in range(H)]

DP = [[0 for _ in range(W+1)] for _ in range(H+1)]
DP[0][0] = 1 << 12800

for h in range(H):
    for w in range(W):
        d = abs(A[h][w] - B[h][w])
        DP[h+1][w] |= DP[h][w] >> d
        DP[h+1][w] |= DP[h][w] << d
        DP[h][w+1] |= DP[h][w] >> d
        DP[h][w+1] |= DP[h][w] << d
l = 1 << 12800
r = 1 << 12800
for i in range(12801):
    if (DP[-1][-2]& l) | (DP[-1][-2] & r):
        print(i)
        break
    l = l << 1
    r = r >> 1

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
M = (H + W) * 80

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

dp = [[0] * W for _ in range(H)]
dp[0][0] = (1 << (M - abs(A[0][0] - B[0][0])))

for h in range(H):
    for w, (a, b) in enumerate(zip(A[h], B[h])):
        d = abs(a - b)
        mask = 0
        if h > 0:
            mask |= (dp[h - 1][w] << d)
            mask |= (dp[h - 1][w] >> d)
        if w > 0:
            mask |= (dp[h][w - 1] << d)
            mask |= (dp[h][w - 1] >> d)
        dp[h][w] |= mask

state = dp[-1][-1]
nums = []
for digit, b in enumerate(bin(state)[2:][:: -1]):
    if b == '1':
        nums.append(digit - M)
ans = min(abs(n) for n in nums)
print(ans)

Submission status: Accepted

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

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()))
	B[i] = b

D = [[abs(A[i][j] - B[i][j]) for j in range(W)] for i in range(H)]
R = 160*80
"""
dp = [[[False for k in range(R)] for j in range(W)] for i in range(H)]
dp[0][0][D[0][0]] = True
for i in range(H):
	for j in range(W):
		r = 80 * (i+j+2)
		for n in range(r):
			if not dp[i][j][n]:
				continue
			if j != W-1:
				d = D[i][j+1]
				dp[i][j+1][n+d] = True
				dp[i][j+1][abs(n-d)] = True
			if i != H-1:
				d = D[i+1][j]
				dp[i+1][j][n+d] = True
				dp[i+1][j][abs(n-d)] = True

"""
dp = [[0 for j in range(W)] for i in range(H)]
dp[0][0] = 2**(R + D[0][0]) | 2**(R - D[0][0])
for i in range(H):
	for j in range(W):
		if j != W-1:
			d = D[i][j+1]
			dp[i][j+1] |= (dp[i][j] << d | dp[i][j] >> d)
		if i != H-1:
			d = D[i+1][j]
			dp[i+1][j] |= (dp[i][j] << d | dp[i][j] >> d)
h,w = H-1, W-1
for i in range(R):
	mask = 2 ** (R+i) | 2 ** (R-i)
	if dp[h][w] & mask > 0:
		print(i)
		exit()

Submission status: Accepted

Solution code:
#!/bin/bash
''':'
docker run --rm -it -v $(cd $(dirname $0) && pwd):/vo:ro pypy:3-2.4.0 /bin/bash -c "pypy3 /vo/$(basename $0) < /vo/g.inp"; exit $?
exit 0
'''
import sys

def _ia(): return [ int(x) for x in sys.stdin.readline().strip().split() ]

# read input
h,w = _ia()
ab = []
for _ in range(h): ab.append(_ia())
for i in range(h):
    r = ab[i]
    for j,bj in enumerate(_ia()):
        r[j] = abs(r[j] - bj)
    t = max(r)

# initialize
dp = [[None for _ in range(w)] for _ in range(h)]
dp[0][0] = {ab[0][0]}
hw1 = h + w - 1
for ij in range(1,hw1):
    iend = ( hw1 - ij ) * 80
    for i in range(min(ij+1,h)):
        j = ij - i
        if j>=w: continue
        #
        ref = set()
        if i>0: ref|= dp[i-1][j]
        if j>0: ref|= dp[i][j-1]
        #
        x = ab[i][j]
        nxt = dp[i][j] = set()
        for idx in ref:
            ix = abs(idx-x)
            if ix<=iend: nxt.add(ix)
            ix = idx + x
            if ix<=iend: nxt.add(ix)
            
# stdout
print(min(dp[h-1][w-1]))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
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)]
X = [[abs(A[i][j] - B[i][j]) for j in range(W)] for i in range(H)]
dp1 = [set() for _ in range(W)]
dp1[0].add(X[0][0])
dp2 = [set() for _ in range(W)]
dplimit = [[0] * W for _ in range(H)]
dplimit[-1][-1] = 80
for i in range(H - 1, -1, -1):
  for j in range(W - 1, -1, -1):
    x = X[i][j]
    if i > 0: dplimit[i - 1][j] = max(dplimit[i - 1][j], dplimit[i][j] + x)
    if j > 0: dplimit[i][j - 1] = max(dplimit[i][j - 1], dplimit[i][j] + x)
for i in range(H):
  if i % 2 == 0:
    dp2 = [set() for _ in range(W)]
  else: dp1 = [set() for _ in range(W)]
  for j in range(W):
    if i % 2 == 0:
      for k in dp1[j]:
        if i + 1 < H:
          u = k + X[i + 1][j]
          v = abs(k - X[i + 1][j])
          if u <= dplimit[i][j]: dp2[j].add(u)
          if v <= dplimit[i][j]: dp2[j].add(v)
        if j + 1 < W:
          u = k + X[i][j + 1]
          v = abs(k - X[i][j + 1])
          if u <= dplimit[i][j]: dp1[j + 1].add(u)
          if v <= dplimit[i][j]: dp1[j + 1].add(v)
    else:
      for k in dp2[j]:
        if i + 1 < H:
          u = k + X[i + 1][j]
          v = abs(k - X[i + 1][j])
          if u <= dplimit[i][j]: dp1[j].add(u)
          if v <= dplimit[i][j]: dp1[j].add(v)
        if j + 1 < W:
          u = k + X[i][j + 1]
          v = abs(k - X[i][j + 1])
          if u <= dplimit[i][j]: dp2[j + 1].add(u)
          if v <= dplimit[i][j]: dp2[j + 1].add(v)
res = float("inf")
if H % 2:
  for k in dp1[-1]: res = min(k, res)
else:
  for k in dp2[-1]: res = min(k, res)
print(res)

Submission status: Accepted

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

def solve(H: int, W: int, A: "List[List[int]]", B: "List[List[int]]"):
    SA=[[0]*W for i in range(H)]
    MAX = (H+W)*80
    for i in range(H):
        for j in range(W):
            SA[i][j]=abs(A[i][j]-B[i][j])

    DP=[[0 for i in range(W)] for j in range(H)]
    DP[0][0]=1<<MAX+SA[0][0]

    for i in range(H):
        for j in range(W):
            tempbit=DP[i][j]
            if i<H-1:
                DP[i+1][j]|=tempbit<<SA[i+1][j]
                DP[i+1][j]|=tempbit>>SA[i+1][j]

            if j<W-1:
                DP[i][j+1]|=tempbit<<SA[i][j+1]
                DP[i][j+1]|=tempbit>>SA[i][j+1]

    ANS=1<<MAX*2
    for i in range(MAX*2+1):
        if 1<<i & DP[-1][-1]!=0:
            ANS=min(ANS,abs(i-MAX))

    print(ANS)
    return



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: Accepted

Solution code:
#https://atcoder.jp/contests/abc147/submissions/8874645
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    ofs=6400
    h,w=map(int,input().split())
    A=[list(map(int,input().split())) for _ in range(h)]
    B=[list(map(int,input().split())) for _ in range(h)]
    dp=[[0]*w for _ in range(h)]
    x=abs(A[0][0]-B[0][0])
    dp[0][0]|=((1<<(ofs+x))|(1<<(ofs-x)))

    from itertools import product
    for i,j in product(range(h),range(w)):
        x=abs(A[i][j]-B[i][j])
        t=0
        if(i-1>=0):
            t|=dp[i-1][j]
        if(j-1>=0):
            t|=dp[i][j-1]
        dp[i][j]|=((t<<x)|(t>>x))

    for i,s in enumerate(bin(dp[-1][-1])[-ofs-1:]):
        if(s=='1'):
            print(i)
            return
                    
resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    h,w=map(int,input().split())
    A=[list(map(int,input().split())) for _ in range(h)]
    B=[list(map(int,input().split())) for _ in range(h)]
    dp=[[0]*w for _ in range(h)]
    x=abs(A[0][0]-B[0][0])
    offset=12800
    dp[0][0]|=1<<(x+offset)
    dp[0][0]|=1<<(-x+offset)

    from itertools import product
    for i,j in product(range(h),range(w)):
        if(i==0 and j==0): continue
        x=abs(A[i][j]-B[i][j])
        S=0
        if(i>0): S|=dp[i-1][j]
        if(j>0): S|=dp[i][j-1]
        dp[i][j]=(S<<x)|(S>>x)

    for i in range(12800):
        if((dp[-1][-1]>>(i+offset))&1):
            print(i)
            return
resolve()

Submission status: Accepted

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

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

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

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

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

DP=[[0 for i in range(W)] for j in range(H)]

DP[0][0]=1<<(H+W)*80+SA[0][0]

for i in range(H):
    for j in range(W):
        tempbit=DP[i][j]
        if i+1<H:
            DP[i+1][j]|=tempbit<<SA[i+1][j]
            DP[i+1][j]|=tempbit>>SA[i+1][j]

        if j+1<W:
            DP[i][j+1]|=tempbit<<SA[i][j+1]
            DP[i][j+1]|=tempbit>>SA[i][j+1]

ANS=1<<30
for i in range((H+W)*160+1):
    if 1<<i & DP[-1][-1]!=0:
        ANS=min(ANS,abs(i-(H+W)*80))

print(ANS)

Submission status: Accepted

Solution code:

import sys

sys.setrecursionlimit(500000)
def input():
    return sys.stdin.readline()[:-1]

def main():
    H,W = list(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)]



    DP = [[[0]*(80*160+1) for j in range(W)] for i in range(H)]

    DP[0][0][C[0][0]] = 1

    for j in range(1,W):
        for k in range(80*160+1):
            if DP[0][j-1][k] == 1:
                DP[0][j][abs(k-C[0][j])] = 1
                DP[0][j][abs(k+C[0][j])] = 1

    for i in range(1,H):
        for k in range(80*160+1):
            if DP[i-1][0][k] == 1:
                DP[i][0][abs(k-C[i][0])] = 1
                DP[i][0][abs(k+C[i][0])] = 1


    for i in range(1,H):
        for j in range(1,W):
            for k in range(80*160+1):
                if DP[i][j-1][k] == 1 or DP[i-1][j][k] == 1:
                    DP[i][j][abs(k-C[i][j])] = 1
                    DP[i][j][abs(k+C[i][j])] = 1

    for i in range(80*160+1):
        if DP[H-1][W-1][i]==1:
            print(i)
            break

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
A = [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):
        A[i][j] = abs(A[i][j]-b[j])
NUM = 6400
DP = [[[0]*NUM for i in range(W)]for j in range(H)]
DP[0][0][A[0][0]] = 1
i = 0
for j in range(W-1):
    a = A[i][j+1]
    for k in range(NUM):
        if DP[i][j][k] == 1:
            if 0 <= a-k < NUM:
                DP[i][j+1][a-k] = 1
            if 0 <= k-a < NUM:
                DP[i][j+1][k-a] = 1
            if 0 <= k+a < NUM:
                DP[i][j+1][k+a] = 1
j = 0
for i in range(H-1):
    a = A[i+1][j]
    for k in range(NUM):
        if DP[i][j][k] == 1:
            if 0 <= a-k < NUM:
                DP[i+1][j][a-k] = 1
            if 0 <= k-a < NUM:
                DP[i+1][j][k-a] = 1
            if 0 <= k+a < NUM:
                DP[i+1][j][k+a] = 1
for i in range(H-1):
    for j in range(W-1):
        a = A[i+1][j+1]
        for k in range(NUM):
            if DP[i+1][j][k] == 1:
                if 0 <= a-k < NUM:
                    DP[i+1][j+1][a-k] = 1
                if 0 <= k-a < NUM:
                    DP[i+1][j+1][k-a] = 1
                if 0 <= k+a < NUM:
                    DP[i+1][j+1][k+a] = 1
            if DP[i][j+1][k] == 1:
                if 0 <= a-k < NUM:
                    DP[i+1][j+1][a-k] = 1
                if 0 <= k-a < NUM:
                    DP[i+1][j+1][k-a] = 1
                if 0 <= k+a < NUM:
                    DP[i+1][j+1][k+a] = 1

print(DP[-1][-1].index(1))

Submission status: Accepted

Solution code:
from itertools import product

def offset(a, b):
    result = 0
    if b == 0: return 0
    for i in range(b+1):
        if (a >> i) & 1:
            result |= (1 << b) >> i
    return result

H, W = map(int, input().split())
diff = [list(map(int, input().split())) for _ in range(H)]
M = 80
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])
dp = [[0]*W for _ in range(H)]
dp[0][0] = 1 << diff[0][0]
for i, j in product(range(H), range(W)):
    if (i, j) == (H-1, W-1): break
    if i+1 < H:
        k = diff[i+1][j]
        dp[i+1][j] |= (dp[i][j] >> k) | (dp[i][j] << k) | (offset(dp[i][j], k))
    if j+1 < W:
        k = diff[i][j+1]
        dp[i][j+1] |= (dp[i][j] >> k) | (dp[i][j] << k) | (offset(dp[i][j], k))
ans = dp[H-1][W-1]
print((ans & -ans).bit_length() - 1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
H, W = map(int, input().split())
A = []
for _ in range(H):
    A.append(list(map(int, input().split())))
B = []
C = []
for y in range(H):
    B.append(list(map(int, input().split())))
    C.append(list(abs(a-b) for (a, b) in zip(A[y], B[y])))
VMAX = 80*159+1
dp = [[0 for _ in range(W)] for _ in range(H)]
dp[0][0] |= 1 << C[0][0]
for y in range(H):
    for x in range(W):
        if y==0 and x==0:
            continue
        if y-1 >= 0:
            dp[y][x] |= dp[y-1][x] << C[y][x]
            dp[y][x] |= dp[y-1][x] >> C[y][x]
            d = C[y][x]+1
            r = format(dp[y-1][x] & (2**d-1), '0'+str(d)+'b')
            r = r[::-1]
            dp[y][x] |= int(r, 2)
        if x-1 >= 0:
            dp[y][x] |= dp[y][x-1] << C[y][x]
            dp[y][x] |= dp[y][x-1] >> C[y][x]
            d = C[y][x]+1
            r = format(dp[y][x-1] & (2**d-1), '0'+str(d)+'b')
            r = r[::-1]
            dp[y][x] |= int(r, 2)
ans = -1
for v in range(VMAX):
    if dp[-1][-1] >> v & 1:
        ans = v
        break
print(ans)