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: Wrong Answer

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=h*w*max([max([abs(i)+abs(j) for i,j in zip(a[k],b[k])])for k in range(h+1)])
ini=1<<MX
sup=1<<(MX*2)
dp=[[0 for i in range(w+1)]for j in range(h+1)]
for i in range(1,h+1):
    dp[i][0]=ini
for j in range(1,w+1):
    dp[0][j]=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: Wrong Answer

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: Wrong Answer

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 = [[[False]*200 for _ in range(w+1)] for _ in range(h+1)]

bias = 100
icost = a[0][0] - b[0][0]
dp[1][1][icost + bias] = True

dp[1][1][-icost + bias] = True

for i in range(1,h+1):
    for j in range(1,w+1):
        cost = a[i-1][j-1] - b[i-1][j-1]
        for k in range(200):
            if dp[i-1][j][k]:
                if 0 <= k+cost < 200:
                    dp[i][j][k+cost] = True
                if 0 <= k-cost < 200:
                    dp[i][j][k-cost] = True
            if dp[i][j-1][k]:
                if 0 <= k+cost < 200:
                    dp[i][j][k+cost] = True
                if 0 <= k-cost < 200:
                    dp[i][j][k-cost] = True

ans = 10010001001
for i in range(200):
    if dp[h][w][i]:
        ans = min(ans,abs(i-bias))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000000)
input = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = 10 ** 15

def main():
    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)]

    dp = [[[0]*6400 for _ in range(W)] for _ in range(H)]
    dp[0][0][3200] = 1
    for i in range(H):
        for j in range(W):
            if i == H - 1 and j == W - 1:
                break
            a,b = A[i][j],B[i][j]
            for k in range(6400):
                if dp[i][j][k] == 0:
                    continue
                if 0 <= k + a - b < 6400:
                    if i + 1 < H:
                        dp[i + 1][j][k + a - b] |= dp[i][j][k]
                    if j + 1  < W:
                        dp[i][j + 1][k + a - b] |= dp[i][j][k]
                if 0 <= k - a + b < 6400:
                    if i + 1 < H:
                        dp[i + 1][j][k - a + b] |= dp[i][j][k]
                    if j + 1 < W:
                        dp[i][j + 1][k - a + b] |= dp[i][j][k]
    
    ans = INF
    a,b = A[-1][-1],B[-1][-1]
    for i in range(6400):
        if (0 <= i + a - b < 6400 and dp[-1][-1][i + a - b]) or (0 <= i - a + b < 6400 and dp[-1][-1][i - a + b]):
            ans = min(ans,abs(i - 3200))

    print(ans)                
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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)
N = 2*U*(H+W)+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: Wrong Answer

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

amat=[[int(x) for x in input().split()] for _ in range(H)]
bmat=[[int(x) for x in input().split()] for _ in range(H)]

mat=[[None for _ in range(W)] for _ in range(H)]
for i in range(H):
  for j in range(W):
    mat[i][j]=abs(amat[i][j]-bmat[i][j])
#print(mat)

dp=[[set() for _ in range(W)] for _ in range(H)]
dp[0][0]={mat[0][0]}

for i in range(1,H):
  for x in dp[i-1][0]:
    dp[i][0].add(abs(x+mat[i][0]))
    dp[i][0].add(abs(x-mat[i][0]))

for j in range(1,W):
  for x in dp[0][j-1]:
    dp[0][j].add(abs(x+mat[0][j]))
    dp[0][j].add(abs(x-mat[0][j]))
    
limit=3200
for i in range(1,H):
  for j in range(1,W):
    for x in dp[i-1][j]:
      if x+mat[i][j]<=limit:
        dp[i][j].add(abs(x+mat[i][j]))
      dp[i][j].add(abs(x-mat[i][j]))
    for x in dp[i][j-1]:
      if x+mat[i][j]<=limit:
        dp[i][j].add(abs(x+mat[i][j]))
      dp[i][j].add(abs(x-mat[i][j]))
      
#print(dp)
print(min(dp[-1][-1]))

Submission status: Wrong Answer

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

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: Wrong Answer

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]*w for i in range(h)]
sub=abs(a[0][0]-b[0][0])
dp[0][0]=1<<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
            s="0"*sub+bin(dp[c][l-1])[2:]
            dp[c][l]|=int(s[-sub:][::-1],2)<<1
        if c!=0:
            dp[c][l]|=dp[c-1][l]<<sub
            dp[c][l]|=dp[c-1][l]>>sub
            s="0"*sub+bin(dp[c-1][l])[2:]
            dp[c][l]|=int(s[-sub:][::-1],2)<<1
bit=dp[-1][-1]
print((bit^(bit-1)).bit_length()-1)

Submission status: Wrong Answer

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]*w for i in range(h)]
sub=abs(a[0][0]-b[0][0])
dp[0][0]=1<<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]
print((bit^(bit-1)).bit_length()-1)

Submission status: Wrong Answer

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

import numpy as np
dp = [[0]*(w+1) for _ in range(h+1)]
import numpy as np
d = 80
D = 2*d+1
dp[0][0] = np.zeros(D, np.bool)
dp[0][0][C[0][0]+d] = 1
#dp[0][0][-C[0][0]+d] = 1
for i in range(h):
    for j in range(w):
        c = C[i][j]
        if i == 0 and j == 0:
            continue
        elif i == 0:
            b = np.zeros(D, np.bool)
            b[c:] |= dp[i][j-1][:D-c]
            b[:D-c] |= dp[i][j-1][c:]
        elif j == 0:
            b = np.zeros(D, np.bool)
            b[c:] |= dp[i-1][j][:D-c]
            b[:D-c] |= dp[i-1][j][c:]
        else:
            b = np.zeros(D, np.bool)
            b[c:] |= dp[i][j-1][:D-c]
            b[:D-c] |= dp[i][j-1][c:]
            b[c:] |= dp[i-1][j][:D-c]
            b[:D-c] |= dp[i-1][j][c:]
        dp[i][j] = b
#print(dp[h-1][w-1])
ans = float('inf')
for i in range(D):
    if dp[h-1][w-1][i]:
        #print(abs(i-d))
        ans = min(ans, abs(i-d))
print(ans)

Submission status: Wrong Answer

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

import numpy as np
dp = [[0]*(w+1) for _ in range(h+1)]
import numpy as np
d = 80
D = 2*d+1
dp[0][0] = np.zeros(D, np.bool)
dp[0][0][C[0][0]+d] = 1
dp[0][0][-C[0][0]+d] = 1
for i in range(h):
    for j in range(w):
        c = C[i][j]
        if i == 0 and j == 0:
            continue
        elif i == 0:
            b = np.zeros(D, np.bool)
            b[c:] |= dp[i][j-1][:D-c]
            b[:D-c] |= dp[i][j-1][c:]
        elif j == 0:
            b = np.zeros(D, np.bool)
            b[c:] |= dp[i-1][j][:D-c]
            b[:D-c] |= dp[i-1][j][c:]
        else:
            b = np.zeros(D, np.bool)
            b[c:] |= dp[i][j-1][:D-c]
            b[:D-c] |= dp[i][j-1][c:]
            b[c:] |= dp[i-1][j][:D-c]
            b[:D-c] |= dp[i-1][j][c:]
        dp[i][j] = b
#print(dp[h-1][w-1])
ans = float('inf')
for i in range(D):
    if dp[h-1][w-1][i]:
        #print(abs(i-d))
        ans = min(ans, abs(i-d))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
def input(): return sys.stdin.readline().strip()


def main():
    H, W = map(int, input().split())
    A = []
    for _ in range(H):
        A.append(list(map(int, input().split())))
    B = []
    for _ in range(H):
        B.append(list(map(int, input().split())))
    
    """
    明らかなdp臭。
        dp[i][j] = (マス(0, 0)から(i, j)に進むときの偏りとしてありうるものの集合)
    とおく。(0<=i<=H-1, 0<=j<=W-1, 0<=d<=80)

    残念ながらPypyだとsetでdp値を保持しているとTLEするので、setではなくビットで偏りの値を管理する
    ただし-diffの方向にビットシフトするとき0桁目以下が切り捨てられてしまうので、最初から適当に
    offsetで桁の水増しをしておく
    """

    offset = 80 * 164

    dp = [[0] * W for _ in range(H)]
    dp[0][0] |= 1 << (A[0][0] - B[0][0] + offset)
    dp[0][0] |= 1 << (B[0][0] - A[0][0] + offset)
    for i in range(1, H):
        diff = abs(A[i][0] - B[i][0])
        dp[i][0] |= dp[i - 1][0] << diff
        dp[i][0] |= dp[i - 1][0] >> diff
    for j in range(1, W):
        diff = abs(A[0][j] - B[0][j])
        dp[i][0] |= dp[0][j - 1] << diff
        dp[i][0] |= dp[0][j - 1] >> diff

    for i in range(1, H):
        for j in range(1, W):
            diff = abs(A[i][j] - B[i][j])
            dp[i][j] |= dp[i - 1][j] << diff
            dp[i][j] |= dp[i - 1][j] >> diff
            dp[i][j] |= dp[i][j - 1] << diff
            dp[i][j] |= dp[i][j - 1] >> diff
    
    ans1 = offset
    while not (dp[H - 1][W - 1] & (1 << ans1)):
        ans1 += 1
    ans2 = offset
    while not (dp[H - 1][W - 1] & (1 << ans2)):
        ans2 -= 1
    print(min(ans1 - offset, offset - ans2))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
def input(): return sys.stdin.readline().strip()


def main():
    H, W = map(int, input().split())
    A = []
    for _ in range(H):
        A.append(list(map(int, input().split())))
    B = []
    for _ in range(H):
        B.append(list(map(int, input().split())))
    
    """
    明らかなdp臭。
        dp[i][j] = (マス(0, 0)から(i, j)に進むときの偏りとしてありうるものの集合)
    とおく。(0<=i<=H-1, 0<=j<=W-1, 0<=d<=80)
    """

    dp = [[set([]) for _ in range(W)] for _ in range(H)]
    dp[0][0].add(abs(A[0][0] - B[0][0]))
    for i in range(1, H):
        diff = A[i][0] - B[i][0]
        for val in dp[i - 1][0]:
            if abs(val + diff) <= 1600: dp[i][0].add(abs(val + diff))
            if abs(val - diff) <= 1600: dp[i][0].add(abs(val - diff))
    for j in range(1, W):
        diff = A[0][j] - B[0][j]
        for val in dp[0][j - 1]:
            if abs(val + diff) <= 1600: dp[0][j].add(abs(val + diff))
            if abs(val - diff) <= 1600: dp[0][j].add(abs(val - diff))

    for i in range(1, H):
        for j in range(1, W):
            diff = A[i][j] - B[i][j]
            for val in dp[i - 1][j]:
                if abs(val + diff) <= 1600: dp[i][j].add(abs(val + diff))
                if abs(val - diff) <= 1600: dp[i][j].add(abs(val - diff))
            for val in dp[i][j - 1]:
                if abs(val + diff) <= 1600: dp[i][j].add(abs(val + diff))
                if abs(val - diff) <= 1600: dp[i][j].add(abs(val - diff))
    
    print(min(dp[H - 1][W - 1]))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
def input(): return sys.stdin.readline().strip()


def main():
    H, W = map(int, input().split())
    A = []
    for _ in range(H):
        A.append(list(map(int, input().split())))
    B = []
    for _ in range(H):
        B.append(list(map(int, input().split())))
    
    """
    明らかなdp臭。
        dp[i][j] = (マス(0, 0)から(i, j)に進むときの偏りとしてありうるものの集合)
    とおく。(0<=i<=H-1, 0<=j<=W-1, 0<=d<=80)
    """

    dp = [[set([]) for _ in range(W)] for _ in range(H)]
    dp[0][0].add(abs(A[0][0] - B[0][0]))
    for i in range(1, H):
        diff = A[i][0] - B[i][0]
        for val in dp[i - 1][0]:
            if abs(val + diff) <= 160: dp[i][0].add(abs(val + diff))
            if abs(val - diff) <= 160: dp[i][0].add(abs(val - diff))
    for j in range(1, W):
        diff = A[0][j] - B[0][j]
        for val in dp[0][j - 1]:
            if abs(val + diff) <= 160: dp[0][j].add(abs(val + diff))
            if abs(val - diff) <= 160: dp[0][j].add(abs(val - diff))

    for i in range(1, H):
        for j in range(1, W):
            diff = A[i][j] - B[i][j]
            for val in dp[i - 1][j]:
                if abs(val + diff) <= 160: dp[i][j].add(abs(val + diff))
                if abs(val - diff) <= 160: dp[i][j].add(abs(val - diff))
            for val in dp[i][j - 1]:
                if abs(val + diff) <= 160: dp[i][j].add(abs(val + diff))
                if abs(val - diff) <= 160: dp[i][j].add(abs(val - diff))
    
    print(min(dp[H - 1][W - 1]))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
A = tuple(tuple(map(int, input().split())) for _ in range(H))
B = tuple(tuple(map(int, input().split())) for _ in range(H))

dp = [[set() for _ in range(W)] for _ in range(H)]
dp[0][0].add(A[0][0] - B[0][0])
dp[0][0].add(B[0][0] - A[0][0])

for i in range(H):
    for j in range(W):
        c = abs(A[i][j]-B[i][j])
        if i > 0:
            dp[i][j] |= {x + c for x in dp[i - 1][j] if x + c <= 200}
            dp[i][j] |= {x - c for x in dp[i - 1][j] if x - c >= -200}
        if j > 0:
            dp[i][j] |= {x + c for x in dp[i][j - 1] if x + c <= 200}
            dp[i][j] |= {x - c for x in dp[i][j - 1] if x - c >= -200}

ans = min(abs(x) for x in dp[-1][-1])
print(ans)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
A = tuple(tuple(map(int, input().split())) for _ in range(H))
B = tuple(tuple(map(int, input().split())) for _ in range(H))

dp = [[set() for _ in range(W)] for _ in range(H)]
dp[0][0].add(A[0][0] - B[0][0])
dp[0][0].add(B[0][0] - A[0][0])

for i in range(H):
    for j in range(W):
        c = abs(A[i][j]-B[i][j])
        if i > 0:
            dp[i][j] |= {x + c for x in dp[i - 1][j] if x + c <= 200}
            dp[i][j] |= {x - c for x in dp[i - 1][j] if x - c >= -200}
        if j > 0:
            dp[i][j] |= {x + c for x in dp[i][j - 1] if x + c <= 200}
            dp[i][j] |= {x - c for x in dp[i][j - 1] if x - c >= -200}

print(*dp, sep="\n")

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
A = tuple(tuple(map(int, input().split())) for _ in range(H))
B = tuple(tuple(map(int, input().split())) for _ in range(H))

dp = [[set() for _ in range(W)] for _ in range(H)]
dp[0][0].add(A[0][0] - B[0][0])
dp[0][0].add(B[0][0] - A[0][0])

for i in range(H):
    for j in range(W):
        c = abs(A[i][j]-B[i][j])
        if i > 0:
            dp[i][j] |= {x + c for x in dp[i - 1][j] if x + c <= 160}
            dp[i][j] |= {x - c for x in dp[i - 1][j] if x - c >= -160}
        if j > 0:
            dp[i][j] |= {x + c for x in dp[i][j - 1] if x + c <= 160}
            dp[i][j] |= {x - c for x in dp[i][j - 1] if x - c >= -160}

ans = min(abs(x) for x in dp[H - 1][W - 1])
print(ans)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
A = tuple(tuple(map(int, input().split())) for _ in range(H))
B = tuple(tuple(map(int, input().split())) for _ in range(H))

dp = [[set() for _ in range(W)] for _ in range(H)]
dp[0][0].add(A[0][0] - B[0][0])
dp[0][0].add(B[0][0] - A[0][0])

for i in range(H):
    for j in range(W):
        c = abs(A[i][j]-B[i][j])
        if i > 0:
            dp[i][j] |= {x + c for x in dp[i - 1][j] if x + c <= 80}
            dp[i][j] |= {x - c for x in dp[i - 1][j] if x - c >= -80}
        if j > 0:
            dp[i][j] |= {x + c for x in dp[i][j - 1] if x + c <= 80}
            dp[i][j] |= {x - c for x in dp[i][j - 1] if x - c >= -80}

ans = min(abs(x) for x in dp[H - 1][W - 1])
print(ans)

Submission status: Wrong Answer

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)]
d=[]
for i in range(h):
    lis=[]
    for j in range(w):
        lis.append(abs(a[i][j]-b[i][j]))
    d.append(lis)

dp = [[0 for _ in range(6400)] for _ in range(h*w)]
dp[0][d[0][0]]=1

Submission status: Wrong Answer

Solution code:
import sys
def main():
    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)]
    """
    ofset = 80*164
    #mask = (1 << (ofset*2)) - 1
    dp=[[0 for i in range(w)] for j in range(h)]
    dp[0][0] |= 1 << (a[0][0] - b[0][0] + ofset)
    dp[0][0] |= 1 << (b[0][0] - a[0][0] + ofset)
    for i in range(h):
        for j in range(w):
            if i < h - 1:
                A = abs(a[i+1][j] - b[i+1][j])
                dp[i+1][j] |= (dp[i][j] << A)
                dp[i+1][j] |= (dp[i][j] >> A)
            if j < w - 1:
                A = abs(a[i][j+1] - b[i][j+1])
                dp[i][j+1] |= (dp[i][j] << A)
                dp[i][j+1] |= (dp[i][j] >> A)
    ans = 10000000000
    for i in range(ofset, 80*330):
        if (dp[h-1][w-1]>>i)&1:
            ans = i - ofset
            break
    for i in reversed(range(ofset)):
        if (dp[h-1][w-1]>>i)&1:
            ans = min(ans, ofset - i)
            break
    print(ans)
    """
if __name__=='__main__':
  main()

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
input=sys.stdin.readline
h,w=map(int,input().split())
red=[list(map(int,input().split()))+[0] for i in range(h)]+[[0 for i in range(w+1)]]
blue=[list(map(int,input().split()))+[0] for i in range(h)]+[[0 for i in range(w+1)]]
field = [[None]*(w+1) for i in range(h+1)]
for i in range(h):
    for j in range(w):
        field[i][j] = np.zeros(6500, np.bool)
for i in range(h):
    for j in range(w):
        for f in range(6401):
            if field[i][j][f]:
                field[i][j+1][f+abs(red[i][j+1]-blue[i][j+1])]=True
                field[i][j+1][abs(f-abs(red[i][j+1]-blue[i][j+1]))]=True
                field[i+1][j][f+abs(red[i+1][j]-blue[i+1][j])]=True
                field[i+1][j][abs(f-abs(red[i+1][j]-blue[i+1][j]))]=True
for i in range(6500):
    if field[h-1][w-1][i]:print(i);exit()

Submission status: Wrong Answer

Solution code:
import sys
def main():
  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)]
  infi=10**9
  dp=[[[infi,0] for i in range(w)] for j in range(h)]
  dp[h-1][w-1]=[a[-1][-1],b[-1][-1]]
  for i in reversed(range(h)):
    for j in reversed(range(w)):
      if i>=1:
        if abs(dp[i-1][j][0]-dp[i-1][j][1])>abs(dp[i][j][0]+a[i-1][j]-dp[i][j][1]-b[i-1][j]):
          dp[i-1][j][0]=dp[i][j][0]+a[i-1][j]
          dp[i-1][j][1]=dp[i][j][1]+b[i-1][j]
        if abs(dp[i-1][j][0]-dp[i-1][j][1])>abs(dp[i][j][0]+b[i-1][j]-dp[i][j][1]-a[i-1][j]):
          dp[i-1][j][0]=dp[i][j][0]+b[i-1][j]
          dp[i-1][j][1]=dp[i][j][1]+a[i-1][j]
      if j>=1:
        if abs(dp[i][j-1][0]-dp[i][j-1][1])>abs(dp[i][j][0]+a[i][j-1]-dp[i][j][1]-b[i][j-1]):
          dp[i][j-1][0]=dp[i][j][0]+a[i][j-1]
          dp[i][j-1][1]=dp[i][j][1]+b[i][j-1]
        if abs(dp[i][j-1][0]-dp[i][j-1][1])>abs(dp[i][j][0]+b[i][j-1]-dp[i][j][1]-a[i][j-1]):
          dp[i][j-1][0]=dp[i][j][0]+b[i][j-1]
          dp[i][j-1][1]=dp[i][j][1]+a[i][j-1]
  dp1=[[[infi,0] for i in range(w)] for j in range(h)]
  dp1[0][0]=[a[0][0],b[0][0]]
  for i in range(h):
    for j in range(w):
      if i<h-1:
        if abs(dp1[i+1][j][0]-dp1[i+1][j][1])>abs(dp1[i][j][0]+a[i+1][j]-dp1[i][j][1]-b[i+1][j]):
          dp[i+1][j][0]=dp[i][j][0]+a[i+1][j]
          dp[i+1][j][1]=dp[i][j][1]+b[i+1][j]
        if abs(dp1[i+1][j][0]-dp1[i+1][j][1])>abs(dp1[i][j][0]+b[i+1][j]-dp1[i][j][1]-a[i+1][j]):
          dp1[i+1][j][0]=dp1[i][j][0]+b[i+1][j]
          dp1[i+1][j][1]=dp1[i][j][1]+a[i+1][j]
      if j<w-1:
        if abs(dp1[i][j+1][0]-dp1[i][j+1][1])>abs(dp1[i][j][0]+a[i][j+1]-dp1[i][j][1]-b[i][j+1]):
          dp1[i][j+1][0]=dp1[i][j][0]+a[i][j+1]
          dp1[i][j+1][1]=dp1[i][j][1]+b[i][j+1]
        if abs(dp1[i][j+1][0]-dp1[i][j+1][1])>abs(dp1[i][j][0]+b[i][j+1]-dp1[i][j][1]-a[i][j+1]):
          dp1[i][j+1][0]=dp1[i][j][0]+b[i][j+1]
          dp1[i][j+1][1]=dp1[i][j][1]+a[i][j+1]
  #print(dp)
  #print(dp1)
  return print(min(abs(dp[0][0][0]-dp[0][0][1]),abs(dp1[h-1][w-1][0]-dp1[h-1][w-1][1])))
if __name__=='__main__':
  main()