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

R, C, k = (int(x) for x in input().split())
V = [[0] * (C + 5) for _ in range(R + 5)]
for _ in range(k):
    r, c, v = (int(x) for x in input().split())
    V[r][c] = v

# dp[i][j][3]
dp = [[[0] * 4 for _ in range(C + 5)] for _ in range(R + 5)]
for i in range(R + 3):
    for j in range(C + 3):
        for k in range(4):
            # 行移動
            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] + V[i + 1][j])
            # 列移動
            dp[i][j + 1][k] = max(dp[i][j + 1][k], dp[i][j][k])
            if k < 3:
                dp[i][j + 1][k + 1] = max(dp[i][j + 1][k + 1], dp[i][j][k] + V[i][j + 1])
print(max(dp[R][C]))


Fixed submission:
import sys
def input(): return sys.stdin.readline().rstrip()

R, C, k = (int(x) for x in input().split())
V = [[0] * (C + 5) for _ in range(R + 5)]
for _ in range(k):
    r, c, v = (int(x) for x in input().split())
    V[r][c] = v

# dp[3][i][j]
dp = [[[0] * (C + 5) for _ in range(R + 5)] for _ in range(4)]
for i in range(R + 3):
    for j in range(C + 3):
        for k in range(4):
            # 行移動
            dp[0][i + 1][j] = max(dp[0][i + 1][j], dp[k][i][j])
            dp[1][i + 1][j] = max(dp[1][i + 1][j], dp[k][i][j] + V[i + 1][j])
            # 列移動
            dp[k][i][j + 1] = max(dp[k][i][j + 1], dp[k][i][j])
            if k < 3:
                dp[k + 1][i][j + 1] = max(dp[k + 1][i][j + 1], dp[k][i][j] + V[i][j + 1])
print(max(dp[k][R][C] for k in range(4)))

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

R, C, k = (int(x) for x in input().split())
V = [[0] * (C + 5) for _ in range(R + 5)]
for _ in range(k):
    r, c, v = (int(x) for x in input().split())
    V[r][c] = v

# dp[i][j][3]
dp = [[[0] * (C+5) for _ in range(R + 5)] for _ in range(4)]
for i in range(1, R + 3):
    for j in range(1, C + 3):
        # 行移動
        dp[0][i][j] = max(dp[0][i][j], max(dp[k][i - 1][j] for k in range(4)))
        dp[1][i][j] = max(dp[1][i][j], max(dp[k][i - 1][j] for k in range(4)) + V[i][j])
        for k in range(4):
            # 列移動
            if k > 0:
                dp[k][i][j] = max(dp[k][i][j], dp[k-1][i][j-1] + V[i][j])
            dp[k][i][j] = max(dp[k][i][j], dp[k][i][j-1])
print(max(dp[k][R][C] for k in range(4)))


Fixed submission:
import sys
def input(): return sys.stdin.readline().rstrip()

R, C, k = (int(x) for x in input().split())
V = [[0] * (C + 5) for _ in range(R + 5)]
for _ in range(k):
    r, c, v = (int(x) for x in input().split())
    V[r][c] = v

# dp[3][i][j]
dp = [[[0] * (C + 5) for _ in range(R + 5)] for _ in range(4)]
for i in range(R + 3):
    for j in range(C + 3):
        for k in range(4):
            # 行移動
            dp[0][i + 1][j] = max(dp[0][i + 1][j], dp[k][i][j])
            dp[1][i + 1][j] = max(dp[1][i + 1][j], dp[k][i][j] + V[i + 1][j])
            # 列移動
            dp[k][i][j + 1] = max(dp[k][i][j + 1], dp[k][i][j])
            if k < 3:
                dp[k + 1][i][j + 1] = max(dp[k + 1][i][j + 1], dp[k][i][j] + V[i][j + 1])
print(max(dp[k][R][C] for k in range(4)))

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

R, C, k = (int(x) for x in input().split())
V = [[0] * (C + 5) for _ in range(R + 5)]
for _ in range(k):
    r, c, v = (int(x) for x in input().split())
    V[r][c] = v

# dp[i][j][3]
dp = [[[0] * 4 for _ in range(C + 5)] for _ in range(R + 5)]
for i in range(1, R + 3):
    for j in range(1, C + 3):
        # 行移動
        dp[i][j][0] = max(dp[i][j][0], max(dp[i - 1][j]))
        dp[i][j][1] = max(dp[i][j][1], max(dp[i - 1][j]) + V[i][j])
        for k in range(4):
            # 列移動
            if k > 0:
                dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k - 1] + V[i][j])
            dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k])
print(max(dp[R][C]))


Fixed submission:
import sys
def input(): return sys.stdin.readline().rstrip()

R, C, k = (int(x) for x in input().split())
V = [[0] * (C + 5) for _ in range(R + 5)]
for _ in range(k):
    r, c, v = (int(x) for x in input().split())
    V[r][c] = v

# dp[3][i][j]
dp = [[[0] * (C + 5) for _ in range(R + 5)] for _ in range(4)]
for i in range(R + 3):
    for j in range(C + 3):
        for k in range(4):
            # 行移動
            dp[0][i + 1][j] = max(dp[0][i + 1][j], dp[k][i][j])
            dp[1][i + 1][j] = max(dp[1][i + 1][j], dp[k][i][j] + V[i + 1][j])
            # 列移動
            dp[k][i][j + 1] = max(dp[k][i][j + 1], dp[k][i][j])
            if k < 3:
                dp[k + 1][i][j + 1] = max(dp[k + 1][i][j + 1], dp[k][i][j] + V[i][j + 1])
print(max(dp[k][R][C] for k in range(4)))

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

R, C, k = (int(x) for x in input().split())
V = [[0] * (C + 5) for _ in range(R + 5)]
for _ in range(k):
    r, c, v = (int(x) for x in input().split())
    V[r][c] = v

# dp[i][j][3]
dp = [[[0] * 4 for _ in range(C + 5)] for _ in range(R + 5)]
for i in range(1, R + 3):
    for j in range(1, C + 3):
        # 行移動
        dp[i][j][0] = max(dp[i][j][0], max(dp[i - 1][j]))
        dp[i][j][1] = max(dp[i][j][1], max(dp[i - 1][j]) + V[i][j])
        for k in range(4):
            # 列移動
            if k > 0:
                dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k - 1] + V[i][j])
            dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k])
print(max(dp[R][C]))

Fixed submission:
import sys
def input(): return sys.stdin.readline().rstrip()

R, C, k = (int(x) for x in input().split())
V = [[0] * (C + 5) for _ in range(R + 5)]
for _ in range(k):
    r, c, v = (int(x) for x in input().split())
    V[r][c] = v

# dp[3][i][j]
dp = [[[0] * (C + 5) for _ in range(R + 5)] for _ in range(4)]
for i in range(R + 3):
    for j in range(C + 3):
        for k in range(4):
            # 行移動
            dp[0][i + 1][j] = max(dp[0][i + 1][j], dp[k][i][j])
            dp[1][i + 1][j] = max(dp[1][i + 1][j], dp[k][i][j] + V[i + 1][j])
            # 列移動
            dp[k][i][j + 1] = max(dp[k][i][j + 1], dp[k][i][j])
            if k < 3:
                dp[k + 1][i][j + 1] = max(dp[k + 1][i][j + 1], dp[k][i][j] + V[i][j + 1])
print(max(dp[k][R][C] for k in range(4)))

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

R, C, k = (int(x) for x in input().split())
V = [[0] * (C + 5) for _ in range(R + 5)]
for _ in range(k):
    r, c, v = (int(x) for x in input().split())
    V[r][c] = v

# dp[i][j][3]
dp = [[[0] * 4 for _ in range(C + 5)] for _ in range(R + 5)]
for i in range(1, R + 3):
    for j in range(1, C + 3):
        for k in range(4):
            # 行移動
            dp[i][j][0] = max(dp[i][j][0], max(dp[i-1][j]))
            dp[i][j][1] = max(dp[i][j][1], max(dp[i-1][j])+V[i][j])
            # 列移動
            if k > 0:
                dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k - 1] + V[i][j])
            dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k])
print(max(dp[R][C]))

Fixed submission:
import sys
def input(): return sys.stdin.readline().rstrip()

R, C, k = (int(x) for x in input().split())
V = [[0] * (C + 5) for _ in range(R + 5)]
for _ in range(k):
    r, c, v = (int(x) for x in input().split())
    V[r][c] = v

# dp[3][i][j]
dp = [[[0] * (C + 5) for _ in range(R + 5)] for _ in range(4)]
for i in range(R + 3):
    for j in range(C + 3):
        for k in range(4):
            # 行移動
            dp[0][i + 1][j] = max(dp[0][i + 1][j], dp[k][i][j])
            dp[1][i + 1][j] = max(dp[1][i + 1][j], dp[k][i][j] + V[i + 1][j])
            # 列移動
            dp[k][i][j + 1] = max(dp[k][i][j + 1], dp[k][i][j])
            if k < 3:
                dp[k + 1][i][j + 1] = max(dp[k + 1][i][j + 1], dp[k][i][j] + V[i][j + 1])
print(max(dp[k][R][C] for k in range(4)))

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

R, C, k = (int(x) for x in input().split())
RCV = [tuple(int(x) for x in input().split()) for _ in range(k)]
V = [[0] * (C + 5) for _ in range(R + 5)]
for r, c, v in RCV:
    V[r][c] = v
# dp[i][j][3]
dp = [[[0] * 4 for _ in range(C + 5)] for _ in range(R + 5)]
for i in range(1, R + 3):
    for j in range(1, C + 3):
        for k in range(4):
            # 行移動
            dp[i][j][0] = max(dp[i][j][0], max(dp[i-1][j]))
            dp[i][j][1] = max(dp[i][j][1], max(dp[i-1][j])+V[i][j])
            # 列移動
            if k > 0:
                dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k - 1] + V[i][j])
            dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k])
print(max(dp[R][C]))


Fixed submission:
import sys
def input(): return sys.stdin.readline().rstrip()

R, C, k = (int(x) for x in input().split())
V = [[0] * (C + 5) for _ in range(R + 5)]
for _ in range(k):
    r, c, v = (int(x) for x in input().split())
    V[r][c] = v

# dp[3][i][j]
dp = [[[0] * (C + 5) for _ in range(R + 5)] for _ in range(4)]
for i in range(R + 3):
    for j in range(C + 3):
        for k in range(4):
            # 行移動
            dp[0][i + 1][j] = max(dp[0][i + 1][j], dp[k][i][j])
            dp[1][i + 1][j] = max(dp[1][i + 1][j], dp[k][i][j] + V[i + 1][j])
            # 列移動
            dp[k][i][j + 1] = max(dp[k][i][j + 1], dp[k][i][j])
            if k < 3:
                dp[k + 1][i][j + 1] = max(dp[k + 1][i][j + 1], dp[k][i][j] + V[i][j + 1])
print(max(dp[k][R][C] for k in range(4)))

Buggy python submission (verdict: Time Limit Exceeded):
R, C, k = (int(x) for x in input().split())
RCV = [tuple(int(x) for x in input().split()) for _ in range(k)]
V = [[0] * (C + 5) for _ in range(R + 5)]
for r, c, v in RCV:
    V[r][c] = v
# dp[i][j][3]
dp = [[[0] * 4 for _ in range(C + 5)] for _ in range(R + 5)]
for i in range(1, R + 3):
    for j in range(1, C + 3):
        for k in range(4):
            # 行移動
            dp[i][j][0] = max(dp[i][j][0], max(dp[i-1][j]))
            dp[i][j][1] = max(dp[i][j][1], max(dp[i-1][j])+V[i][j])
            # 列移動
            if k > 0:
                dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k - 1] + V[i][j])
            dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k])
print(max(dp[R][C]))


Fixed submission:
import sys
def input(): return sys.stdin.readline().rstrip()

R, C, k = (int(x) for x in input().split())
V = [[0] * (C + 5) for _ in range(R + 5)]
for _ in range(k):
    r, c, v = (int(x) for x in input().split())
    V[r][c] = v

# dp[3][i][j]
dp = [[[0] * (C + 5) for _ in range(R + 5)] for _ in range(4)]
for i in range(R + 3):
    for j in range(C + 3):
        for k in range(4):
            # 行移動
            dp[0][i + 1][j] = max(dp[0][i + 1][j], dp[k][i][j])
            dp[1][i + 1][j] = max(dp[1][i + 1][j], dp[k][i][j] + V[i + 1][j])
            # 列移動
            dp[k][i][j + 1] = max(dp[k][i][j + 1], dp[k][i][j])
            if k < 3:
                dp[k + 1][i][j + 1] = max(dp[k + 1][i][j + 1], dp[k][i][j] + V[i][j + 1])
print(max(dp[k][R][C] for k in range(4)))