Problem p02839 (python)

Fixed submission:
M = 6400*4
mid = M//2
INF = 10**18

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

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

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

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

# 左右の対称性から、がんばったら80を超えることはなくないか？
M = 0
for i in range(H):
    for j in range(W):
        M = max(M, diffs[i][j])
M *= H + W    

# (i,j)において、偏りがkになることがあるか
diff_s = diffs[0][0]
# 初期値
dp = [[[False]*M for i in range(W)] for j in range(H)]
dp[0][0][diff_s] = True
# もらうDP
for i in range(H):
    for j in range(W):
        # 行方向
        if i+1 < H:
            d = diffs[i+1][j]
            for k in range(M):
                x = dp[i][j][k]
                if x:
                    if d + k < M:
                        dp[i+1][j][d+k] = x
                    dp[i+1][j][abs(d-k)] = x
        # 列方向
        if j+1 < W:
            d = diffs[i][j+1]
            for k in range(M):
                x = dp[i][j][k]
                if x:                
                    if d + k < M:                  
                        dp[i][j+1][d+k] = x
                    dp[i][j+1][abs(d-k)] = x
        # print(i,j,diffs[i][j],dp)

ans = 0
for i,b in enumerate(dp[i][j]):
    if b:
        print(i)
        exit()

Buggy submission (verdict: Runtime Error):
H,W = map(int, input().split())
As = []
for i in range(H):
    As.append(list(map(int, input().split())))
diffs = []
for i in range(H):
    bs = list(map(int, input().split()))
    diffs.append([a-b for a,b in zip(As[i],bs)])
# max_d = 0
# for i in range(H):
#     for j in range(W):
#         max_d = max(max_d,abs(diffs[i][j]))

# M = max_d*(H+W)

# 左右の対称性から、がんばったら80を超えることはなくないか？
M = 160

# (i,j)において、偏りがkになることがあるか
diff_s = abs(diffs[0][0])
# 初期値
dp = [[[False]*M for i in range(W)] for j in range(H)]
dp[0][0][diff_s] = True
# もらうDP
for i in range(H):
    for j in range(W):
        # 行方向
        if i+1 < H:
            d = abs(diffs[i+1][j])
            for k in range(M):
                x = dp[i][j][k]
                if x:
                    dp[i+1][j][d+k] = x
                    dp[i+1][j][abs(d-k)] = x
        # 列方向
        if j+1 < W:
            d = abs(diffs[i][j+1])
            for k in range(M):
                x = dp[i][j][k]
                if x:                
                    dp[i][j+1][d+k] = x
                    dp[i][j+1][abs(d-k)] = x
        # print(i,j,diffs[i][j],dp)

ans = 0
for i,b in enumerate(dp[i][j]):
    if b:
        print(i)
        exit()

Buggy submission (verdict: Runtime Error):
H,W = map(int, input().split())
As = []
for i in range(H):
    As.append(list(map(int, input().split())))
diffs = []
for i in range(H):
    bs = list(map(int, input().split()))
    diffs.append([a-b for a,b in zip(As[i],bs)])
max_d = 0
for i in range(H):
    for j in range(W):
        max_d = max(max_d,abs(diffs[i][j]))

M = max_d*(H+W)

# print(M)
# (i,j)において、偏りがkになることがあるか
diff_s = abs(diffs[0][0])
# 初期値
dp = [[[False]*M for i in range(W)] for j in range(H)]
dp[0][0][diff_s] = True
# もらうDP
for i in range(H):
    for j in range(W):
        # 行方向
        if i+1 < H:
            d = abs(diffs[i+1][j])
            for k in range(M):
                x = dp[i][j][k]
                if x:
                    dp[i+1][j][d+k] = x
                    dp[i+1][j][abs(d-k)] = x
        # 列方向
        if j+1 < W:
            d = abs(diffs[i][j+1])
            for k in range(M):
                x = dp[i][j][k]
                if x:                
                    dp[i][j+1][d+k] = x
                    dp[i][j+1][abs(d-k)] = x
        # print(i,j,diffs[i][j],dp)

ans = 0
for i,b in enumerate(dp[i][j]):
    if b:
        print(i)
        exit()

Buggy submission (verdict: Runtime Error):
H,W = map(int, input().split())
As = []
for i in range(H):
    As.append(list(map(int, input().split())))
diffs = []
for i in range(H):
    bs = list(map(int, input().split()))
    diffs.append([a-b for a,b in zip(As[i],bs)])
import numpy as np 
M = np.array(diffs).max()*(H+W)

# print(M)
# (i,j)において、偏りがkになることがあるか
diff_s = abs(diffs[0][0])
# 初期値
dp = [[[False]*M for i in range(W)] for j in range(H)]
dp[0][0][diff_s] = True
# もらうDP
for i in range(H):
    for j in range(W):
        # 行方向
        if i+1 < H:
            d = abs(diffs[i+1][j])
            for k in range(M):
                x = dp[i][j][k]
                if x:
                    dp[i+1][j][d+k] = x
                    dp[i+1][j][abs(d-k)] = x
        # 列方向
        if j+1 < W:
            d = abs(diffs[i][j+1])
            for k in range(M):
                x = dp[i][j][k]
                if x:                
                    dp[i][j+1][d+k] = x
                    dp[i][j+1][abs(d-k)] = x
        # print(i,j,diffs[i][j],dp)

ans = 0
for i,b in enumerate(dp[i][j]):
    if b:
        print(i)
        exit()

Buggy submission (verdict: Runtime Error):
H,W = map(int, input().split())
As = []
for i in range(H):
    As.append(list(map(int, input().split())))
diffs = []
for i in range(H):
    bs = list(map(int, input().split()))
    diffs.append([a-b for a,b in zip(As[i],bs)])
import numpy as np 
M = np.array(diffs).max()*(H+W)

# print(M)
# (i,j)において、偏りがkになることがあるか
diff_s = abs(diffs[0][0])
# 初期値
dp = [[[False]*M for i in range(W)] for j in range(H)]
dp[0][0][diff_s] = True
# もらうDP
for i in range(H):
    for j in range(W):
        # 行方向
        if i+1 < H:
            d = abs(diffs[i+1][j])
            for k in range(M):
                x = dp[i][j][k]
                if x:
                    dp[i+1][j][d+k] = x
                    dp[i+1][j][abs(d-k)] = x
        # 列方向
        if j+1 < W:
            d = abs(diffs[i][j+1])
            for k in range(M):
                x = dp[i][j][k]
                if x:                
                    dp[i][j+1][d+k] = x
                    dp[i][j+1][abs(d-k)] = x
        # print(i,j,diffs[i][j],dp)

ans = 0
for i,b in enumerate(dp[i][j]):
    if b:
        print(i)
        exit()