Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
def main():
    R, C, K = map(int, input().split())
    item_map = [[0]*C for _ in range(R)]

    for _ in range(K):
        ir, ic, iv = map(int, input().split())
        item_map[ir-1][ic-1] = iv
    dp = []
    for row in range(R):
        ls = []
        for col in range(C):
            ls.append([0, 0, 0, 0])
        dp.append(ls)

    for row in range(R):
        for col in range(C):
            item = item_map[row][col]
            if row>=1 and col>=1:
                M = max(
                    dp[row-1][col][0],
                    dp[row-1][col][1],
                    dp[row-1][col][2],
                    dp[row-1][col][3],
                    dp[row][col-1][0],
                )
                dp[row][col][0] = M
                
                dp[row][col][1] = dp[row][col-1][1]
                dp[row][col][2] = dp[row][col-1][2]
                dp[row][col][3] = dp[row][col-1][3]
                if item:
                    dp[row][col][1] = max(
                        M + item,
                        dp[row][col-1][1]
                        )
                    dp[row][col][2] = max(
                        dp[row][col-1][1] + item,
                        dp[row][col-1][2]
                        )
                    dp[row][col][3] = max(
                        dp[row][col-1][2] + item,
                        dp[row][col-1][3]
                        )
            elif row == 0 and col == 0:
                if item != 0:
                    dp[row][col][1] = item
                    continue
            elif row == 0:
                dp[row][col][0] = dp[row][col-1][0]
                dp[row][col][1] = dp[row][col-1][1]
                dp[row][col][2] = dp[row][col-1][2]
                dp[row][col][3] = dp[row][col-1][3]
                if item:
                    dp[row][col][1] = max(dp[row][col-1][1], dp[row][col-1][0] + item)
                    dp[row][col][2] = max(dp[row][col-1][2], dp[row][col-1][1] + item)
                    dp[row][col][3] = max(dp[row][col-1][3], dp[row][col-1][2] + item)
                continue
            elif col == 0:
                dp[row][col][0] = max(
                    dp[row-1][col][0], dp[row-1][col][1], dp[row-1][col][2], dp[row-1][col][3])
                
                if item:
                    dp[row][col][1] = dp[row][col][0] + item
                continue
    print(max(dp[R-1][C-1]))
main()


Fixed submission:
R, C,K = map(int, input().split())
dp = [[[0]*(C+1) for k in range(R+1)] for _ in range(4)]
# dp[r][c][j] :=r index c columns already j cnt
dp[0][0][0] = 0
D = [[0 for i in range(C+1)] for j in range(R+1)]
import random
for i in range(K):
    r, c, v = map(int,input().split())
    D[r][c] = v
 
for i in range(R+1):
    for j in range(C+1):
        if D[i][j] > 0:
            v = D[i][j]
            M = max(dp[k][i-1][j] for k in range(4))
            dp[0][i][j] = max(dp[0][i][j-1], M)
            dp[1][i][j] = max(dp[0][i][j-1]+v, dp[1][i][j-1], M+v)
            dp[2][i][j] = max(dp[1][i][j-1]+v, dp[2][i][j-1])
            dp[3][i][j] = max(dp[2][i][j-1]+v, dp[3][i][j-1])
 
        else:
            M = max(dp[k][i-1][j] for k in range(4))
            dp[0][i][j] = max(dp[0][i][j-1], M)
            dp[1][i][j] = dp[1][i][j-1]
            dp[2][i][j] = dp[2][i][j-1]
            dp[3][i][j] = dp[3][i][j-1]
 
ans = 0
for i in range(4):
    ans = max(ans, dp[i][-1][-1])
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
def main():
    R, C, K = map(int, input().split())
    item_map = [[0]*C for _ in range(R)]

    for _ in range(K):
        ir, ic, iv = map(int, input().split())
        item_map[ir-1][ic-1] = iv
    dp = []
    for row in range(R):
        ls = []
        for col in range(C):
            ls.append([0, 0, 0, 0])
        dp.append(ls)

    for row in range(R):
        for col in range(C):
            item = item_map[row][col]
            if row == 0 and col == 0:
                if item != 0:
                    dp[row][col][1] = item
                    continue
            elif row == 0:
                dp[row][col][0] = dp[row][col-1][0]
                dp[row][col][1] = dp[row][col-1][1]
                dp[row][col][2] = dp[row][col-1][2]
                dp[row][col][3] = dp[row][col-1][3]
                if item:
                    dp[row][col][1] = max(dp[row][col-1][1], dp[row][col-1][0] + item)
                    dp[row][col][2] = max(dp[row][col-1][2], dp[row][col-1][1] + item)
                    dp[row][col][3] = max(dp[row][col-1][3], dp[row][col-1][2] + item)
                continue
            elif col == 0:
                dp[row][col][0] = max(
                    dp[row-1][col][0], dp[row-1][col][1], dp[row-1][col][2], dp[row-1][col][3])
                
                if item:
                    dp[row][col][1] = dp[row][col][0] + item
                continue
            else:
                M = max(
                    dp[row-1][col][0],
                    dp[row-1][col][1],
                    dp[row-1][col][2],
                    dp[row-1][col][3],
                    dp[row][col-1][0],
                )
                dp[row][col][0] = M
                
                dp[row][col][1] = dp[row][col-1][1]
                dp[row][col][2] = dp[row][col-1][2]
                dp[row][col][3] = dp[row][col-1][3]
                if item:
                    dp[row][col][1] = max(
                        M + item,
                        dp[row][col-1][1]
                        )
                    dp[row][col][2] = max(
                        dp[row][col-1][1] + item,
                        dp[row][col-1][2]
                        )
                    dp[row][col][3] = max(
                        dp[row][col-1][2] + item,
                        dp[row][col-1][3]
                        )
    print(max(dp[R-1][C-1]))
main()

Fixed submission:
R, C,K = map(int, input().split())
dp = [[[0]*(C+1) for k in range(R+1)] for _ in range(4)]
# dp[r][c][j] :=r index c columns already j cnt
dp[0][0][0] = 0
D = [[0 for i in range(C+1)] for j in range(R+1)]
import random
for i in range(K):
    r, c, v = map(int,input().split())
    D[r][c] = v
 
for i in range(R+1):
    for j in range(C+1):
        if D[i][j] > 0:
            v = D[i][j]
            M = max(dp[k][i-1][j] for k in range(4))
            dp[0][i][j] = max(dp[0][i][j-1], M)
            dp[1][i][j] = max(dp[0][i][j-1]+v, dp[1][i][j-1], M+v)
            dp[2][i][j] = max(dp[1][i][j-1]+v, dp[2][i][j-1])
            dp[3][i][j] = max(dp[2][i][j-1]+v, dp[3][i][j-1])
 
        else:
            M = max(dp[k][i-1][j] for k in range(4))
            dp[0][i][j] = max(dp[0][i][j-1], M)
            dp[1][i][j] = dp[1][i][j-1]
            dp[2][i][j] = dp[2][i][j-1]
            dp[3][i][j] = dp[3][i][j-1]
 
ans = 0
for i in range(4):
    ans = max(ans, dp[i][-1][-1])
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
def main():
    R, C, K = map(int, input().split())
    item_map = [[0]*C for _ in range(R)]

    for _ in range(K):
        ir, ic, iv = map(int, input().split())
        item_map[ir-1][ic-1] = iv
    dp = []
    for row in range(R):
        ls = []
        for col in range(C):
            ls.append([0, 0, 0, 0])
        dp.append(ls)

    for row in range(R):
        for col in range(C):
            item = item_map[row][col]
            if row == 0 and col == 0:
                if item != 0:
                    dp[row][col][1] = item
                    continue
            elif row == 0:
                dp[row][col][0] = dp[row][col-1][0]
                dp[row][col][1] = dp[row][col-1][1]
                dp[row][col][2] = dp[row][col-1][2]
                dp[row][col][3] = dp[row][col-1][3]
                if item:
                    dp[row][col][1] = max(dp[row][col-1][1], dp[row][col-1][0] + item)
                    dp[row][col][2] = max(dp[row][col-1][2], dp[row][col-1][1] + item)
                    dp[row][col][3] = max(dp[row][col-1][3], dp[row][col-1][2] + item)
                continue
            elif col == 0:
                dp[row][col][0] = max(
                    dp[row-1][col][0], dp[row-1][col][1], dp[row-1][col][2], dp[row-1][col][3])
                
                if item:
                    dp[row][col][1] = dp[row][col][0] + item
                continue
            else:
                dp[row][col][0] = max(
                    dp[row][col-1][0],
                    dp[row-1][col][0],
                    dp[row-1][col][1],
                    dp[row-1][col][2],
                    dp[row-1][col][3])
                
                dp[row][col][1] = dp[row][col-1][1]
                dp[row][col][2] = dp[row][col-1][2]
                dp[row][col][3] = dp[row][col-1][3]
                if item:
                    dp[row][col][1] = max(
                        dp[row-1][col][0] + item, 
                        dp[row-1][col][1] + item,
                        dp[row-1][col][2] + item,
                        dp[row-1][col][3] + item,
                        dp[row][col-1][0] + item,
                        dp[row][col-1][1]
                        )
                    dp[row][col][2] = max(
                        dp[row][col-1][1] + item,
                        dp[row][col-1][2]
                        )
                    dp[row][col][3] = max(
                        dp[row][col-1][2] + item,
                        dp[row][col-1][3]
                        )
    print(max(dp[R-1][C-1]))
main()

Fixed submission:
R, C,K = map(int, input().split())
dp = [[[0]*(C+1) for k in range(R+1)] for _ in range(4)]
# dp[r][c][j] :=r index c columns already j cnt
dp[0][0][0] = 0
D = [[0 for i in range(C+1)] for j in range(R+1)]
import random
for i in range(K):
    r, c, v = map(int,input().split())
    D[r][c] = v
 
for i in range(R+1):
    for j in range(C+1):
        if D[i][j] > 0:
            v = D[i][j]
            M = max(dp[k][i-1][j] for k in range(4))
            dp[0][i][j] = max(dp[0][i][j-1], M)
            dp[1][i][j] = max(dp[0][i][j-1]+v, dp[1][i][j-1], M+v)
            dp[2][i][j] = max(dp[1][i][j-1]+v, dp[2][i][j-1])
            dp[3][i][j] = max(dp[2][i][j-1]+v, dp[3][i][j-1])
 
        else:
            M = max(dp[k][i-1][j] for k in range(4))
            dp[0][i][j] = max(dp[0][i][j-1], M)
            dp[1][i][j] = dp[1][i][j-1]
            dp[2][i][j] = dp[2][i][j-1]
            dp[3][i][j] = dp[3][i][j-1]
 
ans = 0
for i in range(4):
    ans = max(ans, dp[i][-1][-1])
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
def main():
    R, C, K = map(int, input().split())
    item_map = [[0]*C for _ in range(R)]

    for _ in range(K):
        ir, ic, iv = map(int, input().split())
        item_map[ir-1][ic-1] = iv
    dp = []
    for row in range(R):
        ls = []
        for col in range(C):
            ls.append([0, 0, 0, 0])
        dp.append(ls)

    for row in range(R):
        for col in range(C):
            item = item_map[row][col]
            if row == 0 and col == 0:
                if item != 0:
                    dp[row][col][1] = item
                    continue
            elif row == 0:
                dp[row][col][0] = dp[row][col-1][0]
                if item == 0:
                    dp[row][col][1] = dp[row][col-1][1]
                    dp[row][col][2] = dp[row][col-1][2]
                    dp[row][col][3] = dp[row][col-1][3]
                else:
                    dp[row][col][1] = max(dp[row][col-1][1], dp[row][col-1][0] + item)
                    dp[row][col][2] = max(dp[row][col-1][2], dp[row][col-1][1] + item)
                    dp[row][col][3] = max(dp[row][col-1][3], dp[row][col-1][2] + item)
                continue
            elif col == 0:
                dp[row][col][0] = max(
                    dp[row-1][col][0], dp[row-1][col][1], dp[row-1][col][2], dp[row-1][col][3])
                
                if item != 0:
                    dp[row][col][1] = dp[row][col][0] + item
                continue
            else:
                dp[row][col][0] = max(
                    dp[row][col-1][0],
                    dp[row-1][col][0],
                    dp[row-1][col][1],
                    dp[row-1][col][2],
                    dp[row-1][col][3])
                if item == 0:
                    dp[row][col][1] = dp[row][col-1][1]
                    dp[row][col][2] = dp[row][col-1][2]
                    dp[row][col][3] = dp[row][col-1][3]
                else:
                    dp[row][col][1] = max(
                        dp[row-1][col][0] + item, 
                        dp[row-1][col][1] + item,
                        dp[row-1][col][2] + item,
                        dp[row-1][col][3] + item,
                        dp[row][col-1][0] + item,
                        dp[row][col-1][1]
                        )
                    dp[row][col][2] = max(
                        dp[row][col-1][1] + item,
                        dp[row][col-1][2]
                        )
                    dp[row][col][3] = max(
                        dp[row][col-1][2] + item,
                        dp[row][col-1][3]
                        )
    print(max(dp[R-1][C-1]))
main()

Fixed submission:
R, C,K = map(int, input().split())
dp = [[[0]*(C+1) for k in range(R+1)] for _ in range(4)]
# dp[r][c][j] :=r index c columns already j cnt
dp[0][0][0] = 0
D = [[0 for i in range(C+1)] for j in range(R+1)]
import random
for i in range(K):
    r, c, v = map(int,input().split())
    D[r][c] = v
 
for i in range(R+1):
    for j in range(C+1):
        if D[i][j] > 0:
            v = D[i][j]
            M = max(dp[k][i-1][j] for k in range(4))
            dp[0][i][j] = max(dp[0][i][j-1], M)
            dp[1][i][j] = max(dp[0][i][j-1]+v, dp[1][i][j-1], M+v)
            dp[2][i][j] = max(dp[1][i][j-1]+v, dp[2][i][j-1])
            dp[3][i][j] = max(dp[2][i][j-1]+v, dp[3][i][j-1])
 
        else:
            M = max(dp[k][i-1][j] for k in range(4))
            dp[0][i][j] = max(dp[0][i][j-1], M)
            dp[1][i][j] = dp[1][i][j-1]
            dp[2][i][j] = dp[2][i][j-1]
            dp[3][i][j] = dp[3][i][j-1]
 
ans = 0
for i in range(4):
    ans = max(ans, dp[i][-1][-1])
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
def main():
    R, C, K = map(int, input().split())
    item_map = [[0]*C for _ in range(R)]

    for _ in range(K):
        ir, ic, iv = map(int, input().split())
        item_map[ir-1][ic-1] = iv

    dp = []
    for row in range(R):
        ls = []
        for col in range(C):
            ls.append([0, 0, 0, 0])
        dp.append(ls)

    for row in range(R):
        for col in range(C):
            if row == 0 and col == 0:
                if item_map[row][col] != 0:
                    dp[row][col][1] = item_map[row][col]
                    continue
            elif row == 0:
                dp[row][col][0] = dp[row][col-1][0]
                if item_map[row][col] == 0:
                    dp[row][col][1] = dp[row][col-1][1]
                    dp[row][col][2] = dp[row][col-1][2]
                    dp[row][col][3] = dp[row][col-1][3]
                else:
                    dp[row][col][1] = max(dp[row][col-1][1], dp[row][col-1][0] + item_map[row][col])
                    dp[row][col][2] = max(dp[row][col-1][2], dp[row][col-1][1] + item_map[row][col])
                    dp[row][col][3] = max(dp[row][col-1][3], dp[row][col-1][2] + item_map[row][col])
                continue
            elif col == 0:
                dp[row][col][0] = max(
                    dp[row-1][col][0], dp[row-1][col][1], dp[row-1][col][2], dp[row-1][col][3])
                
                if item_map[row][col] != 0:
                    dp[row][col][1] = dp[row][col][0] + item_map[row][col]
                continue
            else:
                dp[row][col][0] = max(
                    dp[row][col-1][0],
                    dp[row-1][col][0],
                    dp[row-1][col][1],
                    dp[row-1][col][2],
                    dp[row-1][col][3])
                if item_map[row][col] == 0:
                    dp[row][col][1] = dp[row][col-1][1]
                    dp[row][col][2] = dp[row][col-1][2]
                    dp[row][col][3] = dp[row][col-1][3]
                else:
                    dp[row][col][1] = max(
                        dp[row-1][col][0] + item_map[row][col], 
                        dp[row-1][col][1] + item_map[row][col],
                        dp[row-1][col][2] + item_map[row][col],
                        dp[row-1][col][3] + item_map[row][col],
                        dp[row][col-1][0] + item_map[row][col],
                        dp[row][col-1][1]
                        )
                    dp[row][col][2] = max(
                        dp[row][col-1][1] + item_map[row][col],
                        dp[row][col-1][2]
                        )
                    dp[row][col][3] = max(
                        dp[row][col-1][2] + item_map[row][col],
                        dp[row][col-1][3]
                        )
    print(max(dp[R-1][C-1]))
main()

Fixed submission:
R, C,K = map(int, input().split())
dp = [[[0]*(C+1) for k in range(R+1)] for _ in range(4)]
# dp[r][c][j] :=r index c columns already j cnt
dp[0][0][0] = 0
D = [[0 for i in range(C+1)] for j in range(R+1)]
import random
for i in range(K):
    r, c, v = map(int,input().split())
    D[r][c] = v
 
for i in range(R+1):
    for j in range(C+1):
        if D[i][j] > 0:
            v = D[i][j]
            M = max(dp[k][i-1][j] for k in range(4))
            dp[0][i][j] = max(dp[0][i][j-1], M)
            dp[1][i][j] = max(dp[0][i][j-1]+v, dp[1][i][j-1], M+v)
            dp[2][i][j] = max(dp[1][i][j-1]+v, dp[2][i][j-1])
            dp[3][i][j] = max(dp[2][i][j-1]+v, dp[3][i][j-1])
 
        else:
            M = max(dp[k][i-1][j] for k in range(4))
            dp[0][i][j] = max(dp[0][i][j-1], M)
            dp[1][i][j] = dp[1][i][j-1]
            dp[2][i][j] = dp[2][i][j-1]
            dp[3][i][j] = dp[3][i][j-1]
 
ans = 0
for i in range(4):
    ans = max(ans, dp[i][-1][-1])
print(ans)

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

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

    # row2item = {r: [0]*C for r in range(R)}
    #  # r -> index, col, val
    item_map = [[0]*C for _ in range(R)]

    for i in range(K):
        ir, ic, iv = map(int, input().split())
        item_map[ir-1][ic-1] = iv

    dp = []
    for row in range(R):
        ls = []
        for col in range(C):
            ls.append([0, 0, 0, 0])
        dp.append(ls)

    for row in range(R):
        for col in range(C):
            if row == 0 and col == 0:
                if item_map[row][col] != 0:
                    dp[row][col][1] = item_map[row][col]
            elif row == 0:
                dp[row][col][0] = dp[row][col-1][0]
                if item_map[row][col] == 0:
                    dp[row][col][1] = dp[row][col-1][1]
                    dp[row][col][2] = dp[row][col-1][2]
                    dp[row][col][3] = dp[row][col-1][3]
                else:
                    dp[row][col][1] = max(dp[row][col-1][1], dp[row][col-1][0] + item_map[row][col])
                    dp[row][col][2] = max(dp[row][col-1][2], dp[row][col-1][1] + item_map[row][col])
                    dp[row][col][3] = max(dp[row][col-1][3], dp[row][col-1][2] + item_map[row][col])
            elif col == 0:
                dp[row][col][0] = max(
                    dp[row-1][col][0], dp[row-1][col][1], dp[row-1][col][2], dp[row-1][col][3])
                
                if item_map[row][col] != 0:
                    dp[row][col][1] = dp[row][col][0] + item_map[row][col]
            else:
                dp[row][col][0] = max(
                    dp[row][col-1][0],
                    dp[row-1][col][0],
                    dp[row-1][col][1],
                    dp[row-1][col][2],
                    dp[row-1][col][3])
                if item_map[row][col] == 0:
                    dp[row][col][1] = dp[row][col-1][1]
                    dp[row][col][2] = dp[row][col-1][2]
                    dp[row][col][3] = dp[row][col-1][3]
                else:
                    dp[row][col][1] = max(
                        dp[row-1][col][0] + item_map[row][col], 
                        dp[row-1][col][1] + item_map[row][col],
                        dp[row-1][col][2] + item_map[row][col],
                        dp[row-1][col][3] + item_map[row][col],
                        dp[row][col-1][0] + item_map[row][col],
                        dp[row][col-1][1]
                        )
                    dp[row][col][2] = max(
                        dp[row][col-1][1] + item_map[row][col],
                        dp[row][col-1][2]
                        )
                    dp[row][col][3] = max(
                        dp[row][col-1][2] + item_map[row][col],
                        dp[row][col-1][3]
                        )
    print(max(dp[R-1][C-1]))
main()

Fixed submission:
R, C,K = map(int, input().split())
dp = [[[0]*(C+1) for k in range(R+1)] for _ in range(4)]
# dp[r][c][j] :=r index c columns already j cnt
dp[0][0][0] = 0
D = [[0 for i in range(C+1)] for j in range(R+1)]
import random
for i in range(K):
    r, c, v = map(int,input().split())
    D[r][c] = v
 
for i in range(R+1):
    for j in range(C+1):
        if D[i][j] > 0:
            v = D[i][j]
            M = max(dp[k][i-1][j] for k in range(4))
            dp[0][i][j] = max(dp[0][i][j-1], M)
            dp[1][i][j] = max(dp[0][i][j-1]+v, dp[1][i][j-1], M+v)
            dp[2][i][j] = max(dp[1][i][j-1]+v, dp[2][i][j-1])
            dp[3][i][j] = max(dp[2][i][j-1]+v, dp[3][i][j-1])
 
        else:
            M = max(dp[k][i-1][j] for k in range(4))
            dp[0][i][j] = max(dp[0][i][j-1], M)
            dp[1][i][j] = dp[1][i][j-1]
            dp[2][i][j] = dp[2][i][j-1]
            dp[3][i][j] = dp[3][i][j-1]
 
ans = 0
for i in range(4):
    ans = max(ans, dp[i][-1][-1])
print(ans)

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

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

    # row2item = {r: [0]*C for r in range(R)}
    #  # r -> index, col, val
    item_map = [[0]*C for _ in range(R)]

    for i in range(K):
        ir, ic, iv = map(int, input().split())
        item_map[ir-1][ic-1] = iv

    dp = []
    for row in range(R):
        ls = []
        for col in range(C):
            ls.append([0, 0, 0, 0])
        dp.append(ls)

    for row in range(R):
        for col in range(C):
            if row == 0 and col == 0:
                if item_map[row][col] != 0:
                    dp[row][col][1] = item_map[row][col]
            elif row == 0:
                dp[row][col][0] = dp[row][col-1][0]
                if item_map[row][col] == 0:
                    dp[row][col][1] = dp[row][col-1][1]
                    dp[row][col][2] = dp[row][col-1][2]
                    dp[row][col][3] = dp[row][col-1][3]
                else:
                    dp[row][col][1] = max(dp[row][col-1][1], dp[row][col-1][0] + item_map[row][col])
                    dp[row][col][2] = max(dp[row][col-1][2], dp[row][col-1][1] + item_map[row][col])
                    dp[row][col][3] = max(dp[row][col-1][3], dp[row][col-1][2] + item_map[row][col])
            elif col == 0:
                dp[row][col][0] = max(
                    dp[row-1][col][0], dp[row-1][col][1], dp[row-1][col][2], dp[row-1][col][3])
                
                if item_map[row][col] != 0:
                    dp[row][col][1] = dp[row][col][0] + item_map[row][col]
            else:
                dp[row][col][0] = max(
                    dp[row][col-1][0],
                    dp[row-1][col][0],
                    dp[row-1][col][1],
                    dp[row-1][col][2],
                    dp[row-1][col][3])
                if item_map[row][col] == 0:
                    dp[row][col][1] = dp[row][col-1][1]
                    dp[row][col][2] = dp[row][col-1][2]
                    dp[row][col][3] = dp[row][col-1][3]
                else:
                    dp[row][col][1] = max(
                        dp[row-1][col][0] + item_map[row][col], 
                        dp[row-1][col][1] + item_map[row][col],
                        dp[row-1][col][2] + item_map[row][col],
                        dp[row-1][col][3] + item_map[row][col],
                        dp[row][col-1][0] + item_map[row][col],
                        dp[row][col-1][1]
                        )
                    dp[row][col][2] = max(
                        dp[row][col-1][1] + item_map[row][col],
                        dp[row][col-1][2]
                        )
                    dp[row][col][3] = max(
                        dp[row][col-1][2] + item_map[row][col],
                        dp[row][col-1][3]
                        )
    print(max(dp[R-1][C-1]))
main()

Fixed submission:
R, C,K = map(int, input().split())
dp = [[[0]*(C+1) for k in range(R+1)] for _ in range(4)]
# dp[r][c][j] :=r index c columns already j cnt
dp[0][0][0] = 0
D = [[0 for i in range(C+1)] for j in range(R+1)]
import random
for i in range(K):
    r, c, v = map(int,input().split())
    D[r][c] = v
 
for i in range(R+1):
    for j in range(C+1):
        if D[i][j] > 0:
            v = D[i][j]
            M = max(dp[k][i-1][j] for k in range(4))
            dp[0][i][j] = max(dp[0][i][j-1], M)
            dp[1][i][j] = max(dp[0][i][j-1]+v, dp[1][i][j-1], M+v)
            dp[2][i][j] = max(dp[1][i][j-1]+v, dp[2][i][j-1])
            dp[3][i][j] = max(dp[2][i][j-1]+v, dp[3][i][j-1])
 
        else:
            M = max(dp[k][i-1][j] for k in range(4))
            dp[0][i][j] = max(dp[0][i][j-1], M)
            dp[1][i][j] = dp[1][i][j-1]
            dp[2][i][j] = dp[2][i][j-1]
            dp[3][i][j] = dp[3][i][j-1]
 
ans = 0
for i in range(4):
    ans = max(ans, dp[i][-1][-1])
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
R, C, K = map(int, input().split())

# row2item = {r: [0]*C for r in range(R)}
#  # r -> index, col, val
item_map = [[0]*C for _ in range(R)]

for i in range(K):
    ir, ic, iv = map(int, input().split())
    item_map[ir-1][ic-1] = iv

dp = []
for row in range(R):
    ls = []
    for col in range(C):
        ls.append([0, 0, 0, 0])
    dp.append(ls)

for row in range(R):
    for col in range(C):
        if row == 0 and col == 0:
            if item_map[row][col] != 0:
                dp[row][col][1] = item_map[row][col]
        elif row == 0:
            dp[row][col][0] = dp[row][col-1][0]
            if item_map[row][col] == 0:
                dp[row][col][1] = dp[row][col-1][1]
                dp[row][col][2] = dp[row][col-1][2]
                dp[row][col][3] = dp[row][col-1][3]
            else:
                dp[row][col][1] = max(dp[row][col-1][1], dp[row][col-1][0] + item_map[row][col])
                dp[row][col][2] = max(dp[row][col-1][2], dp[row][col-1][1] + item_map[row][col])
                dp[row][col][3] = max(dp[row][col-1][3], dp[row][col-1][2] + item_map[row][col])
        elif col == 0:
            dp[row][col][0] = max(
                dp[row-1][col][0], dp[row-1][col][1], dp[row-1][col][2], dp[row-1][col][3])
            
            if item_map[row][col] != 0:
                dp[row][col][1] = dp[row][col][0] + item_map[row][col]
        else:
            dp[row][col][0] = max(
                dp[row][col-1][0],
                dp[row-1][col][0],
                dp[row-1][col][1],
                dp[row-1][col][2],
                dp[row-1][col][3])
            if item_map[row][col] == 0:
                dp[row][col][1] = dp[row][col-1][1]
                dp[row][col][2] = dp[row][col-1][2]
                dp[row][col][3] = dp[row][col-1][3]
            else:
                dp[row][col][1] = max(
                    dp[row-1][col][0] + item_map[row][col], 
                    dp[row-1][col][1] + item_map[row][col],
                    dp[row-1][col][2] + item_map[row][col],
                    dp[row-1][col][3] + item_map[row][col],
                    dp[row][col-1][0] + item_map[row][col],
                    dp[row][col-1][1]
                    )
                dp[row][col][2] = max(
                    dp[row][col-1][1] + item_map[row][col],
                    dp[row][col-1][2]
                    )
                dp[row][col][3] = max(
                    dp[row][col-1][2] + item_map[row][col],
                    dp[row][col-1][3]
                    )
print(max(dp[R-1][C-1]))

Fixed submission:
R, C,K = map(int, input().split())
dp = [[[0]*(C+1) for k in range(R+1)] for _ in range(4)]
# dp[r][c][j] :=r index c columns already j cnt
dp[0][0][0] = 0
D = [[0 for i in range(C+1)] for j in range(R+1)]
import random
for i in range(K):
    r, c, v = map(int,input().split())
    D[r][c] = v
 
for i in range(R+1):
    for j in range(C+1):
        if D[i][j] > 0:
            v = D[i][j]
            M = max(dp[k][i-1][j] for k in range(4))
            dp[0][i][j] = max(dp[0][i][j-1], M)
            dp[1][i][j] = max(dp[0][i][j-1]+v, dp[1][i][j-1], M+v)
            dp[2][i][j] = max(dp[1][i][j-1]+v, dp[2][i][j-1])
            dp[3][i][j] = max(dp[2][i][j-1]+v, dp[3][i][j-1])
 
        else:
            M = max(dp[k][i-1][j] for k in range(4))
            dp[0][i][j] = max(dp[0][i][j-1], M)
            dp[1][i][j] = dp[1][i][j-1]
            dp[2][i][j] = dp[2][i][j-1]
            dp[3][i][j] = dp[3][i][j-1]
 
ans = 0
for i in range(4):
    ans = max(ans, dp[i][-1][-1])
print(ans)

Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
P = [P[i] - 1 for i in range(N)]

loop_list = [] # ([indexes])
loop_score_list = []
loop_index_list = [0]*N
is_included_loop = [0] * N
num_loop = 0

for start in range(N):
    if is_included_loop[start]:
        continue
    now = start
    count = 1
    visited = [-1]*N # count
    visited[now] = 0
    while True:
        now = P[now]
        if visited[now] != -1:
            terminate_count = count
            start_count = visited[now]
            loop_start_idx = now
            break
        visited[now] = count
        count += 1
    
    num_loop += 1
    now = loop_start_idx
    loop_indexes = [now]
    visited = [-1]*N
    visited[now] = 0
    count = 1
    loop_score = 0
    while True:
        now = P[now]
        if visited[now] != -1:
            break
        loop_indexes.append(now)
        visited[now] = count
        loop_index_list[now] = num_loop
        loop_score += C[now]
        is_included_loop[now] = 1
    loop_list.append(loop_indexes)
    loop_score_list.append(loop_score)


scores = []
for start in range(N):
    tmp_score = 0
    rest = K
    now = start
    while not is_included_loop[now] and rest > 0:
        now = P[now]
        rest -= 1
        tmp_score += C[now]
        scores.append(tmp_score)
    
    if rest <= 0:
        scores.append(tmp_score)
        continue
    # loop
    number_of_loop = loop_index_list[now] - 1
    one_cicle_score = loop_score_list[number_of_loop]
    if one_cicle_score < 0:
        continue
    if rest <= len(loop_list[number_of_loop]):
        while rest >= 0:
            now = P[now]
            rest -= 1
            tmp_score += C[now]
            scores.append(tmp_score)
        continue
    else:
        n_l = rest // len(loop_list[number_of_loop])
        tmp_score += n_l * one_cicle_score
        scores.append(tmp_score)
print(max(scores))
        
    

Fixed submission:
R, C,K = map(int, input().split())
dp = [[[0]*(C+1) for k in range(R+1)] for _ in range(4)]
# dp[r][c][j] :=r index c columns already j cnt
dp[0][0][0] = 0
D = [[0 for i in range(C+1)] for j in range(R+1)]
import random
for i in range(K):
    r, c, v = map(int,input().split())
    D[r][c] = v
 
for i in range(R+1):
    for j in range(C+1):
        if D[i][j] > 0:
            v = D[i][j]
            M = max(dp[k][i-1][j] for k in range(4))
            dp[0][i][j] = max(dp[0][i][j-1], M)
            dp[1][i][j] = max(dp[0][i][j-1]+v, dp[1][i][j-1], M+v)
            dp[2][i][j] = max(dp[1][i][j-1]+v, dp[2][i][j-1])
            dp[3][i][j] = max(dp[2][i][j-1]+v, dp[3][i][j-1])
 
        else:
            M = max(dp[k][i-1][j] for k in range(4))
            dp[0][i][j] = max(dp[0][i][j-1], M)
            dp[1][i][j] = dp[1][i][j-1]
            dp[2][i][j] = dp[2][i][j-1]
            dp[3][i][j] = dp[3][i][j-1]
 
ans = 0
for i in range(4):
    ans = max(ans, dp[i][-1][-1])
print(ans)