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
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)]
d=[]
for i in range(h):
  d.append([abs(a[i][j]-b[i][j]) for j in range(w)])
dp=np.zeros((h,w,12800))
# dp[r][c][j]:(r,c)まで考えたときjにできるか。0：できない。1以上：できる。
dp[0,0,d[0][0]+6400]=1
for i in range(w-1):
  if d[0][i+1]==0:
    dp[0,i+1]+=dp[0,i]
    continue
  dp[0,i+1,d[0][i+1]:]+=dp[0,i,:-d[0][i+1]]
  dp[0,i+1,:-d[0][i+1]]+=dp[0,i,d[0][i+1]:]
for i in range(h-1):
  if d[i+1][0]==0:
    dp[i+1,0]+=dp[i,0]
    continue
  dp[i+1,0,d[i+1][0]:]+=dp[i,0,:-d[i+1][0]]
  dp[i+1,0,:-d[i+1][0]]+=dp[i,0,d[i+1][0]:]
for r in range(1,h):
  for c in range(1,w):
    if d[r][c]==0:
      dp[r,c]+=dp[r-1,c]
      dp[r,c]+=dp[r,c-1]
      continue
    dp[r,c,d[r][c]:]+=dp[r-1,c,:-d[r][c]]
    dp[r,c,:-d[r][c]]+=dp[r-1,c,d[r][c]:]
    dp[r,c,d[r][c]:]+=dp[r,c-1,:-d[r][c]]
    dp[r,c,:-d[r][c]]+=dp[r,c-1,d[r][c]:]
print(min([abs(e-6400) for e in np.where(dp[h-1,w-1]>0)[0]]))

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
A=[list(map(int,input().split())) for i 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])
D=80*(H+W)+1
D2=D*2
dp=[[0]*W for i in range(H)]
dp[0][0]|=1<<(D+A[0][0])
dp[0][0]|=1<<(D-A[0][0])
for i in range(H):
    for j in range(W):
        if i:
            dp[i][j]|=dp[i-1][j]<<A[i][j]
            dp[i][j]|=dp[i-1][j]>>A[i][j]
        if j:
            dp[i][j]|=dp[i][j-1]<<A[i][j]
            dp[i][j]|=dp[i][j-1]>>A[i][j]
res=dp[-1][-1]
ans=10**18
for i in range(D2):
    if res>>i&1:
        ans=min(ans,abs(D-i))
print(ans)

Submission status: Accepted

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

    MAX_BIAS = 80 * (H + W - 1)

    A = []
    for _ in range(H):
        A += map(int, input().split())  # 速度のため一次元で管理
    B = []
    for _ in range(H):
        B += map(int, input().split())  # 速度のため一次元で管理

    dp = [0] * (H * W)  # 速度のため一次元で管理,dp[pos]:=bit,[-80*(H+W-1),80*(H+W-1)]->[0,2*80*(H+W-1)]
    dp[0] |= (1 << MAX_BIAS)

    for r in range(H):
        for c in range(W):
            p = r * W + c
            d = abs(A[p] - B[p])
            x = dp[p]
            if r > 0:
                x |= dp[p - W]
            if c > 0:
                x |= dp[p - 1]
            dp[p] = (x << d) | (x >> d)

    ans = MAX_BIAS
    for j in range(2 * MAX_BIAS + 1):
        if (dp[H * W - 1] >> j) & 1:
            t = j - MAX_BIAS
            if ans > abs(t):
                ans = abs(t)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

H, W = map(int, input().split())
A = np.array([input().split() for _ in range(H)], dtype=int)
B = np.array([input().split() for _ in range(H)], dtype=int)
dif = np.abs(A - B).tolist()

U = (H + W) * 80
Um = U // 2

dp = [[[] for _ in range(W)] for _ in range(H)]
X = np.zeros(U + 1, dtype=bool)
X[Um + dif[0][0]] = True
X[Um - dif[0][0]] = True
dp[0][0] = X


for i in range(H):
    for j in range(W):
        if i == j == 0:
            continue
        d = dif[i][j]
        X = np.zeros(U + 1, dtype=bool)
        if d:
            if i > 0:
                X[d:] |= dp[i - 1][j][:-d]
                X[:-d] |= dp[i - 1][j][d:]
            if j > 0:
                X[d:] |= dp[i][j - 1][:-d]
                X[:-d] |= dp[i][j - 1][d:]
        else:
            if i > 0:
                X |= dp[i - 1][j]
            if j > 0:
                X |= dp[i][j - 1]
        dp[i][j] = X

tmp = np.arange(U+1)[dp[H-1][W-1]]
ans = np.abs(tmp - Um).min()
print(ans)

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)]
can_make = [[None for _ in range(W)] for _ in range(H)]
for i in range(H):
    for j in range(W):
        x = A[i][j] - B[i][j]
        if i == j == 0:
            can_make[i][j] = set([abs(x)])
            continue
        st = set()
        ub = 80 * (W - i + H - j)
        if i > 0:
            for y in can_make[i-1][j]:
                if abs(y + x) <= ub:
                    st.add(abs(y + x))
                if abs(y - x) <= ub:
                    st.add(abs(y - x))
        if j > 0:
            for y in can_make[i][j-1]:
                if abs(y + x) <= ub:
                    st.add(abs(y + x))
                if abs(y - x) <= ub:
                    st.add(abs(y - x))
        can_make[i][j] = st
print(min(can_make[-1][-1], key=lambda x: abs(x)))

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
A = [tuple(map(int, input().split())) for _ in range(H)]
B = [tuple(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)]

D = 80 * (H + W) + 1
D2 = D * 2

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

dp[0][0] |= 1 << (D + C[0][0])
dp[0][0] |= 1 << (D - C[0][0])

for h in range(H):
    for w in range(W):
        c = C[h][w]
        if h >= 1:
            dp[h][w] |= dp[h - 1][w] << c
            dp[h][w] |= dp[h - 1][w] >> c
        if w >= 1:
            dp[h][w] |= dp[h][w - 1] << c
            dp[h][w] |= dp[h][w - 1] >> c

ans = D2
tmp = dp[H - 1][W - 1]

for i in range(D2):
    if (tmp >> i) & 1:
        ans = min(ans, abs(i - D))

print (ans)

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 = [[abs(a-b) for a,b in zip(arow,brow)] for arow,brow in zip(A,B)]

ofs = 80*(H+W)
dp = [[0]*W for _ in range(H)]
dp[0][0] = (1<<(ofs+C[0][0])) | (1<<(ofs-C[0][0]))
for i,crow in enumerate(C):
    for j,c in enumerate(crow):
        if i:
            dp[i][j] = (dp[i-1][j]<<c) | (dp[i-1][j]>>c)
        if j:
            dp[i][j] |= ((dp[i][j-1]<<c) | (dp[i][j-1]>>c))

ans = ofs*2
for i in range(ofs*2):
    if dp[-1][-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)]

Z = (H + W) * 80 + 10

dp = [[0] * (W + 1) for _ in range(H + 1)]
dp[0][0] = (1 << Z)

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

        dp[h + 1][w] |= (d << k) | (d >> k)
        dp[h][w + 1] |= (d << k) | (d >> k)

ans = 10**18
for a in (dp[H][W - 1], dp[H - 1][W]):
    for d in range(Z * 2 + 10):
        if a & (1 << d) != 0:
            ans = min(ans, abs(d - Z))
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)]

Z = 1000

dp = [[0] * (W + 1) for _ in range(H + 1)]
dp[0][0] = (1 << Z)

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

        dp[h + 1][w] |= (d << k) | (d >> k)
        dp[h][w + 1] |= (d << k) | (d >> k)

ans = 10**18
for a in (dp[H][W - 1], dp[H - 1][W]):
    for d in range(Z * 2 + 10):
        if a & (1 << d) != 0:
            ans = min(ans, abs(d - Z))
print(ans)

Submission status: Accepted

Solution code:


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

amap = [list(map(int, input().split())) for i in range(H)]
bmap = [list(map(int, input().split())) for i in range(H)]
dist_map = [[amap[y][x] - bmap[y][x] for x in range(W)] for y in range(H)]

mid = 80 * 80 * 5 // 2
# mid = 20
dp = [[1 << mid] * W for y in range(H)]

dp[0][0] = ((1 << (dist_map[0][0] + mid)) | (1 << (mid - dist_map[0][0])))


for x in range(1, W):
    y = 0
    d = abs(dist_map[y][x])
    dp[y][x] = (dp[y][x - 1] << d) | (dp[y][x - 1] >> d)


for y in range(1, H):
    x = 0
    d = abs(dist_map[y][x])
    dp[y][x] = (dp[y - 1][x] << d) | (dp[y - 1][x] >> d)


for y in range(1, H):
    for x in range(1, W):
        d = abs(dist_map[y][x])
        dp[y][x] = (dp[y][x - 1] << d) | (dp[y][x - 1] >> d) | ((dp[y - 1][x] << d) | (dp[y - 1][x] >> d))


ans = dp[-1][-1]

for i in range(mid + 1):
    if (ans & (1 << (mid - i))) or (ans & (1 << (mid + i))):
        print(i)
        exit()

Submission status: Accepted

Solution code:
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(n,base=2):
    rt=[]
    for tb in range(base**n):s=[tb//(base**bt)%base for bt in range(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)
 
YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
FourNb=[(1,0),(-1,0),(0,1),(0,-1)];EightNb=[(1,0),(-1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('EWNS',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()
 
class Tree:
    def __init__(self,inp_size=None,ls=None,init=True,index=0):
        self.LCA_init_stat=False
        self.ETtable=[]
        if init:
            if ls==None:
                self.stdin(inp_size,index=index)
            else:
                self.size=len(ls)+1
                self.edges,_=GI(self.size,self.size-1,ls,index=index)
        return
 
    def stdin(self,inp_size=None,index=1):
        if inp_size==None:
            self.size=int(input())
        else:
            self.size=inp_size
        self.edges,_=GI(self.size,self.size-1,index=index)
        return
    
    def listin(self,ls,index=0):
        self.size=len(ls)+1
        self.edges,_=GI(self.size,self.size-1,ls,index=index)
        return
 
    def __str__(self):
        return  str(self.edges)
 
    def dfs(self,x,func=lambda prv,nx,dist:prv+dist,root_v=0):
        q=deque()
        q.append(x)
        v=[-1]*self.size
        v[x]=root_v
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==-1:
                    q.append(nb)
                    v[nb]=func(v[c],nb,d)
        return v
 
    def EulerTour(self,x):
        q=deque()
        q.append(x)
        self.depth=[None]*self.size
        self.depth[x]=0
        self.ETtable=[]
        self.ETdepth=[]
        self.ETin=[-1]*self.size
        self.ETout=[-1]*self.size
        cnt=0
        while q:
            c=q.pop()
            if c<0:
                ce=~c
            else:
                ce=c
                for nb,d in self.edges[ce]:
                    if self.depth[nb]==None:
                        q.append(~ce)
                        q.append(nb)
                        self.depth[nb]=self.depth[ce]+1
            self.ETtable.append(ce)
            self.ETdepth.append(self.depth[ce])
            if self.ETin[ce]==-1:
                self.ETin[ce]=cnt
            else:
                self.ETout[ce]=cnt
            cnt+=1
        return
    
    def LCA_init(self,root):
        self.EulerTour(root)
        self.st=SparseTable(self.ETdepth,init_func=min,init_idl=inf)
        self.LCA_init_stat=True
        return
    
    def LCA(self,root,x,y):
        if self.LCA_init_stat==False:
            self.LCA_init(root)
        xin,xout=self.ETin[x],self.ETout[x]
        yin,yout=self.ETin[y],self.ETout[y]
        a=min(xin,yin)
        b=max(xout,yout,xin,yin)
        id_of_min_dep_in_et=self.st.query_id(a,b+1)
        return self.ETtable[id_of_min_dep_in_et]
 
class SparseTable: # O(N log N) for init, O(1) for query(l,r)
    def __init__(self,ls,init_func=min,init_idl=float('inf')):
        self.func=init_func
        self.idl=init_idl
        self.size=len(ls)
        self.N0=self.size.bit_length()
        self.table=[ls[:]]
        self.index=[list(range(self.size))]
        self.lg=[0]*(self.size+1)
        
        for i in range(2,self.size+1):
            self.lg[i]=self.lg[i>>1]+1
 
        for i in range(self.N0):
            tmp=[self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) for j in range(self.size)]
            tmp_id=[self.index[i][j] if self.table[i][j]==self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) else self.index[i][min(j+(1<<i),self.size-1)] for j in range(self.size)]
            self.table+=[tmp]
            self.index+=[tmp_id]
    
    # return func of [l,r)
    def query(self,l,r):
        if r>self.size:r=self.size
        #N=(r-l).bit_length()-1
        N=self.lg[r-l]
        return self.func(self.table[N][l],self.table[N][max(0,r-(1<<N))])
    
    # return index of which val[i] = func of v among [l,r)
    def query_id(self,l,r):
        if r>self.size:r=self.size
        #N=(r-l).bit_length()-1
        N=self.lg[r-l]
        a,b=self.index[N][l],self.index[N][max(0,r-(1<<N))]
        if self.table[0][a]==self.func(self.table[N][l],self.table[N][r-(1<<N)]):
            b=a
        return b
    
    def __str__(self):
        return str(self.table[0])
 
    def print(self):
        for i in self.table:
            print(*i)
 
class Comb:
    def __init__(self,n,mo=10**9+7):
        self.fac=[0]*(n+1)
        self.inv=[1]*(n+1)
        self.fac[0]=1
        self.fact(n)
        for i in range(1,n+1):
            self.fac[i]=i*self.fac[i-1]%mo
            self.inv[n]*=i
            self.inv[n]%=mo
        self.inv[n]=pow(self.inv[n],mo-2,mo)
        for i in range(1,n):
            self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
        return
    
    def fact(self,n):
        return self.fac[n]
        
    def invf(self,n):
        return self.inv[n]
 
    def comb(self,x,y):
        if y<0 or y>x:
            return 0
        return self.fac[x]*self.inv[x-y]*self.inv[y]%mo
 
show_flg=False
show_flg=True
ans=0
 

h,w=LI()
ans=0
a=[[0]*(1+w)]
b=[[0]*(1+w)]
for i in range(h):
    a.append([0]+LI())
for i in range(h):
    b.append([0]+LI())

MX=80*80*3
ini=1<<MX
dp=[[0 for i in range(w+1)]for j in range(h+1)]
dp[0][1]=ini

for i in range(1,h+1):
    for j in range(1,w+1):
        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)

ans=dp[h][w]
for i in range(MX+1):
    if (ans>>(MX+i))&1:
        print(i)
        exit()
    if (ans>>(MX-i))&1:
        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)]
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:
h, w = map(int, input().split())
mat = []
for i in range(h):
  a = list(map(int, input().split()))
  mat.append(a)
for i in range(h):
  b = list(map(int, input().split()))
  for j in range(w):
    mat[i][j] = abs(mat[i][j]-b[j])
m = max(map(max, mat))
dp = [[0b0 for i in range(w)] for k in range(h)]
dp[0][0] |= 0b1 << mat[0][0]
for y in range(h):
  for x in range(w):
        if x > 0:
          dp[y][x] |= dp[y][x-1] << mat[y][x]
          dp[y][x] |= dp[y][x-1] >> mat[y][x]
          anded = dp[y][x-1] & int('1'*(mat[y][x]+1), 2)
          reverse = format(anded, "0"+str(mat[y][x]+1)+"b")[::-1]

          dp[y][x] |= int(reverse, 2)
        if y > 0:
          dp[y][x] |= dp[y-1][x] << mat[y][x]
          dp[y][x] |= dp[y-1][x] >> mat[y][x]
          anded = dp[y-1][x] & int('1'*(mat[y][x]+1), 2)
          reverse = format(anded, "0"+str(mat[y][x]+1)+"b")[::-1]

          dp[y][x] |= int(reverse, 2)
        #print(bin(dp[y][x]))

keta = 0
while dp[h-1][w-1] % 2 == 0:
  keta += 1
  dp[h-1][w-1] //= 2
print(keta)

Submission status: Accepted

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


def reverse(d, x):
  res = 0
  for i in range(x+1):
    res <<= 1
    if (1<<i) & d:
      res |= 1
  return res


for i in range(h):
  for j in range(w):
    dp[i][j+1] |= (dp[i][j] << diff[i][j+1])
    dp[i][j+1] |= (dp[i][j] >> diff[i][j+1])
    dp[i][j+1] |= reverse(dp[i][j], diff[i][j+1])
    dp[i+1][j] |= (dp[i][j] << diff[i+1][j])
    dp[i+1][j] |= (dp[i][j] >> diff[i+1][j])
    dp[i+1][j] |= reverse(dp[i][j], diff[i+1][j])
last = dp[h-1][w-1]
for i in range(6401):
  if (last >> i) & 1:
    ans = i
    break
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# E: bit演算を活用して効率的に計算しないとTLEになる

# dp[[i][j]で、(i,j)で可能な偏りを格納していく
# 1, 2, 3が可能な場合は"00000111"と表現する
# n + m を可能にするには、n << mにすれば良い
# (1, 2, 3)に2を足して(3, 4, 5)を可能にするなら、
# "00011100"としたいので、n << mで良い
# (3, 4, 5)に±4する場合；
# 求めたいのは(7, 8, 9) | (-1, 0, 1)
# −１を1としたい

import sys
# 再起回数上限変更
# sys.setrecursionlimit(1000000)

H, W = map(int, input().split())
a = []
x = []

for i in range(H):
    a.append(list(map(int, input().split())))
for i in range(H):
    x.append(list(map(int, input().split())))
    for j in range(W):
        x[i][j] = abs(x[i][j] - a[i][j])


dp = [[0 for _ in range(W)] for _ in range(H)]
dp[0][0] = 1 << x[0][0]
# print(bin(dp[0][0]))


def reverse(d, x):
    res = 0
    for i in range(x+1):
        res <<= 1
        if (1<<i) & d:
            res |= 1
    return res


for i in range(H):
    for j in range(W):
        g = x[i][j]
        if i > 0:
            d1 = dp[i-1][j]
            dp[i][j] |= d1 << g | d1 >> g | reverse(d1, g)
        if j > 0:
            d2 = dp[i][j-1]
            dp[i][j] |= d2 << g | d2 >> g | reverse(d2, g)


a = dp[H-1][W-1]
for i in range(a.bit_length()):
    if a >> i & 1 == 1:
        print(i)
        sys.exit()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    #inf = 10**17
    #mod = 10**9 + 7

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

    mid = 6400
    dp = [[0]*w for _ in range(h)]
    dp[0][0] = (1<<(mid+c[0][0])) | (1<<(mid-c[0][0]))
    for x in range(h):
        for y in range(w):
            for dx, dy in [[0, 1], [1, 0]]:
                nx = x + dx
                ny = y + dy
                if 0<=nx<h and 0<=ny<w:
                    dp[nx][ny] = dp[nx][ny] | (dp[x][y]<<c[nx][ny])
                    dp[nx][ny] = dp[nx][ny] | (dp[x][y]>>c[nx][ny])
    
    for i in range(mid+1):
        if (dp[-1][-1]>>i) & 1:
            res = mid - i

    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    #inf = 10**17
    #mod = 10**9 + 7

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

    mid = 3200
    dp = [[0]*w for _ in range(h)]
    dp[0][0] = (1<<(mid+c[0][0])) | (1<<(mid-c[0][0]))
    for x in range(h):
        for y in range(w):
            for dx, dy in [[0, 1], [1, 0]]:
                nx = x + dx
                ny = y + dy
                if 0<=nx<h and 0<=ny<w:
                    dp[nx][ny] = dp[nx][ny] | (dp[x][y]<<c[nx][ny])
                    dp[nx][ny] = dp[nx][ny] | (dp[x][y]>>c[nx][ny])
    
    for i in range(mid+1):
        if (dp[-1][-1]>>i) & 1:
            res = mid - i

    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    #inf = 10**17
    #mod = 10**9 + 7

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

    mid = 12800
    dp = [[0]*w for _ in range(h)]
    dp[0][0] = (1<<(mid+c[0][0])) | (1<<(mid-c[0][0]))
    for x in range(h):
        for y in range(w):
            for dx, dy in [[0, 1], [1, 0]]:
                nx = x + dx
                ny = y + dy
                if 0<=nx<h and 0<=ny<w:
                    dp[nx][ny] = dp[nx][ny] | (dp[x][y]<<c[nx][ny])
                    dp[nx][ny] = dp[nx][ny] | (dp[x][y]>>c[nx][ny])
    
    for i in range(mid+1):
        if (dp[-1][-1]>>i) & 1:
            res = mid - i

    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    #inf = 10**17
    #mod = 10**9 + 7

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

    # 80*160//2 xbit目が1→数値x-6400を取る
    mid = 6400
    dp = [[0]*w for _ in range(h)]
    dp[0][0] = (1<<(mid+c[0][0])) | (1<<(mid-c[0][0]))
    for x in range(h):
        for y in range(w):
            for dx, dy in [[0, 1], [1, 0]]:
                nx = x + dx
                ny = y + dy
                if 0<=nx<h and 0<=ny<w:
                    dp[nx][ny] = dp[nx][ny] | (dp[x][y]<<c[nx][ny])
                    dp[nx][ny] = dp[nx][ny] | (dp[x][y]>>c[nx][ny])
    
    for i in range(mid+1):
        if dp[-1][-1] & 1:
            res = mid - i
        dp[-1][-1] >>= 1
    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    #inf = 10**17
    #mod = 10**9 + 7

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

    # 80*160//2 xbit目が1→数値x-6400を取る
    mid = 6400
    dp = [[0]*w for _ in range(h)]
    dp[0][0] = (1<<(mid+c[0][0])) | (1<<(mid-c[0][0]))
    for x in range(h):
        for y in range(w):
            for dx, dy in [[0, 1], [1, 0]]:
                nx = x + dx
                ny = y + dy
                if 0<=nx<h and 0<=ny<w:
                    dp[nx][ny] = dp[nx][ny] | (dp[x][y]<<c[nx][ny])
                    dp[nx][ny] = dp[nx][ny] | (dp[x][y]>>c[nx][ny])
    
    for i in range(mid+1):
        if (dp[-1][-1]>>i) & 1:
            res = mid - i
    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
H,W,*L = map(int, open(0).read().split())
A = L[:H*W]
B = L[H*W:]
C = [abs(b-a) for a,b in zip(A,B)]
U = max(C)*(H+W)
N = 2*U+1
INF = 10**10
dp = np.zeros((H,W,N),dtype=bool)
dp[0,0,C[0]+U] = True
for i in range(1,W):
  c = C[i]
  dp[0,i,c:] |= dp[0,i-1,:N-c]
  dp[0,i,:N-c] |= dp[0,i-1,c:]
for i in range(1,H):
  c = C[i*W]
  dp[i,0,c:] |= dp[i-1,0,:N-c]
  dp[i,0,:N-c] |= dp[i-1,0,c:]
for i in range(1,H):
  for j in range(1,W):
    c = C[i*W+j]
    dp[i,j,c:] |= dp[i,j-1,:N-c]
    dp[i,j,:N-c] |= dp[i,j-1,c:]
    dp[i,j,c:] |= dp[i-1,j,:N-c]
    dp[i,j,:N-c] |= dp[i-1,j,c:]
ans = np.min(np.abs(np.where(dp[H-1][W-1])[0]-U))
print(ans)

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 _ in range(h)]
  B = [list(map(int, input().split())) for _ in range(h)]
  M = 80*(h+w)
  dp = [[0]*w for i in range(h)]
  d = abs(A[0][0] - B[0][0])
  mask = (1 << (2*M)) - 1
  dp[0][0] |= 1 << (M-d)
  dp[0][0] |= 1 << (M+d)
  for i in range(h):
    for j in range(w):
      d = abs(A[i][j] - B[i][j])
      if i:
        dp[i][j] |= (dp[i-1][j] << d) & mask
        dp[i][j] |= dp[i-1][j] >> d
      if j:
        dp[i][j] |= (dp[i][j-1] << d) & mask
        dp[i][j] |= dp[i][j-1] >> d
  t = dp[-1][-1] >> M
  ans = (t & (-t)).bit_length() - 1
  print(ans)
  
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)]

pos = 160*80
dp=[[0]*w for i in range(h)]
sub=abs(a[0][0]-b[0][0])
dp[0][0]=1<<(pos-sub)|1<<(pos+sub)

for c in range(h):
    for l in range(w):
        sub=abs(a[c][l]-b[c][l])
        if l!=0 and c!=0:
            dp[c][l]|=dp[c][l-1]<<sub|dp[c][l-1]>>sub|dp[c-1][l]<<sub|dp[c-1][l]>>sub
        elif c!=0:
            dp[c][l]|=dp[c-1][l]<<sub|dp[c-1][l]>>sub
        elif l!=0:
            dp[c][l]|=dp[c][l-1]<<sub|dp[c][l-1]>>sub
bit=dp[-1][-1]
for i in range(pos):
    if (bit&1<<(pos+i))or(bit&1<<(pos-i)):
        print(i)
        break

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

pos = 160*80
dp=[[0]*w for i in range(h)]
sub=abs(a[0][0]-b[0][0])
dp[0][0]=1<<(pos-sub)
dp[0][0]=1<<(pos+sub)

for c in range(h):
    for l in range(w):
        sub=abs(a[c][l]-b[c][l])
        if l!=0:
            dp[c][l]|=dp[c][l-1]<<sub
            dp[c][l]|=dp[c][l-1]>>sub
        if c!=0:
            dp[c][l]|=dp[c-1][l]<<sub
            dp[c][l]|=dp[c-1][l]>>sub
bit=dp[-1][-1]
for i in range(pos):
    if (bit&1<<(pos+i))or(bit&1<<(pos-i)):
        print(i)
        break

Submission status: Accepted

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

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

D = 80 * (H + W) + 1
D2 = D * 2

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

dp[0][0] |= 1 << (D + C[0][0])
dp[0][0] != 1 << (D - C[0][0])

for h in range(H):
    for w in range(W):
        tmp = C[h][w]
        if h:
            dp[h][w] |= dp[h - 1][w] << tmp
            dp[h][w] |= dp[h - 1][w] >> tmp
        if w:
            dp[h][w] |= dp[h][w - 1] << tmp
            dp[h][w] |= dp[h][w - 1] >> tmp

ans = D2

tmp = dp[H - 1][W - 1]

for i in range(D2):
    if (tmp >> i) & 1:
        ans = min(ans, abs(i - D))

print (ans)