Problem p02839 (python)

Fixed submission:
import sys
input = sys.stdin.readline


h, w = map(int, input().split())
inf = float('INF')
A = []
B = []

for i in range(h):
    line = list(map(int, input().split()))
    A.append(line)

for i in range(h):
    line = list(map(int, input().split()))
    B.append(line)

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


def slide_down(y, x, possible):
    new = set()
    delta = D[y+1][x]
    limit = (h+w) * 80
    for num in possible:
        if num + delta <= limit - (y+x)*80:
            new.add(num+delta)
        if abs(num-delta) <= limit - (y+x)*80:
            new.add(abs(num-delta))
    return new


def slide_right(y, x, possible):
    new = set()
    delta = D[y][x+1]
    limit = (h+w) * 80
    for num in possible:
        if num + delta <= limit - (y+x)*80:
            new.add(num+delta)
        if abs(num-delta) <= limit - (y+x)*80:
            new.add(abs(num-delta))
    return new


DP = [[set() for j in range(w)] for i in range(h)]
DP[0][0] = {D[0][0]}
for row in range(h):
    for col in range(w):
        possible = DP[row][col]
        if col < w-1:
            new = slide_right(row, col, possible)
            DP[row][col+1] |= new
        if row < h-1:
            new = slide_down(row, col, possible)
            DP[row+1][col] |= new

ans = min(DP[h-1][w-1])
print(ans)

Buggy submission (verdict: Runtime Error):
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

mod = 10**9+7 #出力の制限

# a = cmb(n,r)
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

def ans():
    H,W = m()

    a = []

    for i in range(H):
        a.append(l())

    ma = 0
    b = []
    for i in range(H):
        b.append(l())
        for j in range(W):
            ma = max(ma,abs(a[i][j]-b[i][j]))

    dp = [[[0 for i in range(ma*(min(H,W)))]for j in range(W)] for k in range(H)]

    for i in range(H):
        for j in range(W):
            if i == 0 and j == 0:
                dp[0][0][abs(a[0][0] - b[0][0])] = 1
            elif i == 0:
                for k in range(ma*(min(H,W))):
                    if abs(k + abs(a[i][j] - b[i][j])) < ma*min(H,W):
                        dp[i][j][abs(k + abs(a[i][j] - b[i][j]))] = max(dp[i][j-1][k],dp[i][j][abs(k + abs(a[i][j] - b[i][j]))])
                    if abs(k - abs(a[i][j] - b[i][j])) < ma*min(H,W):
                        dp[i][j][abs(k - abs(a[i][j] - b[i][j]))] = max(dp[i][j-1][k],dp[i][j][abs(k - abs(a[i][j] - b[i][j]))])
            elif j == 0:
                for k in range(ma*(min(H,W))):
                    if abs(k + abs(a[i][j] - b[i][j])) < ma*min(H,W):
                        dp[i][j][abs(k + abs(a[i][j] - b[i][j]))] = max(dp[i-1][j][k],dp[i][j][abs(k + abs(a[i][j] - b[i][j]))])
                    if abs(k - abs(a[i][j] - b[i][j])) < ma*min(H,W):
                        dp[i][j][abs(k - abs(a[i][j] - b[i][j]))] = max(dp[i-1][j][k],dp[i][j][abs(k - abs(a[i][j] - b[i][j]))])
            else:
                for k in range(ma*(min(H,W))):
                    if abs(k + abs(a[i][j] - b[i][j])) < ma*min(H,W):
                        dp[i][j][abs(k + abs(a[i][j] - b[i][j]))] = max(dp[i][j-1][k],dp[i-1][j][k],dp[i][j][abs(k + abs(a[i][j] - b[i][j]))])
                    if abs(k - abs(a[i][j] - b[i][j])) < ma*min(H,W):
                        dp[i][j][abs(k - abs(a[i][j] - b[i][j]))] = max(dp[i][j-1][k],dp[i-1][j][k],dp[i][j][abs(k - abs(a[i][j] - b[i][j]))])

    for i in range(ma*min(H,W)):
        if dp[-1][-1][i] == 1:
            print(i)
            exit()




if __name__ == "__main__":
    ans()

Buggy submission (verdict: Runtime Error):
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

mod = 10**9+7 #出力の制限

# a = cmb(n,r)
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

def ans():
    H,W = m()

    a = []

    for i in range(H):
        a.append(l())

    ma = 0
    b = []
    for i in range(H):
        b.append(l())
        for j in range(W):
            ma = max(ma,abs(a[i][j]-b[i][j]))

    dp = [[[0 for i in range(ma*(H+W))]for j in range(W)] for k in range(H)]

    for i in range(H):
        for j in range(W):
            if i == 0 and j == 0:
                dp[0][0][abs(a[0][0] - b[0][0])] = 1
            elif i == 0:
                for k in range(ma*(H+W)):
                    if abs(k + abs(a[i][j] - b[i][j])) < ma*(H+W):
                        dp[i][j][abs(k + abs(a[i][j] - b[i][j]))] = max(dp[i][j-1][k],dp[i][j][abs(k + abs(a[i][j] - b[i][j]))])
                    if abs(k - abs(a[i][j] - b[i][j])) < ma*(H+W):
                        dp[i][j][abs(k - abs(a[i][j] - b[i][j]))] = max(dp[i][j-1][k],dp[i][j][abs(k - abs(a[i][j] - b[i][j]))])
            elif j == 0:
                for k in range(ma*(H+W)):
                    if abs(k + abs(a[i][j] - b[i][j])) < ma*(H+W):
                        dp[i][j][abs(k + abs(a[i][j] - b[i][j]))] = max(dp[i-1][j][k],dp[i][j][abs(k + abs(a[i][j] - b[i][j]))])
                    if abs(k - abs(a[i][j] - b[i][j])) < ma*(H+W):
                        dp[i][j][abs(k - abs(a[i][j] - b[i][j]))] = max(dp[i-1][j][k],dp[i][j][abs(k - abs(a[i][j] - b[i][j]))])
            else:
                for k in range(ma*(H+W)):
                    if abs(k + abs(a[i][j] - b[i][j])) < ma*(H+W):
                        dp[i][j][abs(k + abs(a[i][j] - b[i][j]))] = max(dp[i][j-1][k],dp[i-1][j][k],dp[i][j][abs(k + abs(a[i][j] - b[i][j]))])
                    if abs(k - abs(a[i][j] - b[i][j])) < ma*(H+W):
                        dp[i][j][abs(k - abs(a[i][j] - b[i][j]))] = max(dp[i][j-1][k],dp[i-1][j][k],dp[i][j][abs(k - abs(a[i][j] - b[i][j]))])

    for i in range(ma*(H+W)):
        if dp[-1][-1][i] == 1:
            print(i)
            exit()




if __name__ == "__main__":
    ans()

Buggy submission (verdict: Runtime Error):
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

mod = 10**9+7 #出力の制限

# a = cmb(n,r)
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""
H,W = m()

a = []

for i in range(H):
    a.append(l())

ma = 0
b = []
for i in range(H):
    b.append(l())
    for j in range(W):
        ma = max(ma,abs(a[i][j]-b[i][j]))

dp = [[[0 for i in range(ma*(H+W))]for j in range(W)] for k in range(H)]

for i in range(H):
    for j in range(W):
        if i == 0 and j == 0:
            dp[0][0][abs(a[0][0] - b[0][0])] = 1
        elif i == 0:
            for k in range(ma*(H+W)):
                if abs(k + abs(a[i][j] - b[i][j])) < ma*(H+W):
                    dp[i][j][abs(k + abs(a[i][j] - b[i][j]))] = max(dp[i][j-1][k],dp[i][j][abs(k + abs(a[i][j] - b[i][j]))])
                if abs(k - abs(a[i][j] - b[i][j])) < ma*(H+W):
                    dp[i][j][abs(k - abs(a[i][j] - b[i][j]))] = max(dp[i][j-1][k],dp[i][j][abs(k - abs(a[i][j] - b[i][j]))])
        elif j == 0:
            for k in range(ma*(H+W)):
                if abs(k + abs(a[i][j] - b[i][j])) < ma*(H+W):
                    dp[i][j][abs(k + abs(a[i][j] - b[i][j]))] = max(dp[i-1][j][k],dp[i][j][abs(k + abs(a[i][j] - b[i][j]))])
                if abs(k - abs(a[i][j] - b[i][j])) < ma*(H+W):
                    dp[i][j][abs(k - abs(a[i][j] - b[i][j]))] = max(dp[i-1][j][k],dp[i][j][abs(k - abs(a[i][j] - b[i][j]))])
        else:
            for k in range(ma*(H+W)):
                if abs(k + abs(a[i][j] - b[i][j])) < ma*(H+W):
                    dp[i][j][abs(k + abs(a[i][j] - b[i][j]))] = max(dp[i][j-1][k],dp[i-1][j][k],dp[i][j][abs(k + abs(a[i][j] - b[i][j]))])
                if abs(k - abs(a[i][j] - b[i][j])) < ma*(H+W):
                    dp[i][j][abs(k - abs(a[i][j] - b[i][j]))] = max(dp[i][j-1][k],dp[i-1][j][k],dp[i][j][abs(k - abs(a[i][j] - b[i][j]))])

for i in range(ma*(H+W)):
    if dp[-1][-1][i] == 1:
        print(i)
        exit()

Buggy submission (verdict: Runtime Error):
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

mod = 10**9+7 #出力の制限

# a = cmb(n,r)
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""
H,W = m()

a = []

for i in range(H):
    a.append(l())

ma = 0
b = []
for i in range(H):
    b.append(l())
    for j in range(W):
        ma = max(ma,abs(a[i][j]-b[i][j]))

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

for i in range(H):
    for j in range(W):
        if i == 0 and j == 0:
            dp[0][0][abs(a[0][0] - b[0][0])] = 1
        elif i == 0:
            for k in range(ma*H*W):
                if abs(k + abs(a[i][j] - b[i][j])) < ma*H*W:
                    dp[i][j][abs(k + abs(a[i][j] - b[i][j]))] = max(dp[i][j-1][k],dp[i][j][abs(k + abs(a[i][j] - b[i][j]))])
                if abs(k - abs(a[i][j] - b[i][j])) < ma*H*W:
                    dp[i][j][abs(k - abs(a[i][j] - b[i][j]))] = max(dp[i][j-1][k],dp[i][j][abs(k - abs(a[i][j] - b[i][j]))])
        elif j == 0:
            for k in range(ma*H*W):
                if abs(k + abs(a[i][j] - b[i][j])) < ma*H*W:
                    dp[i][j][abs(k + abs(a[i][j] - b[i][j]))] = max(dp[i-1][j][k],dp[i][j][abs(k + abs(a[i][j] - b[i][j]))])
                if abs(k - abs(a[i][j] - b[i][j])) < ma*H*W:
                    dp[i][j][abs(k - abs(a[i][j] - b[i][j]))] = max(dp[i-1][j][k],dp[i][j][abs(k - abs(a[i][j] - b[i][j]))])
        else:
            for k in range(ma*H*W):
                if abs(k + abs(a[i][j] - b[i][j])) < ma*H*W:
                    dp[i][j][abs(k + abs(a[i][j] - b[i][j]))] = max(dp[i][j-1][k],dp[i-1][j][k],dp[i][j][abs(k + abs(a[i][j] - b[i][j]))])
                if abs(k - abs(a[i][j] - b[i][j])) < ma*H*W:
                    dp[i][j][abs(k - abs(a[i][j] - b[i][j]))] = max(dp[i][j-1][k],dp[i-1][j][k],dp[i][j][abs(k - abs(a[i][j] - b[i][j]))])

for i in range(ma*H*W):
    if dp[-1][-1][i] == 1:
        print(i)
        exit()

Buggy submission (verdict: Runtime Error):
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

mod = 10**9+7 #出力の制限

# a = cmb(n,r)
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""
H,W = m()

a = []

for i in range(H):
    a.append(l())

ma = 0
b = []
for i in range(H):
    b.append(l())
    for j in range(W):
        ma = max(ma,abs(a[i][j]-b[i][j]))

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

for i in range(H):
    for j in range(W):
        if i == 0 and j == 0:
            dp[0][0][abs(a[0][0] - b[0][0])] = 1
        elif i == 0:
            for k in range(ma*H*W):
                if abs(k + abs(a[i][j] - b[i][j])) < ma*H*W:
                    dp[i][j][abs(k + abs(a[i][j] - b[i][j]))] = max(dp[i][j-1][k],dp[i][j][abs(k + abs(a[i][j] - b[i][j]))])
                if abs(k - abs(a[i][j] - b[i][j])) < ma*H*W:
                    dp[i][j][abs(k - abs(a[i][j] - b[i][j]))] = max(dp[i][j-1][k],dp[i][j][abs(k - abs(a[i][j] - b[i][j]))])
        elif j == 0:
            for k in range(ma*H*W):
                if abs(k + abs(a[i][j] - b[i][j])) < ma*H*W:
                    dp[i][j][abs(k + abs(a[i][j] - b[i][j]))] = max(dp[i-1][j][k],dp[i][j][abs(k + abs(a[i][j] - b[i][j]))])
                if abs(k - abs(a[i][j] - b[i][j])) < ma*H*W:
                    dp[i][j][abs(k - abs(a[i][j] - b[i][j]))] = max(dp[i-1][j][k],dp[i][j][abs(k - abs(a[i][j] - b[i][j]))])
        else:
            for k in range(ma*H*W):
                if abs(k + abs(a[i][j] - b[i][j])) < ma*H*W:
                    dp[i][j][abs(k + abs(a[i][j] - b[i][j]))] = max(dp[i][j-1][k],dp[i-1][j][k],dp[i][j][abs(k + abs(a[i][j] - b[i][j]))])
                if abs(k - abs(a[i][j] - b[i][j])) < ma*H*W:
                    dp[i][j][abs(k - abs(a[i][j] - b[i][j]))] = max(dp[i][j-1][k],dp[i-1][j][k],dp[i][j][abs(k - abs(a[i][j] - b[i][j]))])

for i in range(ma*H*W):
    if dp[-1][-1][i] == 1:
        print(i)
        exit()