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

class list2D:
    def __init__(self, H, W, num):
        self.__H = H
        self.__W = W
        self.__dat = [num] * (H * W)

    def __getitem__(self, a):
        return self.__dat[a[0]*self.__W+a[1]]

    def __setitem__(self, a, b):
        self.__dat[a[0]*self.__W+a[1]] = b

    def debug(self):
        print(self.__dat)

class list3D:
    def __init__(self, H, W, D, num):
        self.__H = H
        self.__W = W
        self.__D = D
        self.__X = W * D
        self.__dat = [num] * (H * W * D)

    def __getitem__(self, a):
        return self.__dat[a[0]*self.__X+a[1]*self.__D + a[2]]

    def __setitem__(self, a, b):
        self.__dat[a[0]*self.__X+a[1]*self.__D + a[2]] = b

    def debug(self):
        print(self.__dat)

def main():
    r,c,k=map(int,input().split())
    v = list2D(r, c, 0)

    for _ in range(k):
        ri,ci,a=map(int,input().split())
        v[ri-1, ci-1] = a

    dp = list3D(r, c, 4, 0)
    
    if v[0, 0]>0: dp[0, 0, 1]=v[0, 0]

    for i in range(r):
        for j in range(c):
            val = v[i, j]
            if i>0:
                x = max(dp[i-1, j, 0], dp[i-1, j, 1], dp[i-1, j, 2], dp[i-1, j, 3])
                dp[i, j, 1]=max(dp[i, j, 1],x+val)
                dp[i, j, 0]=max(dp[i, j, 0],x)

            if j>0:
                X = dp[i, j-1, 0]
                Y = dp[i, j-1, 1]
                V = dp[i, j-1, 2]
                Z = dp[i, j-1, 3]
                dp[i, j, 0]=max(dp[i, j, 0],X)
                dp[i, j, 1]=max(dp[i, j, 1],X+val,Y)
                dp[i, j, 2]=max(dp[i, j, 2],Y+val,V)
                dp[i, j, 3]=max(dp[i, j, 3],V+val,Z)

    
    ans=0
    for i in range(4): ans=max(dp[r-1, c-1, i],ans)
    return print(ans)
if __name__=="__main__":
    main()

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

class list2D:
    def __init__(self, H, W, num):
        self.__H = H
        self.__W = W
        self.__dat = [num] * (H * W)

    def __getitem__(self, a):
        return self.__dat[a[0]*self.__W+a[1]]

    def __setitem__(self, a, b):
        self.__dat[a[0]*self.__W+a[1]] = b

    def debug(self):
        print(self.__dat)

class list3D:
    def __init__(self, H, W, D, num):
        self.__H = H
        self.__W = W
        self.__D = D
        self.__dat = [num] * (H * W * D)

    def __getitem__(self, a):
        return self.__dat[a[0]*self.__W*self.__D+a[1]*self.__D + a[2]]

    def __setitem__(self, a, b):
        self.__dat[a[0]*self.__W*self.__D+a[1]*self.__D + a[2]] = b

    def debug(self):
        print(self.__dat)

def main():
    r,c,k=map(int,input().split())
    v = list2D(r, c, 0)

    for _ in range(k):
        ri,ci,a=map(int,input().split())
        v[ri-1, ci-1] = a

    dp = list3D(r, c, 4, 0)
    
    if v[0, 0]>0: dp[0, 0, 1]=v[0, 0]

    for i in range(r):
        for j in range(c):
            val = v[i, j]
            if i>0:
                x = max(dp[i-1, j, 0], dp[i-1, j, 1], dp[i-1, j, 2], dp[i-1, j, 3])
                dp[i, j, 1]=max(dp[i, j, 1],x+val)
                dp[i, j, 0]=max(dp[i, j, 0],x)

            if j>0:
                X = dp[i, j-1, 0]
                Y = dp[i, j-1, 1]
                V = dp[i, j-1, 2]
                Z = dp[i, j-1, 3]
                dp[i, j, 0]=max(dp[i, j, 0],X)
                dp[i, j, 1]=max(dp[i, j, 1],X+val,Y)
                dp[i, j, 2]=max(dp[i, j, 2],Y+val,V)
                dp[i, j, 3]=max(dp[i, j, 3],V+val,Z)

    
    ans=0
    for i in range(4): ans=max(dp[r-1, c-1, i],ans)
    return print(ans)
if __name__=="__main__":
    main()

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

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

    dp= [0] * (c * r * 4)

    
    x = c * r
    if v[0]>0: dp[x] = v[0]

    for i in range(r):
        for j in range(c):
            idx = i*c+j
            idx2 = (i-1)*c + j
            idx3 = i*c + j-1

            if i>0:
                a = max(dp[idx2],dp[x + idx2],dp[2*x+idx2],dp[3*x+idx2])+v[idx]
                dp[x+idx]=max(dp[x+idx], a)
                dp[idx]=max(dp[idx],dp[idx2],dp[x+idx2],dp[2*x+idx2],dp[3*x+idx2])

            if j>0:
                dp[idx]=max(dp[idx],dp[idx3])
                dp[x + idx]=max(dp[x + idx],dp[idx3]+v[idx],dp[x + idx3])
                dp[2*x + idx]=max(dp[2*x + idx],dp[x + idx3]+v[idx],dp[2*x + idx3])
                dp[3*x + idx]=max(dp[3*x + idx],dp[2*x + idx3]+v[idx],dp[3*x + idx3])

    
    ans=0
    for i in range(4): ans = max(dp[i*x + (r-1)*c + (c-1)],ans)
    return print(ans)

if __name__=="__main__":
    main()

Solution (Python):
import sys
input=sys.stdin.readline
def main():
    r,c,k=map(int,input().split())
    v=[0] * (c * r)
    for _ in range(k):
        ri,ci,a=map(int,input().split())
        v[(ri-1)*c + (ci-1)]=a
    dp= [0] * (c * r * 4)
    
    x = c * r
    if v[0]>0: dp[x] = v[0]

    for i in range(r):
        for j in range(c):
            idx = i*c+j
            idx2 = (i-1)*c + j
            idx3 = i*c + j-1
            if i>0:
                dp[x + idx] = max(dp[x + idx], dp[idx2]+v[idx])
                dp[idx] = max(dp[idx],dp[idx2])
                dp[x + idx]=max(dp[x + idx],dp[x + idx2]+v[idx])
                dp[idx]=max(dp[idx],dp[x + idx2])
                dp[x + idx]=max(dp[x + idx],dp[2*x + idx2]+v[idx])
                dp[idx]=max(dp[idx],dp[2*x + idx2])
                dp[x + idx]=max(dp[x + idx],dp[3*x + idx2]+v[idx])
                dp[idx]=max(dp[idx],dp[3*x + idx2])
            if j>0:
                dp[x + idx]=max(dp[x + idx],dp[idx3]+v[idx])
                dp[2*x + idx]=max(dp[2*x + idx],dp[x + idx3]+v[idx])
                dp[3*x + idx]=max(dp[3*x + idx],dp[2*x + idx3]+v[idx])
                dp[idx]=max(dp[idx],dp[idx3])
                dp[x + idx]=max(dp[x + idx],dp[x + idx3])
                dp[2*x + idx]=max(dp[2*x + idx],dp[2*x + idx3])
                dp[3*x + idx]=max(dp[3*x + idx],dp[3*x + idx3])

    
    ans=0
    for i in range(4): ans=max(dp[i*x + (r-1)*c + (c-1)],ans)
    return print(ans)

if __name__=="__main__":
    main()

Solution (Python):
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
R,C,K = ma()
V = [[0 for i in range(R+1)] for j in range(C+1)]
for i in range(K):
    r,c,v = ma()
    V[c][r] = v
dp_prev = [[0]*4 for i in range(C+1)]
dp_nex = [[0]*4 for i in range(C+1)] 
for r in range(1,R+1):
    for c in range(1,C+1):
        v = V[c][r]
        for k in range(4):
            if k==0:
                dp_nex[c][0] = max(dp_prev[c][3],dp_nex[c-1][0])
            elif k >0:
                dp_nex[c][k] = max(dp_nex[c-1][k],dp_nex[c-1][k-1]+v,dp_prev[c][3]+v)
    dp_prev,dp_nex = dp_nex,dp_prev
    


print(dp_prev[C][3])

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
from decimal import Decimal, ROUND_CEILING
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

R, C, K = MAP()

dp1 = [[0]*4 for _ in range(C+1)]
dp2 = [[0]*4 for _ in range(C+1)]

field = [[0]*(C+1)] + [[0]*(C+1) for _ in range(R)]

for _ in range(K):
    r, c, v = MAP()
    field[r][c] = v

for i in range(1, R+1):
    for j in range(1, C+1):
        if i%2 == 0:       
            up_max = max(dp1[j])
            p = field[i][j]
            dp2[j][0] = max(up_max, dp1[j-1][0])
            dp2[j][1] = max(up_max+p, dp2[j-1][1], dp2[j-1][0]+p)
            dp2[j][2] = max(dp2[j-1][2], dp2[j-1][1]+p)
            dp2[j][3] = max(dp2[j-1][3], dp2[j-1][2]+p)
        else:
            up_max = max(dp2[j])
            p = field[i][j]
            dp1[j][0] = max(up_max, dp2[j-1][0])
            dp1[j][1] = max(up_max+p, dp1[j-1][1], dp1[j-1][0]+p)
            dp1[j][2] = max(dp1[j-1][2], dp1[j-1][1]+p)
            dp1[j][3] = max(dp1[j-1][3], dp1[j-1][2]+p)

a = max(dp1[-1])
b = max(dp2[-1])
print(max(a, b))

Solution (Python):
import sys
input=sys.stdin.readline
def main():
    r,c,k=map(int,input().split())
    v=[[0]*c for _ in range(r)]
    for _ in range(k):
        ri,ci,a=map(int,input().split())
        ri-=1
        ci-=1
        v[ri][ci]=a
    dp=[[[0]*c for _ in range(r)] for i in range(4)]
    
    if v[0][0]>0:
        dp[1][0][0]=v[0][0]

    for i in range(r):
        for j in range(c):
            if i>0:
                dp[1][i][j]=max(dp[1][i][j],dp[0][i-1][j]+v[i][j])
                dp[0][i][j]=max(dp[0][i][j],dp[0][i-1][j])
                dp[1][i][j]=max(dp[1][i][j],dp[1][i-1][j]+v[i][j])
                dp[0][i][j]=max(dp[0][i][j],dp[1][i-1][j])
                dp[1][i][j]=max(dp[1][i][j],dp[2][i-1][j]+v[i][j])
                dp[0][i][j]=max(dp[0][i][j],dp[2][i-1][j])
                dp[1][i][j]=max(dp[1][i][j],dp[3][i-1][j]+v[i][j])
                dp[0][i][j]=max(dp[0][i][j],dp[3][i-1][j])
            if j>0:
                dp[1][i][j]=max(dp[1][i][j],dp[0][i][j-1]+v[i][j])
                dp[2][i][j]=max(dp[2][i][j],dp[1][i][j-1]+v[i][j])
                dp[3][i][j]=max(dp[3][i][j],dp[2][i][j-1]+v[i][j])
                dp[0][i][j]=max(dp[0][i][j],dp[0][i][j-1])
                dp[1][i][j]=max(dp[1][i][j],dp[1][i][j-1])
                dp[2][i][j]=max(dp[2][i][j],dp[2][i][j-1])
                dp[3][i][j]=max(dp[3][i][j],dp[3][i][j-1])
    
    ans=0
    for i in range(4):
        ans=max(dp[i][r-1][c-1],ans)
    return print(ans)
if __name__=="__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))


r,c,k = readints()
a = [[0]*(c+1) for i in range(r+1)]

for i in range(k):
    R,C,V = readints()
    a[R][C] = V

dp = [0]*(r+1)*(c+1)*4

for x in range((r+1)*(c+1)*4):
    i = x//((c+1)*4)
    l = x%((c+1)*4)
    j = l//4
    l %= 4
    if i==0 or j==0:
        continue
    if l==0:
        dp[x] = max(dp[i*(c+1)*4 + (j-1)*4], dp[(i-1)*(c+1)*4 + j*4 + 3])
    else:
        dp[x] = max(dp[i*(c+1)*4 + (j-1)*4 + l], dp[(i-1)*(c+1)*4 + j*4 + 3]+a[i][j], dp[i*(c+1)*4 + (j-1)*4 + l-1]+a[i][j])

print(dp[-1])

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

dp = [[0, 0, 0, 0] for _ in range(C)]
for r in range(R):
    for c in range(C):
        if c > 0:
            dp[c][0] = max(dp[c])
            dp[c][1] = dp[c - 1][1]
            dp[c][2] = dp[c - 1][2]
            dp[c][3] = dp[c - 1][3]
        else:
            dp[c][0] = max(dp[c])
            dp[c][1] = 0
            dp[c][2] = 0
            dp[c][3] = 0
        if v_list[r][c] > 0:
            v = v_list[r][c]
            dp[c][3] = max(dp[c][2] + v, dp[c][3])
            dp[c][2] = max(dp[c][1] + v, dp[c][2])
            dp[c][1] = max(dp[c][0] + v, dp[c][1])            
print(max(dp[-1]))

Solution (Python):
import sys,heapq
input = sys.stdin.buffer.readline
 
R,C,k = map(int,input().split())
 
 
val = dict()
for _ in range(k):
    rr,cc,vv = map(int,input().split())
    rr -= 1
    cc -= 1
    val[rr*C + cc] = vv
 
dp = [[0,0,0,0] for i in range(C)]
dp2 = [[0,0,0,0] for i in range(C)]

for i in range(R):
    for j in range(C):
        idx  = j
        if i*C + j in val:
            v = val[i*C + j]
        else:
            v = 0
        if i%2 == 0:
            if i == 0:
                if j == 0:
                    dp[idx][1] = v
                else:
                    dp[idx][1] = max(dp[idx-1][1],v)
                    dp[idx][2] = max(dp[idx-1][2],dp[idx-1][1] + v)
                    dp[idx][3] = max(dp[idx-1][3],dp[idx-1][2] + v)
            else:
                if j == 0:
                    dp[idx][0] = max(dp2[idx][0],dp2[idx][1],dp2[idx][2],dp2[idx][3])
                    dp[idx][1] = dp[idx][0] + v
                else:
                    dp[idx][0] = max(dp2[idx][0],dp2[idx][1],dp2[idx][2],dp2[idx][3],dp[idx-1][0])
                    dp[idx][1] = max(dp[idx-1][1],dp[idx][0] + v)
                    dp[idx][2] = max(dp[idx-1][2],dp[idx-1][1] + v)
                    dp[idx][3] = max(dp[idx-1][3],dp[idx-1][2] + v)
        else:
            if i == 0:
                if j == 0:
                    dp2[idx][1] = v
                else:
                    dp2[idx][1] = max(dp2[idx-1][1],v)
                    dp2[idx][2] = max(dp2[idx-1][2],dp2[idx-1][1] + v)
                    dp2[idx][3] = max(dp2[idx-1][3],dp2[idx-1][2] + v)
            else:
                if j == 0:
                    dp2[idx][0] = max(dp[idx][0],dp[idx][1],dp[idx][2],dp[idx][3])
                    dp2[idx][1] = dp2[idx][0] + v
                else:
                    dp2[idx][0] = max(dp[idx][0],dp[idx][1],dp[idx][2],dp[idx][3],dp2[idx-1][0])
                    dp2[idx][1] = max(dp2[idx-1][1],dp2[idx][0] + v)
                    dp2[idx][2] = max(dp2[idx-1][2],dp2[idx-1][1] + v)
                    dp2[idx][3] = max(dp2[idx-1][3],dp2[idx-1][2] + v)
 
print(max(max(dp[-1]),max(dp2[-1])))

Solution (Python):
import sys
input = sys.stdin.readline
def main(R,C,K,rcv):
  inf=float('inf')
  dp0=[[-inf,-inf,-inf,0] for _ in range(C)]
  item=[[0]*C for _ in range(R)]
  for r,c,v in rcv:
    item[r-1][c-1]=v
  
  for i in range(R):
    
    
    for j in range(C):
      if j>0:
        dp0[j][3]=max(dp0[j])
        dp0[j][0]=dp0[j-1][0]
        dp0[j][1]=dp0[j-1][1]
        dp0[j][2]=dp0[j-1][2]
      else:
        dp0[0][3]=max(dp0[0])
        dp0[0][2]=-inf
        dp0[0][1]=-inf
        dp0[0][0]=-inf 
      if item[i][j]>0:
        v=item[i][j]
        dp0[j][0]=max(dp0[j][0],dp0[j][1]+v)
        dp0[j][1]=max(dp0[j][1],dp0[j][2]+v)
        dp0[j][2]=max(dp0[j][2],dp0[j][3]+v)
  print(max(dp0[-1]))
if __name__=='__main__':
  R,C,K=map(int,input().split())
  rcv=[list(map(int,input().split())) for _ in range(K)]
  main(R,C,K,rcv)

Solution (Python):
import sys
input = sys.stdin.readline
def main(R,C,K,rcv):
  inf=float('inf')
  dp0=[[-inf,-inf,-inf,0] for _ in range(C)]
  item=[[0]*C for _ in range(R)]
  for r,c,v in rcv:
    item[r-1][c-1]=v
  
  for i in range(R):
    
    
    for j in range(C):
      dp0[j][3]=max(dp0[j])
      dp0[j][2]=-inf
      dp0[j][1]=-inf
      dp0[j][0]=-inf
    for j in range(C):
      if j>0:
        dp0[j][0]=max(dp0[j][0],dp0[j-1][0])
        dp0[j][1]=dp0[j-1][1]
        dp0[j][2]=dp0[j-1][2]
      if item[i][j]>0:
        v=item[i][j]
        dp0[j][0]=max(dp0[j][0],dp0[j][1]+v)
        dp0[j][1]=max(dp0[j][1],dp0[j][2]+v)
        dp0[j][2]=max(dp0[j][2],dp0[j][3]+v)
  print(max(dp0[-1]))
if __name__=='__main__':
  R,C,K=map(int,input().split())
  rcv=[list(map(int,input().split())) for _ in range(K)]
  main(R,C,K,rcv)

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

def main(R,C,K,rcv):
  inf=float('inf')
  dp0=[[-inf,-inf,-inf,0] for _ in range(C)]
  dp1=[[-inf]*4 for _ in range(C)]
  dp0[0][3]=0
  rcv.sort(key=lambda x:C*R*x[0]+x[1])
  i=0
  nowc=0
  while i<K and rcv[i][0]==1:
    nextc=rcv[i][1]-1
    for j in range(nowc+1,nextc+1):
      dp0[j][0]=dp0[nowc][0]
      dp0[j][1]=dp0[nowc][1]
      dp0[j][2]=dp0[nowc][2]
    v=rcv[i][2]
    dp0[nextc][0]=max(dp0[nextc][0],dp0[nextc][1]+v)
    dp0[nextc][1]=max(dp0[nextc][1],dp0[nextc][2]+v)
    dp0[nextc][2]=max(dp0[nextc][2],dp0[nextc][3]+v)
    i+=1
    nowc=nextc
    for j in range(nowc+1,C):
      dp0[j][0]=dp0[nowc][0]
      dp0[j][1]=dp0[nowc][1]
      dp0[j][2]=dp0[nowc][2]
  for j in range(1,R):
    for c in range(C):
      dp0[c][3]=max(dp0[c])
      dp0[c][2]=-inf
      dp0[c][1]=-inf
      dp0[c][0]=-inf
    nowc=0
    while i<K and rcv[i][0]==j+1:
      nextc=rcv[i][1]-1
      for k in range(nowc+1,nextc+1):
        dp0[k][0]=dp0[nowc][0]
        dp0[k][1]=dp0[nowc][1]
        dp0[k][2]=dp0[nowc][2]
      v=rcv[i][2]
      dp0[nextc][0]=max(dp0[nextc][0],dp0[nextc][1]+v)
      dp0[nextc][1]=max(dp0[nextc][1],dp0[nextc][2]+v)
      dp0[nextc][2]=max(dp0[nextc][2],dp0[nextc][3]+v)
      i+=1
      nowc=nextc
    for j in range(nowc+1,C):
      dp0[j][0]=dp0[nowc][0]
      dp0[j][1]=dp0[nowc][1]
      dp0[j][2]=dp0[nowc][2]
    

  print(max(dp0[-1]))


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

Solution (Python):
import sys
input = sys.stdin.readline
def main(R,C,K,rcv):
  inf=float('inf')
  dp0=[[-inf,-inf,-inf,0] for _ in range(C)]
  
  rcv.sort(key=lambda x:C*R*x[0]+x[1])
  i=0
  nowc=0
  for j in range(R):
    
    
    for c in range(C):
      dp0[c][3]=max(dp0[c])
      dp0[c][2]=-inf
      dp0[c][1]=-inf
      dp0[c][0]=-inf
    nowc=0
    while i<K and rcv[i][0]==j+1:
      nextc=rcv[i][1]-1
      for k in range(nowc+1,nextc+1):
        dp0[k][0]=max(dp0[k][0],dp0[nowc][0])
        dp0[k][1]=max(dp0[k][1],dp0[nowc][1])
        dp0[k][2]=max(dp0[k][2],dp0[nowc][2])
      v=rcv[i][2]
      dp0[nextc][0]=max(dp0[nextc][0],dp0[nextc][1]+v)
      dp0[nextc][1]=max(dp0[nextc][1],dp0[nextc][2]+v)
      dp0[nextc][2]=max(dp0[nextc][2],dp0[nextc][3]+v)
      i+=1
      nowc=nextc
    for k in range(nowc+1,C):
      dp0[k][0]=max(dp0[k][0],dp0[nowc][0])
      dp0[k][1]=max(dp0[k][1],dp0[nowc][1])
      dp0[k][2]=max(dp0[k][2],dp0[nowc][2])
    
  print(max(dp0[-1]))
if __name__=='__main__':
  R,C,K=map(int,input().split())
  rcv=[list(map(int,input().split())) for _ in range(K)]
  main(R,C,K,rcv)

Solution (Python):
f=lambda:map(int,input().split())
R,C,K=f()
g=[[0]*(C+1) for _ in range(R+1)]
for _ in range(K):
  r,c,v=f()
  g[r][c]=v
dp=[[[0]*(C+2) for _ in range(R+2)] for _ in range(4)]
for i in range(1,R+1):
  for j in range(1,C+1):
    for k in range(3,-1,-1):
      if k: dp[k][i][j]=max(dp[k][i][j],dp[k-1][i][j]+g[i][j])
      dp[0][i+1][j]=max(dp[0][i+1][j],dp[k][i][j])
      dp[k][i][j+1]=max(dp[k][i][j+1],dp[k][i][j])
print(max(dp[k][R][C] for k in range(4)))

Solution (Python):
f=lambda:map(int,input().split())
R,C,K=f()
g=[[0]*(C+1) for _ in range(R+1)]
for _ in range(K):
  r,c,v=f()
  g[r][c]=v
dp=[[[0]*(C+2) for _ in range(R+2)] for _ in range(4)]
for i in range(1,R+1):
  for j in range(1,C+1):
    for k in range(3,-1,-1):
      if k: dp[k][i][j]=max(dp[k][i][j],dp[k-1][i][j]+g[i][j])
      dp[0][i+1][j]=max(dp[0][i+1][j],dp[k][i][j])
      dp[k][i][j+1]=max(dp[k][i][j+1],dp[k][i][j])
print(max(dp[i][R][C] for i in range(4)))

Solution (Python):
def solve():
    R,C,K = map(int, input().split())
    
    dp = [[[0 for _ in range(C+1)] for _ in range (R+1)] for _ in range(5)]
    for _ in range(K):
        r,c,v = map(int, input().split())
        dp[4][r][c] = v

    
    

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

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

solve()

Solution (Python):
r,c,k=map(int,input().split())
a=[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 a:
    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,dp[0][i-1][j]+v,dp[1][i-1][j]+v,dp[2][i-1][j]+v,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):
import sys
input = sys.stdin.readline
R,C,K = map(int,input().split())
lis = [[0] * (C+1) for i in range(R+1)]
for _ in range(K):
    r,c,v = map(int,input().split())
    lis[r][c] = 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[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] + lis[i][j])

            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] + lis[i][j])




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

Solution (Python):
import numpy as np
from numba import jit


def test():
    R, C, K = map(int, input().split())
    rcv = [list(map(int, input().split())) for _ in range(K)]

    items = np.zeros((R+1, C+1), dtype='int64')
    for item in rcv:
        items[item[0]][item[1]] = item[2]

    dp = np.zeros((R+1, C+1), dtype='int64')

    
    for j in range(1, R+1):
        for i in range(1, C+1):
            
            dp[j][i] = max(dp[j][i], dp[j-1][i] + items[j][i])

            
            dp[j][i] = max(dp[j][i], dp[j][i-1] + items[j][i])

    print(dp[R][C])


@jit
def main(R, C, items):

    dp = np.zeros((4, R+1, C+1), dtype=np.int64)

    
    for i in range(1, R+1):
        for j in range(1, C+1):
            for k in range(4):
                
                
                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] + items[i][j])

                
                
                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] + items[i][j])

    ans = 0
    for k in range(4):
        if ans < dp[k][R][C]:
            ans = dp[k][R][C]

    print(ans)


if __name__ == "__main__":
    R, C, K = map(int, input().split())
    rcv = [list(map(int, input().split())) for _ in range(K)]
    items = np.zeros((R+1, C+1), dtype=np.int64)
    for item in rcv:
        items[item[0]][item[1]] = item[2]
    main(R, C, items)

Solution (Python):
import sys


def input():
    return sys.stdin.readline().rstrip()


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

    field = [[0 for j in range(C)] for i in range(R)]

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

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

    for i in range(R):
        for j in range(C):
            ct = field[i ][j ]
            pm = max(dp[0][i-1][j],dp[1][i-1][j],dp[2][i-1][j],dp[3][i-1][j])
            if ct == 0:
                dp[0][i][j] = max(dp[0][i][j-1],pm)

                for k in range(1, 4):
                    if j>0:
                        dp[k][i][j] = dp[k][i][j - 1]
            else:
                dp[0][i][j] = max(dp[0][i][j - 1],pm)
                dp[1][i][j] = max(ct + max(dp[0][i][j - 1], pm),dp[1][i][j-1])
                for k in range(2, 4):
                    if j >0:
                        dp[k][i][j] = max(dp[k - 1][i][j - 1] +ct,dp[k][i][j-1])

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

if __name__ == "__main__":
    main()

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

r, c, k = map(int, input().split())
v = [[0 for _ in range(c)] for _ in range(r)]

for i in range(k):
    rr, cc, vv = map(int, input().split())
    rr, cc = rr - 1, cc - 1
    v[rr][cc] = vv

dp = [[0 for _ in range(c + 1)] for _ in range(4)]
for y in range(r):
    tmp = [[0 for _ in range(c + 1)] for _ in range(4)]
    for x in range(c):
        for i in range(2, -1, -1):
            dp[i + 1][x] = max(dp[i + 1][x], dp[i][x] + v[y][x])
        for i in range(4):
            tmp[0][x] = max(tmp[0][x], dp[i][x])
            dp[i][x + 1] = max(dp[i][x + 1], dp[i][x])
    dp = tmp
print(dp[0][c - 1])

Solution (Python):
import sys
from itertools import product
input = lambda:sys.stdin.buffer.readline().rstrip()

m, n, k = map(int, input().split())
grid = [[0] * n for _ in range(m)]
for _ in range(k):
    i, j, v = map(int, input().split())
    i -= 1; j -= 1
    grid[i][j] = v

dp = [[0] * 4 for _ in range(n)]
for i in range(m):
    ndp = [[0] * 4 for _ in range(n)]
    for j, k in product(range(n), range(4)):
        
        ndp[j][0] = max(ndp[j][0], dp[j][k])
        ndp[j][1] = max(ndp[j][1], dp[j][k] + grid[i][j])
        
        if j > 0:
            ndp[j][k] = max(ndp[j][k], ndp[j - 1][k])
            if k > 0:
                ndp[j][k] = max(ndp[j][k], ndp[j - 1][k - 1] + grid[i][j])
    dp = ndp

print(max(dp[-1]))

Solution (Python):




import sys;      from decimal import Decimal
import math;     from itertools import combinations, product
import bisect;   from collections import Counter, deque, defaultdict


MOD = 10 ** 6 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def lcm(a: int, b: int) -> int: return (a * b) // math.gcd(a, b)

from numba import njit, i8
import numpy as np

@njit(i8(i8, i8, i8[:,:]))
def dp(R, C, grid):
    dp = np.zeros((R+1, C+1, 4), np.int64)
    for y in range(1, R+1):
        for x in range(1, C+1):
            for i in range(4):
                dp[y][x][i] = max(dp[y][x - 1][i], dp[y - 1][x][3])
            for i in range(3, 0, -1):
                dp[y][x][i] = max(dp[y][x][i], dp[y][x][i - 1] + grid[y-1][x-1])
    return dp[R][C][3]

def Main():
    R, C, k = read_ints()
    item = [read_int_list() for _ in range(k)]
    grid = np.zeros((R, C), np.int64)
    for r, c, v in item:
        grid[r - 1][c - 1] = v
    print(dp(R, C, grid))

if __name__ ==  '__main__':
    Main()

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

dp = [[[0] * C for _ in range(4)] for _ in range(R)]
dp[0][1][0] = goods[0][0]
for i in range(R):
    for j in range(4):
        for k in range(C):
            if i < R - 1:
                dp[i+1][0][k] = max(dp[i+1][0][k], dp[i][j][k])
                dp[i+1][1][k] = max(dp[i+1][1][k], dp[i][j][k] + goods[i+1][k])
        
            if k < C - 1:
                dp[i][j][k+1] = max(dp[i][j][k+1], dp[i][j][k])
                if j < 3:
                    dp[i][j+1][k+1] = max(dp[i][j+1][k+1], dp[i][j][k] + goods[i][k+1])

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

print(res)

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

dp = [[[0] * C for _ in range(4)] for _ in range(R)]
dp[0][1][0] = goods[0][0]
for i in range(R):
    for j in range(4):
        for k in range(C):
            if i < R - 1:
                dp[i+1][0][k] = max(dp[i+1][0][k], dp[i][j][k])
                dp[i+1][1][k] = max(dp[i+1][1][k], dp[i][j][k] + goods[i+1][k])
        
            if k < C - 1:
                dp[i][j][k+1] = max(dp[i][j][k+1], dp[i][j][k])
                if j < 3:
                    dp[i][j+1][k+1] = max(dp[i][j+1][k+1], dp[i][j][k] + goods[i][k+1])

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

Solution (Python):
R, C, K = map(int,input().split())
MAP = [[0 for i in range(C)] for j in range(R)]
DP = [[[0 for i in range(C+1)] for j in range(4)] for k in range(R+1)]
 
for _ in range(K):
    r, c, v = map(int,input().split())
    MAP[r-1][c-1] = v
 
for i in range(R):
    for j in range(4):
        for k in range(C):
            DP[i+1][j][k+1] = max(DP[i][3][k+1], DP[i+1][j][k])
            if j == 0:
                continue
            v = MAP[i][k]
            if v == 0:
                continue
            DP[i+1][j][k+1] = max(DP[i+1][j][k+1], max(DP[i][3][k+1], DP[i+1][j-1][k]) + v)

print(DP[R][3][C])