Buggy python submission (verdict: Time Limit Exceeded):
"""
dp[i][j][k] => i行目j列到達時点での最大価値。i行目において拾えるアイテムの数はK個。
"""
def main():
    import sys
    input = sys.stdin.readline
    R,C,K = map(int,input().split())
    items = [[0]*C for _ in range(R)]
    for _ in range(K):
        r,c,v = map(int,input().split())
        items[r-1][c-1] = v

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

    for i in range(R):
        for j in range(C):
            v = items[i][j]

            #上から入るパターン
            dp[i][j][0] = max(dp[i-1][j])
            if v:
                dp[i][j][1] = dp[i][j][0]+v
            
            #左から入ってくるパターン
            if j > 0:
                for k in range(4):
                    #このマスのアイテムをとらないパターン
                    dp[i][j][k] = max(dp[i][j][k],dp[i][j-1][k])
                    if v and k>0:
                        dp[i][j][k] = max(dp[i][j][k],dp[i][j-1][k-1]+v)

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

Fixed submission:
"""
dp[i][j]　=> i行目j列目がゴールの場合の最大値
"""
def main():
    import sys
    input = sys.stdin.readline
    R,C,K = map(int,input().split())
    items = [[0]*(C) for _ in range(R)]

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

    dp = [[0]*4 for _ in range(C)]
    dp[0][1] = items[0][0]
    for i in range(R):
        for j in range(C):
            v = items[i][j]
            if i==0 and j == 0:
                continue

            if i!=0:
                #上から入る場合のシミュレート
                dp[j][0] = max(dp[j])
                if v:
                    dp[j][1] = dp[j][0]+v

            if j!=0:
                #左から入る場合のシミュレート
                dp[j][0] = max(dp[j][0],dp[j-1][0])
                if v:
                    #itemが存在する場合の処理
                    for k in range(1,4):
                        dp[j][k] = max(dp[j][k],dp[j-1][k-1]+v,dp[j-1][k])
                else:
                    for k in range(1,4):
                        dp[j][k] = max(dp[j][k],dp[j-1][k])
    print(max(dp[-1]))
main()

Buggy python submission (verdict: Time Limit Exceeded):
"""
dp[i][j][k] => i行目j列到達時点での最大価値。i行目において拾えるアイテムの数はK個。
"""
R,C,K = map(int,input().split())
items = [[0]*C for _ in range(R)]
for _ in range(K):
    r,c,v = map(int,input().split())
    items[r-1][c-1] = v

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

for i in range(R):
    for j in range(C):
        v = items[i][j]

        #上から入るパターン
        dp[i][j][0] = max(dp[i-1][j])
        if v:
            dp[i][j][1] = dp[i][j][0]+v
        
        #左から入ってくるパターン
        if j > 0:
            for k in range(4):
                #このマスのアイテムをとらないパターン
                dp[i][j][k] = max(dp[i][j][k],dp[i][j-1][k])
                if v and k>0:
                    dp[i][j][k] = max(dp[i][j][k],dp[i][j-1][k-1]+v)

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

Fixed submission:
"""
dp[i][j]　=> i行目j列目がゴールの場合の最大値
"""
def main():
    import sys
    input = sys.stdin.readline
    R,C,K = map(int,input().split())
    items = [[0]*(C) for _ in range(R)]

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

    dp = [[0]*4 for _ in range(C)]
    dp[0][1] = items[0][0]
    for i in range(R):
        for j in range(C):
            v = items[i][j]
            if i==0 and j == 0:
                continue

            if i!=0:
                #上から入る場合のシミュレート
                dp[j][0] = max(dp[j])
                if v:
                    dp[j][1] = dp[j][0]+v

            if j!=0:
                #左から入る場合のシミュレート
                dp[j][0] = max(dp[j][0],dp[j-1][0])
                if v:
                    #itemが存在する場合の処理
                    for k in range(1,4):
                        dp[j][k] = max(dp[j][k],dp[j-1][k-1]+v,dp[j-1][k])
                else:
                    for k in range(1,4):
                        dp[j][k] = max(dp[j][k],dp[j-1][k])
    print(max(dp[-1]))
main()

Buggy python submission (verdict: Time Limit Exceeded):
"""
dp[i][j][k] => i行目、j列のマスまで見る。k個取る時の最高値。
"""
def main():
    import sys
    input = sys.stdin.readline
    R,C,K = map(int,input().split())
    items = [[0]*C for _ in range(R)]
    for _ in range(K):
        r,c,v = map(int,input().split())
        items[r-1][c-1] = v

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

    for i in range(R):
        for j in range(C):
            v = items[i][j]
            if i == 0 and j == 0 and v != 0:
                dp[i][j][1] = v

            #上から降りてくる場合の価値を求める
            if i != 0:
                #i行目j列のアイテムを取らない場合
                dp[i][j][0] = max(dp[i-1][j])
                #i行目j列のアイテムを取る場合
                if v!=0:
                    dp[i][j][1] = max(dp[i-1][j]) + v

            #左から入ってくる場合の価値を求める
            if j != 0:
                if v == 0:
                    for k in range(4):
                        dp[i][j][k] = max(dp[i][j][k],dp[i][j-1][k])
                else:
                    for k in range(1,4):
                        dp[i][j][k] = max(dp[i][j][k],dp[i][j-1][k],dp[i][j-1][k-1]+v)
        if i > 0:
            tmp = dp[i-1]
            dp[i-1] = []
            del(tmp)
    print(max(dp[-1][-1]))
main()

Fixed submission:
"""
dp[i][j]　=> i行目j列目がゴールの場合の最大値
"""
def main():
    import sys
    input = sys.stdin.readline
    R,C,K = map(int,input().split())
    items = [[0]*(C) for _ in range(R)]

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

    dp = [[0]*4 for _ in range(C)]
    dp[0][1] = items[0][0]
    for i in range(R):
        for j in range(C):
            v = items[i][j]
            if i==0 and j == 0:
                continue

            if i!=0:
                #上から入る場合のシミュレート
                dp[j][0] = max(dp[j])
                if v:
                    dp[j][1] = dp[j][0]+v

            if j!=0:
                #左から入る場合のシミュレート
                dp[j][0] = max(dp[j][0],dp[j-1][0])
                if v:
                    #itemが存在する場合の処理
                    for k in range(1,4):
                        dp[j][k] = max(dp[j][k],dp[j-1][k-1]+v,dp[j-1][k])
                else:
                    for k in range(1,4):
                        dp[j][k] = max(dp[j][k],dp[j-1][k])
    print(max(dp[-1]))
main()

Buggy python submission (verdict: Runtime Error):
"""
dp[i][j][k] => i行目、j列のマスまで見る。k個取る時の最高値。
"""
def main():
    import sys
    input = sys.stdin.readline
    R,C,K = map(int,input().split())
    items = [[0]*C for _ in range(R)]
    for _ in range(K):
        r,c,v = map(int,input().split())
        items[r-1][c-1] = v

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

    for i in range(R):
        for j in range(C):
            v = items[i][j]
            if i == 0 and j == 0 and v != 0:
                dp[i][j][1] = v

            #上から降りてくる場合の価値を求める
            if i != 0:
                #i行目j列のアイテムを取らない場合
                dp[i][j][0] = max(dp[i-1][j])
                #i行目j列のアイテムを取る場合
                if v!=0:
                    dp[i][j][1] = max(dp[i-1][j]) + v

            #左から入ってくる場合の価値を求める
            if j != 0:
                if v == 0:
                    for k in range(4):
                        dp[i][j][k] = max(dp[i][j][k],dp[i][j-1][k])
                else:
                    for k in range(1,4):
                        dp[i][j][k] = max(dp[i][j][k],dp[i][j-1][k],dp[i][j-1][k-1]+v)
        if i > 0:
            del(dp[i-1])
    print(max(dp[-1][-1]))
main()

Fixed submission:
"""
dp[i][j]　=> i行目j列目がゴールの場合の最大値
"""
def main():
    import sys
    input = sys.stdin.readline
    R,C,K = map(int,input().split())
    items = [[0]*(C) for _ in range(R)]

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

    dp = [[0]*4 for _ in range(C)]
    dp[0][1] = items[0][0]
    for i in range(R):
        for j in range(C):
            v = items[i][j]
            if i==0 and j == 0:
                continue

            if i!=0:
                #上から入る場合のシミュレート
                dp[j][0] = max(dp[j])
                if v:
                    dp[j][1] = dp[j][0]+v

            if j!=0:
                #左から入る場合のシミュレート
                dp[j][0] = max(dp[j][0],dp[j-1][0])
                if v:
                    #itemが存在する場合の処理
                    for k in range(1,4):
                        dp[j][k] = max(dp[j][k],dp[j-1][k-1]+v,dp[j-1][k])
                else:
                    for k in range(1,4):
                        dp[j][k] = max(dp[j][k],dp[j-1][k])
    print(max(dp[-1]))
main()

Buggy python submission (verdict: Time Limit Exceeded):
"""
dp[i][j][k] => i行目、j列のマスまで見る。k個取る時の最高値。
"""
def main():
    import sys
    input = sys.stdin.readline
    R,C,K = map(int,input().split())
    items = [[0]*C for _ in range(R)]
    for _ in range(K):
        r,c,v = map(int,input().split())
        items[r-1][c-1] = v

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

    for i in range(R):
        for j in range(C):
            v = items[i][j]
            if i == 0 and j == 0 and v != 0:
                dp[i][j][1] = v

            #上から降りてくる場合の価値を求める
            if i != 0:
                #i行目j列のアイテムを取らない場合
                dp[i][j][0] = max(dp[i-1][j])
                #i行目j列のアイテムを取る場合
                if v!=0:
                    dp[i][j][1] = max(dp[i-1][j]) + v

            #左から入ってくる場合の価値を求める
            if j != 0:
                if v == 0:
                    for k in range(4):
                        dp[i][j][k] = max(dp[i][j][k],dp[i][j-1][k])
                else:
                    for k in range(1,4):
                        dp[i][j][k] = max(dp[i][j][k],dp[i][j-1][k],dp[i][j-1][k-1]+v)
        if i > 0:
            dp[i-1] = []
    print(max(dp[-1][-1]))
main()

Fixed submission:
"""
dp[i][j]　=> i行目j列目がゴールの場合の最大値
"""
def main():
    import sys
    input = sys.stdin.readline
    R,C,K = map(int,input().split())
    items = [[0]*(C) for _ in range(R)]

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

    dp = [[0]*4 for _ in range(C)]
    dp[0][1] = items[0][0]
    for i in range(R):
        for j in range(C):
            v = items[i][j]
            if i==0 and j == 0:
                continue

            if i!=0:
                #上から入る場合のシミュレート
                dp[j][0] = max(dp[j])
                if v:
                    dp[j][1] = dp[j][0]+v

            if j!=0:
                #左から入る場合のシミュレート
                dp[j][0] = max(dp[j][0],dp[j-1][0])
                if v:
                    #itemが存在する場合の処理
                    for k in range(1,4):
                        dp[j][k] = max(dp[j][k],dp[j-1][k-1]+v,dp[j-1][k])
                else:
                    for k in range(1,4):
                        dp[j][k] = max(dp[j][k],dp[j-1][k])
    print(max(dp[-1]))
main()

Buggy python submission (verdict: Runtime Error):
"""
dp[i][j][k] => i行目、j列のマスまで見る。k個取る時の最高値。
"""
def main():
    import sys
    input = sys.stdin.readline
    R,C,K = map(int,input().split())
    items = [[0]*C for _ in range(R)]
    for _ in range(K):
        r,c,v = map(int,input().split())
        items[r-1][c-1] = v

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

    for i in range(R):
        for j in range(C):
            v = items[i][j]
            if i == 0 and j == 0 and v != 0:
                dp[i][j][1] = v

            #上から降りてくる場合の価値を求める
            if i != 0:
                #i行目j列のアイテムを取らない場合
                dp[i][j][0] = max(dp[i-1][j])
                #i行目j列のアイテムを取る場合
                if v!=0:
                    dp[i][j][1] = max(dp[i-1][j]) + v

            #左から入ってくる場合の価値を求める
            if j != 0:
                if v == 0:
                    for k in range(4):
                        dp[i][j][k] = max(dp[i][j][k],dp[i][j-1][k])
                else:
                    for k in range(1,4):
                        dp[i][j][k] = max(dp[i][j][k],dp[i][j-1][k],dp[i][j-1][k-1]+v)
        if i > 0:
            dp[i] = []
    print(max(dp[-1][-1]))
main()

Fixed submission:
"""
dp[i][j]　=> i行目j列目がゴールの場合の最大値
"""
def main():
    import sys
    input = sys.stdin.readline
    R,C,K = map(int,input().split())
    items = [[0]*(C) for _ in range(R)]

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

    dp = [[0]*4 for _ in range(C)]
    dp[0][1] = items[0][0]
    for i in range(R):
        for j in range(C):
            v = items[i][j]
            if i==0 and j == 0:
                continue

            if i!=0:
                #上から入る場合のシミュレート
                dp[j][0] = max(dp[j])
                if v:
                    dp[j][1] = dp[j][0]+v

            if j!=0:
                #左から入る場合のシミュレート
                dp[j][0] = max(dp[j][0],dp[j-1][0])
                if v:
                    #itemが存在する場合の処理
                    for k in range(1,4):
                        dp[j][k] = max(dp[j][k],dp[j-1][k-1]+v,dp[j-1][k])
                else:
                    for k in range(1,4):
                        dp[j][k] = max(dp[j][k],dp[j-1][k])
    print(max(dp[-1]))
main()

Buggy python submission (verdict: Time Limit Exceeded):
"""
dp[i][j][k] => i行目、j列のマスまで見る。k個取る時の最高値。
"""
def main():
    import sys
    input = sys.stdin.readline
    R,C,K = map(int,input().split())
    items = [[0]*C for _ in range(R)]
    for _ in range(K):
        r,c,v = map(int,input().split())
        items[r-1][c-1] = v

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

    for i in range(R):
        for j in range(C):
            v = items[i][j]
            if i == 0 and j == 0 and v != 0:
                dp[i][j][1] = v

            #上から降りてくる場合の価値を求める
            if i != 0:
                #i行目j列のアイテムを取らない場合
                dp[i][j][0] = max(dp[i-1][j])
                #i行目j列のアイテムを取る場合
                if v!=0:
                    dp[i][j][1] = max(dp[i-1][j]) + v

            #左から入ってくる場合の価値を求める
            if j != 0:
                if v == 0:
                    for k in range(4):
                        dp[i][j][k] = max(dp[i][j][k],dp[i][j-1][k])
                else:
                    for k in range(1,4):
                        dp[i][j][k] = max(dp[i][j][k],dp[i][j-1][k],dp[i][j-1][k-1]+v)
    print(max(dp[-1][-1]))
main()

Fixed submission:
"""
dp[i][j]　=> i行目j列目がゴールの場合の最大値
"""
def main():
    import sys
    input = sys.stdin.readline
    R,C,K = map(int,input().split())
    items = [[0]*(C) for _ in range(R)]

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

    dp = [[0]*4 for _ in range(C)]
    dp[0][1] = items[0][0]
    for i in range(R):
        for j in range(C):
            v = items[i][j]
            if i==0 and j == 0:
                continue

            if i!=0:
                #上から入る場合のシミュレート
                dp[j][0] = max(dp[j])
                if v:
                    dp[j][1] = dp[j][0]+v

            if j!=0:
                #左から入る場合のシミュレート
                dp[j][0] = max(dp[j][0],dp[j-1][0])
                if v:
                    #itemが存在する場合の処理
                    for k in range(1,4):
                        dp[j][k] = max(dp[j][k],dp[j-1][k-1]+v,dp[j-1][k])
                else:
                    for k in range(1,4):
                        dp[j][k] = max(dp[j][k],dp[j-1][k])
    print(max(dp[-1]))
main()

Buggy python submission (verdict: Time Limit Exceeded):
"""
dp[i][j][k] => i行目、j列のマスまで見る。k個取る時の最高値。
"""
R,C,K = map(int,input().split())
items = [[0]*C for _ in range(R)]
for _ in range(K):
    r,c,v = map(int,input().split())
    items[r-1][c-1] = v

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

for i in range(R):
    for j in range(C):
        v = items[i][j]
        if i == 0 and j == 0 and v != 0:
            dp[i][j][1] = v

        #上から降りてくる場合の価値を求める
        if i != 0:
            #i行目j列のアイテムを取らない場合
            dp[i][j][0] = max(dp[i-1][j])
            #i行目j列のアイテムを取る場合
            if v!=0:
                dp[i][j][1] = max(dp[i-1][j]) + v

        #左から入ってくる場合の価値を求める
        if j != 0:
            if v == 0:
                for k in range(4):
                    dp[i][j][k] = max(dp[i][j][k],dp[i][j-1][k])
            else:
                for k in range(1,4):
                    dp[i][j][k] = max(dp[i][j][k],dp[i][j-1][k],dp[i][j-1][k-1]+v)
print(max(dp[-1][-1]))

Fixed submission:
"""
dp[i][j]　=> i行目j列目がゴールの場合の最大値
"""
def main():
    import sys
    input = sys.stdin.readline
    R,C,K = map(int,input().split())
    items = [[0]*(C) for _ in range(R)]

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

    dp = [[0]*4 for _ in range(C)]
    dp[0][1] = items[0][0]
    for i in range(R):
        for j in range(C):
            v = items[i][j]
            if i==0 and j == 0:
                continue

            if i!=0:
                #上から入る場合のシミュレート
                dp[j][0] = max(dp[j])
                if v:
                    dp[j][1] = dp[j][0]+v

            if j!=0:
                #左から入る場合のシミュレート
                dp[j][0] = max(dp[j][0],dp[j-1][0])
                if v:
                    #itemが存在する場合の処理
                    for k in range(1,4):
                        dp[j][k] = max(dp[j][k],dp[j-1][k-1]+v,dp[j-1][k])
                else:
                    for k in range(1,4):
                        dp[j][k] = max(dp[j][k],dp[j-1][k])
    print(max(dp[-1]))
main()

Buggy python submission (verdict: Time Limit Exceeded):
"""
dp[i][j]　=> i行目j列目がゴールの場合の最大値
"""
def main():
    import sys
    input = sys.stdin.readline
    R,C,K = map(int,input().split())
    items = [[0]*(C) for _ in range(R)]

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

    dp = [[[0]*4 for _ in range(C)] for _ in range(R)]
    dp[0][0][1] = items[0][0]
    for i in range(R):
        for j in range(C):
            v = items[i][j]
            if i==0 and j == 0:
                continue

            if i!=0:
                #上から入る場合のシミュレート
                dp[i][j][0] = max(dp[i][j][0],max(dp[i-1][j]))
                if v:
                    dp[i][j][1] = max(dp[i][j][1],max(dp[i-1][j])+v)

            if j!=0:
                #左から入る場合のシミュレート
                dp[i][j][0] = max(dp[i][j][0],dp[i][j-1][0])
                if v:
                    #itemが存在する場合の処理
                    for k in range(1,4):
                        dp[i][j][k] = max(dp[i][j][k],dp[i][j-1][k-1]+v,dp[i][j-1][k])
                else:
                    for k in range(1,4):
                        dp[i][j][k] = max(dp[i][j][k],dp[i][j-1][k])
    print(max(dp[-1][-1]))
main()

Fixed submission:
"""
dp[i][j]　=> i行目j列目がゴールの場合の最大値
"""
def main():
    import sys
    input = sys.stdin.readline
    R,C,K = map(int,input().split())
    items = [[0]*(C) for _ in range(R)]

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

    dp = [[0]*4 for _ in range(C)]
    dp[0][1] = items[0][0]
    for i in range(R):
        for j in range(C):
            v = items[i][j]
            if i==0 and j == 0:
                continue

            if i!=0:
                #上から入る場合のシミュレート
                dp[j][0] = max(dp[j])
                if v:
                    dp[j][1] = dp[j][0]+v

            if j!=0:
                #左から入る場合のシミュレート
                dp[j][0] = max(dp[j][0],dp[j-1][0])
                if v:
                    #itemが存在する場合の処理
                    for k in range(1,4):
                        dp[j][k] = max(dp[j][k],dp[j-1][k-1]+v,dp[j-1][k])
                else:
                    for k in range(1,4):
                        dp[j][k] = max(dp[j][k],dp[j-1][k])
    print(max(dp[-1]))
main()

Buggy python submission (verdict: Time Limit Exceeded):
"""
dp[i][j]　=> i行目j列目がゴールの場合の最大値
"""

R,C,K = map(int,input().split())
items = [[0]*(C) for _ in range(R)]

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

dp = [[[0]*4 for _ in range(C)] for _ in range(R)]
dp[0][0][1] = items[0][0]
for i in range(R):
    for j in range(C):
        v = items[i][j]
        if i==0 and j == 0:
            continue

        if i!=0:
            #上から入る場合のシミュレート
            dp[i][j][0] = max(dp[i][j][0],max(dp[i-1][j]))
            if v:
                dp[i][j][1] = max(dp[i][j][1],max(dp[i-1][j])+v)

        if j!=0:
            #左から入る場合のシミュレート
            dp[i][j][0] = max(dp[i][j][0],dp[i][j-1][0])
            if v:
                #itemが存在する場合の処理
                for k in range(1,4):
                    dp[i][j][k] = max(dp[i][j][k],dp[i][j-1][k-1]+v,dp[i][j-1][k])
            else:
                for k in range(1,4):
                    dp[i][j][k] = max(dp[i][j][k],dp[i][j-1][k])
print(max(dp[-1][-1]))

Fixed submission:
"""
dp[i][j]　=> i行目j列目がゴールの場合の最大値
"""
def main():
    import sys
    input = sys.stdin.readline
    R,C,K = map(int,input().split())
    items = [[0]*(C) for _ in range(R)]

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

    dp = [[0]*4 for _ in range(C)]
    dp[0][1] = items[0][0]
    for i in range(R):
        for j in range(C):
            v = items[i][j]
            if i==0 and j == 0:
                continue

            if i!=0:
                #上から入る場合のシミュレート
                dp[j][0] = max(dp[j])
                if v:
                    dp[j][1] = dp[j][0]+v

            if j!=0:
                #左から入る場合のシミュレート
                dp[j][0] = max(dp[j][0],dp[j-1][0])
                if v:
                    #itemが存在する場合の処理
                    for k in range(1,4):
                        dp[j][k] = max(dp[j][k],dp[j-1][k-1]+v,dp[j-1][k])
                else:
                    for k in range(1,4):
                        dp[j][k] = max(dp[j][k],dp[j-1][k])
    print(max(dp[-1]))
main()