Buggy python submission (verdict: Time Limit Exceeded):
# https://atcoder.jp/contests/abc175/submissions/15965930

def main():
    import sys
    input = sys.stdin.readline

    H, W, K = map(int, input().split())

    G = [[0] * W for _ in range(H)]
    for _ in range(K):
        r, c, v = map(int, input().split())
        G[r - 1][c - 1] = v

    dp0 = [0] * (W + 1)
    dp1 = [0] * (W + 1)
    dp2 = [0] * (W + 1)
    dp3 = [0] * (W + 1)
    # dpx:=行内取得x個以下の最大値
    # <cは更新済の同じ行の値
    # c<=は前の行の値

    for r in range(H):
        for c in range(W):
            v = G[r][c]

            dp0[c] = max(dp0[c], dp3[c])  # 垂直移動
            vertical_take = dp0[c] + v  # 垂直移動+(r,c)取得

            dp3[c] = max(dp3[c - 1], dp2[c - 1] + v, vertical_take)
            dp2[c] = max(dp2[c - 1], dp1[c - 1] + v, vertical_take)
            dp1[c] = max(dp1[c - 1], dp0[c - 1] + v, vertical_take)
            # 水平移動（左）から来て取らない
            # 水平移動（左）から来て取る
            # 垂直移動で来て取らない:=dp0
            # 垂直移動で来て取る:=dpx(x>0)

            # print(f'{dp0=}')
            # print(f'{dp1=}')
            # print(f'{dp2=}')
            # print(f'{dp3=}')
            # print('*******************')

    print(dp3[-2])


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    import sys
    input = sys.stdin.readline

    H, W, K = map(int, input().split())

    G = [[0] * W for _ in range(H)]
    for _ in range(K):
        r, c, v = map(int, input().split())
        G[r - 1][c - 1] = v

    pdp = [[0] * 4 for _ in range(W)]
    for r in range(H):
        dp = [[0] * 4 for _ in range(W)]
        left = [0] * 4
        for c in range(W):
            cell = dp[c]

            for k in range(4):
                cell[k] = left[k]

            up = max(pdp[c])
            if cell[0] < up:
                cell[0] = up

            for k in range(2, -1, -1):
                cell[k + 1] = max(
                    cell[k + 1],
                    cell[k] + G[r][c])
            left = cell
        pdp = dp

    # for k in range(4):
    #     for row in range(H):
    #         for col in range(W):
    #             print(dp[row][col][k], end=' ')
    #         print()
    #     print()

    # print(*G, sep='\n')

    ans = max(dp[-1])
    print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    import sys
    input = sys.stdin.readline

    H, W, K = map(int, input().split())

    G = [[0] * W for _ in range(H)]
    for _ in range(K):
        r, c, v = map(int, input().split())
        G[r - 1][c - 1] = v

    dp = [[[0] * 4 for _ in range(W + 1)] for _ in range(H + 1)]
    for r in range(H):
        for c in range(W):
            cell = dp[r][c]
            up = dp[r - 1][c]
            left = dp[r][c - 1]

            for k in range(4):
                cell[0] = max(cell[0], up[k])
                cell[k] = max(cell[k], left[k])

            for k in range(2, -1, -1):
                cell[k + 1] = max(
                    cell[k + 1],
                    cell[k] + G[r][c])

    # for k in range(4):
    #     for row in range(H):
    #         for col in range(W):
    #             print(dp[row][col][k], end=' ')
    #         print()
    #     print()

    # print(*G, sep='\n')

    ans = max(dp[-2][-2])
    print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    import sys
    input = sys.stdin.readline

    H, W, K = map(int, input().split())

    G = [[0] * W for _ in range(H)]
    for _ in range(K):
        r, c, v = map(int, input().split())
        G[r - 1][c - 1] = v

    pdp = [[0] * 4 for _ in range(W)]
    for r in range(H):
        dp = [[0] * 4 for _ in range(W)]
        left = [0] * 4
        for c in range(W):
            cell = dp[c]

            for k in range(4):
                cell[k] = left[k]

            up = max(pdp[c])
            if cell[0] < up:
                cell[0] = up

            for k in range(2, -1, -1):
                cell[k + 1] = max(
                    cell[k + 1],
                    cell[k] + G[r][c])
            left = cell
        pdp = dp

    # for k in range(4):
    #     for row in range(H):
    #         for col in range(W):
    #             print(dp[row][col][k], end=' ')
    #         print()
    #     print()

    # print(*G, sep='\n')

    ans = max(dp[-1])
    print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    import sys
    input = sys.stdin.readline

    R, C, K = map(int, input().split())

    G = [[0] * C for _ in range(R)]
    for _ in range(K):
        r, c, v = map(int, input().split())
        r -= 1
        c -= 1
        G[r][c] = v

    dp = [[[0] * 4 for _ in range(C + 1)] for _ in range(R + 1)]

    for r in range(R):
        for c in range(C):
            dp[r][c][0] = max(
                dp[r - 1][c][0],
                dp[r - 1][c][1],
                dp[r - 1][c][2],
                dp[r - 1][c][3],
                dp[r][c - 1][0]
            )
            for i in range(1, 4):
                dp[r][c][i] = max(dp[r][c][i], dp[r][c - 1][i])
            for i in range(2, -1, -1):
                dp[r][c][i + 1] = max(dp[r][c][i + 1], dp[r][c][i] + G[r][c])

    # print(f'{dp=}')
    ans = max(dp[-2][-2])
    print(ans)


if __name__ == '__main__':
    main()

# def binary_search(*, ok, ng, func):
#     while abs(ok - ng) > 1:
#         mid = (ok + ng) // 2
#         if func(mid):
#             ok = mid
#         else:
#             ng = mid
#     return ok


Fixed submission:
def main():
    import sys
    input = sys.stdin.readline

    H, W, K = map(int, input().split())

    G = [[0] * W for _ in range(H)]
    for _ in range(K):
        r, c, v = map(int, input().split())
        G[r - 1][c - 1] = v

    pdp = [[0] * 4 for _ in range(W)]
    for r in range(H):
        dp = [[0] * 4 for _ in range(W)]
        left = [0] * 4
        for c in range(W):
            cell = dp[c]

            for k in range(4):
                cell[k] = left[k]

            up = max(pdp[c])
            if cell[0] < up:
                cell[0] = up

            for k in range(2, -1, -1):
                cell[k + 1] = max(
                    cell[k + 1],
                    cell[k] + G[r][c])
            left = cell
        pdp = dp

    # for k in range(4):
    #     for row in range(H):
    #         for col in range(W):
    #             print(dp[row][col][k], end=' ')
    #         print()
    #     print()

    # print(*G, sep='\n')

    ans = max(dp[-1])
    print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    import sys
    input = sys.stdin.readline

    R, C, K = map(int, input().split())

    G = [[0] * C for _ in range(R)]
    for _ in range(K):
        r, c, v = map(int, input().split())
        r -= 1
        c -= 1
        G[r][c] = v

    dp = [[[0] * 4 for _ in range(C)] for _ in range(R)]

    for r in range(R):
        for c in range(C):
            for i in range(4):
                if r > 0:
                    dp[r][c][0] = max(dp[r][c][0], dp[r - 1][c][i])
                if c > 0:
                    dp[r][c][i] = max(dp[r][c][i], dp[r][c - 1][i])
            for i in range(2, -1, -1):
                dp[r][c][i + 1] = max(dp[r][c][i + 1], dp[r][c][i] + G[r][c])

    # print(f'{dp=}')
    ans = max(dp[-1][-1])
    print(ans)


if __name__ == '__main__':
    main()

# def binary_search(*, ok, ng, func):
#     while abs(ok - ng) > 1:
#         mid = (ok + ng) // 2
#         if func(mid):
#             ok = mid
#         else:
#             ng = mid
#     return ok


Fixed submission:
def main():
    import sys
    input = sys.stdin.readline

    H, W, K = map(int, input().split())

    G = [[0] * W for _ in range(H)]
    for _ in range(K):
        r, c, v = map(int, input().split())
        G[r - 1][c - 1] = v

    pdp = [[0] * 4 for _ in range(W)]
    for r in range(H):
        dp = [[0] * 4 for _ in range(W)]
        left = [0] * 4
        for c in range(W):
            cell = dp[c]

            for k in range(4):
                cell[k] = left[k]

            up = max(pdp[c])
            if cell[0] < up:
                cell[0] = up

            for k in range(2, -1, -1):
                cell[k + 1] = max(
                    cell[k + 1],
                    cell[k] + G[r][c])
            left = cell
        pdp = dp

    # for k in range(4):
    #     for row in range(H):
    #         for col in range(W):
    #             print(dp[row][col][k], end=' ')
    #         print()
    #     print()

    # print(*G, sep='\n')

    ans = max(dp[-1])
    print(ans)


if __name__ == '__main__':
    main()