Problem p02839 (python)

Fixed submission:
def main():
    from sys import stdin
    def input():
        return stdin.readline().strip()

    h, w = map(int, input().split())
    g = []
    for _ in range(h):
        g.append(list(map(int, input().split())))
    for i in range(h):
        k = list(map(int, input().split()))
        for j in range(w):
            g[i][j] = abs(g[i][j] - k[j])

    m = (h + w) * 80

    if m == 0:
        print(0)
        exit()

    dp = [[False] * m for _ in range(w)]
    dp[0][g[0][0]] = True
    for j in range(1, w):
        for k in range(m):
            if dp[j-1][k]:
                dp[j][abs(k - g[0][j])] = True
                dp[j][k + g[0][j]] = True
    
    for i in range(1, h):
        new_dp = [[False] * m for _ in range(w)]
        for k in range(m):
            if dp[0][k]:
                new_dp[0][abs(k - g[i][0])] = True
                new_dp[0][k + g[i][0]] = True
        
        for j in range(1, w):
            for k in range(m):
                if new_dp[j-1][k] or dp[j][k]:
                    new_dp[j][abs(k - g[i][j])] = True
                    new_dp[j][k + g[i][j]] = True
        dp = new_dp

    for j in range(m):
        if dp[w-1][j]:
            print(j)
            break

main()

Buggy submission (verdict: Runtime Error):
h, w = map(int, input().split())
grid = [[0] * (w + 1)]
for _ in range(h):
    grid.append([0] + list(map(int, input().split())))
for i in range(1, h + 1):
    l = [0] + list(map(int, input().split()))
    for j in range(w + 1):
        grid[i][j] = abs(grid[i][j] - l[j])

biggest = max([max(i) for i in grid])
m = (h + w) * biggest

unba = [[[False] * m for _ in range(w + 1)] for _ in range(h + 1)]

for i in range(1, w + 1):
    unba[0][i][0] = True
for i in range(1, h + 1):
    unba[i][0][0] = True

for i in range(1, h + 1):
    for j in range(1, w + 1):
        for k in range(m):
            if unba[i-1][j][k] or unba[i][j-1][k]:
                unba[i][j][grid[i][j] + k] = True
                unba[i][j][abs(grid[i][j] - k)] = True

l = [i for i in range(m) if unba[h][w][i]]
print(min(l))

Buggy submission (verdict: Runtime Error):
h, w = map(int, input().split())
grid = []
for _ in range(h):
    grid.append(list(map(int, input().split())))
for i in range(h):
    l = list(map(int, input().split()))
    for j in range(w):
        grid[i][j] = abs(grid[i][j] - l[j])

biggest = max([max(i) for i in grid])
m = (h + w) * biggest

unba = [[[False] * m for _ in range(w)] for _ in range(h)]

# 0行目
unba[0][0][grid[0][0]] = True
for i in range(1, w):
    for j in range(m):
        if unba[0][i-1][j]:
            unba[0][i][grid[0][i] + j] = True
            unba[0][i][abs(grid[0][i] - j)] = True

# 1~h-1行目
for i in range(1, h):

    # i行0列
    for j in range(m):
        if unba[i-1][0][j]:
            unba[i][0][grid[i][0] + j] = True
            unba[i][0][abs(grid[i][0] - j)] = True

    # i行j列
    for j in range(1, w):
        for k in range(m):
            if unba[i-1][j][k] or unba[i][j-1][k]:
                unba[i][j][grid[i][j] + k] = True
                unba[i][j][abs(grid[i][j] - k)] = True

l = [i for i in range(m) if unba[h-1][w-1][i]]
print(min(l))

Buggy submission (verdict: Runtime Error):
h, w = map(int, input().split())
grid = []
for _ in range(h):
    grid.append(list(map(int, input().split())))
for i in range(h):
    l = list(map(int, input().split()))
    for j in range(w):
        grid[i][j] = abs(grid[i][j] - l[j])

biggest = max([max(i) for i in grid])
m = (h + w) * biggest

unba = [[[False for _ in range(m)] for _ in range(w)] for _ in range(h)]

# 0行目
unba[0][0][grid[0][0]] = True
for i in range(1, w):
    for j in range(m):
        if unba[0][i-1][j]:
            unba[0][i][grid[0][i] + j] = True
            unba[0][i][abs(grid[0][i] - j)] = True

# 1~h-1行目
for i in range(1, h):

    # i行0列
    for j in range(m):
        if unba[i-1][0][j]:
            unba[i][0][grid[i][0] + j] = True
            unba[i][0][abs(grid[i][0] - j)] = True

    # i行j列
    for j in range(1, w):
        for k in range(m):
            if unba[i-1][j][k] or unba[i][j-1][k]:
                unba[i][j][grid[i][j] + k] = True
                unba[i][j][abs(grid[i][j] - k)] = True

l = [i for i in range(m) if unba[h-1][w-1][i]]
print(min(l))

Buggy submission (verdict: Runtime Error):
h, w = map(int, input().split())
grid = []
for _ in range(h):
    grid.append(list(map(int, input().split())))
for i in range(h):
    l = list(map(int, input().split()))
    for j in range(w):
        grid[i][j] = abs(grid[i][j] - l[j])

biggest = max([max(i) for i in grid])
m = (h + w) * biggest

unba = [[[False for _ in range(m)] for _ in range(w)] for _ in range(h)]

# 0行目
unba[0][0][grid[0][0]] = True
for i in range(1, w):
    for j in range(m):
        if unba[0][i-1][j]:
            unba[0][i][grid[0][i] + j] = True
            unba[0][i][abs(grid[0][i] - j)] = True

# 1~h-1行目
for i in range(1, h):

    # i行0列
    for j in range(m):
        if unba[i-1][0][j]:
            unba[i][0][grid[i][0] + j] = True
            unba[i][0][abs(grid[i][0] - j)] = True

    # i行j列
    for j in range(1, w):
        for k in range(m):
            if unba[i-1][j][k] or unba[i][j-1][k]:
                unba[i][j][grid[i][j] + k] = True
                unba[i][j][abs(grid[i][j] - k)] = True

l = [i for i in range(m) if unba[h-1][w-1][i]]
print(min(l))

Buggy submission (verdict: Runtime Error):
h, w = map(int, input().split())
grid = []
for _ in range(h):
    grid.append(list(map(int, input().split())))
for i in range(h):
    l = list(map(int, input().split()))
    for j in range(w):
        grid[i][j] = abs(grid[i][j] - l[j])

biggest = max([max(i) for i in grid])
m = (h + w) * biggest

unba = [[[0 for _ in range(m)] for _ in range(w)] for _ in range(h)]

# 0行目
unba[0][0][grid[0][0]] = 1
for i in range(1, w):
    for j in range(m):
        if unba[0][i-1][j] == 1:
            unba[0][i][grid[0][i] + j] = 1
            unba[0][i][abs(grid[0][i] - j)] = 1

# 1~h-1行目
for i in range(1, h):

    # i行0列
    for j in range(m):
        if unba[i-1][0][j] == 1:
            unba[i][0][grid[i][0] + j] = 1
            unba[i][0][abs(grid[i][0] - j)] = 1

    # i行j列
    for j in range(1, w):
        for k in range(m):
            if unba[i-1][j][k] == 1 or unba[i][j-1][k] == 1:
                unba[i][j][grid[i][j] + k] = 1
                unba[i][j][abs(grid[i][j] - k)] = 1

l = [i for i in range(m) if unba[h-1][w-1][i] == 1]
print(min(l))

Buggy submission (verdict: Runtime Error):
h, w = map(int, input().split())
grid = []
for _ in range(h):
    grid.append(list(map(int, input().split())))
for i in range(h):
    l = list(map(int, input().split()))
    for j in range(w):
        grid[i][j] = grid[i][j] - l[j]

biggest = max([max([max(i) for i in grid]), -min([min(i) for i in grid])])
m = (h + w) * biggest

unba = [[[0 for _ in range(2*m)] for _ in range(w)] for _ in range(h)]

# 0行目
unba[0][0][grid[0][0]] = 1
unba[0][0][-grid[0][0]] = 1
for i in range(1, w):
    for j in range(-m, m):
        if unba[0][i-1][j] == 1:
            unba[0][i][grid[0][i] + j] = 1
            unba[0][i][grid[0][i] - j] = 1

# 1~h-1行目
for i in range(1, h):

    # i行0列
    for j in range(-m, m):
        if unba[i-1][0][j] == 1:
            unba[i][0][grid[i][0] + j] = 1
            unba[i][0][grid[i][0] - j] = 1

    # i行j列
    for j in range(1, w):
        for k in range(-m, m):
            if unba[i-1][j][k] == 1 or unba[i][j-1][k]:
                unba[i][j][grid[i][j] + k] = 1
                unba[i][j][grid[i][j] - k] = 1

ans = [abs(i) for i in range(-m, m) if unba[h-1][w-1][i] == 1]
print(min(ans))

Buggy submission (verdict: Runtime Error):
h, w = map(int, input().split())
grid = []
for _ in range(h):
    grid.append(list(map(int, input().split())))
for i in range(h):
    l = list(map(int, input().split()))
    for j in range(w):
        grid[i][j] = grid[i][j] - l[j]

biggest = max([max(i) for i in grid])
m = (h + w) * biggest

unba = [[[0 for _ in range(2*m)] for _ in range(w)] for _ in range(h)]

# 0行目
unba[0][0][grid[0][0]] = 1
unba[0][0][-grid[0][0]] = 1
for i in range(1, w):
    for j in range(-m, m):
        if unba[0][i-1][j] == 1:
            unba[0][i][grid[0][i] + j] = 1
            unba[0][i][grid[0][i] - j] = 1

# 1~h-1行目
for i in range(1, h):

    # i行0列
    for j in range(-m, m):
        if unba[i-1][0][j] == 1:
            unba[i][0][grid[i][0] + j] = 1
            unba[i][0][grid[i][0] - j] = 1

    # i行j列
    for j in range(1, w):
        for k in range(-m, m):
            if unba[i-1][j][k] == 1 or unba[i][j-1][k]:
                unba[i][j][grid[i][j] + k] = 1
                unba[i][j][grid[i][j] - k] = 1

ans = [abs(i) for i in range(-m, m) if unba[h-1][w-1][i] == 1]
print(min(ans))