Problem:
 Score : 500 points    Problem Statement There are K items placed on a grid of squares with R rows and C columns. Let (i, j) denote the square at the i -th row ( 1 \leq i \leq R ) and the j -th column ( 1 \leq j \leq C ). The i -th item is at (r_i, c_i) and has the value v_i .  Takahashi will begin at (1, 1) , the start, and get to (R, C) , the goal. When he is at (i, j) , he can move to (i + 1, j) or (i, j + 1) (but cannot move to a non-existent square).  He can pick up items on the squares he visits, including the start and the goal, but at most three for each row. It is allowed to ignore the item on a square he visits.  Find the maximum possible sum of the values of items he picks up.      Constraints  1 \leq R, C \leq 3000  1 \leq K \leq \min(2 \times 10^5, R \times C)  1 \leq r_i \leq R  1 \leq c_i \leq C  (r_i, c_i) \neq (r_j, c_j) (i \neq j)  1 \leq v_i \leq 10^9  All values in input are integers.         Input Input is given from Standard Input in the following format:  R  C  K  r_1  c_1  v_1  r_2  c_2  v_2  :  r_K  c_K  v_K       Output Print the maximum possible sum of the values of items Takahashi picks up.        Sample Input 1 2 2 3
1 1 3
2 1 4
1 2 5      Sample Output 1 8  He has two ways to get to the goal:   Visit (1, 1) , (1, 2) , and (2, 2) , in this order. In this case, the total value of the items he can pick up is 3 + 5 = 8 .  Visit (1, 1) , (2, 1) , and (2, 2) , in this order. In this case, the total value of the items he can pick up is 3 + 4 = 7 .   Thus, the maximum possible sum of the values of items he picks up is 8 .       Sample Input 2 2 5 5
1 1 3
2 4 20
1 2 1
1 3 4
1 4 2      Sample Output 2 29  We have four items in the 1 -st row. The optimal choices are as follows:   Visit (1, 1)  (1, 2) , (1, 3) , (1, 4) , (2, 4) , and (2, 5) , in this order, and pick up all items except the one on (1, 2) . Then, the total value of the items he picks up will be 3 + 4 + 2 + 20 = 29 .        Sample Input 3 4 5 10
2 5 12
1 5 12
2 3 15
1 2 20
1 1 28
2 4 26
3 2 27
4 5 21
3 5 10
1 3 10      Sample Output 3 142

Solution (Python):

import sys
input = sys.stdin.readline

def main():
    R, C, K = map(int, input().split())
    V = [[0] * C for _ in [None] * R]
    for _ in [None] * K:
        r, c, v = map(int, input().split())
        V[r - 1][c - 1] = v

    dp = [[[-1] * C for _ in [None] * R] for _ in [None] * 4]

    dp[0][0][0] = 0
    for r in range(R):
        for c in range(C):
            v = V[r][c]
            for i in range(4):
                if dp[i][r][c] > -1:
                    if r < R - 1:
                        dp[0][r + 1][c] = max(dp[0][r + 1][c], dp[i][r][c])
                    if c < C - 1:
                        dp[i][r][c + 1] = max(dp[i][r][c + 1], dp[i][r][c])
                    if i < 3 and v:
                        if r < R - 1:
                            dp[0][r + 1][c] = max(dp[0][r + 1][c], dp[i][r][c] + v)
                        if c < C - 1:
                            dp[i + 1][r][c + 1] = max(dp[i + 1][r][c + 1], dp[i][r][c] + v)

    v = V[R - 1][C - 1]
    ans = dp[3][R - 1][C - 1]
    for i in range(3):
        ans = max(ans, dp[i][R - 1][C - 1] + v)
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
import sys

input = sys.stdin.buffer.readline
r, c, k = map(int, input().split())


graph = [[0] * (c) for _ in range(r)]

for _ in range(k):
    d, e, f = map(int, input().split())
    graph[d - 1][e - 1] = f


infi = 10 ** 10
money = [[[-infi] * (c) for _ in range(r)] for _ in range(4)]
money[0][0][0] = 0
for i in range(r):
    for j in range(c):
        for t in range(4):
            m = money[t][i][j]
            delta = graph[i][j]
            if i < r - 1:
                ni = i + 1
                nj = j
                nt = 0
                money[nt][ni][nj] = max(money[nt][ni][nj], m)
                if t < 3:
                    money[nt][ni][nj] = max(money[nt][ni][nj], m + delta)

            if j < c - 1:
                ni = i
                nj = j + 1
                nt = t
                money[nt][ni][nj] = max(money[nt][ni][nj], m)
                if t < 3:
                    nt = t + 1
                    money[nt][ni][nj] = max(money[nt][ni][nj], m + delta)

ans = 0
if graph[r - 1][c - 1] > 0:
    for t in range(3):
        money[t][r - 1][c - 1] += graph[r - 1][c - 1]
for i in range(4):
    ans = max(money[i][r - 1][c - 1], ans)

print(ans)

Solution (Python):
import os,io
import sys
input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
r,c,k=map(int,input().split())
dp = [0]*(r*c*4)
m=[]
for i in range(r):
  m.append([])
  for j in range(c):
    m[i].append(0)
for i in range(k):
  ri,ci,v=map(int,input().split())
  m[ri-1][ci-1]=v
dp[0*r*c+0*c+0]=0
dp[1*r*c+0*c+0]=m[0][0]
dp[2*r*c+0*c+0]=m[0][0]
dp[3*r*c+0*c+0]=m[0][0]
for i in range(r):
  for j in range(c):
    if j+1<c:
      dp[0*r*c+i*c+j+1]=max(dp[0*r*c+i*c+j+1],dp[0*r*c+i*c+j])
      dp[1*r*c+i*c+j+1]=max(dp[1*r*c+i*c+j],max(dp[1*r*c+i*c+j+1],dp[0*r*c+i*c+j]+m[i][j+1]))
      dp[2*r*c+i*c+j+1]=max(dp[2*r*c+i*c+j],max(dp[2*r*c+i*c+j+1],dp[1*r*c+i*c+j]+m[i][j+1]))
      dp[3*r*c+i*c+j+1]=max(dp[3*r*c+i*c+j],max(dp[3*r*c+i*c+j+1],dp[2*r*c+i*c+j]+m[i][j+1]))
    if i+1<r:
      dp[0*r*c+(i+1)*c+j]=dp[3*r*c+i*c+j]
      dp[1*r*c+(i+1)*c+j]=dp[3*r*c+i*c+j]+m[i+1][j]
      dp[2*r*c+(i+1)*c+j]=dp[3*r*c+i*c+j]+m[i+1][j]
      dp[3*r*c+(i+1)*c+j]=dp[3*r*c+i*c+j]+m[i+1][j]
print(dp[3*r*c+(r-1)*c+c-1])

Solution (Python):
import sys
input = sys.stdin.readline

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

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

for i in range(K):
    r,c,v = map(int,input().split())
    tb[r][c] = v

for i in range(1,R+1):
    for j in range(1,C+1):
        pmx = 0
        for k in range(4):
            mx = dp[j-1][k]
            if k > 0:
                mx = max(mx,dp[j-1][k-1]+tb[i][j])
            if k == 0:
                mx = max(mx,prev[j])
            elif k == 1:
                mx = max(mx,prev[j]+tb[i][j])
            dp[j][k] = mx
            pmx = max(pmx,mx)
        prev[j] = pmx

print(prev[C])

Solution (Python):
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)
 
R, C, K = rl()
I = [[0]*(C+2) for _ in range(R+2)]
for i in range(K):
	r, c, v = rl()
	I[r][c] = v
 
dp = [[0]*4 for _ in range(C+2)]
dp2 = [[0]*4 for _ in range(C+2)]
 
for i in range(R+1):
	for j in range(C+1):
		for m in range(4):
			ni, nj = i, j+1
			dp[nj][m] = max(dp[nj][m], dp[j][m])
			if m < 3:
				dp[nj][m+1] = max(dp[nj][m+1], dp[j][m]+I[ni][nj])
			ni, nj = i+1, j
			dp2[nj][0] = max(dp2[nj][0], dp[j][m])
			dp2[nj][1] = max(dp2[nj][1], dp[j][m]+I[ni][nj])
	dp = dp2
	dp2 = [[0]*4 for _ in range(C+2)]
ans = 0
for m in range(4):
	ans = max(ans, dp[C][m])
print(ans)

Solution (Python):
import sys

def solve():
    input = sys.stdin.readline
    R, C, K = map(int, input().split())
    item = [[0 for _ in range(C)] for r in range(R)]
    for _ in range(K):
        r, c, k = map(int, input().split())
        item[r-1][c-1] = k
    
    DP = [[[-1 for _ in range(C)] for r in range(R)] for i in range(4)]
    DP[0][0][0] = 0
    for r in range(R):
        for c in range(C):
            for i in range(4):
                if DP[i][r][c] > -1:
                    if r + 1 < R: 
                        DP[0][r+1][c] = max(DP[0][r+1][c], DP[i][r][c])
                    if c + 1 < C: 
                        DP[i][r][c+1] = max(DP[i][r][c+1], DP[i][r][c])
                    if i < 3 and item[r][c] > 0:
                        if r + 1 < R: DP[0][r+1][c] = max(DP[0][r+1][c], DP[i][r][c] + item[r][c])
                        if c + 1 < C: DP[i+1][r][c+1] = max(DP[i+1][r][c+1], DP[i][r][c] + item[r][c])

    ans = DP[3][R-1][C-1]
    for i in range(3): ans = max(ans, DP[i][R-1][C-1] + item[R-1][C-1])
    print(ans)
    return 0

if __name__ == "__main__":
    solve()

Solution (Python):
import sys
input = sys.stdin.buffer.readline
H, W, K = map(int, input().split())
B = {}
for _ in range(K):
    r, c, v = map(int, input().split())
    B[(r, c)] = v

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

for i in range(1, H+1):
    for j in range(1, W+1):
        if (i, j) in B:
            v = B[(i, j)]
            dp[0][j] = max(dp[0][j-1], dp[0][j], dp[1][j], dp[2][j], dp[3][j])
            dp[1][j] = max(dp[1][j-1], dp[0][j]+v)
            dp[2][j] = max(dp[2][j-1], dp[1][j-1]+v)
            dp[3][j] = max(dp[3][j-1], dp[2][j-1]+v)
        else:
            dp[0][j] = max(dp[0][j-1], dp[0][j], dp[1][j], dp[2][j], dp[3][j])
            dp[1][j] = dp[1][j-1]
            dp[2][j] = dp[2][j-1]
            dp[3][j] = dp[3][j-1]

print(max(dp[i][-1] for i in range(4)))

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

R, C, K = mapint()
dp = [[[0]*C for _ in range(R)] for _ in range(4)]
from collections import defaultdict
dic = [[0]*C for _ in range(R)]
for _ in range(K):
    r, c, v = mapint()
    dic[r-1][c-1] = v

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

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

Solution (Python):
R, C,K = map(int, input().split())
dp = [[[0]*(C+1) for k in range(R+1)] for _ in range(4)]

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)

Solution (Python):
def solve():
  R, C, K = map(int, input().split())
  item = [[0]*C for _ in range(R)]
  for i in range(K):
    r,c,v = map(int, input().split())
    item[r-1][c-1] = v
  last_dp = [[0]*(C+1) for _ in range(5)]
  for i in range(1,R+1):
    dp = [[0]*(C+1) for _ in range(5)]
    for j in range(1,C+1):
      for k in range(4): 
        dp[k][j] = dp[k][j-1]
      
      dp[0][j] = max(dp[0][j],last_dp[-1][j])
      if item[i-1][j-1]>0:
        
        dp[1][j] = max(dp[1][j],last_dp[-1][j]+item[i-1][j-1])
        for k in range(1,4): 
          dp[k][j] = max(dp[k][j],dp[k-1][j-1]+item[i-1][j-1])
      for k in range(4):
        dp[-1][j] = max(dp[-1][j],dp[k][j])
    last_dp = dp
  ans = last_dp[-1][-1]
  return ans
print(solve())

Solution (Python):


R, C, K = map(int, input().split())
dp = [[[0]*(C+1) for _ in range(R+1)]for __ in range(4)]

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

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)

Solution (Python):
R, C,K = map(int, input().split())
dp = [[[0]*(C+1) for k in range(R+1)] for _ in range(4)]

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)

Solution (Python):
def solve():
  R, C, K = map(int, input().split())
  item = [[0]*C for _ in range(R)]
  for i in range(K):
    r,c,v = map(int, input().split())
    item[r-1][c-1] = v
  last_dp = [[0]*5 for _ in range(C+1)]
  for i in range(1,R+1):
    dp = [[0]*5 for _ in range(C+1)]
    for j in range(1,C+1):
      for k in range(4): 
        dp[j][k] = dp[j-1][k]
      
      dp[j][0] = max(dp[j][0],last_dp[j][-1])
      if item[i-1][j-1]>0:
        
        dp[j][1] = max(dp[j][1],last_dp[j][-1]+item[i-1][j-1])
        for k in range(1,4): 
          dp[j][k] = max(dp[j][k],dp[j-1][k-1]+item[i-1][j-1])
      dp[j][4] = max(dp[j][:4])
    last_dp = dp
  ans = max(last_dp[-1])
  return ans
print(solve())

Solution (Python):
import sys
from numpy import*
def main(h,w,k,t):
    c=zeros((3001,3001),int_)
    dp=zeros((4,3001,3001),int_)
    for i in range(k):
        y,x,v=t[i]
        c[y,x]=v
    for i in range(1,h+1):
        for j in range(1,w+1):
            x=max(dp[:,i-1,j])
            for k in range(4):
                if k:dp[k,i,j]=max(dp[k,i,j-1],dp[k-1,i,j-1]+c[i,j])
                else:dp[k,i,j]=max(dp[k,i,j-1],x)
            dp[1,i,j]=max(dp[1,i,j],x+c[i,j])
    return max(dp[:,h,w])
if sys.argv[-1]=='ONLINE_JUDGE':
  from numba.pycc import CC
  cc=CC('my_module')
  cc.export('main','i8(i8,i8,i8,i8[:,:])')(main)
  cc.compile()
  exit()
from my_module import main
(h,w,k),*t=[int_(t.split())for t in open(0)]
print(main(h,w,k,int_(t)))

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

I = [[0 for _ in range(C+1)] for _ in range(R+1)]
for i in range(K): 
  r, c, v = map(int, input().split())
  I[r][c] = v 
  
DP1 = [0 for _ in range(C+1)] 
DP2 = [0 for _ in range(C+1)] 
DP3 = [0 for _ in range(C+1)] 


for r in range(1,R+1):
  for c in range(1,C+1): 
    
    
    mid = DP3[c] + I[r][c] 
    DP3[c] = max(DP3[c-1], mid, DP2[c-1] + I[r][c]) 
    DP2[c] = max(DP2[c-1], mid, DP1[c-1] + I[r][c]) 
    DP1[c] = max(DP1[c-1], mid) 
  
    
print(DP3[C])

Solution (Python):
c=[[0]*3001for _ in range(3001)]
dp=[[[0]*3001for _ in range(3001)]for _ in range(4)]
h,w,k=map(int,input().split())
for i in range(k):
    y,x,v=map(int,input().split())
    c[y][x]=v
for i in range(1,h+1):
    for j in range(1,w+1):
        x=max(dp[0][i-1][j],dp[1][i-1][j],dp[2][i-1][j],dp[3][i-1][j])
        for k in range(4):
            if k:dp[k][i][j]=max(dp[k][i][j-1],dp[k-1][i][j-1]+c[i][j])
            else:dp[k][i][j]=max(dp[k][i][j-1],x)
        dp[1][i][j]=max(dp[1][i][j],x+c[i][j])
print(max(dp[0][h][w],dp[1][h][w],dp[2][h][w],dp[3][h][w]))

Solution (Python):

import sys
input = sys.stdin.readline

R, C, k = map(int, input().split())
field = [[0] * C for _ in range(R)]
for _ in range(k):
    r, c, v = map(int, input().split())
    r -= 1; c -= 1
    field[r][c] = v


dp = [[-1] * (C + 1) * (R + 1) for _ in range(4)]
dp0 = dp[0]; dp1 = dp[1]; dp2 = dp[2]; dp3 = dp[3]
dp[0][0] = 0
for j in range(C):
    for i in range(R):
        ij = i * C + j
        ij1 = ij + 1
        i1j = ij + C
        item = field[i][j]
        
        if item:
            dp1[ij1] = max(dp1[ij1], dp0[ij] + item) 
            dp0[i1j] = max(dp0[i1j], dp0[ij] + item) 
        dp0[i1j] = max(dp0[i1j], dp0[ij]) 
        dp0[ij1] = max(dp0[ij1], dp0[ij]) 
        if item:
            dp2[ij1] = max(dp2[ij1], dp1[ij] + item) 
            dp0[i1j] = max(dp0[i1j], dp1[ij] + item) 
        dp0[i1j] = max(dp0[i1j], dp1[ij]) 
        dp1[ij1] = max(dp1[ij1], dp1[ij]) 
        if item:
            dp3[ij1] = max(dp3[ij1], dp2[ij] + item) 
            dp0[i1j] = max(dp0[i1j], dp2[ij] + item) 
        dp0[i1j] = max(dp0[i1j], dp2[ij]) 
        dp2[ij1] = max(dp2[ij1], dp2[ij]) 
        dp0[i1j] = max(dp0[i1j], dp3[ij]) 
        dp3[ij1] = max(dp3[ij1], dp3[ij]) 

ans = 0
for i in range(4):
    for j in range(R + 1):
        ans = max(ans, dp[i][j * C + C - 1])
print(ans)

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

p = []
for k in range(K):
  p.append(list(map(int, input().split())))

maps = [[0 for _ in range(C)] for _ in range(R)]
for k in range(K):
  maps[p[k][0]-1][p[k][1]-1] += p[k][2]

point1 = [[0 for _ in range(C)] for _ in range(R)]
point2 = [[0 for _ in range(C)] for _ in range(R)]
point3 = [[0 for _ in range(C)] for _ in range(R)]

point1[0][0] = maps[0][0]

for r in range(R):
  for c in range(C):
    a, b, d = point1[r][c], point2[r][c], point3[r][c]  
    if c < C - 1:
      x = maps[r][c+1]
      point1[r][c+1] = max(point1[r][c+1], x, a)
      point2[r][c+1] = max(point2[r][c+1], a + x, b)
      point3[r][c+1] = max(point3[r][c+1], b + x, d)
    if r < R - 1:
      point1[r+1][c] = maps[r+1][c] + max(a, b, d)


print(max(point1[-1][-1], point2[-1][-1], point3[-1][-1]))

Solution (Python):

import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

R, C, K = map(int, readline().split())
rcv = list(map(int, read().split()))
rc2v = {}
for rr, cc, vv in zip(rcv[::3], rcv[1::3], rcv[2::3]):
    rc2v[(rr, cc)] = vv

dp = [[0]*4 for c in range(C+1)]
for r in range(1, R+1):
  for c in range(1, C+1):
    v = rc2v[(r, c)] if (r, c) in rc2v else 0
    dp[c][0] = max(dp[c-1][0], max(dp[c]))
    dp[c][1] = max(dp[c-1][1], dp[c][0] + v)
    dp[c][2] = max(dp[c-1][2], dp[c-1][1] + v)
    dp[c][3] = max(dp[c-1][3], dp[c-1][2] + v)

print(max(dp[-1]))

Solution (Python):
import os,io
import sys
input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
r,c,k=map(int,input().split())
dp = [[[0 for y in range(c)] for z in range(r)] for P in range(4)]
m=[]
for i in range(r):
  m.append([])
  for j in range(c):
    m[i].append(0)
for i in range(k):
  ri,ci,v=map(int,input().split())
  m[ri-1][ci-1]=v
dp[0][0][0]=0
dp[1][0][0]=m[0][0]
dp[2][0][0]=m[0][0]
dp[3][0][0]=m[0][0]
for i in range(r):
  for j in range(c):
    if j+1<c:
      dp[0][i][j+1]=max(dp[0][i][j+1],dp[0][i][j])
      dp[1][i][j+1]=max(dp[1][i][j],max(dp[1][i][j+1],dp[0][i][j]+m[i][j+1]))
      dp[2][i][j+1]=max(dp[2][i][j],max(dp[2][i][j+1],dp[1][i][j]+m[i][j+1]))
      dp[3][i][j+1]=max(dp[3][i][j],max(dp[3][i][j+1],dp[2][i][j]+m[i][j+1]))
    if i+1<r:
      dp[0][i+1][j]=dp[3][i][j]
      dp[1][i+1][j]=dp[3][i][j]+m[i+1][j]
      dp[2][i+1][j]=dp[3][i][j]+m[i+1][j]
      dp[3][i+1][j]=dp[3][i][j]+m[i+1][j]
print(dp[3][r-1][c-1])

Solution (Python):
import sys







import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

@njit((i8[:], i8, i8, i8), cache=True)
def solve(items,R,C,K):  
    
    

    grid = np.zeros((R, C), np.int64)

    for i in range(0, 3 * K, 3):
        x, y, v = items[i:i + 3]
        grid[x - 1, y - 1] = v

    
    

    dp = np.zeros((R, C, 4), np.int64)
    maxx = np.zeros((R, C), np.int64)

    if grid[0,0] > 0:
        dp[0][0][1] = dp[0][0][0] + grid[0][0]

    for i in range(1,R):
        dp[i][0][0] = max(dp[i-1][0][0], dp[i-1][0][1])
        if grid[i][0] > 0:
            dp[i][0][1] = dp[i][0][0] + grid[i][0]
        maxx[i][0] = max(dp[i][0])

    for j in range(1,C):
        for k in range(1,4):
            dp[0][j][k] = max(dp[0][j-1][k], dp[0][j-1][k-1] + grid[0][j])
        maxx[0][j] = max(dp[0][j])

    
    
    
    
    

    for i in range(1,R):
        j_1 = 0
        for j in range(1,C):
            dp[i][j][0] = max(maxx[i-1][j], dp[i][j-1][0])
            if grid[i][j] > 0:
                dp[i][j][1] = max(dp[i][j-1][1], dp[i][j][0] + grid[i][j])
                for k in range(2,4):
                    dp[i][j][k] = max(dp[i][j-1][k], dp[i][j-1][k-1] + grid[i][j])
                j_1 = j
            else:
                for k in range(1,4):
                    dp[i][j][k] = dp[i][j-1][k]
            maxx[i][j] = max(dp[i][j])

    
    
    
    
    

    
    return dp.max()


def console(*args):  
    
    return

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

H, W, K = map(int, readline().split())
XYV = np.array(read().split(), np.int64)
 
print(solve(XYV, H, W, K))

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

I = [[0 for _ in range(C+1)] for _ in range(R+1)]
for i in range(K): 
  r, c, v = map(int, input().split())
  I[r][c] = v 
  
DP1 = [0 for _ in range(C+1)] 
DP2 = [0 for _ in range(C+1)] 
DP3 = [0 for _ in range(C+1)] 


for r in range(1,R+1):
  for c in range(1,C+1): 
    
    
    mid = DP3[c] + I[r][c] 
    DP3[c] = max(DP3[c-1], mid, DP2[c-1] + I[r][c]) 
    DP2[c] = max(DP2[c-1], mid, DP1[c-1] + I[r][c]) 
    DP1[c] = max(DP1[c-1], mid) 
  
    
print(DP3[C])

Solution (Python):

import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

R, C, K = map(int, readline().split())
rcv = list(map(int, read().split()))
rc2v = {}
for rr, cc, vv in zip(rcv[::3], rcv[1::3], rcv[2::3]):
    rc2v[(rr, cc)] = vv

dp = [[0]*4 for c in range(C+1)]
for r in range(1, R+1):
  for c in range(1, C+1):
    v = rc2v[(r, c)] if (r, c) in rc2v else 0
    dp[c][0] = max(dp[c-1][0], max(dp[c]))
    dp[c][1] = max(dp[c-1][1], dp[c][0] + v)
    for k in range(2, 4):
      dp[c][k] = max(dp[c-1][k], dp[c-1][k-1] + v)

print(max(dp[-1]))

Solution (Python):
import sys
input = sys.stdin.readline
r,c,k = map(int,input().split())
l = [[0]*c for i in range(r)] 
for i in range(k):
    x,y,v = map(int,input().split())
    l[x-1][y-1] = v
dp = [[0]*4 for i in range(c+1)]

for i in range(r):
    ndp = [[0]*4 for i in range(c+1)]
    for j in range(c):
        M = max(dp[j+1])
        if l[i][j]>0:
            v = l[i][j]
            ndp[j+1][0] = max(M,dp[j][0],ndp[j][0])
            ndp[j+1][1] = max(M+v,dp[j][0]+v,ndp[j][0]+v,dp[j][1],ndp[j][1])
            ndp[j+1][2] = max(dp[j][1]+v,ndp[j][1]+v,dp[j][2],ndp[j][2])
            ndp[j+1][3] = max(dp[j][2]+v,ndp[j][2]+v,dp[j][3],ndp[j][3])
        else:
            ndp[j+1][0] = max(M,dp[j][0],ndp[j][0])
            ndp[j+1][1] = max(dp[j][1],ndp[j][1])
            ndp[j+1][2] = max(dp[j][2],ndp[j][2])
            ndp[j+1][3] = max(dp[j][3],ndp[j][3])
    dp = ndp
print(max(dp[-1]))

Solution (Python):
R, C, K = map(int, input().split())
g = [[-float('inf')]*C for _ in range(R)]
for i in range(K):
    r, c, k = map(int, input().split())
    r -= 1
    c -= 1
    g[r][c] = k

dp = [[[0]*(C+1) for _ in range(R+1)] for _ in range(4)]
for r in range(R):
    for c in range(C):
        
        
        for k in range(2, -1, -1):
            dp[k+1][r][c] = max(
                dp[k+1][r][c],
                dp[k][r][c]+g[r][c]
            )

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

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

Solution (Python):
import sys
import time
s1 = time.time()
*data, = map(int, sys.stdin.read().split()[::-1])

def inp():
    global data
    return data.pop()
R, C, k = inp(), inp(), inp()
grid = [[0] * C for _ in range(R)]

for _ in range(k):
    ri, ci, v = inp(), inp(), inp()
    grid[ri - 1][ci - 1] = v


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


mx = 0
for row in range(1, R + 1):
    for col in range(1, C + 1):
        level = 0
        dp[1][row][col] = max(dp[1][row][col], dp[3][row - 1][col] + grid[row - 1][col - 1])
        dp[0][row][col] = max(dp[0][row][col], dp[3][row - 1][col])
        level = 1
        v = grid[row - 1][col - 1]
        while level < 4:
            dp[level][row][col] = max(
                dp[level - 1][row][col],
                dp[level][row][col],
                dp[level][row][col - 1],
                dp[level - 1][row][col - 1] + v,
            )
            mx = max(mx, dp[level][row][col])
            level += 1


print(mx)

Solution (Python):

import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub


import sys
sys.setrecursionlimit(10**6)

buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(R, C, K, RCV):
    V = [[0] * C for _ in range(R)]
    for r, c, v in RCV:
        V[r-1][c-1] = v
    memo = [[[0] * (C+1) for _ in range(R+1)] for __ in range(4)]

    for i in range(R):
        for j in range(C):
            for p in range(4):
                memo[p][i][j+1] = max(memo[p][i][j+1], memo[p][i][j])
                memo[0][i+1][j] = max(memo[0][i+1][j], memo[p][i][j])
                if p != 3:
                    memo[p+1][i][j+1] = max(memo[p+1][i][j+1], memo[p][i][j] + V[i][j])
                    memo[0][i+1][j] = max(memo[0][i+1][j], memo[p][i][j] + V[i][j])

    return max(memo[0][-1])


def main():
    R, C, K = read_int_n()
    RCV = [read_int_n() for _ in range(K)]
    print(slv(R, C, K, RCV))


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from itertools import accumulate
def input(): return sys.stdin.readline().strip()

def main():
    R, C, K = map(int, input().split())
    R, C = C, R
    items = [[0] * R for _ in range(C)]
    for _ in range(K):
        r, c, v = map(int, input().split())
        items[r - 1][c - 1] = v

    dp = [[0] * R for _ in range(4)]
    for i in range(1, 4):
        dp[i][0] = items[0][0]
        for r in range(1, R):
            dp[i][r] = max(dp[i][r - 1], dp[i - 1][r - 1] + items[0][r])

    for c in range(1, C):
        dp2 = [[0] * R for _ in range(4)]
        for i in range(1, 4):
            dp2[i][0] = max(dp[1][0], dp[2][0], dp[3][0]) + items[c][0]
            for r in range(1, R):
                upper = max(dp[1][r], dp[2][r], dp[3][r]) + items[c][r]
                dp2[i][r] = max(upper, dp2[i][r - 1], dp2[i - 1][r - 1] + items[c][r])
        dp = dp2

    print(dp[3][R - 1])



if __name__ == "__main__":
    main()

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip()
r, c, k = map(int, input().split())
pt = [[0 for _ in range(c + 5)] for _ in range(r + 5)]

for i in range(k):
    r1, c1, v = map(int, input().split())
    pt[r1][c1] = v

memo = [[0] * 4 for _ in range(c + 1)]
prev = [[0] * 4 for _ in range(c + 1)]
for i in range(1, r + 1):
    memo, prev = prev, memo
    for j in range(1, c + 1):
        V = pt[i][j]
        memo[j][0] = max(prev[j][3], memo[j - 1][0])
        memo[j][1] = max(memo[j][0] + V, memo[j - 1][1])
        memo[j][2] = max(memo[j][1], memo[j - 1][1] + V, memo[j - 1][2])
        memo[j][3] = max(memo[j][2], memo[j - 1][2] + V, memo[j - 1][3])
print(memo[-1][3])

Solution (Python):
def solve():
  R, C, K = map(int, input().split())
  item = [[0]*C for _ in range(R)]
  for i in range(K):
    r,c,v = map(int, input().split())
    item[r-1][c-1] = v
  dp = [[[0]*(C+1) for _ in range(R+1)] for _ in range(4)]
  for i in range(1,R+1):
    for j in range(1,C+1):
      for k in range(4): 
        dp[k][i][j] = dp[k][i][j-1]
      
      dp[0][i][j] = max(dp[0][i][j],dp[-1][i-1][j])
      if item[i-1][j-1]>0:
        
        dp[1][i][j] = max(dp[1][i][j],dp[-1][i-1][j]+item[i-1][j-1])
        for k in range(1,4): 
          dp[k][i][j] = max(dp[k][i][j],dp[k-1][i][j-1]+item[i-1][j-1])
      for k in range(1,4):
        dp[k][i][j] = max(dp[k-1][i][j],dp[k][i][j])
  ans = 0
  for k in range(4):
    ans = max(ans,dp[k][-1][-1])
  return ans
print(solve())

Solution (Python):
import sys

input = lambda: sys.stdin.readline().rstrip()
r, c, k = map(int, input().split())

pt = [[0 for _ in range(c + 5)] for _ in range(r + 5)]

for i in range(k):
    r1, c1, v = map(int, input().split())
    
    pt[r1][c1] = v


a = 0


def solve():
    memo = [[0] * 4 for _ in range(c + 1)]
    prev = [[0] * 4 for _ in range(c + 1)]
    for i in range(1, r + 1):
        memo, prev = prev, memo
        for j in range(1, c + 1):
            V = pt[i][j]
            memo[j][0] = max(prev[j][3], memo[j - 1][0])
            memo[j][1] = max(memo[j][0] + V, memo[j - 1][1])
            memo[j][2] = max(memo[j][1], memo[j - 1][1] + V, memo[j - 1][2])
            memo[j][3] = max(memo[j][2], memo[j - 1][2] + V, memo[j - 1][3])

            
            
            
            
            

    

    

    
    return memo[-1][3]





if __name__ == '__main__':
    print(solve())

Solution (Python):

import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

R, C, K = map(int, readline().split())
rcv = list(map(int, read().split()))
rc2v = {}
for rr, cc, vv in zip(rcv[::3], rcv[1::3], rcv[2::3]):
    rc2v[(rr-1, cc-1)] = vv

dp = [[[0]*4 for c in range(C)] for r in range(2)]
dp[0][0][1] = rc2v[(0, 0)] if (0, 0) in rc2v else 0

for c in range(1, C):
  for k in range(1, 4):
    v = rc2v[(0, c)] if (0, c) in rc2v else 0
    dp[0][c][k] = max(dp[0][c-1][k], dp[0][c-1][k-1]+v)

for r in range(1, R):
  rr = r % 2
  dp[rr][0][0] = max(dp[rr-1][0])
  v = rc2v[(r, 0)] if (r, 0) in rc2v else 0
  dp[rr][0][1] = dp[rr][0][0] + v
  for c in range(1, C):
    v = rc2v[(r, c)] if (r, c) in rc2v else 0
    temp_max = max(dp[rr-1][c])
    dp[rr][c][1] = max(dp[rr][c-1][1], max(dp[rr][c-1][0], temp_max)+v)
    for k in range(2, 4):
      dp[rr][c][k] = max(dp[rr][c-1][k], dp[rr][c-1][k-1]+v)
    
if R % 2:
  print(max(dp[0][-1]))
else:
  print(max(dp[-1][-1]))