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

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

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

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

            dp[i][r][c] = max(dp[i][r][c], dp[i][r][c-1])
            if i > 0:
                dp[i][r][c] = max(dp[i][r][c], dp[i-1][r][c-1] + v)

ans = 0
for i in range(4):
    ans = max(ans, dp[i][R][C])

print(ans)


Fixed submission:
R, C, K = map(int, input().split())
rcv = [list(map(int, input().split())) for _ in range(K)]

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

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

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

            dp[i][r][c] = max(dp[i][r][c], dp[i][r][c-1])
            if i > 0:
                dp[i][r][c] = max(dp[i][r][c], dp[i-1][r][c-1] + v)

ans = 0
for i in range(4):
    ans = max(ans, dp[i][R][C])

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from copy import deepcopy
from collections import defaultdict


def main():
    R, C, K = map(int, input().split())
    rcv = [list(map(int, input().split())) for _ in range(K)]

    d = defaultdict(list)
    for r, c, v in rcv:
        d[r].append([c, v])

    for r in d.keys():
        d[r].sort()

    dp = [0] * (C + 1)

    for r, li in sorted(d.items()):
        prev = deepcopy(dp)
        for i, (cs, vs) in enumerate(li):
            mx = 0
            for cg, vg in li[i+1:]:
                val = vs + mx + vg
                dp[cg] = max(dp[cg], prev[cs] + val)
                mx = max(mx, vg)

            dp[cs] = max(dp[cs], prev[cs] + vs)

        for c in range(C):
            dp[c+1] = max(dp[c+1], dp[c])

    ans = dp[C]
    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
R, C, K = map(int, input().split())
rcv = [list(map(int, input().split())) for _ in range(K)]

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

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

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

            dp[i][r][c] = max(dp[i][r][c], dp[i][r][c-1])
            if i > 0:
                dp[i][r][c] = max(dp[i][r][c], dp[i-1][r][c-1] + v)

ans = 0
for i in range(4):
    ans = max(ans, dp[i][R][C])

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from copy import deepcopy
from collections import defaultdict

R, C, K = map(int, input().split())
rcv = [list(map(int, input().split())) for _ in range(K)]
N = (R + 1) * (C + 1)

d = defaultdict(list)
for r, c, v in rcv:
    d[r].append([c, v])

for r in d.keys():
    d[r].sort()

dp = [0] * (C + 1)

for r, li in sorted(d.items()):
    prev = deepcopy(dp)
    for i, (cs, vs) in enumerate(li):
        mx = 0
        for cg, vg in li[i+1:]:
            val = vs + mx + vg
            dp[cg] = max(dp[cg], prev[cs] + val)
            mx = max(mx, vg)

        dp[cs] = max(dp[cs], prev[cs] + vs)

    for c in range(C):
        dp[c+1] = max(dp[c+1], dp[c])

ans = dp[C]
print(ans)


Fixed submission:
R, C, K = map(int, input().split())
rcv = [list(map(int, input().split())) for _ in range(K)]

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

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

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

            dp[i][r][c] = max(dp[i][r][c], dp[i][r][c-1])
            if i > 0:
                dp[i][r][c] = max(dp[i][r][c], dp[i-1][r][c-1] + v)

ans = 0
for i in range(4):
    ans = max(ans, dp[i][R][C])

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from copy import deepcopy
from collections import defaultdict

R, C, K = map(int, input().split())
rcv = [list(map(int, input().split())) for _ in range(K)]
N = (R + 1) * (C + 1)

d = defaultdict(list)
for r, c, v in rcv:
    d[r].append([c, v])

for r in d.keys():
    d[r].sort()

dp = [0] * (C + 1)

for r, li in sorted(d.items()):
    prev = deepcopy(dp)
    for i, (cs, vs) in enumerate(li):
        mx = 0
        for cg, vg in li[i+1:]:
            val = vs + mx + vg
            dp[cg] = max(dp[cg], prev[cs] + val)
            mx = max(mx, vg)

        dp[cs] = max(dp[cs], prev[cs] + vs)

    for c in range(C):
        dp[c+1] = max(dp[c+1], dp[c])

ans = dp[C]
print(ans)


Fixed submission:
R, C, K = map(int, input().split())
rcv = [list(map(int, input().split())) for _ in range(K)]

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

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

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

            dp[i][r][c] = max(dp[i][r][c], dp[i][r][c-1])
            if i > 0:
                dp[i][r][c] = max(dp[i][r][c], dp[i-1][r][c-1] + v)

ans = 0
for i in range(4):
    ans = max(ans, dp[i][R][C])

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from copy import deepcopy

R, C, K = map(int, input().split())
rcv = [list(map(int, input().split())) for _ in range(K)]
N = (R + 1) * (C + 1)

d = [[] for _ in range(R + 1)]
for r, c, v in rcv:
    d[r].append([c, v])

for r in range(R + 1):
    d[r].sort()

dp = [0] * (C + 1)
for r, li in enumerate(d[1:], 1):
    prev = deepcopy(dp)
    for i, (cs, vs) in enumerate(li):
        mx = 0
        for cg, vg in li[i+1:]:
            val = vs + mx + vg
            dp[cg] = max(dp[cg], prev[cs] + val)
            mx = max(mx, vg)

        dp[cs] = max(dp[cs], prev[cs] + vs)

    for c in range(C):
        dp[c+1] = max(dp[c+1], dp[c])

ans = dp[C]
print(ans)


Fixed submission:
R, C, K = map(int, input().split())
rcv = [list(map(int, input().split())) for _ in range(K)]

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

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

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

            dp[i][r][c] = max(dp[i][r][c], dp[i][r][c-1])
            if i > 0:
                dp[i][r][c] = max(dp[i][r][c], dp[i-1][r][c-1] + v)

ans = 0
for i in range(4):
    ans = max(ans, dp[i][R][C])

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from copy import deepcopy


def translate(r, c):
    return r * (C + 1) + c


R, C, K = map(int, input().split())
rcv = [list(map(int, input().split())) for _ in range(K)]
N = (R + 1) * (C + 1)

d = [[] for _ in range(R + 1)]
for r, c, v in rcv:
    d[r].append([c, v])

for r in range(R + 1):
    d[r].sort()

dp = [[0] * (C + 1) for _ in range(R + 1)]
for r, li in enumerate(d[1:], 1):
    dp[r] = deepcopy(dp[r-1])
    for i, (cs, vs) in enumerate(li):
        mx = 0
        for cg, vg in li[i+1:]:
            val = vs + mx + vg
            dp[r][cg] = max(dp[r][cg], dp[r-1][cs] + val)
            mx = max(mx, vg)

        dp[r][cs] = max(dp[r][cs], dp[r-1][cs] + vs)

    for c in range(C):
        dp[r][c+1] = max(dp[r][c+1], dp[r][c])

ans = dp[R][C]
print(ans)


Fixed submission:
R, C, K = map(int, input().split())
rcv = [list(map(int, input().split())) for _ in range(K)]

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

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

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

            dp[i][r][c] = max(dp[i][r][c], dp[i][r][c-1])
            if i > 0:
                dp[i][r][c] = max(dp[i][r][c], dp[i-1][r][c-1] + v)

ans = 0
for i in range(4):
    ans = max(ans, dp[i][R][C])

print(ans)