Buggy python submission (verdict: Time Limit Exceeded):

import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read 
inp = sys.stdin.buffer.readline
def inpS(): return inp().rstrip().decode()

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

    dp = [[[0] * 4 for _ in range(C + 1)] for _ in range(R + 1)]
    for i in range(R + 1):
        for j in range(C + 1):
            for k in range(4):
                # 次の行に移動する場合
                if i + 1 <= R:
                    # 移動先のアイテムを取らない場合
                    dp[i + 1][j][0] = max(dp[i + 1][j][0], dp[i][j][k])
                    # 移動先のアイテムを取る場合
                    dp[i + 1][j][1] = max(dp[i + 1][j][1], dp[i][j][k] + G[i + 1][j])
                # 次の列に移動する場合
                if j + 1 <= C:
                    # 移動先のアイテムを取らない場合
                    dp[i][j + 1][k] = max(dp[i][j + 1][k], dp[i][j][k])
                    # 現在のkが3未満のときのみ, 移動先のアイテムを取ることが可能
                    if k < 3:
                        dp[i][j + 1][k + 1] = max(dp[i][j + 1][k + 1], dp[i][j][k] + G[i][j + 1])

    ans = 0
    for k in range(4):
        ans = max(ans, dp[-1][-1][k])
    print(ans)


if __name__ == "__main__":
    resolve()


Fixed submission:

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

    DP1 = [0 for _ in range(C + 1)]  # c列目までとったとき、最新の行で1個以下とったという条件のもとの最大
    DP2 = [0 for _ in range(C + 1)]  # c列目までとったとき、最新の行で2個以下とったという条件のもとの最大
    DP3 = [0 for _ in range(C + 1)]  # c列目までとったとき、最新の行で3個以下とったという条件のもとの最大

    for r in range(1, R+1):
        for c in range(1, C+1):
            # 更新の順番に注意
            # mid = max(DP1[c], DP2[c], DP3[c]) + I[r][c]
            mid = DP3[c] + G[r][c]
            DP3[c] = max(DP3[c - 1], mid, DP2[c - 1] + G[r][c])  # 3個
            DP2[c] = max(DP2[c - 1], mid, DP1[c - 1] + G[r][c])  # 2個
            DP1[c] = max(DP1[c - 1], mid)  # 1個

    print(DP3[C])

if __name__ == "__main__":
    resolve()

Buggy python submission (verdict: Time Limit Exceeded):

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

    dp = [[[0] * 4 for _ in range(C + 1)] for _ in range(R + 1)]
    for i in range(R + 1):
        for j in range(C + 1):
            for k in range(4):
                # 次の行に移動する場合
                if i + 1 <= R:
                    # 移動先のアイテムを取らない場合
                    dp[i + 1][j][0] = max(dp[i + 1][j][0], dp[i][j][k])
                    # 移動先のアイテムを取る場合
                    dp[i + 1][j][1] = max(dp[i + 1][j][1], dp[i][j][k] + G[i + 1][j])
                # 次の列に移動する場合
                if j + 1 <= C:
                    # 移動先のアイテムを取らない場合
                    dp[i][j + 1][k] = max(dp[i][j + 1][k], dp[i][j][k])
                    # 現在のkが3未満のときのみ, 移動先のアイテムを取ることが可能
                    if k < 3:
                        dp[i][j + 1][k + 1] = max(dp[i][j + 1][k + 1], dp[i][j][k] + G[i][j + 1])

    ans = 0
    for k in range(4):
        ans = max(ans, dp[-1][-1][k])
    print(ans)


if __name__ == "__main__":
    resolve()

Fixed submission:

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

    DP1 = [0 for _ in range(C + 1)]  # c列目までとったとき、最新の行で1個以下とったという条件のもとの最大
    DP2 = [0 for _ in range(C + 1)]  # c列目までとったとき、最新の行で2個以下とったという条件のもとの最大
    DP3 = [0 for _ in range(C + 1)]  # c列目までとったとき、最新の行で3個以下とったという条件のもとの最大

    for r in range(1, R+1):
        for c in range(1, C+1):
            # 更新の順番に注意
            # mid = max(DP1[c], DP2[c], DP3[c]) + I[r][c]
            mid = DP3[c] + G[r][c]
            DP3[c] = max(DP3[c - 1], mid, DP2[c - 1] + G[r][c])  # 3個
            DP2[c] = max(DP2[c - 1], mid, DP1[c - 1] + G[r][c])  # 2個
            DP1[c] = max(DP1[c - 1], mid)  # 1個

    print(DP3[C])

if __name__ == "__main__":
    resolve()

Buggy python submission (verdict: Time Limit Exceeded):

def resolve():
    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())
        G[r - 1][c - 1] = v

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

    for i in range(R):
        for j in range(C):
            for k in range(2, -1, -1):
                dp[i][j][k + 1] = max(dp[i][j][k + 1], dp[i][j][k] + G[i][j])
            for k in range(4):
                dp[i + 1][j][0] = max(dp[i + 1][j][0], dp[i][j][k])
                dp[i][j + 1][k] = max(dp[i][j + 1][k], dp[i][j][k])
                
    ans = 0
    for k in range(4):
        ans = max(ans, dp[R-1][C-1][k])
    print(ans)


if __name__ == "__main__":
    resolve()

Fixed submission:

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

    DP1 = [0 for _ in range(C + 1)]  # c列目までとったとき、最新の行で1個以下とったという条件のもとの最大
    DP2 = [0 for _ in range(C + 1)]  # c列目までとったとき、最新の行で2個以下とったという条件のもとの最大
    DP3 = [0 for _ in range(C + 1)]  # c列目までとったとき、最新の行で3個以下とったという条件のもとの最大

    for r in range(1, R+1):
        for c in range(1, C+1):
            # 更新の順番に注意
            # mid = max(DP1[c], DP2[c], DP3[c]) + I[r][c]
            mid = DP3[c] + G[r][c]
            DP3[c] = max(DP3[c - 1], mid, DP2[c - 1] + G[r][c])  # 3個
            DP2[c] = max(DP2[c - 1], mid, DP1[c - 1] + G[r][c])  # 2個
            DP1[c] = max(DP1[c - 1], mid)  # 1個

    print(DP3[C])

if __name__ == "__main__":
    resolve()