Buggy python submission (verdict: Time Limit Exceeded):
R, C, K = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(K)]

items = [[0] * (C + 1) for _ in range(R + 1)]
for r, c, v in X:
    items[r][c] = v

dp = [[[0] * 4 for _ in range(C + 1)] for _ in range(R + 1)]
for i in range(1, R + 1):
    for j in range(1, C + 1):
        # k=0, horizontal and vertical transitions are allowed
        dp[i][j][0] = max(dp[i][j - 1][0], dp[i - 1][j][0], dp[i - 1][j][1],
                          dp[i - 1][j][2], dp[i - 1][j][3])

        # k=1~3, horizontal transition and picking up are allowed
        dp[i][j][3] = max(dp[i][j - 1][3], dp[i][j - 1][2] + items[i][j],
                          dp[i][j][2] + items[i][j])

        dp[i][j][2] = max(dp[i][j - 1][2], dp[i][j - 1][1] + items[i][j],
                          dp[i][j][1] + items[i][j])

        dp[i][j][1] = max(dp[i][j - 1][1], dp[i][j - 1][0] + items[i][j],
                          dp[i][j][0] + items[i][j])

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


Fixed submission:

R, C, K = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(K)]

items = [[0] * (C + 1) for _ in range(R + 1)]
for r, c, v in X:
    items[r][c] = v

dp = [[0] * 4 for _ in range(C + 1)]
for i in range(1, R + 1):
    # Vertical transition
    for j in range(1, C + 1):
        dp[j][0] = max(dp[j])
        for k in range(1, 4):
            dp[j][k] = 0

    # Horizontal or picking-up transition
    for j in range(1, C + 1):
        for k in reversed(range(4)):
            dp[j][k] = max(dp[j][k], dp[j - 1][k])
            if items[i][j] and k < 3:
                dp[j][k + 1] = max(dp[j][k + 1], dp[j][k] + items[i][j])

print(max(dp[-1]))

Buggy python submission (verdict: Time Limit Exceeded):

R, C, K = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(K)]

items = [[0] * (C + 1) for _ in range(R + 1)]
for r, c, v in X:
    items[r][c] = v

dp = [[[0] * 4 for _ in range(C + 1)] for _ in range(R + 1)]
for i in range(1, R + 1):
    for j in range(1, C + 1):
        # k=0, horizontal and vertical transitions are allowed
        dp[i][j][0] = max(dp[i][j - 1][0], dp[i - 1][j][0], dp[i - 1][j][1],
                          dp[i - 1][j][2], dp[i - 1][j][3])

        # k=1~3, horizontal transition and picking up are allowed
        dp[i][j][3] = max(dp[i][j - 1][3], dp[i][j - 1][2] + items[i][j],
                          dp[i][j][2] + items[i][j])

        dp[i][j][2] = max(dp[i][j - 1][2], dp[i][j - 1][1] + items[i][j],
                          dp[i][j][1] + items[i][j])

        dp[i][j][1] = max(dp[i][j - 1][1], dp[i][j - 1][0] + items[i][j],
                          dp[i][j][0] + items[i][j])

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


Fixed submission:

R, C, K = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(K)]

items = [[0] * (C + 1) for _ in range(R + 1)]
for r, c, v in X:
    items[r][c] = v

dp = [[0] * 4 for _ in range(C + 1)]
for i in range(1, R + 1):
    # Vertical transition
    for j in range(1, C + 1):
        dp[j][0] = max(dp[j])
        for k in range(1, 4):
            dp[j][k] = 0

    # Horizontal or picking-up transition
    for j in range(1, C + 1):
        for k in reversed(range(4)):
            dp[j][k] = max(dp[j][k], dp[j - 1][k])
            if items[i][j] and k < 3:
                dp[j][k + 1] = max(dp[j][k + 1], dp[j][k] + items[i][j])

print(max(dp[-1]))

Buggy python submission (verdict: Time Limit Exceeded):

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

items = dict()
for i in range(K):
    r, c, v = map(int, input().split())
    items[(r, c)] = v

dp = [[[0] * 4 for _ in range(C + 1)] for _ in range(R + 1)]
for i in range(1, R + 1):
    for j in range(1, C + 1):
        for k in range(4):
            # Horizontal
            dp[i][j][k] = max(dp[i][j][k], dp[i][j - 1][k])

            # Vertical
            dp[i][j][0] = max(dp[i][j][0], dp[i - 1][j][k])

        for k in reversed(range(4)):
            # Pick up items
            if (i, j) in items and k < 3:
                dp[i][j][k + 1] = max(
                    dp[i][j][k + 1], dp[i][j][k] + items[(i, j)])

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


Fixed submission:

R, C, K = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(K)]

items = [[0] * (C + 1) for _ in range(R + 1)]
for r, c, v in X:
    items[r][c] = v

dp = [[0] * 4 for _ in range(C + 1)]
for i in range(1, R + 1):
    # Vertical transition
    for j in range(1, C + 1):
        dp[j][0] = max(dp[j])
        for k in range(1, 4):
            dp[j][k] = 0

    # Horizontal or picking-up transition
    for j in range(1, C + 1):
        for k in reversed(range(4)):
            dp[j][k] = max(dp[j][k], dp[j - 1][k])
            if items[i][j] and k < 3:
                dp[j][k + 1] = max(dp[j][k + 1], dp[j][k] + items[i][j])

print(max(dp[-1]))

Buggy python submission (verdict: Time Limit Exceeded):

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

items = dict()
for i in range(K):
    r, c, v = map(int, input().split())
    items[(r, c)] = v

dp = [[[0] * 4 for _ in range(C + 1)] for _ in range(R + 1)]
for i in range(1, R + 1):
    for j in range(1, C + 1):
        for k in range(4):
            # Horizontal
            dp[i][j][k] = max(dp[i][j][k], dp[i][j - 1][k])

            # Vertical
            dp[i][j][0] = max(dp[i][j][0], dp[i - 1][j][k])

        for k in reversed(range(4)):
            # Pick up items
            if (i, j) in items and k < 3:
                dp[i][j][k + 1] = max(
                    dp[i][j][k + 1], dp[i][j][k] + items[(i, j)])

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


Fixed submission:

R, C, K = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(K)]

items = [[0] * (C + 1) for _ in range(R + 1)]
for r, c, v in X:
    items[r][c] = v

dp = [[0] * 4 for _ in range(C + 1)]
for i in range(1, R + 1):
    # Vertical transition
    for j in range(1, C + 1):
        dp[j][0] = max(dp[j])
        for k in range(1, 4):
            dp[j][k] = 0

    # Horizontal or picking-up transition
    for j in range(1, C + 1):
        for k in reversed(range(4)):
            dp[j][k] = max(dp[j][k], dp[j - 1][k])
            if items[i][j] and k < 3:
                dp[j][k + 1] = max(dp[j][k + 1], dp[j][k] + items[i][j])

print(max(dp[-1]))

Buggy python submission (verdict: Time Limit Exceeded):

from collections import defaultdict

R, C, K = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(K)]

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

items = defaultdict(int)
for r, c, v in X:
    items[(r, c)] = v

for i in range(1, R + 1):
    for j in range(1, C + 1):
        for k in range(4):
            # Horizontal
            dp[i][j][k] = max(dp[i][j][k], dp[i][j - 1][k])

            # Vertical
            dp[i][j][0] = max(dp[i][j][0], dp[i - 1][j][k])

        for k in reversed(range(4)):
            if items[(i, j)] > 0 and k < 3:
                dp[i][j][k + 1] = max(
                    dp[i][j][k + 1], dp[i][j][k] + items[(i, j)])

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


Fixed submission:

R, C, K = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(K)]

items = [[0] * (C + 1) for _ in range(R + 1)]
for r, c, v in X:
    items[r][c] = v

dp = [[0] * 4 for _ in range(C + 1)]
for i in range(1, R + 1):
    # Vertical transition
    for j in range(1, C + 1):
        dp[j][0] = max(dp[j])
        for k in range(1, 4):
            dp[j][k] = 0

    # Horizontal or picking-up transition
    for j in range(1, C + 1):
        for k in reversed(range(4)):
            dp[j][k] = max(dp[j][k], dp[j - 1][k])
            if items[i][j] and k < 3:
                dp[j][k + 1] = max(dp[j][k + 1], dp[j][k] + items[i][j])

print(max(dp[-1]))