Problem p02586 (python)

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

    r, c, k = map(int, input().split())
    v = [[0] * c for _ in range(r)]
    for _ in range(k):
        i, j, k = map(int, input().split())
        v[i-1][j-1] = k

    # dp[j][n] = j列にいて、n個itemを拾った時のアイテムの価値の合計の最大値
    # 1行ずつdpを更新する
    # 0行目
    value = v[0][0]
    if value == 0:
        dp = [[0] * 4]
    else:
        dp = [[0, value, value, value]]
    for j in range(1, c):
        value = v[0][j]
        if value == 0:
            dp.append(dp[j-1])
            continue
        a = dp[j-1].copy()
        b = [0, a[0]+value, a[1]+value, a[2]+value]
        for k in range(1, 4):
            if a[k] < b[k]:
                a[k] = b[k]
        dp.append(a)

    # i行目
    for i in range(1, r):
        pre = dp[0][3]
        value = v[i][0]
        if value == 0:
            new_dp = [[pre] * 4]
        else:
            new_dp = [[pre, pre+value, pre+value, pre+value]]
        for j in range(1, c):
            value = v[i][j]
            if value == 0:
                a = new_dp[j-1].copy()
                b = [dp[j][3]] * 4
                for k in range(4):
                    if a[k] < b[k]:
                        a[k] = b[k]
                new_dp.append(a)
            else:
                a = new_dp[j-1].copy()
                pre = dp[j][3]
                b = [pre, pre+value, pre+value, pre+value]
                d = [a[0], a[0]+value, a[1]+value, a[2]+value]
                for k in range(4):
                    if a[k] < b[k]:
                        a[k] = b[k]
                    if a[k] < d[k]:
                        a[k] = d[k]
                new_dp.append(a)
        dp = new_dp

    print(dp[c-1][3])

main()

Buggy submission (verdict: Runtime Error):
def main():
    from sys import stdin
    def input():
        return stdin.readline().strip()

    r, c, k = map(int, input().split())
    v = [[0] * c for _ in range(r)]
    for _ in range(k):
        i, j, k = map(int, input().split())
        v[i-1][j-1] = k

    # dp[j][n] = j列にいて、n個itemを拾った時のアイテムの価値の合計の最大値
    # 1行ずつdpを更新する
    # 0行目
    value = v[0][0]
    if value == 0:
        dp = [[0] * 4]
    else:
        dp = [[0, value, value, value]]
    for j in range(1, c):
        value = v[0][j]
        if value == 0:
            dp.append(dp[j-1])
            continue
        a = dp[j-1].copy()
        b = [0, a[0]+value, a[1]+value, a[2]+value]
        for k in range(1, 4):
            if a[k] < b[k]:
                a[k] = b[k]
        dp.append(a)

    print(dp)

    # i行目
    for i in range(1, r):
        pre = dp[0][3]
        value = v[i][0]
        if value == 0:
            new_dp = [[pre] * 4]
        else:
            new_dp = [[pre, pre+value, pre+value, pre+value]]
        for j in range(1, c):
            value = v[i][j]
            if value == 0:
                a = new_dp[j-1].copy()
                b = [dp[j][3]] * 4
                for k in range(4):
                    if a[k] < b[k]:
                        a[k] = b[k]
                new_dp.append(a)
            else:
                a = new_dp[j-1].copy()
                pre = dp[j][3]
                b = [pre, pre+value, pre+value, pre+value]
                d = [a[0], a[0]+value, a[1]+value, a[2]+value]
                for k in range(4):
                    if a[k] < b[k]:
                        a[k] = b[k]
                    if a[k] < d[k]:
                        a[k] = d[k]
                new_dp.append(a)
        dp = new_dp
        print(dp)

    print(dp[c-1][3])

main()

Buggy submission (verdict: Runtime Error):
def main():
    from sys import stdin
    def input():
        return stdin.readline().strip()

    r, c, k = map(int, input().split())
    value = [[0] * c for _ in range(r)]
    for _ in range(k):
        i, j, k = map(int, input().split())
        value[i-1][j-1] = k

    # dp
    # g[i][j][n] == [a, b]: 座標(i, j)にいてi行でn個itemを拾った状態
    # a = sum of values
    # b = list of values in row of i
    g = [[[None, None, None, None] for _ in range(c)] for _ in range(r)]
    if value[0][0] > 0:
        g[0][0][1] = [value[0][0], [value[0][0]]]
    else:
        g[0][0][0] = [[0, []]]

    # 0列
    for i in range(1, r):
        if value[i][0] > 0:
            if g[i-1][0][1] == None:
                g[i][0][1] = g[i-1][0][0].copy()
            else:
                g[i][0][1] = g[i-1][0][1].copy()
            g[i][0][1][0] += value[i][0]
            g[i][0][1][1] = [value[i][0]]
        else:
            if g[i-1][0][1] == None:
                g[i][0][0] = g[i-1][0][0].copy()
            else:
                g[i][0][0] = g[i-1][0][1].copy()
            g[i][0][0][1] = []

    # 0行
    for j in range(1, c):
        for k in range(4):
            if g[0][j-1][k] == None:
                continue
            if value[0][j] > 0:
                if k == 3:
                    g[0][j][3] = g[0][j-1][3].copy()
                    g[0][j][3][0] += value[0][j]
                    g[0][j][3][1].append(value[0][j])
                    g[0][j][3][1].sort(reverse=True)
                    g[0][j][3][0] -= g[0][j][3][1].pop(3)
                else:
                    g[0][j][k+1] = g[0][j-1][k].copy()
                    g[0][j][k+1][0] += value[0][j]
                    g[0][j][k+1][1].append(value[0][j])
            else:
                g[0][j][k] = g[0][j-1][k].copy()
            break

    for i in range(1, r):
        for j in range(1, c):
            if value[i][j] > 0:
                # 下
                for k in range(4):
                    if g[i-1][j][k] == None:
                        continue
                    if g[i][j][1] == None or g[i][j][1][0] < g[i-1][j][k][0] + value[i][j]:
                        g[i][j][1] = g[i-1][j][k].copy()
                        g[i][j][1][0] += value[i][j]
                        g[i][j][1][1] = [value[i][j]].copy()

                # 右
                for k in range(4):
                    if g[i][j-1][k] == None:
                        continue
                    if k == 3:
                        if g[i][j][3] == None or g[i][j][3][0] < g[i][j-1][3][0] + value[i][j] - min(g[i][j-1][3][1] + [value[i][j]]):
                            g[i][j][3] = g[i][j-1][3].copy()
                            g[i][j][3][0] += value[i][j]
                            g[i][j][3][1].append(value[i][j])
                            g[i][j][3][1].sort(reverse=True)
                            g[i][j][3][0] -= g[i][j][3][1].pop(3)
                    else:
                        if g[i][j][k+1] == None or g[i][j][k+1][0] < g[i][j-1][k][0] + value[i][j]:
                            g[i][j][k+1] = g[i][j-1][k].copy()
                            g[i][j][k+1][0] += value[i][j]
                            g[i][j][k+1][1].append(value[i][j])
                            
            else:
                # 下
                for k in range(4):
                    if g[i-1][j][k] == None:
                        continue
                    if g[i][j][0] == None or g[i][j][0][0] < g[i-1][j][k][0]:
                        g[i][j][0] = g[i-1][j][k].copy()
                        g[i][j][0][1] = []

                # 右
                for k in range(4):
                    if g[i][j-1][k] == None:
                        continue
                    if g[i][j][k] == None or g[i][j][k][0] < g[i][j-1][k][0]:
                            g[i][j][k] = g[i][j-1][k].copy()

    ans = 0
    for i in g[r-1][c-1]:
        if i != None and ans < i[0]:
            ans = i[0]
    print(ans)

main()