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:
maxV = 80*(80+80)

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

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

for i in range(H):
    for j in range(W):
        A, B = Ass[i][j], Bss[i][j]
        if A > B:
            A, B = B, A
        if i == 0 and j == 0:
            dp[i][j] = 1<<(maxV+B-A) | 1<<(maxV-B+A)
        if i > 0:
            dp[i][j] |= dp[i-1][j]<<(B-A) | dp[i-1][j]>>(B-A)
        if j > 0:
            dp[i][j] |= dp[i][j-1]<<(B-A) | dp[i][j-1]>>(B-A)

bitset = dp[-1][-1]
mask = 1<<(2*maxV)
ans = maxV
for i in range(-maxV, maxV+1):
    if bitset & mask:
        ans = min(ans, abs(i))
    mask >>= 1

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

h, w = map(int, input().split())
A = [0]*h
B = [0]*h
for _ in range(h):
  A[_] = list(map(int, input().split()))
  
for _ in range(h):
  B[_] = list(map(int, input().split()))

C = [[0]*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])
    
dp = [[0]*w for _ in range(h)]
D = 80 * (h + w)
L = 2*D + 1
dp[0][0] = np.zeros(L, np.bool)
dp[0][0][D+C[0][0]] = 1
for i in range(h):
  for j in range(w):
    if i == 0 and j == 0:
      continue
    x = np.zeros(L, np.bool)
    if i != 0:
      x[C[i][j]:] |= dp[i-1][j][:L-C[i][j]]
      x[:L-C[i][j]] |= dp[i-1][j][C[i][j]:]
    if j != 0:
      x[C[i][j]:] |= dp[i][j-1][:L-C[i][j]]
      x[:L-C[i][j]] |= dp[i][j-1][C[i][j]:]
    dp[i][j] = x
    
temp = np.where(dp[-1][-1]>0)[0]-D
temp = np.abs(temp)
print(np.min(temp))

Submission status: Accepted

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)]
grid = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
  for j in range(w):
    grid[i][j] = abs(a[i][j]-b[i][j])
dp = [[0 for j in range(w)] for k in range(h)]
buf = (h+w)*80
for i in range(h):
  for j in range(w):
      t = grid[i][j]
      if i == j == 0:
        dp[i][j] = 1 << buf+t | 1 << buf-t
      if j > 0:
        dp[i][j] = dp[i][j] | dp[i][j-1] << t | dp[i][j-1] >> t
      if i > 0:
        dp[i][j] = dp[i][j] | dp[i-1][j] << t | dp[i-1][j] >> t
for i in range(buf):
  if (dp[h-1][w-1] & 1 << buf+i) or (dp[h-1][w-1] & 1 << buf-i):
    print(i)
    exit()

Submission status: Accepted

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)]
grid = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
  for j in range(w):
    grid[i][j] = abs(a[i][j]-b[i][j])
dp = [[0 for j in range(w)] for k in range(h)]
buf = (h+w)*80
for i in range(h):
  for j in range(w):
      t = grid[i][j]
      if i == j == 0:
        dp[i][j] = 1 << buf+t | 1 << buf-t
      if j > 0:
        dp[i][j] = dp[i][j] | dp[i][j-1] << t | dp[i][j-1] >> t
      if i > 0:
        dp[i][j] = dp[i][j] | dp[i-1][j] << t | dp[i-1][j] >> t
for i in range(buf):
  if (dp[h-1][w-1] & 1 << buf+i) or (dp[h-1][w-1] & 1 << buf-i):
    print(i)
    exit()

Submission status: Accepted

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
mod2 = 998244353
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)]
    m = 1 << (80*80*2+3)
    r = [[0]*w for _ in range(h)]
    c = abs(a[0][0] - b[0][0])
    r[0][0] |= (1 << (80*80+1)) << c
    r[0][0] |= (1 << (80*80+1)) >> c
    for i in range(h):
        for j in range(w):
            if i == 0 and j == 0:
                continue
            c = abs(a[i][j] - b[i][j])
            t = 0
            if i > 0:
                t |= (r[i-1][j] << c) % m
                t |= r[i-1][j] >> c
            if j > 0:
                t |= (r[i][j-1] << c) % m
                t |= r[i][j-1] >> c
            r[i][j] = t

    c = r[-1][-1]
    t = 10000
    for i in range((80*80*2+3)):
        if (1<<i) & c > 0:
            k = abs(i-(80*80+1))
            if t > k:
                t = k

    return t


print(main())

Submission status: Accepted

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

C = [[] for i in range(H)]
for i,(arow,brow) in enumerate(zip(A,B)):
    for a,b in zip(arow,brow):
        d = abs(a-b)
        C[i].append(d)

ofs = (H+W)*100
dp = [0] * W
dp[0] = (1<<ofs)
for i,crow in enumerate(C):
    dp2 = [0] * W
    for j,(c,d) in enumerate(zip(C[i],dp)):
        dp2[j] |= (d<<c)
        dp2[j] |= (d>>c)
    for j,c in enumerate(C[i]):
        if j==0: continue
        dp2[j] |= (dp2[j-1]<<c)
        dp2[j] |= (dp2[j-1]>>c)
    dp = dp2

ans = ofs
l = len(bin(dp[-1]))
for i in range(l):
    if dp[-1] & (1<<i):
        ans = min(ans, abs(i-ofs))
print(ans)

Submission status: Accepted

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)]#cを配列にしてfor文と干渉してた
dp = [[0]*w for i in range(h)]#dp = [[[0] for i in range(w)] for j in range(h)]にしてたので、各要素がリストになってた
ofs = 80*(h + w)#h*wにしてた

dp[0][0] = (1<<(ofs+C[0][0]) | 1<<(ofs-C[0][0]))#(1<<ofs+c[0][0] | 1<<ofs-c[0][0])にしてた
for r in range(h):
    for c in range(w):
        if c>0:
            dp[r][c] |= (dp[r][c-1]<<C[r][c] | dp[r][c-1]>>C[r][c])
        if r>0:
            dp[r][c] |= (dp[r-1][c] << C[r][c] | dp[r-1][c] >> C[r][c])

dp[h-1][w-1] >>= ofs#ofs-1にしてた
for i in range(ofs):
    if dp[h-1][w-1]>>i & 1:
        print(i)
        break

Submission status: Accepted

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

A = []
B = []
abs_diff = [[0]*(W+1) for h in range(H+1)]

for h in range(H):
  A.append(list(map(int, input().split())))
  
for h in range(H):
  B.append(list(map(int, input().split())))

max_diff = 0
for h in range(H):
  for w in range(W):
    d = abs(A[h][w] - B[h][w])
    max_diff = max(max_diff, d)
    abs_diff[h+1][w+1] = d

base = max_diff*(H + W)
dp = [[0 for w in range(W+1)] for h in range(H+1)]
dp[0][1] = dp[1][0] = 1 << base
for h in range(1, H+1):
  for w in range(1, W+1):
    dp[h][w] = (
      (dp[h-1][w] << abs_diff[h][w]) | (dp[h-1][w] >> abs_diff[h][w]) 
      | (dp[h][w-1] << abs_diff[h][w]) | (dp[h][w-1] >> abs_diff[h][w]))


positive = bin(dp[H][W] >> base)
print(positive[::-1].find('1'))

Submission status: Accepted

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)]
dp=[[[0]*(80*(h+w+1)+1) for i in range(w)] for j in range(h)]
dp[0][0][abs(a[0][0]-b[0][0])]=1
for i in range(h):
  for j in range(w):
    c=abs(a[i][j]-b[i][j])
    if i!=0 or j!=0:
      for k in range(80*(i+j+1)+1):
        dp[i][j][k]=dp[i-1][j][abs(k-c)]|dp[i-1][j][k+c]|dp[i][j-1][abs(k-c)]|dp[i][j-1][k+c]
for i in range(80*(h+w+1)+1):
  if dp[h-1][w-1][i]==1:
    print(i)
    break

Submission status: Accepted

Solution code:
def main():
  h,w=map(int,input().split())
  a=[list(map(int,input().split())) for i in range(h)]
  b=[list(map(int,input().split())) for i in range(h)]
  dp=[[[0]*(80*(h+w+1)+1) for i in range(w)] for j in range(h)]
  dp[0][0][abs(a[0][0]-b[0][0])]=1
  for i in range(h):
    for j in range(w):
      c=abs(a[i][j]-b[i][j])
      if i!=0 or j!=0:
        for k in range(80*(i+j+1)+1):
          dp[i][j][k]=dp[i-1][j][abs(k-c)]|dp[i-1][j][k+c]|dp[i][j-1][abs(k-c)]|dp[i][j-1][k+c]
  for i in range(80*(h+w+1)+1):
    if dp[h-1][w-1][i]==1:
      print(i)
      break

if __name__=='__main__':
  main()

Submission status: Accepted

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

def main():
  h,w=map(int,input().split())
  a=[list(map(int,input().split())) for i in range(h)]
  b=[list(map(int,input().split())) for i in range(h)]
  dp=[[[0]*(80*(h+w+1)+1) for i in range(w)] for j in range(h)]
  dp[0][0][abs(a[0][0]-b[0][0])]=1
  for i in range(h):
    for j in range(w):
      c=abs(a[i][j]-b[i][j])
      if i!=0 or j!=0:
        for k in range(80*(i+j+1)+1):
          dp[i][j][k]=dp[i-1][j][abs(k-c)]|dp[i-1][j][k+c]|dp[i][j-1][abs(k-c)]|dp[i][j-1][k+c]
  for i in range(80*(h+w+1)+1):
    if dp[h-1][w-1][i]==1:
      print(i)
      break

if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
def main():
    H, W = map(int, input().split())
    N = 80 * (H+W) // 2
    A = [list(map(int, input().split())) for _ in range(H)]
    B = [list(map(int, input().split())) for _ in range(H)]
    dp = [[set() for _ in range(W+1)] for _ in range(2)]
    dp[0][1].add(0)
    def ltN(x): return x <= N
    for i in range(H):
        dp[(i+1) & 1] = [set() for _ in range(W+1)]
        for j in range(W):
            diff = abs(A[i][j] - B[i][j])
            tmp = set()
            for x in dp[i & 1][j + 1]:
                tmp.add(abs(x + diff))
                tmp.add(abs(x - diff))
            for x in dp[(i+1) & 1][j]:
                tmp.add(abs(x + diff))
                tmp.add(abs(x - diff))
            dp[(i+1) & 1][j+1] = tmp
    print(min(dp[H & 1][W]))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:

import sys
from collections import defaultdict
from collections import deque
import numpy as np
import heapq
from heapq import heappush, heappop
import itertools
import math
import copy

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

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

for _ in range(H):
    b = list(map(int, input().split()))
    B.append(b)

C = []
for i in range(H):
    cs = []
    for j in range(W):
        c = abs(A[i][j] - B[i][j])
        cs.append(c)

    C.append(cs)


X = (H+W) * 80
L = X + X + 1

dp = [[0] * W for _ in range(H)]
dp[0][0] = np.zeros(L, np.bool)
d = C[0][0]
dp[0][0][X+d] = 1
dp[0][0][X-d] = 1

for r in range(H):
    for c in range(W):
        if r == 0 and c == 0:
            continue

        l = np.zeros(L, np.bool)
        d = C[r][c]

        if r != 0:
            l[d:] |= dp[r-1][c][:L-d]
            l[:L-d] |= dp[r-1][c][d:]

        if c != 0:
            l[d:] |= dp[r][c-1][:L-d]
            l[:L-d] |= dp[r][c-1][d:]

        dp[r][c] = l

dp = dp[-1][-1]
d = np.where(dp)[0] - X
ans = np.abs(d).min()
print(ans)

Submission status: Accepted

Solution code:
# at ABC 147 e (500)
import sys
X, Y, U = [], [], []
if True:
    H, W, *nums = map(int, sys.stdin.read().split())
    i = 0
    for _ in range(H):
        X.append(nums[i:i + W])
        i += W
        U.append([0] * W)
    for _ in range(H):
        Y.append(nums[i:i + W])
        i += W
else:    
    H, W = map(int, input().split())
    for _ in range(H):
        X.append(list(map(int, input().split())))
        U.append([0 for _ in range(W)])
    for _ in range(H):
        Y.append(list(map(int, input().split())))

mid = 80*80

init = abs(X[0][0] - Y[0][0])
U[0][0] = (1 << (mid - init)) | (1 << (mid + init))

for i in range(W):
    for j in range(H):
        k = abs(X[j][i] - Y[j][i])
        if j > 0:
            U[j][i] |= (U[j - 1][i] << k)
            U[j][i] |= (U[j - 1][i] >> k)
        if i > 0:
            U[j][i] |= (U[j][i - 1] << k)
            U[j][i] |= (U[j][i - 1] >> k)
#        U[j][i] = U[j][i] & ((1 << (2 * mid)) - 1)
    
i = 0
min_ = float("inf")
while True:
     if U[-1][-1] & 1:
         min_ = min(min_, abs(i - mid))
     U[-1][-1] = U[-1][-1] >> 1
     i += 1
     if i >= 2 * mid:
         break
print(min_)

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
A=[]
A.append([0 for i in range(W+1)])
for i in range(H):
    a=[0]+list(map(int,input().split()))
    A.append(a)
B=[]
B.append([0 for i in range(W+1)])
for i in range(H):
    b=[0]+list(map(int,input().split()))
    B.append(b)
C=[[0 for i in range(W+1)]for j in range(H+1)]
for i in range(H+1):
    for j in range(W+1):
        C[i][j]=abs(A[i][j]-B[i][j])
        
ST=1<<80*160+1

dp=[[0 for i in range(W+1)]for j in range(H+1)]
dp[0][1]=ST
for i in range(1,H+1):
    for j in range(1,W+1):
        dp[i][j] |= (dp[i-1][j]<<C[i][j]) |(dp[i-1][j]>>C[i][j])
        dp[i][j] |= (dp[i][j-1]<<C[i][j]) |(dp[i][j-1]>>C[i][j])
#print(bin(dp[-1][-1]>>7))
ANS=list(bin(dp[-1][-1]>>80*160+1))[::-1]
#print(ANS)
for i in range(len(ANS)):
    if ANS[i]=="1":
        print(i)
        exit()

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

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

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

c = 80*(H+W-1)+1

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

for h in range(H):
    for w in range(W):
        if h==0 and w==0:
            DP[h][w] = 1 << (C[h][w]+c)
        elif h==0:
            DP[h][w] = (DP[h][w-1] << C[h][w]) | (DP[h][w-1] >> C[h][w])
        elif w==0:
            DP[h][w] = (DP[h-1][w] << C[h][w]) | (DP[h-1][w] >> C[h][w])
        else:
            DP[h][w] = (DP[h][w-1] << C[h][w]) | (DP[h][w-1] >> C[h][w]) | (DP[h-1][w] << C[h][w]) | (DP[h-1][w] >> C[h][w])

ans = float('inf')
now = DP[H-1][W-1]
tmpans = -c
while now != 0:
    if now%2==1:
        ans = min(ans,abs(tmpans))
    tmpans += 1
    now = now >> 1

print(ans)

Submission status: Accepted

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

import sys
from pprint import pprint
sys.setrecursionlimit(300000)


def solve(H: int, W: int, A: "List[List[int]]", B: "List[List[int]]"):
    diffs = [[0] * (W + 1) for _ in range(H + 1)]
    for i in range(H):
        for j in range(W):
            diffs[i][j] = abs(A[i][j] - B[i][j])
    dp = [[[0] * 6401 for _ in range(W + 1)] for _ in range(H + 1)]
    dp[0][0][diffs[0][0]] += 1
    for i in range(H):
        for j in range(W):
            tmp = dp[i][j]
            for val, flg in enumerate(tmp):
                if not flg:
                    continue
                if val + diffs[i + 1][j] <= 6400:
                    dp[i + 1][j][abs(val + diffs[i + 1][j])] += 1
                if val + diffs[i][j + 1] <= 6400:
                    dp[i][j + 1][abs(val + diffs[i][j + 1])] += 1
                dp[i + 1][j][abs(val - diffs[i + 1][j])] += 1
                dp[i][j + 1][abs(val - diffs[i][j + 1])] += 1
                #dp[i + 1][j].add(abs(val + diffs[i + 1][j]))
                #dp[i + 1][j].add(abs(val - diffs[i + 1][j]))
                #dp[i][j + 1].add(abs(val + diffs[i][j + 1]))
                #dp[i][j + 1].add(abs(val - diffs[i][j + 1]))
    #ret = min(dp[H - 1][W - 1])
    ret = 0
    for val, flg in enumerate(dp[H - 1][W - 1]):
        if flg:
            ret = val
            break
    print(ret)
    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:
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)]
s=[0]*w
s[0]=p=1<<6400
for i in range(h):
    for j in range(w):
        d=abs(a[i][j]-b[i][j])
        if j>0:
            s[j]|=s[j-1]
        s[j]=(s[j]<<d)|(s[j]>>d)
t=s[-1]
for i in range(6401):
    if t&(p<<i) or t&(p>>i):
        print(i)
        break

Submission status: Accepted

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

diffs = []
for y in range(h):
    row = map(int, input().split())
    diffs.append(list(row))

for y in range(h):
    row = map(int, input().split())
    for x, b in zip(range(w), row):
        diffs[y][x] = abs(diffs[y][x] - b)

m = 80 * (h + w)
dp = [[0 for j in range(w)] for k in range(h)]
d = m - diffs[0][0]
dp[0][0] = 1 << d

for y in range(h):
    for x in range(w):
        if x == y == 0:
            continue
        diff = diffs[y][x]
        if y != 0:
            dp[y][x] |= dp[y-1][x] << diff
            dp[y][x] |= dp[y-1][x] >> diff
        if x != 0:
            dp[y][x] |= dp[y][x-1] << diff
            dp[y][x] |= dp[y][x-1] >> diff

end = bin(dp[-1][-1])[2:][::-1]  # reverse

candidates = [abs(i-m) for i, b in enumerate(end) if b == '1']
ans = min(candidates)
print(ans)

Submission status: Accepted

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

bitdp = [[0 for j in range(w)] for i in range(h)]
al = []
bl = []
for _ in range(h):
   a = list(map(int,input().split()))
   al.append(a)
for _ in range(h):
   b = list(map(int,input().split()))
   bl.append(b)
abl = [[] for i in range(h)]
for i in range(h):
   for j in range(w):
      abl[i].append(abs(al[i][j] - bl[i][j]))

bitdp[0][0] = 1 << h*w+abl[0][0]
for i in range(h):
   for j in range(w):
      if j != w-1:
         bitdp[i][j+1] |= bitdp[i][j] << abl[i][j+1] | bitdp[i][j] >> abl[i][j+1]
      if i != h-1:
         bitdp[i+1][j] |= bitdp[i][j] << abl[i+1][j] | bitdp[i][j] >> abl[i+1][j]

ans = []
for i in range(h*w*2+1):
   if (bitdp[-1][-1] >> i & 1):
      ans.append(abs(h*w-i))

print(min(ans))

Submission status: Accepted

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 = [0] * W
    bit_width = 80 * (H + W - 2)
    dp1[0] = 1 << (bit_width)
    for A_i, B_i in zip(A, B):
        dp2 = [0] * W
        
        diff = abs(A_i[0] - B_i[0])
        dp2[0] = (dp1[0] << diff) | (dp1[0] >> diff)
        
        for j, t in enumerate(zip(A_i[1:], B_i[1:]), start=1):
            A_ij, B_ij = t
            diff = abs(A_ij - B_ij)
            b = dp1[j] | dp2[j-1]
            dp2[j] = (b << diff) | (b >> diff)
        
        dp1 = dp2
    
    b = bin(dp2[-1])
    b = b[-bit_width-1:]
    print(b.index('1'))
 
solve()

Submission status: Accepted

Solution code:
def ints():
  return [int(x) for x in input().split()]
def readi():
  return int(input())

H, W = ints()
A = [ints() for _ in range(H)]
B = [ints() for _ in range(H)]
D = [[abs(A[h][w]-B[h][w]) for w in range(W)] for h in range(H)]

memo = {}
memo = {}


N=80*60
memo[(0, 0)] = 1 << (D[0][0]+N)

for h in range(H):
  for w in range(W):
    if h==0 and w==0:
      continue 

    d = D[h][w]
    f = 0
    if h>0:
      s = memo[(h-1, w)]
      f |= s<<d 
      f |= s>>d
    if w>0:
      s = memo[(h, w-1)]
      f |= s<<d
      f |= s>>d

    memo[(h, w)] = f

def min_keta(n):
  b = bin(n>>N)
  for i in range(len(b)):
    if b[-i-1]=='1':
      return i

print(min_keta(memo[(H-1, W-1)]))

Submission status: Accepted

Solution code:
def solve(h, w, A, B):
    center = 80 * (h + w - 1)
    C = [[abs(A[r][c] - B[r][c]) for c in range(w)] for r in range(h)]
    dp = [[0] * w for r in range(h)]
    dp[0][0] = (1 << (center + C[0][0])) | (1 << (center - C[0][0]))
    for r in range(h):
        for c in range(w):
            if r > 0:
                dp[r][c] |= (dp[r-1][c] << C[r][c]) | (dp[r-1][c] >> C[r][c])
            if c > 0:
                dp[r][c] |= (dp[r][c-1] << C[r][c]) | (dp[r][c-1] >> C[r][c])
    mask = bin(dp[-1][-1] >> center)
    return mask[::-1].find("1")
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)]
print(solve(h, w, A, B))

Submission status: Accepted

Solution code:
import numpy as np

H,W = map(int,input().split())
A = np.zeros((H,W))
for c in [1,-1]:
    for i in range(H):
        num = list(map(int,input().split()))
        A[i,:] += np.array(num) * c

M = 160*80
dp = [[0]*W for _ 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] << int(a)) | (dp[i][j] >> int(a))
i = M
while True:
    if (dp[H-1][W-1] >> i) & 1:
        print(i-M)
        break
    i += 1

Submission status: Accepted

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)]
grid = [[0] * w for _ in range(h)]
for i in range(h):
    for j in range(w):
        m = abs(A[i][j] - B[i][j])
        grid[i][j] = m

bias_inf = 2000
dp = [[[0 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]] = 1
dp[0][0][0 + grid[0][0]] = 1
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]] = 1
                    dp[i+1][j][k + grid[i+1][j]] = 1
                    dp[i][j+1][k - grid[i][j+1]] = 1
                    dp[i+1][j][k - grid[i+1][j]] = 1
                elif j == w-1:
                    dp[i+1][j][k - grid[i+1][j]] = 1
                    dp[i+1][j][k + grid[i+1][j]] = 1
                else:
                    dp[i][j+1][k - grid[i][j+1]] = 1
                    dp[i][j+1][k + grid[i][j+1]] = 1
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: Accepted

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(H: int, W: int, A: "List[List[int]]", B: "List[List[int]]"):
    base = [[abs(A[h][w]-B[h][w]) for w in range(W)] for h in range(H)]
    mx = (1 << 12800) - 1
    table = [[0]*W for _ in range(H)]
    table[0][0] = (1 << (6400 + base[0][0])) | (1 << (6400-base[0][0]))
    for h in range(H):
        for w in range(W):
            if h > 0:
                table[h][w] |= (table[h-1][w] << base[h][w])
                table[h][w] |= (table[h-1][w] >> base[h][w])
            if w > 0:
                table[h][w] |= (table[h][w-1] << base[h][w])
                table[h][w] |= (table[h][w-1] >> base[h][w])
            table[h][w] &= mx

    m = INF
    for j in range(12800):
        i = (table[H-1][W-1] >> j) & 1
        if i == 1:
            m = min(m, abs(j-6400))
    print(m)
    # print(table[H-1])

    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:
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)]
Diff = [[0] * (W + 1) for _ in range(H + 1)]
M = 0
for i in range(H):
    for j in range(W):
        m = abs(A[i][j] - B[i][j])
        Diff[i][j] = m
        M += m

dp = [[0] * (W + 1) for _ in range(H + 1)]
dp[0][0] |= (1 << Diff[i][j])

for i in range(0, H):
    for j in range(0, W):
        here = dp[i][j]
        s = Diff[i][j]
        ni = nj = (here << s) | (here >> s)
        ex = 0
        for k in range(1, s + 1):
            if (here >> k) & 1:
                ex |= (1 << (s - k))
        dp[i + 1][j] |= (ni | ex)
        dp[i][j + 1] |= (nj | ex)

a = dp[H - 1][W - 1]
ans = 0
for k in range(M + 1):
    if (a >> k) & 1:
        ans = k
        break

print(k)

Submission status: Accepted

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)]
Diff = [[0] * (W + 1) for _ in range(H + 1)]
M = 0
for i in range(H):
    for j in range(W):
        m = abs(A[i][j] - B[i][j])
        Diff[i][j] = m
        M += m

dp = [[0] * (W + 1) for _ in range(H + 1)]
dp[0][0] |= (1 << Diff[i][j])

for i in range(0, H):
    for j in range(0, W):
        here = dp[i][j]
        s = Diff[i][j]
        ni = 0
        nj = 0
        ni |= (here << s)
        nj |= (here << s)
        ni |= (here >> s)
        nj |= (here >> s)
        ex = 0
        for k in range(1, s + 1):
            if (here >> k) & 1:
                ex |= (1 << (s - k))
        ni |= ex
        nj |= ex
        dp[i + 1][j] |= ni
        dp[i][j + 1] |= nj

a = dp[H - 1][W - 1]
ans = 0
for k in range(M + 1):
    if (a >> k) & 1:
        ans = k
        break

print(k)

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

ofs=80*(H+W)

X[0][0]=1<<(ofs+C[0][0])|1<<(ofs-C[0][0])
for i in range(H):
    for j in range(W):
        if i>0:
            X[i][j]|=(X[i-1][j]<<C[i][j]|X[i-1][j]>>C[i][j])
        if j>0:
            X[i][j]|=(X[i][j-1]<<C[i][j]|X[i][j-1]>>C[i][j])

for k in range(ofs):
    if (X[i][j]>>(k+ofs)&1):
        break
print(k)

Submission status: Accepted

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 = [[abs(a-b) for a, b in zip(ar, br)] for ar, br in zip(A, B)]
    S = W*H*80
    dp = [[0 for _ in range(W)] for __ in range(H)]
    dp[0][0] = 1 << (S-M[0][0]) | 1 << (S+M[0][0])
    for i in range(H):
        for j in range(W):
            for k, l in [(-1, 0), (0, -1)]:
                D = M[i][j]
                dp[i][j] |= dp[i+k][j+l] << D
                dp[i][j] |= dp[i+k][j+l] >> D

    ans = None
    cand = dp[H-1][W-1]
    for i in range(H*W*80):
        if cand & (1 << (S+i)) != 0:
            ans = i
            break
    assert ans is not None
    return ans


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

    # H = 80
    # W = 80

    # # A = [[random.randint(0, 1000) for __ in range(W)] for _ in range(H)]
    # # B = [[random.randint(0, 1000) for __ in range(W)] for _ in range(H)]
    # A = [[0 for __ in range(W)] for _ in range(H)]
    # B = [[random.randint(0, 80) for __ in range(W)] for _ in range(H)]
    # print(slv(H, W, A, B))


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)]
B = [list(map(int, input().split())) for _ in range(H)]

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

SIZE = 20000

D = abs(A[0][0] - B[0][0])
dp[0][0] = 1 << SIZE - D | 1 << SIZE + D
#print("dp:", dp)

for i in range(H):
  for j in range(W):
    D = abs(A[i][j] - B[i][j])
    dp[i][j] |= dp[i - 1][j] << D | dp[i - 1][j] >> D
    dp[i][j] |= dp[i][j - 1] << D | dp[i][j - 1] >> D

#for i in range(H):
#  a = list(map(lambda x: bin(x)[2::], dp[i]))
#  print(a)

for i in range(SIZE):
  if (dp[-1][-1] >> (SIZE + i)) & 1:
    print(i)
    exit()

Submission status: Accepted

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):
    if i >= 2:
        table[i - 2] = None
    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)