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):
r,c,k=map(int,input().split())
items=[list(map(int,input().split())) for _ in range(k)]
dp=[[[0 for _ in range(c+1)] for _ in range(r+1)] for _ in range(5)]
for x,y,z in items:
    dp[4][x][y]=z
for i in range(1,r+1):
    for j in range(1,c+1):
        v=dp[4][i][j]
        dp[0][i][j]=max(dp[0][i][j-1],dp[0][i-1][j],dp[1][i-1][j],dp[2][i-1][j],dp[3][i-1][j])
        dp[1][i][j]=max(dp[1][i][j-1],dp[0][i][j-1]+v,max(dp[0][i-1][j],dp[1][i-1][j],dp[2][i-1][j],dp[3][i-1][j])+v)
        dp[2][i][j]=max(dp[2][i][j-1],dp[1][i][j-1]+v)
        dp[3][i][j]=max(dp[3][i][j-1],dp[2][i][j-1]+v)
print(max(dp[i][r][c] for i in range(4)))

Solution (Python):
from copy import deepcopy

def getval():
    r,c,k = map(int,input().split())
    item = [[0 for i in range(c)] for i in range(r)]
    for i in range(k):
        ri,ci,vi = map(int,input().split())
        item[ri-1][ci-1] = vi
    return r,c,k,item

def main(r,c,k,item):
    
    prev = [[0 for i in range(4)]]
    inititem = item[0][0]
    prev[0] = [0,inititem,inititem,inititem]
    for i in range(1,r):
        initval = prev[i-1][3]
        temp = []
        cur = item[i][0]
        for j in range(4):
            temp.append(initval)
        for j in range(1,4):
            temp[j] += cur
        prev.append(temp)

    for j in range(1,c):
        init = deepcopy(prev[0])
        for i in range(1,4):
            init[i] = max(prev[0][i],prev[0][i-1]+item[0][j])
        curcol = [init]
        for i in range(1,r):
            cur = item[i][j]
            left = curcol[-1]
            down = prev[i]
            temp = [max(left[3],down[0])]
            for k in range(1,4):
                temp.append(max(max(left[3],down[k-1])+cur,down[k]))
            curcol.append(temp)
        prev = curcol
            
    print(max(prev[-1]))
           
if __name__=="__main__":
    r,c,k,item = getval()
    main(r,c,k,item)

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

dp0 = [[0]*C for _ in range(R)]
dp1 = [[0]*C for _ in range(R)]
dp2 = [[0]*C for _ in range(R)]
dp3 = [[0]*C for _ in range(R)]
for i in range(R):
    for j in range(C):
        if i == 0 and j == 0 and L[i][j] > 0:
            dp1[i][j] = L[i][j]
        elif i == 0:
            dp0[i][j] = dp0[i][j-1]
            dp1[i][j] = dp1[i][j-1]
            dp2[i][j] = dp2[i][j-1]
            dp3[i][j] = dp3[i][j-1]
            if L[i][j] > 0:
                dp1[i][j] = max(dp1[i][j], dp0[i][j-1]+L[i][j])
                dp2[i][j] = max(dp2[i][j], dp1[i][j-1]+L[i][j])
                dp3[i][j] = max(dp3[i][j], dp2[i][j-1]+L[i][j])
        elif j == 0:
            dp0[i][j] = max(dp0[i-1][j], dp1[i-1][j], dp2[i-1][j], dp3[i-1][j])
            if L[i][j] > 0:
                dp1[i][j] = dp0[i][j]+L[i][j]
        else:
            dp0[i][j] = max(dp0[i-1][j], dp1[i-1][j], dp2[i-1][j], dp3[i-1][j], dp0[i][j-1])
            dp1[i][j] = dp1[i][j-1]
            dp2[i][j] = dp2[i][j-1]
            dp3[i][j] = dp3[i][j-1]
            if L[i][j] > 0:
                dp1[i][j] = max(dp1[i][j], dp0[i][j]+L[i][j])
                dp2[i][j] = max(dp2[i][j], dp1[i][j-1]+L[i][j])
                dp3[i][j] = max(dp3[i][j], dp2[i][j-1]+L[i][j])

print(max(dp0[-1][-1], dp1[-1][-1], dp2[-1][-1], dp3[-1][-1]))

Solution (Python):
R,C,K=map(int,input().split())
rcv=[list(map(int,input().split())) for _ in range(K)]
mat=[[0]*C for _ in range(R)]
for r,c,v in rcv:
  mat[r-1][c-1]=v
dp=[0]*C
for i in range(R):
  ndp=[0]*C
  wdp=[0]*4
  for j in range(C):
    wdp[0]=max(wdp[0],dp[j])
    if mat[i][j]>0:
      v=mat[i][j]
      wdp[3]=max(wdp[3],wdp[2]+v)
      wdp[2]=max(wdp[2],wdp[1]+v)
      wdp[1]=max(wdp[1],wdp[0]+v)
    ndp[j]=max(wdp)
  dp=ndp.copy()
print(max(wdp))

Solution (Python):
R,C,K=map(int,input().split())
rcv=[list(map(int,input().split())) for _ in range(K)]
mat=[[0]*C for _ in range(R)]
for r,c,v in rcv:
  mat[r-1][c-1]=v
dp=[0]*C
for i in range(R):
  ndp=[0]*C
  wdp=[0]*4
  for j in range(C):
    wdp[0]=max(wdp[0],dp[j])
    if mat[i][j]>0:
      v=mat[i][j]
      wdp[3]=max(wdp[3],wdp[2]+v)
      wdp[2]=max(wdp[2],wdp[1]+v)
      wdp[1]=max(wdp[1],wdp[0]+v)
    ndp[j]=max(wdp)
  dp=ndp.copy()
print(max(wdp))

Solution (Python):

import sys
from collections import defaultdict
R,C,K=map(int, sys.stdin.readline().split())

value=defaultdict(lambda: 0)
value=[ [0 for _ in range(C+1)] for __ in range(R+1) ]
for _ in range(K):
    r,c,v=map(int, sys.stdin.readline().split())
    value[r][c]=v

dp0=[0]*(C+1)
dp1=[0]*(C+1)
dp2=[0]*(C+1)
dp3=[0]*(C+1)

for r in range(1,R+1):
    for c in range(1,C+1):
        
        if 0<value[r][c]:
            dp3[c]=max( dp3[c-1], dp2[c-1]+value[r][c] )
            dp2[c]=max( dp2[c-1], dp1[c-1]+value[r][c] )
            dp1[c]=max( dp1[c-1], dp0[c-1]+value[r][c], dp0[c]+value[r][c] )
            dp0[c]=max( dp0[c-1], dp0[c] )
        
        else:
            dp0[c]=max( dp0[c-1], dp0[c] )
            dp1[c]=max( dp1[c-1], dp1[c] )
            dp2[c]=max( dp2[c-1], dp2[c] )
            dp3[c]=max( dp3[c-1], dp3[c] )

    
    for c in range(1,C+1):
        dp0[c]=max( dp0[c], dp1[c], dp2[c], dp3[c] )
    dp1=[0]*(C+1)
    dp2=[0]*(C+1)
    dp3=[0]*(C+1)

print dp0[C]

Solution (Python):

import sys
from collections import defaultdict
R,C,K=map(int, sys.stdin.readline().split())

value=defaultdict(lambda: 0)
value=[ [0 for _ in range(C+1)] for __ in range(R+1) ]
for _ in range(K):
    r,c,v=map(int, sys.stdin.readline().split())
    value[r][c]=v

dp0=[0]*(C+1)
dp1=[0]*(C+1)
dp2=[0]*(C+1)
dp3=[0]*(C+1)

for r in range(1,R+1):
    for c in range(1,C+1):
        
        if 0<value[r][c]:
            dp3[c]=max( dp3[c-1], dp2[c-1]+value[r][c] )
            dp2[c]=max( dp2[c-1], dp1[c-1]+value[r][c] )
            
            dp1[c]=max( dp1[c-1], dp0[c]+value[r][c] )
            
            dp0[c]=dp0[c]
        
        else:
            
            
            
            
            dp0[c]=dp0[c]
            dp1[c]=dp1[c-1]
            dp2[c]=dp2[c-1]
            dp3[c]=dp3[c-1]

    
    for c in range(1,C+1):
        dp0[c]=max( dp0[c], dp1[c], dp2[c], dp3[c] )
    dp1=[0]*(C+1)
    dp2=[0]*(C+1)
    dp3=[0]*(C+1)

print dp0[C]

Solution (Python):

import sys
from collections import defaultdict
R,C,K=map(int, sys.stdin.readline().split())

value=defaultdict(lambda: 0)
value=[ [0 for _ in range(C+1)] for __ in range(R+1) ]
for _ in range(K):
    r,c,v=map(int, sys.stdin.readline().split())
    value[r][c]=v

dp0=[0]*(C+1)
dp1=[0]*(C+1)
dp2=[0]*(C+1)
dp3=[0]*(C+1)

for r in range(1,R+1):
    for c in range(1,C+1):
        
        if 0<value[r][c]:
            dp3[c]=max( dp3[c-1], dp2[c-1]+value[r][c] )
            dp2[c]=max( dp2[c-1], dp1[c-1]+value[r][c] )
            dp1[c]=max( dp1[c-1], dp0[c-1]+value[r][c], dp0[c]+value[r][c] )
            dp0[c]=max( dp0[c-1], dp0[c] )
        
        else:
            
            
            
            
            dp0[c]=dp0[c]
            dp1[c]=dp1[c-1]
            dp2[c]=dp2[c-1]
            dp3[c]=dp3[c-1]

    
    for c in range(1,C+1):
        dp0[c]=max( dp0[c], dp1[c], dp2[c], dp3[c] )
    dp1=[0]*(C+1)
    dp2=[0]*(C+1)
    dp3=[0]*(C+1)

print dp0[C]

Solution (Python):

import sys
from collections import defaultdict
R,C,K=map(int, sys.stdin.readline().split())

value=defaultdict(lambda: 0)
value=[ [0 for _ in range(C+1)] for __ in range(R+1) ]
for _ in range(K):
    r,c,v=map(int, sys.stdin.readline().split())
    value[r][c]=v

dp0=[0]*(C+1)
dp1=[0]*(C+1)
dp2=[0]*(C+1)
dp3=[0]*(C+1)

for r in range(1,R+1):
    for c in range(1,C+1):
        
        if 0<value[r][c]:
            dp3[c]=max( dp3[c-1], dp2[c-1]+value[r][c] )
            dp2[c]=max( dp2[c-1], dp1[c-1]+value[r][c] )
            dp1[c]=max( dp1[c-1], dp0[c-1]+value[r][c], dp0[c]+value[r][c] )
            dp0[c]=max( dp0[c-1], dp0[c] )
        
        else:
            
            
            
            
            dp0[c]=max( dp0[c-1], dp0[c] )
            dp1[c]=dp1[c-1]
            dp2[c]=dp2[c-1]
            dp3[c]=dp3[c-1]

    
    for c in range(1,C+1):
        dp0[c]=max( dp0[c], dp1[c], dp2[c], dp3[c] )
    dp1=[0]*(C+1)
    dp2=[0]*(C+1)
    dp3=[0]*(C+1)

print dp0[C]

Solution (Python):

import sys
from collections import defaultdict
R,C,K=map(int, sys.stdin.readline().split())

value=defaultdict(lambda: 0)
value=[ [0 for _ in range(C+1)] for __ in range(R+1) ]
for _ in range(K):
    r,c,v=map(int, sys.stdin.readline().split())
    value[r][c]=v

dp0=[0]*(C+1)
dp1=[0]*(C+1)
dp2=[0]*(C+1)
dp3=[0]*(C+1)

for r in range(1,R+1):
    for c in range(1,C+1):
        
        if 0<value[r][c]:
            dp3[c]=max( dp3[c-1], dp2[c-1]+value[r][c] )
            dp2[c]=max( dp2[c-1], dp1[c-1]+value[r][c] )
            dp1[c]=max( dp1[c-1], dp0[c-1]+value[r][c], dp0[c]+value[r][c] )
            dp0[c]=max( dp0[c-1], dp0[c] )
        
        else:
            dp0[c]=max( dp0[c-1], dp0[c] )
            dp1[c]=max( dp1[c-1], dp1[c] )
            dp2[c]=max( dp2[c-1], dp2[c] )
            dp3[c]=max( dp3[c-1], dp3[c] )

    
    for c in range(1,C+1):
        dp0[c]=max( dp0[c], dp1[c], dp2[c], dp3[c] )
    dp1=[0]*(C+1)
    dp2=[0]*(C+1)
    dp3=[0]*(C+1)

print dp0[C]

Solution (Python):

import sys
from collections import defaultdict
R,C,K=map(int, sys.stdin.readline().split())

value=defaultdict(lambda: 0)
value=[ [0 for _ in range(C+1)] for __ in range(R+1) ]
for _ in range(K):
    r,c,v=map(int, sys.stdin.readline().split())
    value[r][c]=v

dp0=[0]*(C+1)
dp1=[0]*(C+1)
dp2=[0]*(C+1)
dp3=[0]*(C+1)



for r in range(1,R+1):
    for c in range(1,C+1):
        
        if 0<value[r][c]:
            dp3[c]=max( dp3[c-1], dp2[c-1]+value[r][c] )
            dp2[c]=max( dp2[c-1], dp1[c-1]+value[r][c] )
            dp1[c]=max( dp1[c-1], dp0[c-1]+value[r][c], dp0[c]+value[r][c] )
            dp0[c]=max( dp0[c-1], dp0[c] )
        
        else:
            dp0[c]=max( dp0[c-1], dp0[c] )
            dp1[c]=max( dp1[c-1], dp1[c] )
            dp2[c]=max( dp2[c-1], dp2[c] )
            dp3[c]=max( dp3[c-1], dp3[c] )

    
    for c in range(1,C+1):
        dp0[c]=max( dp0[c], dp1[c], dp2[c], dp3[c] )
    dp1=[0]*(C+1)
    dp2=[0]*(C+1)
    dp3=[0]*(C+1)

print dp0[C]

Solution (Python):

import sys
from collections import defaultdict
R,C,K=map(int, sys.stdin.readline().split())

value=defaultdict(lambda: 0)
value=[ [0 for _ in range(C+1)] for __ in range(R+1) ]
for _ in range(K):
    r,c,v=map(int, sys.stdin.readline().split())
    value[r][c]=v

dp0=[0]*(C+1)
dp1=[0]*(C+1)
dp2=[0]*(C+1)
dp3=[0]*(C+1)



for r in range(1,R+1):
    for c in range(1,C+1):
        dp0[c]=max( dp0[c-1], dp0[c] )
        dp1[c]=max( dp1[c-1], dp1[c] )
        dp2[c]=max( dp2[c-1], dp2[c] )
        dp3[c]=max( dp3[c-1], dp3[c] )
        
        if 0<value[r][c]:
            dp3[c]=max( dp3[c-1], dp2[c]+value[r][c] )
            dp2[c]=max( dp2[c-1], dp1[c]+value[r][c] )
            dp1[c]=max( dp1[c-1], dp0[c]+value[r][c] )

    
    for c in range(1,C+1):
        dp0[c]=max( dp0[c], dp1[c], dp2[c], dp3[c] )
    dp1=[0]*(C+1)
    dp2=[0]*(C+1)
    dp3=[0]*(C+1)

print dp0[C]

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

r, c, k = map(int, input().split())
v = [[0]*(c+1) for i in range(r+1)]
for i in range(k):
    cr, cc, cv = map(int, input().split())
    v[cr][cc] = cv

dp = [[0]*4 for _ in range(c+1)]
last = [[0]*4 for _ in range(c+1)]
for cr in range(1, r+1):
    for cc in range(1, c+1):
        upper = max(last[cc][0], last[cc][1], last[cc][2], last[cc][3])
        dp[cc][0] = max(upper, dp[cc-1][0], dp[cc][0])
        dp[cc][1] = max(dp[cc-1][1], dp[cc-1][0]+v[cr][cc], upper+v[cr][cc])
        dp[cc][2] = max(dp[cc-1][2], dp[cc-1][1]+v[cr][cc])
        dp[cc][3] = max(dp[cc-1][3], dp[cc-1][2]+v[cr][cc])
        last = dp
print(max(dp[c]))

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

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

max_pre = [0]*(C+1)
for i in range(R+1):
    now = [[0]*(3+1) for _ in range(C+1)]
    for j in range(C+1):
        v = V[i][j]
        la = lb = 0
        if j > 0:
            la = now[j-1][0]
            lb = now[j-1][1]
            now[j][2] = max(now[j][2], now[j-1][2], lb + v)
            now[j][3] = max(now[j][3], now[j-1][3], now[j-1][2] + v)
        if i > 0:
            now[j][0] = max(now[j][0], max_pre[j], la)
            now[j][1] = max(now[j][1], max_pre[j] + v, la + v, lb)
        max_pre[j] = max(now[j])

print(max(now[C]))

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

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

max_p = [0]*(C+1)
for i in range(R+1):
    now0, now1, now2, now3 = [[0]*(C+1) for _ in range(4)]
    for j in range(C+1):
        v = V[i][j]
        la = lb = 0
        if j > 0:
            la = now0[j-1]
            lb = now1[j-1]
            now2[j] = max(now2[j], now2[j-1], lb + v)
            now3[j] = max(now3[j], now3[j-1], now2[j-1] + v)
        if i > 0:
            now0[j] = max(now0[j], max_p[j], la)
            now1[j] = max(now1[j], max_p[j] + v, la + v, lb)
        max_p[j] = max(now0[j], now1[j], now2[j], now3[j])

print(max(now0[C], now1[C], now2[C], now3[C]))

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

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

max_p = [0]*(C+1)
for i in range(R+1):
    now0 = [0]*(C+1)
    now1 = [0]*(C+1)
    now2 = [0]*(C+1)
    now3 = [0]*(C+1)
    for j in range(C+1):
        v = V[i][j]
        la = lb = 0
        if j > 0:
            la = now0[j-1]
            lb = now1[j-1]
            now2[j] = max(now2[j], now2[j-1], lb + v)
            now3[j] = max(now3[j], now3[j-1], now2[j-1] + v)
        if i > 0:
            now0[j] = max(now0[j], max_p[j], la)
            now1[j] = max(now1[j], max_p[j] + v, la + v, lb)
        max_p[j] = max(now0[j], now1[j], now2[j], now3[j])

print(max(now0[C], now1[C], now2[C], now3[C]))

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

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

pre0 = [0]*(C+1)
pre1 = [0]*(C+1)
pre2 = [0]*(C+1)
pre3 = [0]*(C+1)
for i in range(R+1):
    now0 = [0]*(C+1)
    now1 = [0]*(C+1)
    now2 = [0]*(C+1)
    now3 = [0]*(C+1)
    for j in range(C+1):
        v = V[i][j]
        la = lb = 0
        if j > 0:
            la = now0[j-1]
            lb = now1[j-1]
            now2[j] = max(now2[j], now2[j-1], lb + v)
            now3[j] = max(now3[j], now3[j-1], now2[j-1] + v)
        if i > 0:
            max_p = max(pre0[j], pre1[j], pre2[j], pre3[j])
            now0[j] = max(now0[j], max_p, la)
            now1[j] = max(now1[j], max_p + v, la + v, lb)
    pre0 = now0
    pre1 = now1
    pre2 = now2
    pre3 = now3

print(max(now0[C], now1[C], now2[C], now3[C]))

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

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

dp0 = [[0]*(C+1) for _ in range(R+1)]
dp1 = [[0]*(C+1) for _ in range(R+1)]
dp2 = [[0]*(C+1) for _ in range(R+1)]
dp3 = [[0]*(C+1) for _ in range(R+1)]
for i in range(R+1):
    for j in range(C+1):
        v = V[i][j]

        la = lb = lc = ld = 0
        if j > 0:
            la = dp0[i][j-1]
            lb = dp1[i][j-1]
            lc = dp2[i][j-1]
            ld = dp3[i][j-1]
            dp2[i][j] = max(dp2[i][j], lc, lb + v)
            dp3[i][j] = max(dp3[i][j], ld, lc + v)

        if i > 0:
            max_p = max(dp0[i-1][j], dp1[i-1][j], dp2[i-1][j], dp3[i-1][j])
            dp0[i][j] = max(dp0[i][j], max_p, la)
            dp1[i][j] = max(dp1[i][j], max_p + v, lb, la + v)

print(max(dp0[R][C], dp1[R][C], dp2[R][C], dp3[R][C]))

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

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

dp0 = [[0]*(C+1) for _ in range(R+1)]
dp1 = [[0]*(C+1) for _ in range(R+1)]
dp2 = [[0]*(C+1) for _ in range(R+1)]
dp3 = [[0]*(C+1) for _ in range(R+1)]
for i in range(R+1):
    for j in range(C+1):
        v = V[i][j]

        la = lb = lc = ld = 0
        if j > 0:
            la = dp0[i][j-1]
            lb = dp1[i][j-1]
            lc = dp2[i][j-1]
            ld = dp3[i][j-1]
            dp2[i][j] = max(dp2[i][j], lc, lb + v)
            dp3[i][j] = max(dp3[i][j], ld, lc + v)

        if i > 0:
            max_p = max(dp0[i-1][j], dp1[i-1][j], dp2[i-1][j], dp3[i-1][j])
            dp0[i][j] = max(dp0[i][j], max_p, la)
            dp1[i][j] = max(dp0[i][j], max_p + v, lb, la + v)

print(max(dp0[R][C], dp1[R][C], dp2[R][C], dp3[R][C]))

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

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

dp0 = [[0]*(C+1) for _ in range(R+1)]
dp1 = [[0]*(C+1) for _ in range(R+1)]
dp2 = [[0]*(C+1) for _ in range(R+1)]
dp3 = [[0]*(C+1) for _ in range(R+1)]
for i in range(R+1):
    for j in range(C+1):
        v = V[i][j]

        max_p = 0
        if i > 0:
            max_p = max(dp0[i-1][j], dp1[i-1][j], dp2[i-1][j], dp3[i-1][j])

        la = lb = lc = ld = 0
        if j > 0:
            la = dp0[i][j-1]
            lb = dp1[i][j-1]
            lc = dp2[i][j-1]
            ld = dp3[i][j-1]

        dp0[i][j] = max(dp0[i][j], max_p, la)
        dp1[i][j] = max(dp0[i][j], max_p + v, lb, la + v)
        dp2[i][j] = max(dp2[i][j], lc, lb + v)
        dp3[i][j] = max(dp3[i][j], ld, lc + v)


print(max(dp0[R][C], dp1[R][C], dp2[R][C], dp3[R][C]))

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

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

dp0 = [[0]*(C+1) for _ in range(R+1)]
dp1 = [[0]*(C+1) for _ in range(R+1)]
dp2 = [[0]*(C+1) for _ in range(R+1)]
dp3 = [[0]*(C+1) for _ in range(R+1)]
for i in range(R+1):
    for j in range(C+1):
        v = V[i][j]

        a = dp0[i][j]
        b = dp0[i][j]
        c = dp0[i][j]
        d = dp0[i][j]

        pa = pb = pc = pd = 0
        if i > 0:
            pa = dp0[i-1][j]
            pb = dp1[i-1][j]
            pc = dp2[i-1][j]
            pd = dp3[i-1][j]

        la = lb = lc = ld = 0
        if j > 0:
            la = dp0[i][j-1]
            lb = dp1[i][j-1]
            lc = dp2[i][j-1]
            ld = dp3[i][j-1]

        a = max(a, pa)
        b = max(b, pa+v)
        a = max(a, la)

        a = max(a, pb)
        b = max(b, pb+v)
        b = max(b, lb, la+v)

        a = max(a, pc)
        b = max(b, pc+v)
        c = max(c, lc, lb+v)

        a = max(a, pd)
        b = max(b, pd+v)
        d = max(d, ld, lc+v)

        dp0[i][j] = a
        dp1[i][j] = b
        dp2[i][j] = c
        dp3[i][j] = d

print(max(dp0[R][C], dp1[R][C], dp2[R][C], dp3[R][C]))

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

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

pre = [[0]*(3+1) for _ in range(C+1)]
for i in range(R+1):
    now = [[0]*(3+1) for _ in range(C+1)]
    for j in range(C+1):
        for k in range(3+1):
            if i-1 >= 0:
                now[j][0] = max(now[j][0], pre[j][k])
                now[j][1] = max(now[j][1], pre[j][k] + V[i][j])

            if j-1 >= 0:
                now[j][k] = max(now[j][k], now[j-1][k])
                if k-1 >= 0:
                    now[j][k] = max(now[j][k], now[j-1][k-1] + V[i][j])
    pre = now

print(max(now[C]))

Solution (Python):
R,C,K=map(int,input().split())
value=[[0]*(C+1) for i in range(R+1)]
for i in range(K):
  r,c,v=map(int,input().split())
  value[r][c]=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(1,R+1):
  for j in range(1,C+1):
    v=value[i][j]
    a=DP0[i][j-1]
    b=DP1[i][j-1]
    c=DP1[i-1][j]
    d=DP2[i-1][j]
    e=DP3[i-1][j]
    f=DP2[i][j-1]
    DP0[i][j]=max(a,c,d,e)
    DP1[i][j]=max(DP0[i-1][j]+v,c+v,d+v,e+v,b,a+v)
    DP2[i][j]=max(b+v,f)
    DP3[i][j]=max(f+v,DP3[i][j-1])

print(max(DP0[R][C],DP1[R][C],DP2[R][C],DP3[R][C]))

Solution (Python):
import sys
input=sys.stdin.readline
r,c,k=map(int,input().split())
l=[0]*((r+1)*(c+1))
for i in range(k):
  a1,a2,a3=map(int,input().split())
  l[a1*(c+1)+a2]=a3
dp0=[[0 for i in range(c+1)] for j in range(r+1)]
dp1=[[0 for i in range(c+1)] for j in range(r+1)]
dp2=[[0 for i in range(c+1)] for j in range(r+1)]
dp3=[[0 for i in range(c+1)] for j in range(r+1)]
for i in range(r):
  for j in range(c):
    x=l[i*(c+1)+j+1]
    y=l[(i+1)*(c+1)+j]
    dp3[i+1][j+1]=max(dp2[i][j+1]+x,dp3[i][j+1],dp2[i+1][j]+y,dp3[i+1][j])
    dp2[i+1][j+1]=max(dp2[i][j+1]+x,dp3[i][j+1],dp1[i+1][j]+y,dp2[i+1][j])
    dp1[i+1][j+1]=max(dp2[i][j+1]+x,dp3[i][j+1],dp0[i+1][j]+y,dp1[i+1][j])
    dp0[i+1][j+1]=max(dp2[i][j+1]+x,dp3[i][j+1],dp0[i+1][j])
z=l[r*(c+1)+c]
print(max(dp2[r][c]+z,dp3[r][c]))

Solution (Python):
from collections import defaultdict
import sys
input=sys.stdin.readline
r,c,k=map(int,input().split())
l=[0]*((r+1)*(c+1))
for i in range(k):
  a1,a2,a3=map(int,input().split())
  l[a1*(c+1)+a2]=a3
dp0=[[0 for i in range(c+1)] for j in range(r+1)]
dp1=[[0 for i in range(c+1)] for j in range(r+1)]
dp2=[[0 for i in range(c+1)] for j in range(r+1)]
dp3=[[0 for i in range(c+1)] for j in range(r+1)]
for i in range(r):
  for j in range(c):
    x=l[i*(c+1)+j+1]
    y=l[(i+1)*(c+1)+j]
    dp3[i+1][j+1]=max(dp2[i][j+1]+x,dp3[i][j+1],dp2[i+1][j]+y,dp3[i+1][j])
    dp2[i+1][j+1]=max(dp2[i][j+1]+x,dp3[i][j+1],dp1[i+1][j]+y,dp2[i+1][j])
    dp1[i+1][j+1]=max(dp2[i][j+1]+x,dp3[i][j+1],dp0[i+1][j]+y,dp1[i+1][j])
    dp0[i+1][j+1]=max(dp2[i][j+1]+x,dp3[i][j+1],dp0[i+1][j])
z=l[r*(c+1)+c]
print(max(dp2[r][c]+z,dp3[r][c]))

Solution (Python):
"""
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 i in range(R):
        for j in range(C):
            v = items[i][j]

            
            dp[j][0] = max(dp[j])
            if v:
                dp[j][1] = dp[j][0]+v
            
            
            if j > 0:
                for k in range(4):
                    
                    dp[j][k] = max(dp[j][k],dp[j-1][k])
                    if v and k>0:
                        dp[j][k] = max(dp[j][k],dp[j-1][k-1]+v)

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

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

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

for i in range(K):
  r,c,v = map(int, input().split())
  r -= 1
  c -= 1
  a[r][c] = v 
  
for i in range(R):
  for j in range(C):
    for k in range(2,-1,-1):
      dp[k+1][i][j] = max(dp[k+1][i][j], dp[k][i][j] + a[i][j])
    for k in range(4):
      dp[k][i][j+1] = max(dp[k][i][j+1], dp[k][i][j])
      dp[0][i+1][j] = max(dp[0][i+1][j], dp[k][i][j])
ans = 0
for k in range(4):
  ans = max(ans, dp[k][R-1][C-1])
  
print(ans)

Solution (Python):
from sys import stdin
input = stdin.readline
def main():
    R, C, K = map(int, input().split())
    items = [[0 for _ in range(C)] for _ in range(R)]
    for _ in range(K):
        r, c, v = map(int, input().split())
        items[r - 1][c - 1] = v
    dp = [[[0 for _ in range(C)] for _ in range(R)] for _ in range(4)]
    dp[1][0][0] = items[0][0]
    for r in range(R):
        for c in range(C):
            for i in range(4):
                tmp = dp[i][r][c]
                
                if c != C - 1:
                    
                    dp[i][r][c + 1] = max(dp[i][r][c+1], tmp)
                    
                    if i < 3:
                        dp[i+1][r][c + 1] = max(dp[i+1][r]
                                                [c + 1], tmp + items[r][c + 1])
                
                if r != R - 1:
                    
                    dp[0][r + 1][c] = max(dp[0][r + 1][c], tmp)
                    
                    dp[1][r + 1][c] = max(dp[1][r + 1][c],
                                          tmp + items[r + 1][c])
    ans = 0
    for i in range(4):
        ans = max(ans, dp[i][-1][-1])
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import numpy as np
from numba import njit, i8


@njit(i8[:](i8[:]), cache=True)
def max_acc(li):
    res = li.copy()
    cur_max = res[0]
    for i in range(len(li)):
        if res[i] > cur_max:
            cur_max = res[i]
        res[i] = cur_max
    return res


@njit(i8(i8, i8, i8[:, :]), cache=True)
def solve(R, C, goods):
    dp = np.zeros(C + 1, dtype=np.int64)
    for i in range(R):
        dp[1:] += goods[i]
        dp = max_acc(dp)
        for _ in range(2):
            dp[1:] = np.maximum(dp[:-1] + goods[i], dp[1:])
            dp = max_acc(dp)
    return dp[-1]


R, C, K, *rcv = map(int, open(0).read().split())
goods = np.zeros((R, C), dtype=np.int64)
for r, c, v in zip(*[iter(rcv)] * 3):
    goods[r - 1][c - 1] = v
print(solve(R, C, goods))

Solution (Python):
import sys
input = sys.stdin.readline
R, C, K = map(int, input().split())

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


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

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

        
        if j <= C - 1:
            
            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 + 1], dp[1][i][j])
            dp[2][i][j + 1] = max(dp[2][i][j + 1], dp[2][i][j])
            dp[3][i][j + 1] = max(dp[3][i][j + 1], dp[3][i][j])
            
            dp[1][i][j + 1] = max(dp[1][i][j + 1],
                                  dp[0][i][j] + item[i][j + 1])
            dp[2][i][j + 1] = max(dp[2][i][j + 1],
                                  dp[1][i][j] + item[i][j + 1])
            dp[3][i][j + 1] = max(dp[3][i][j + 1],
                                  dp[2][i][j] + item[i][j + 1])

ans = max(dp[0][R][C], dp[1][R][C], dp[2][R][C], dp[3][R][C])
print(ans)

Solution (Python):

import sys
def main(R, C, K, RCV):
    V = [[0] * C for _ in range(R)]
    for r, c, v in RCV:
        r, c = r - 1, c - 1
        V[r][c] = v
    dp = [[[0] * C for _ in range(R)] for __ in range(4)]
    dp[1][0][0] = V[0][0]
    for i in range(R):
        for j in range(C):
            for k in range(4):
                if j > 0:
                    dp[k][i][j] = max(dp[k][i][j], dp[k][i][j - 1])
                    if k > 0:
                        dp[k][i][j] = max(dp[k][i][j], dp[k - 1][i][j - 1] + V[i][j])
                if i > 0:
                    dp[0][i][j] = max(dp[0][i][j], dp[k][i - 1][j])
                    dp[1][i][j] = max(dp[1][i][j], dp[k][i - 1][j] + V[i][j])
    print(max(dp[k][R - 1][C - 1] for k in range(4)))

if __name__ == '__main__':
    input = sys.stdin.readline
    R, C, K = map(int, input().split())
    RCV = [list(map(int, input().split())) for _ in range(K)]
    main(R, C, K, RCV)

Solution (Python):
r, c, k = map(int, input().split())

dp = [[[0,0,0,0] for _j in range(c+1)] for _i in range(2)]
bord = [[0]*(c+1) for _i in range(r)]

for _i in range(k):
    _r, _c, _v = map(int, input().split())
    bord[_r-1][_c-1] = _v
            
for i in range(r):
    for j in range(c):
        dp[1][j][0] = max(dp[0][j])
        dp[1][j][1] = dp[1][j][0] + bord[i][j]
        for x in range(1, 4):
            dp[1][j][x] = max(
                dp[1][j][x],
                dp[1][j-1][x],
                dp[1][j-1][x-1]+bord[i][j],             
            )
    dp[0] = dp[1][::]

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