Problem p02586 (python)

Fixed submission:
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())

R,C,K = MI()
item = [[0]*(C+1) for _ in range(R+1)]
for i in range(K):
    r,c,v = MI()
    item[r][c] = v

dp = [[[0]*(C+1) for j in range(4)] for i in range(R+1)]  # dp[i][j][k] = (i,k)に至るまでに拾ったアイテムの価値の合計の最大値、但しi列目からアイテムをj個拾う

for i in range(1,R+1):
    for j in range(4):
        for k in range(1,C+1):
            if item[i][k] == 0:
                if j == 0:
                    dp[i][j][k] = max(dp[i][j][k-1],dp[i-1][0][k],dp[i-1][1][k],dp[i-1][2][k],dp[i-1][3][k])
                else:
                    dp[i][j][k] = dp[i][j][k-1]
            else:
                if j == 0:
                    dp[i][j][k] = max(dp[i][j][k-1],dp[i-1][0][k],dp[i-1][1][k],dp[i-1][2][k],dp[i-1][3][k])
                elif j == 1:
                    dp[i][j][k] = max(dp[i][j][k-1]-item[i][k],dp[i][j-1][k-1],dp[i-1][0][k],dp[i-1][1][k],dp[i-1][2][k],dp[i-1][3][k]) + item[i][k]
                else:
                    dp[i][j][k] = max(dp[i][j][k-1],dp[i][j-1][k-1] + item[i][k])

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

print(ans)

Buggy submission (verdict: Runtime Error):
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

R,C,K = MI()
item = [[0]*(C+1) for _ in range(R+1)]
for i in range(K):
    r,c,v = MI()
    item[r][c] = v

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

for i in range(1,R+1):
    for j in range(4):
        for k in range(1,C+1):
            if item[i][k] == 0:
                if i < R and k < C:
                    dp[i][j][k+1] = max(dp[i][j][k+1],dp[i][j][k])
                    dp[i+1][0][k] = max(dp[i+1][0][k],dp[i][j][k])
                elif i < R and k == C:
                    dp[i + 1][0][k] = max(dp[i + 1][0][k], dp[i][j][k])
                elif i == R and K < C:
                    dp[i][j][k + 1] = max(dp[i][j][k + 1], dp[i][j][k])
            else:
                if i < R and k < C:
                    dp[i][j][k + 1] = max(dp[i][j][k + 1], dp[i][j][k])
                    dp[i + 1][0][k] = max(dp[i + 1][0][k], dp[i][j][k])
                elif i < R and k == C:
                    dp[i + 1][0][k] = max(dp[i + 1][0][k], dp[i][j][k])
                elif i == R and K < C:
                    dp[i][j][k + 1] = max(dp[i][j][k + 1], dp[i][j][k])
                if j != 3:
                    dp[i][j+1][k] += item[i][k]
                    if i < R and k < C:
                        dp[i][j+1][k + 1] = max(dp[i][j+1][k + 1], dp[i][j+1][k])
                        dp[i + 1][0][k] = max(dp[i + 1][0][k], dp[i][j+1][k])
                    elif i < R and k == C:
                        dp[i + 1][0][k] = max(dp[i + 1][0][k], dp[i][j+1][k])
                    elif i == R and K < C:
                        dp[i][j+1][k + 1] = max(dp[i][j+1][k + 1], dp[i][j+1][k])
ans = 0
for j in range(4):
    ans = max(ans,dp[R][j][C])
    print(dp[R][j][C])

print(ans)