Buggy python submission (verdict: Time Limit Exceeded):
import sys
input=lambda: sys.stdin.readline().rstrip()
r,c,k=map(int,input().split())
D=[[0]*c for _ in range(r)] 
for _ in range(k):
	ri,ci,v=map(int,input().split())
	ri-=1
	ci-=1
	D[ri][ci]=v


DP=[[[0]*4 for _ in range(c+1)] for i in range(r+1)]
for i in range(r):
	for j in range(c):
		v=D[i][j]
		if v!=0:
			DP[i][j][1]=max(DP[i-1][j])+v
		for ii in range(4):
			DP[i][j][0]=max(DP[i][j][0],DP[i-1][j][ii])
			if v!=0:
				DP[i][j][1]=max(DP[i][j][1],DP[i-1][j][ii]+v)
			DP[i][j][ii]=max(DP[i][j][ii],DP[i][j-1][ii])
			if v!=0 and ii!=0:
				DP[i][j][ii]=max(DP[i][j][ii],DP[i][j-1][ii-1]+v)
		
ans=max(DP[r-1][c-1])
print(ans)


Fixed submission:
import sys
input=lambda: sys.stdin.readline().rstrip()

r,c,k=map(int,input().split())
D=[[0]*c for _ in range(r)] 
for _ in range(k):
	ri,ci,v=map(int,input().split())
	ri-=1
	ci-=1
	D[ri][ci]=v

DP0=[[0]*(c+1) for i in range(r+1)]
DP1=[[0]*(c+1) for i in range(r+1)]
DP2=[[0]*(c+1) for i in range(r+1)]
DP3=[[0]*(c+1) for i in range(r+1)]
for i in range(r):
	for j in range(c):
		v=D[i][j]
		if v!=0:
			DP1[i][j]=max(DP0[i-1][j],DP1[i-1][j],DP2[i-1][j],DP3[i-1][j])+v

		DP0[i][j]=max(DP0[i][j],DP0[i-1][j],DP1[i-1][j],DP2[i-1][j],DP3[i-1][j])
		if v!=0:
			DP1[i][j]=max(DP1[i][j],DP0[i-1][j]+v,DP1[i-1][j]+v,DP2[i-1][j]+v,DP3[i-1][j]+v)
		DP0[i][j]=max(DP0[i][j],DP0[i][j-1])
		DP1[i][j]=max(DP1[i][j],DP1[i][j-1])
		DP2[i][j]=max(DP2[i][j],DP2[i][j-1])
		DP3[i][j]=max(DP3[i][j],DP3[i][j-1])
		if v!=0:
			DP1[i][j]=max(DP1[i][j],DP0[i][j-1]+v)
			DP2[i][j]=max(DP2[i][j],DP1[i][j-1]+v)
			DP3[i][j]=max(DP3[i][j],DP2[i][j-1]+v)
		
ans=max(DP0[r-1][c-1],DP1[r-1][c-1],DP2[r-1][c-1],DP3[r-1][c-1])
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input=lambda: sys.stdin.readline().rstrip()
import collections
D=collections.defaultdict(int)
r,c,k=map(int,input().split())
for _ in range(k):
	ri,ci,v=map(int,input().split())
	ri-=1
	ci-=1
	D[ri*10**5+ci]=v

DP0=[[0]*(c+1) for i in range(r+1)]
DP1=[[0]*(c+1) for i in range(r+1)]
DP2=[[0]*(c+1) for i in range(r+1)]
DP3=[[0]*(c+1) for i in range(r+1)]
for i in range(r+1):
	for j in range(c+1):
		v=D[i*10**5+j]
		if v!=0:
			DP1[i][j]=max(DP0[i-1][j],DP1[i-1][j],DP2[i-1][j],DP3[i-1][j])+v

		DP0[i][j]=max(DP0[i][j],DP0[i-1][j],DP1[i-1][j],DP2[i-1][j],DP3[i-1][j])
		if v!=0:
			DP1[i][j]=max(DP1[i][j],DP0[i-1][j]+v,DP1[i-1][j]+v,DP2[i-1][j]+v,DP3[i-1][j]+v)
		DP0[i][j]=max(DP0[i][j],DP0[i][j-1])
		DP1[i][j]=max(DP1[i][j],DP1[i][j-1])
		DP2[i][j]=max(DP2[i][j],DP2[i][j-1])
		DP3[i][j]=max(DP3[i][j],DP3[i][j-1])
		if v!=0:
			DP1[i][j]=max(DP1[i][j],DP0[i][j-1]+v)
			DP2[i][j]=max(DP2[i][j],DP1[i][j-1]+v)
			DP3[i][j]=max(DP3[i][j],DP2[i][j-1]+v)
		
ans=max(DP0[r-1][c-1],DP1[r-1][c-1],DP2[r-1][c-1],DP3[r-1][c-1])
print(ans)



Fixed submission:
import sys
input=lambda: sys.stdin.readline().rstrip()

r,c,k=map(int,input().split())
D=[[0]*c for _ in range(r)] 
for _ in range(k):
	ri,ci,v=map(int,input().split())
	ri-=1
	ci-=1
	D[ri][ci]=v

DP0=[[0]*(c+1) for i in range(r+1)]
DP1=[[0]*(c+1) for i in range(r+1)]
DP2=[[0]*(c+1) for i in range(r+1)]
DP3=[[0]*(c+1) for i in range(r+1)]
for i in range(r):
	for j in range(c):
		v=D[i][j]
		if v!=0:
			DP1[i][j]=max(DP0[i-1][j],DP1[i-1][j],DP2[i-1][j],DP3[i-1][j])+v

		DP0[i][j]=max(DP0[i][j],DP0[i-1][j],DP1[i-1][j],DP2[i-1][j],DP3[i-1][j])
		if v!=0:
			DP1[i][j]=max(DP1[i][j],DP0[i-1][j]+v,DP1[i-1][j]+v,DP2[i-1][j]+v,DP3[i-1][j]+v)
		DP0[i][j]=max(DP0[i][j],DP0[i][j-1])
		DP1[i][j]=max(DP1[i][j],DP1[i][j-1])
		DP2[i][j]=max(DP2[i][j],DP2[i][j-1])
		DP3[i][j]=max(DP3[i][j],DP3[i][j-1])
		if v!=0:
			DP1[i][j]=max(DP1[i][j],DP0[i][j-1]+v)
			DP2[i][j]=max(DP2[i][j],DP1[i][j-1]+v)
			DP3[i][j]=max(DP3[i][j],DP2[i][j-1]+v)
		
ans=max(DP0[r-1][c-1],DP1[r-1][c-1],DP2[r-1][c-1],DP3[r-1][c-1])
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input=lambda: sys.stdin.readline().rstrip()
import collections
D=collections.defaultdict(int)
r,c,k=map(int,input().split())
for _ in range(k):
	ri,ci,v=map(int,input().split())
	ri-=1
	ci-=1
	D[ri*10**5+ci]=v

DP=[[[0]*4 for _ in range(c+1)] for i in range(r+1)]
for i in range(r+1):
	for j in range(c+1):
		v=D[i*10**5+j]
		if v!=0:
			DP[i][j][1]=max(DP[i-1][j])+v
		for ii in range(4):
			DP[i][j][0]=max(DP[i][j][0],DP[i-1][j][ii])
			if v!=0:
				DP[i][j][1]=max(DP[i][j][1],DP[i-1][j][ii]+v)
			DP[i][j][ii]=max(DP[i][j][ii],DP[i][j-1][ii])
			if v!=0 and ii!=0:
				DP[i][j][ii]=max(DP[i][j][ii],DP[i][j-1][ii-1]+v)
		
ans=max(DP[r-1][c-1])
print(ans)



Fixed submission:
import sys
input=lambda: sys.stdin.readline().rstrip()

r,c,k=map(int,input().split())
D=[[0]*c for _ in range(r)] 
for _ in range(k):
	ri,ci,v=map(int,input().split())
	ri-=1
	ci-=1
	D[ri][ci]=v

DP0=[[0]*(c+1) for i in range(r+1)]
DP1=[[0]*(c+1) for i in range(r+1)]
DP2=[[0]*(c+1) for i in range(r+1)]
DP3=[[0]*(c+1) for i in range(r+1)]
for i in range(r):
	for j in range(c):
		v=D[i][j]
		if v!=0:
			DP1[i][j]=max(DP0[i-1][j],DP1[i-1][j],DP2[i-1][j],DP3[i-1][j])+v

		DP0[i][j]=max(DP0[i][j],DP0[i-1][j],DP1[i-1][j],DP2[i-1][j],DP3[i-1][j])
		if v!=0:
			DP1[i][j]=max(DP1[i][j],DP0[i-1][j]+v,DP1[i-1][j]+v,DP2[i-1][j]+v,DP3[i-1][j]+v)
		DP0[i][j]=max(DP0[i][j],DP0[i][j-1])
		DP1[i][j]=max(DP1[i][j],DP1[i][j-1])
		DP2[i][j]=max(DP2[i][j],DP2[i][j-1])
		DP3[i][j]=max(DP3[i][j],DP3[i][j-1])
		if v!=0:
			DP1[i][j]=max(DP1[i][j],DP0[i][j-1]+v)
			DP2[i][j]=max(DP2[i][j],DP1[i][j-1]+v)
			DP3[i][j]=max(DP3[i][j],DP2[i][j-1]+v)
		
ans=max(DP0[r-1][c-1],DP1[r-1][c-1],DP2[r-1][c-1],DP3[r-1][c-1])
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input=lambda: sys.stdin.readline().rstrip()
import collections
D=collections.defaultdict(int)
r,c,k=map(int,input().split())
for _ in range(k):
	ri,ci,v=map(int,input().split())
	ri-=1
	ci-=1
	D[ri*10**5+ci]=v

DP=[[[0]*4 for _ in range(c+1)] for i in range(r+1)]
for i in range(r+1):
	for j in range(c+1):
		v=D[i*10**5+j]
		if v!=0:
			DP[i][j][1]=max(DP[i-1][j])+v
		for ii in range(4):
			DP[i][j][0]=max(DP[i][j][0],DP[i-1][j][ii])
			if v!=0:
				DP[i][j][1]=max(DP[i][j][1],DP[i-1][j][ii]+v)
			DP[i][j][ii]=max(DP[i][j][ii],DP[i][j-1][ii])
			if v!=0 and ii!=0:
				DP[i][j][ii]=max(DP[i][j][ii],DP[i][j-1][ii-1]+v)
		
ans=max(DP[r-1][c-1])
print(ans)



Fixed submission:
import sys
input=lambda: sys.stdin.readline().rstrip()

r,c,k=map(int,input().split())
D=[[0]*c for _ in range(r)] 
for _ in range(k):
	ri,ci,v=map(int,input().split())
	ri-=1
	ci-=1
	D[ri][ci]=v

DP0=[[0]*(c+1) for i in range(r+1)]
DP1=[[0]*(c+1) for i in range(r+1)]
DP2=[[0]*(c+1) for i in range(r+1)]
DP3=[[0]*(c+1) for i in range(r+1)]
for i in range(r):
	for j in range(c):
		v=D[i][j]
		if v!=0:
			DP1[i][j]=max(DP0[i-1][j],DP1[i-1][j],DP2[i-1][j],DP3[i-1][j])+v

		DP0[i][j]=max(DP0[i][j],DP0[i-1][j],DP1[i-1][j],DP2[i-1][j],DP3[i-1][j])
		if v!=0:
			DP1[i][j]=max(DP1[i][j],DP0[i-1][j]+v,DP1[i-1][j]+v,DP2[i-1][j]+v,DP3[i-1][j]+v)
		DP0[i][j]=max(DP0[i][j],DP0[i][j-1])
		DP1[i][j]=max(DP1[i][j],DP1[i][j-1])
		DP2[i][j]=max(DP2[i][j],DP2[i][j-1])
		DP3[i][j]=max(DP3[i][j],DP3[i][j-1])
		if v!=0:
			DP1[i][j]=max(DP1[i][j],DP0[i][j-1]+v)
			DP2[i][j]=max(DP2[i][j],DP1[i][j-1]+v)
			DP3[i][j]=max(DP3[i][j],DP2[i][j-1]+v)
		
ans=max(DP0[r-1][c-1],DP1[r-1][c-1],DP2[r-1][c-1],DP3[r-1][c-1])
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input=lambda: sys.stdin.readline().rstrip()
import collections
D=collections.defaultdict(int)
r,c,k=map(int,input().split())
for _ in range(k):
	ri,ci,v=map(int,input().split())
	ri-=1
	ci-=1
	D[ri*10**5+ci]=v

DP=[[[0]*4 for _ in range(c+1)] for i in range(r+1)]
for i in range(r+1):
	for j in range(c+1):
		v=D[i*10**5+j]
		
		DP[i][j][0]=max(DP[i-1][j])
		if v!=0:
			DP[i][j][1]=max(DP[i-1][j])+v
		for ii in range(4):
		
			DP[i][j][ii]=max(DP[i][j][ii],DP[i][j-1][ii])
			if v!=0 and ii!=0:
				DP[i][j][ii]=max(DP[i][j][ii],DP[i][j-1][ii-1]+v)
		
ans=max(DP[r-1][c-1])
print(ans)



Fixed submission:
import sys
input=lambda: sys.stdin.readline().rstrip()

r,c,k=map(int,input().split())
D=[[0]*c for _ in range(r)] 
for _ in range(k):
	ri,ci,v=map(int,input().split())
	ri-=1
	ci-=1
	D[ri][ci]=v

DP0=[[0]*(c+1) for i in range(r+1)]
DP1=[[0]*(c+1) for i in range(r+1)]
DP2=[[0]*(c+1) for i in range(r+1)]
DP3=[[0]*(c+1) for i in range(r+1)]
for i in range(r):
	for j in range(c):
		v=D[i][j]
		if v!=0:
			DP1[i][j]=max(DP0[i-1][j],DP1[i-1][j],DP2[i-1][j],DP3[i-1][j])+v

		DP0[i][j]=max(DP0[i][j],DP0[i-1][j],DP1[i-1][j],DP2[i-1][j],DP3[i-1][j])
		if v!=0:
			DP1[i][j]=max(DP1[i][j],DP0[i-1][j]+v,DP1[i-1][j]+v,DP2[i-1][j]+v,DP3[i-1][j]+v)
		DP0[i][j]=max(DP0[i][j],DP0[i][j-1])
		DP1[i][j]=max(DP1[i][j],DP1[i][j-1])
		DP2[i][j]=max(DP2[i][j],DP2[i][j-1])
		DP3[i][j]=max(DP3[i][j],DP3[i][j-1])
		if v!=0:
			DP1[i][j]=max(DP1[i][j],DP0[i][j-1]+v)
			DP2[i][j]=max(DP2[i][j],DP1[i][j-1]+v)
			DP3[i][j]=max(DP3[i][j],DP2[i][j-1]+v)
		
ans=max(DP0[r-1][c-1],DP1[r-1][c-1],DP2[r-1][c-1],DP3[r-1][c-1])
print(ans)