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 sys
read = sys.stdin.buffer.read
input = sys.stdin.buffer.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)]

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

ab0 = ab[0][0]
size = 80*(h+w)
dp = [[0]*w for hh in range(h)]
dp[0][0] |= 2**(size + ab0)
dp[0][0] |= 2**(size - ab0)
for ch in range(h):
    for cw in range(w):
        if ch < h-1:
            dp[ch+1][cw] |= dp[ch][cw] << ab[ch+1][cw]
            dp[ch+1][cw] |= dp[ch][cw] >> ab[ch+1][cw]
        if cw < w-1:
            dp[ch][cw+1] |= dp[ch][cw] << ab[ch][cw+1]
            dp[ch][cw+1] |= dp[ch][cw] >> ab[ch][cw+1]

a = dp[h-1][w-1]>>size
m = a&(-a)
print(m.bit_length()-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)]

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

ab0 = ab[0][0]
size = 80*(h+w)
dp = [[0]*w for hh in range(h)]
dp[0][0] |= 2**(size + ab0)
dp[0][0] |= 2**(size - ab0)
for ch in range(h):
    for cw in range(w):
        if ch < h-1:
            dp[ch+1][cw] |= dp[ch][cw] << ab[ch+1][cw]
            dp[ch+1][cw] |= dp[ch][cw] >> ab[ch+1][cw]
        if cw < w-1:
            dp[ch][cw+1] |= dp[ch][cw] << ab[ch][cw+1]
            dp[ch][cw+1] |= dp[ch][cw] >> ab[ch][cw+1]

a = dp[h-1][w-1]>>size
m = a&(-a)
print(m.bit_length()-1)

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
A,B=[],[]
for i in range(H):
  X=list(map(int, input().split()))
  A.append(X)
for i in range(H):
  X=list(map(int, input().split()))
  B.append(X)
C=[]
m=0
for i in range(H):
  D=[]
  for j in range(W):
    D.append(abs(A[i][j]-B[i][j]))
    m+=abs(A[i][j]-B[i][j])
  C.append(D)
dp=[[set() for i in range(W)] for i in range(H)]
dp[0][0].add(C[0][0])
dp[0][0].add(-C[0][0])
for i in range(H):
  for j in range(W):
    if i!=0:
      for k in dp[i-1][j]:
        dp[i][j].add(abs(k-C[i][j]))
        dp[i][j].add(abs(k+C[i][j]))
    if j!=0:
      for k in dp[i][j-1]:
        dp[i][j].add(abs(k-C[i][j]))
        dp[i][j].add(abs(k+C[i][j]))
print(min(dp[-1][-1]))

Submission status: Accepted

Solution code:
import sys
import math
import bisect
import heapq


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


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

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

    dp = [[set() for i in range(W)] for i in range(H)]
    # dp[i][j][k]
    dp[0][0].add(A[0][0])

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

    print(min(dp[H-1][W-1]))


if __name__ == "__main__":
    main()

Submission status: Accepted

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


h,w = list(map(int, input().split()))
n = h*w
a = [None]*h
b = [None]*h
for i in range(h):
    a[i] = list(map(int, input().split()))
for i in range(h):
    b[i] = list(map(int, input().split()))
# for i in range(h):
#     for j in range(h):
dp = [[None]*(w) for _ in range(h)]
mask = (1<<12800)-1
m = 6400
dp[0][0] = 1<<(a[0][0]-b[0][0]+m) | 1<<(b[0][0]-a[0][0]+m)
for i in range(h):
    for j in range(w):
        if i==j==0:
            continue
        v = abs(a[i][j]-b[i][j])
        bit = 0
        if i>0:
            bit |= (dp[i-1][j]<<v)&mask
            bit |= (dp[i-1][j]>>v)
        if j>0:
            bit |= (dp[i][j-1]<<v)&mask
            bit |= (dp[i][j-1]>>v)
        dp[i][j] = bit
# ans = min(abs(item) for item in dp[h-1][w-1])
ans = min(abs(val-m) for val in range(12800) if dp[h-1][w-1]>>val&1)
print(ans)

Submission status: Accepted

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def main():
	#a = int(input())
	h, w = tin()
	#s = input()
	al = [lin() for _ in range(h)]
	dl = [[abs(a-b) for a,b in zip(all, lin())] for all in al]
	pp = [[set() for _ in range(w)] for _ in range(h)]
	pp[0][0].add(dl[0][0])
	for wi in range(1, w):
		ss = pp[0][wi]
		d = dl[0][wi]
		for v in pp[0][wi-1]:
			ss.add(v+d)
			ss.add(abs(v-d))
	
			
	for hi in range(1, h):
		ss = pp[hi][0]
		gap = dl[hi][0]
		for v in pp[hi-1][0]:
			ss.add(v+gap)
			ss.add(abs(v-gap))
		
		for wi in range(1, w):
			ss = pp[hi][wi]
			gap = dl[hi][wi]
			for v in pp[hi][wi-1]:
				ss.add(v+gap)
				ss.add(abs(v-gap))
			
			for v in pp[hi-1][wi]:
				ss.add(v+gap)
				ss.add(abs(v-gap))
			
	#for hi in range(h):
	#	for wi in range(w):
	#		print(hi,wi,pp[hi][wi])
			
	ret = min(pp[-1][-1])
	print(ret)
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:
import numpy as np
H, W = map(int, input().split())
red_map = np.array([input().split() for i in range(H)], dtype="int")
blue_map = np.array([input().split() for i in range(H)], dtype="int")
sub_map = abs(red_map - blue_map)
dp = [[2020]*W for i in range(H)]
max_deviation = 2**(80*(H+W))

for i in range(H):
  for j in range(W):
    if not i and not j:
      dp[i][j] = (max_deviation<<sub_map[i][j] | max_deviation>>sub_map[i][j])
    if i > 0:
      dp[i][j] |= (dp[i-1][j]<<sub_map[i][j] | dp[i-1][j]>>sub_map[i][j])
    if j > 0:
      dp[i][j] |= (dp[i][j-1]<<sub_map[i][j] | dp[i][j-1]>>sub_map[i][j])
      
pre_ans = dp[H-1][W-1]>>80*(H+W)
pre_ans_bit = format(pre_ans&-pre_ans, "b")
ans = len(pre_ans_bit)-1
print(ans)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.buffer.readline

h, w = map(int, input().split())
AA = [list(map(int, input().split())) for _ in range(h)]
BB = [list(map(int, input().split())) for _ in range(h)]

kouho = [[0] * (w) for _ in range(h)]
delta = abs(AA[0][0] - BB[0][0])
kouho[0][0] |= 1 << delta
for y in range(h):
    for x in range(w):
        nx = x + 1
        ny = y
        if nx < w:
            delta = abs(AA[ny][nx] - BB[ny][nx])
            temp = 0
            for i in range(1, delta + 1):
                if (kouho[y][x] >> i) % 2:
                    temp |= 1 << (delta - i)
            # print(x,y,kouho[y][x],temp,delta)
            kouho[ny][nx] |= kouho[y][x] << delta
            kouho[ny][nx] |= kouho[y][x] >> delta
            kouho[ny][nx] |= temp

        nx = x
        ny = y + 1
        if ny < h:
            delta = abs(AA[ny][nx] - BB[ny][nx])
            temp = 0
            for i in range(1, delta + 1):
                if (kouho[y][x] >> i) % 2:
                    temp |= 1 << (delta - i)
            # print(x,y,kouho[y][x],temp,delta)
            kouho[ny][nx] |= kouho[y][x] << delta
            kouho[ny][nx] |= kouho[y][x] >> delta
            kouho[ny][nx] |= temp
# print(kouho)
for i in range(81):
    if (kouho[h - 1][w - 1] >> i) % 2:
        print(i)
        exit()

Submission status: Accepted

Solution code:
def main():
    B_MAX = (80 + 80 - 1) * 80 // 2
    H, W = list(map(int, input().split(' ')))
    A = [list(map(int, input().split(' '))) for _ in range(H)]
    B = [list(map(int, input().split(' '))) for _ in range(H)]
    dp = [[[0 for _ in range(B_MAX + 1)] for _ in range(W)] for _ in range(H)]
    dp[0][0][abs(A[0][0] - B[0][0])] = 1
    max_b = abs(A[0][0] - B[0][0])
    for h in range(H):
        for w in range(W):
            if h == 0 and w == 0:
                continue
            d = abs(A[h][w] - B[h][w])
            max_b += d
            for b in range(min(B_MAX, max_b) + 1):
                v = 0
                if h > 0:
                    v = max(v, dp[h - 1][w][abs(b - d)])
                    if b + d <= B_MAX:
                        v = max(v, dp[h - 1][w][b + d])
                if w > 0:
                    v = max(v, dp[h][w - 1][abs(b - d)])
                    if b + d <= B_MAX:
                        v = max(v, dp[h][w - 1][b + d])
                dp[h][w][b] = v
    ans = 0
    while dp[H - 1][W - 1][ans] == 0:
        ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  # ignore trailing spaces


H, W = na()
A_array = naa(H)
B_array = naa(H)
C_array = [[abs(aa-bb) for aa, bb in zip(a, b)]
           for a, b in zip(A_array, B_array)]
# print(C_array)

K = 6400

ans_array = [[[0] * (K+1) for _ in range(W)] for _ in range(H)]

ans_array[0][0][C_array[0][0]] = 1

for i in range(H):
    for j in range(W):
        if i != 0:
            for k in range(K+1):
                ans_array[i][j][k] = ans_array[i][j][k] | ((ans_array[i-1][j][abs(k+C_array[i][j])] if abs(
                    k+C_array[i][j]) <= K else 0) | ans_array[i-1][j][abs(k-C_array[i][j])])
        if j != 0:
            for k in range(K+1):
                ans_array[i][j][k] = ans_array[i][j][k] | ((ans_array[i][j-1][abs(k+C_array[i][j])] if abs(
                    k+C_array[i][j]) <= K else 0) | ans_array[i][j-1][abs(k-C_array[i][j])])

# print(ans_array)

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

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[i][j]=マス(i,j)における可能なポイントのリスト
dp=[[set() for _ in range(W)] for _ in range(H)]
dp[0][0].add(0)

for i in range(W+H-1):
  I,J=0,0
  if i < H:
    I=i
    J=0
  else:
    I=H-1
    J=i-H+1
  while I>=0 and J<W:
    sa = abs(A[I][J] - B[I][J])
    for point in dp[I][J]:
      if I!=H-1:
        dp[I+1][J].add(point+sa)
        dp[I+1][J].add(abs(point-sa))
      if J!=W-1:
        dp[I][J+1].add(point+sa)
        dp[I][J+1].add(abs(point-sa))
    I-=1
    J+=1

ans=dp[H-1][W-1]
sa = abs(A[H-1][W-1] - B[H-1][W-1])
res=float("inf")
for p in ans:
  res=min(res,abs(p+sa),abs(p-sa))
print(res)

Submission status: Accepted

Solution code:
def main():
    import os
    import sys
    from io import BytesIO, IOBase
    
    BUFSIZE = 8192
    
    
    class FastIO(IOBase):
        newlines = 0
    
        def __init__(self, file):
            self._fd = file.fileno()
            self.buffer = BytesIO()
            self.writable = "x" in file.mode or "r" not in file.mode
            self.write = self.buffer.write if self.writable else None
    
        def read(self):
            while 1:
                b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
                if not b:
                    break
                ptr = self.buffer.tell()
                self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
            self.newlines = 0
            return self.buffer.read()
    
        def readline(self):
            while self.newlines == 0:
                b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
                self.newlines = b.count(b"\n") + (not b)
                ptr = self.buffer.tell()
                self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
            self.newlines -= 1
            return self.buffer.readline()
    
        def flush(self):
            if self.writable:
                os.write(self._fd, self.buffer.getvalue())
                self.buffer.truncate(0), self.buffer.seek(0)
    
    
    class IOWrapper(IOBase):
        def __init__(self, file):
            self.buffer = FastIO(file)
            self.flush = self.buffer.flush
            self.writable = self.buffer.writable
            self.write = lambda s: self.buffer.write(s.encode("ascii"))
            self.read = lambda: self.buffer.read().decode("ascii")
            self.readline = lambda: self.buffer.readline().decode("ascii")
    
    
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
    input = lambda: sys.stdin.readline().rstrip("\r\n")
    mod = 10**9 + 7


            

    h, w = map(int, input().split())
    a = [[int(x) for x in input().split()] for _ in range(h)]
    b = [[int(x) for x in input().split()] for _ in range(h)]
    c = [[0]*w for _ in range(h)]
    max_value = 80 * (h + w)
    for i in range(h):
        for j in range(w):
            c[i][j] = abs(a[i][j] - b[i][j])
    dp = [[[0]*(max_value + 1) for _ in range(w)] for _ in range(h)]
    dp[0][0][c[0][0]] = 1
    for i in range(h):
        for j in range(w):
            for k in range(max_value + 1):
                # print(i, j, k, k + c[i][j + 1])
                if 0 <= i + 1 < h and dp[i][j][k]:
                    if 0 <= k + c[i + 1][j] <= max_value:
                        dp[i + 1][j][k + c[i + 1][j]] = 1
                    if 0 <= abs(k - c[i + 1][j]) <= max_value:
                        dp[i + 1][j][abs(k - c[i + 1][j])] = 1
                if 0 <= j + 1 < w and dp[i][j][k]:
                    if 0 <= k + c[i][j + 1] <= max_value:
                        dp[i][j + 1][k + c[i][j + 1]] = 1
                    if 0 <= abs(k - c[i][j + 1]) <= max_value:
                        dp[i][j + 1][abs(k - c[i][j + 1])] = 1
    for k in range(max_value + 1):
        if dp[h - 1][w - 1][k]:
            print(k)
            sys.exit()
main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
h,w = map(int,input().split())
a = []
for i in range(h):
  s = list(map(int,input().split()))
  a.append(s)
  
b = []
for i in range(h):
  s = list(map(int,input().split()))
  b.append(s)
  
dp = [[0]*w for i in range(h)]
t = 80*(h+w)
dp[0][0] = 2**(t+abs(a[0][0]-b[0][0]))

for i in range(h):
  for j in range(w):
    r = abs(a[i][j]-b[i][j])
    if j > 0:
      dp[i][j] |= (dp[i][j-1]<<r | dp[i][j-1]>>r)
    if i > 0:
      dp[i][j] |= (dp[i-1][j]<<r | dp[i-1][j]>>r)
      
a = dp[h-1][w-1]>>t
m = a&(-a)
print(m.bit_length()-1)

Submission status: Accepted

Solution code:
import sys

input=sys.stdin.readline

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

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

dp=[[0 for i in range(0,W)] for i in range(0,H)]
if C[0][0]!=0:
    dp[0][0]=pow(2,6400+C[0][0])+pow(2,6400-C[0][0])
else:
    dp[0][0]=pow(2,6400)
for i in range(0,H):
    for j in range(0,W):
        ans1=0
        ans2=0
        if i!=0:
            ans1=(dp[i-1][j]<<C[i][j])|(dp[i-1][j]>>C[i][j])
        if j!=0:
            ans2=(dp[i][j-1]<<C[i][j])|(dp[i][j-1]>>C[i][j])
        if (i,j)!=(0,0):
            dp[i][j]=ans1|ans2

ans=100
for i in range(0,80+1):
    test=100
    if dp[H-1][W-1]>>(6400+i) &1 ==1:
        test=i
    if ans>test:
        ans=test

print(ans)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.buffer.readline

h, w = map(int, input().split())
AA = [list(map(int, input().split())) for _ in range(h)]
BB = [list(map(int, input().split())) for _ in range(h)]

kouho = [[0] * (w) for _ in range(h)]
delta = abs(AA[0][0] - BB[0][0])
kouho[0][0] |= 1 << delta
for y in range(h):
    for x in range(w):
        nx = x + 1
        ny = y
        if nx < w:
            delta = abs(AA[ny][nx] - BB[ny][nx])
            temp = 0
            for i in range(1, delta + 1):
                if (kouho[y][x] >> i) & 1:
                    temp |= 1 << (delta - i)
            kouho[ny][nx] |= kouho[y][x] << delta
            kouho[ny][nx] |= kouho[y][x] >> delta
            kouho[ny][nx] |= temp

        nx = x
        ny = y + 1
        if ny < h:
            delta = abs(AA[ny][nx] - BB[ny][nx])
            temp = 0
            for i in range(1, delta + 1):
                if (kouho[y][x] >> i) & 1:
                    temp |= 1 << (delta - i)
            kouho[ny][nx] |= kouho[y][x] << delta
            kouho[ny][nx] |= kouho[y][x] >> delta
            kouho[ny][nx] |= temp
for i in range(81):
    if (kouho[h - 1][w - 1] >> i) & 1:
        print(i)
        exit()

Submission status: Accepted

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

def solve():
    maxV = 12800

    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]*(W) for _ in range(H)]
    diff = abs(Ass[0][0] - Bss[0][0])
    dp0 = 1<<maxV
    dp[0][0] = (dp0<<diff) | (dp0>>diff)
    for i in range(H):
        for j in range(W):
            diff = abs(Ass[i][j] - Bss[i][j])
            if i > 0:
                dp0 = dp[i-1][j]
                dp[i][j] |= (dp0<<diff) | (dp0>>diff)
            if j > 0:
                dp0 = dp[i][j-1]
                dp[i][j] |= (dp0<<diff) | (dp0>>diff)

    ans = maxV
    dpHW = dp[-1][-1]
    for i in range(2*maxV+1):
        if (dpHW>>i) & 1:
            j = abs(i-maxV)
            if j < ans:
                ans = j

    print(ans)


solve()

Submission status: Accepted

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

Solution code:
def main():
    # import sys
    # readline = sys.stdin.readline
    # readlines = sys.stdin.readlines
    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 = 0
    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
            M = max(M, m)

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

    for i in range(H):
        for j in range(W):
            here = dp[i][j]
            k = grid[i][j]

            dp[i][j] = (here << k) | (here >> k)
            for l in range(1, k + 1):
                if (here >> l) & 1:
                    dp[i][j] |= (1 << (k - l))

            if i < H - 1:
                dp[i + 1][j] |= dp[i][j]
            if j < W - 1:
                dp[i][j + 1] |= dp[i][j]

    V = dp[-1][-1]
    ans = 0
    while V > 0:
        if V & 1:
            print(ans)
            break
        V >>= 1
        ans += 1


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    # import sys
    # readline = sys.stdin.readline
    # readlines = sys.stdin.readlines
    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 = 0
    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
            M = max(M, m)

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

    for i in range(H):
        for j in range(W):
            here = dp[i][j]
            if i < H - 1:
                nk = grid[i + 1][j]
                dp[i + 1][j] |= (here << nk) | (here >> nk)
                for k in range(1, nk + 1):
                    if (here >> k) & 1:
                        dp[i + 1][j] |= (1 << (nk - k))
            if j < W - 1:
                nk = grid[i][j + 1]
                dp[i][j + 1] |= (here << nk) | (here >> nk)
                for k in range(1, nk + 1):
                    if (here >> k) & 1:
                        dp[i][j + 1] |= (1 << (nk - k))

    k = dp[-1][-1]
    ans = 0
    while k > 0:
        if k & 1:
            print(ans)
            break
        k >>= 1
        ans += 1


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    # import sys
    # readline = sys.stdin.readline
    # readlines = sys.stdin.readlines
    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 = 0
    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
            M = max(M, m)

    L = (H + W) * M
    dp = [[[0] * (L + 1) for _ in range(W)] for _ in range(H)]
    dp[0][0][grid[0][0]] = 1

    for i in range(H):
        for j in range(W):
            for k in range(L + 1):
                if dp[i][j][k] == 1:
                    if i < H - 1:
                        nk = grid[i + 1][j]
                        dp[i + 1][j][k + nk] |= 1
                        dp[i + 1][j][abs(k - nk)] |= 1
                    if j < W - 1:
                        nk = grid[i][j + 1]
                        dp[i][j + 1][k + nk] |= 1
                        dp[i][j + 1][abs(k - nk)] |= 1

    for k in range(L + 1):
        if dp[-1][-1][k] == 1:
            print(k)
            break


if __name__ == "__main__":
    main()

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)]
D = [[0]*W for i in range(H)]
for i in range(H):
    for j in range(W):
        D[i][j] = abs(A[i][j]-B[i][j])
buf = 80*(H+W)
dp = [[0]*W for i in range(H)]
dp[0][0] = 1<<(buf+D[0][0]) | 1<<(buf-D[0][0])
for i in range(H):
    for j in range(W):
        d = D[i][j]
        if i:
            dp[i][j] |= dp[i-1][j]<<d | dp[i-1][j]>>d
        if j:
            dp[i][j] |= dp[i][j-1]<<d | dp[i][j-1]>>d
ans = 10**18
for i in range(buf*2+1):
    if dp[H-1][W-1]&(1<<i):
        ans = min(ans, abs(buf-i))
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

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

    dp = [[0]*(1 + W) for _ in range(H + 1)]
    x = abs(A[0][0] - B[0][0])
    dp[0][0] = 1 << (12800 + x)
    dp[0][0] |= 1 << (12800 - x)
    for i in range(H):
        for j in range(W):
            c = abs(A[i][j] - B[i][j])
            if i > 0:
                dp[i][j] |= dp[i - 1][j] << c
                dp[i][j] |= dp[i - 1][j] >> c
            if j > 0:
                dp[i][j] |= dp[i][j - 1] << c
                dp[i][j] |= dp[i][j - 1] >> c
    ans = INF
    x = dp[H - 1][W - 1]
    for i in range(25600):
        if x&1:
            ans = min(ans,abs(i - 12800))
        x >>= 1
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

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

def main():
    H,W = map(int,input().split())
    point = [[0]*W for _ in range(H)]
    
    for i in range(H):
        a = list(map(int,input().split()))
        for j in range(W):
            point[i][j] += a[j]

    for i in range(H):
        b = list(map(int,input().split()))
        for j in range(W):
            point[i][j] = abs(point[i][j]-b[j])
    
    base = 3200
    dp = [[0]*W for _ in range(H)]
    dp[0][0] = (1 << (base+point[0][0])) | (1 << (base-point[0][0]))
    
    for i in range(H):
        for j in range(W):
            if j < W-1:
                dp[i][j+1] |= (dp[i][j] << point[i][j+1])
                dp[i][j+1] |= (dp[i][j] >> point[i][j+1])
            if i < H-1:
                dp[i+1][j] |= (dp[i][j] << point[i+1][j])
                dp[i+1][j] |= (dp[i][j] >> point[i+1][j])
    
    ans = dp[-1][-1] >> base
    for i in range(ans.bit_length()):
        if (ans >> i)&1:
            print(i)
            exit()
    
if __name__ == "__main__":
    main()

Submission status: Accepted

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))
table = [0] * W
table[0] = 1 << 6400
for i in range(H):
    for j in range(W):
        shamt = abs(A[i][j] - B[i][j])
        if j > 0:
            table[j] |= table[j - 1]
        table[j] = (table[j] << shamt) | (table[j] >> shamt)
dl = dr = 1 << 6400
for i in range(6401):
    if table[W - 1] & (dl | dr):
        print(i)
        break
    dl <<= 1
    dr >>= 1

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
h, w = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(h)]
b = [list(map(int, input().split())) for _ in range(h)]
ab = [[0] * w for _ in range(h)]
for i in range(h):
    for j in range(w):
        ab[i][j] = abs(a[i][j] - b[i][j])

m = 12800
dp = [[0] * w for _ in range(h)]
dp[0][0] = (1 << (m + ab[0][0])) | (1 << (m - ab[0][0]))
for i in range(h):
    for j in range(w):
        for dx, dy in [(1, 0), (0, 1)]:
            nx, ny = i + dx, j + dy
            if 0 <= nx < h and 0 <= ny < w:
                dp[nx][ny] = dp[nx][ny] | (dp[i][j] << ab[nx][ny])
                dp[nx][ny] = dp[nx][ny] | (dp[i][j] >> ab[nx][ny])

#print(dp[-1][-1])
for i in range(m+1):
    if (dp[h-1][w-1] >> i) & 1:
        ans = m - i

print(ans)

Submission status: Accepted

Solution code:
# Atcoder Problem Solving
H,W=map(int,input().split())
c=[list(map(int,input().split())) for i in range(H)]
b=[list(map(int,input().split())) for i in range(H)]
a=[[0 for i  in range(W)] for j in range(H)]

for i in range(H):
    for j in range(W):
        a[i][j]=abs(c[i][j]-b[i][j])
        
dp=[[0 for i in range(W)] for j in range(H)]

# Bitset演算
# 答えは絶対値が絶対-80から80以内に収まる

X=3200

dp[0][0]= (1<<(X+a[0][0]))  | (1<<(X-a[0][0]))
# 初期化の条件

for i in range(H):
    for j in range(W):
        if 0<=i<H and 0<=j+1<W:
            dp[i][j+1]|=(dp[i][j]<<a[i][j+1])
            dp[i][j+1]|=(dp[i][j]>>a[i][j+1]) 
            
        if 0<=i+1<H and 0<=j<W:
            dp[i+1][j]|=(dp[i][j]<<a[i+1][j])
            dp[i+1][j]|=(dp[i][j]>>a[i+1][j])
            
A=str(bin(dp[H-1][W-1]))[::-1]
L=len(A)
ans=3200
for i in range(L):
    if A[i]=="1":
        ans=min(ans,abs(i-X))
print(ans)

Submission status: Accepted

Solution code:
import sys; input = sys.stdin.buffer.readline
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	H, W = getlist()
	A = []
	for i in range(H):
		a = getlist()
		A.append(a)
	B = []
	for i in range(H):
		b = getlist()
		B.append(b)

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

	# print(C)
	diff = 12800
	DP = [[0] * W for i in range(H)]
	DP[0][0] = (1 << (diff + C[0][0])) | (1 << (diff - C[0][0]))
	for i in range(1, W):
		DP[0][i] = (DP[0][i - 1] << C[0][i]) | (DP[0][i - 1] >> C[0][i])
	for i in range(1, H):
		DP[i][0] = (DP[i - 1][0] << C[i][0]) | (DP[i - 1][0] >> C[i][0])

	for i in range(1, H):
		for j in range(W):
			DP[i][j] |= (DP[i][j - 1] << C[i][j]) | (DP[i][j - 1] >> C[i][j])
			DP[i][j] |= (DP[i - 1][j] << C[i][j]) | (DP[i - 1][j] >> C[i][j])

	ans = INF
	for i in range(25601):
		if DP[-1][-1] & (1 << i) == (1 << i):
			ans = min(ans, abs(diff - i))

	print(ans)

if __name__ == '__main__':
	main()