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):
def main():
  import sys
  input = sys.stdin.readline

  r,c,k = map(int,input().split())
  b = [[0 for _ in range(c)] for _ in range(r)]
  for i in range(k):
    y,x,v = map(int,input().split())
    y -= 1
    x -= 1
    b[y][x] = v

  
  dp = [[0 for _ in range(4)] for _ in range(c+1)]
  for i in range(r):
    for j in range(c):
      
      for l in range(2,-1,-1):
        dp[j][l+1] = max(dp[j][l]+b[i][j],dp[j][l+1])
      
      for l in range(4):
        dp[j+1][l] = max(dp[j][l],dp[j+1][l])
        dp[j][0] = max(dp[j][l],dp[j][0])
  ans = 0
  for i in range(4):
    ans = max(dp[c-1][i],ans)
  print(ans)

main()

Solution (Python):
R,C,K=map(int,input().split())
l=[[0] * C for i in range(R)]
for i in range(K):
  a,b,c=map(int,input().split())
  a-=1
  b-=1
  l[a][b]=c
dp=[[0] * C for i in range(R)]
for i in range(R):
  kdp=[0]*4
  for j in range(C):
    if i>0:
      kdp[0]=max(kdp[0],dp[i-1][j])
    for k in range(2,-1,-1):
      kdp[k+1]=max(kdp[k+1],kdp[k]+l[i][j])
      dp[i][j]=max(dp[i][j],kdp[k+1])
print(dp[R-1][C-1])

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    H, W, k = map(int, input().split())
    grid = [[0] * W for _ in range(H)]
    for _ in range(k):
        r, c, v = map(int, input().split())
        grid[r - 1][c - 1] = v

    
    dp = [[[0] * W for _ in range(H)] for _ in range(4)]
    dp[1][0][0] = grid[0][0]
    for h in range(H):
        for w in range(W):
            for i in range(4):
                
                if h + 1 < H:
                    
                    dp[0][h + 1][w] = max(dp[0][h + 1][w], dp[i][h][w])
                    
                    dp[1][h + 1][w] = max(dp[1][h + 1][w], dp[i][h][w] + grid[h + 1][w])
                
                if w + 1 < W:
                    
                    dp[i][h][w + 1] = max(dp[i][h][w + 1], dp[i][h][w])
                    
                    if i + 1 < 4:
                        dp[i + 1][h][w + 1] = max(dp[i + 1][h][w + 1], dp[i][h][w] + grid[h][w + 1])
    res = 0
    for i in range(4):
        res = max(res, dp[i][-1][-1])
    print(res)


if __name__ == '__main__':
    resolve()

Solution (Python):
R,C,K=map(int,input().split())
l=[[0] * C for i in range(R)]
for i in range(K):
  a,b,c=map(int,input().split())
  a-=1
  b-=1
  l[a][b]=c
dp=[0]*C
for i in range(R):
  ndp=[0]*C
  kdp=[0]*4
  for j in range(0,C):
    kdp[0]=max(kdp[0],dp[j])
    for k in range(2,-1,-1):
      kdp[k+1]=max(kdp[k+1],kdp[k]+l[i][j])
    ndp[j]=max(kdp)
  dp=ndp
print(dp[C-1])

Solution (Python):
import sys

R, C, K = map(int, sys.stdin.readline().split())

grid = [[0 for _ in range(C)] for _ in range(R)]
for _ in range(K):
    r, c, v = map(int, sys.stdin.readline().split())
    grid[r-1][c-1] = v


dp0 = [[0 for _ in range(C+1)] for _ in range(R+1)]
dp1 = [[0 for _ in range(C+1)] for _ in range(R+1)]
dp2 = [[0 for _ in range(C+1)] for _ in range(R+1)]
dp3 = [[0 for _ in range(C+1)] for _ in range(R+1)]

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

        if grid[r][c] == 0:
            continue
        
        dp0[r+1][c] = max(dp0[r][c] + grid[r][c], dp0[r+1][c])
        dp0[r+1][c] = max(dp1[r][c] + grid[r][c], dp0[r+1][c])
        dp0[r+1][c] = max(dp2[r][c] + grid[r][c], dp0[r+1][c])

        dp1[r][c+1] = max(dp0[r][c] + grid[r][c], dp1[r][c+1])
        dp2[r][c+1] = max(dp1[r][c] + grid[r][c], dp2[r][c+1])
        dp3[r][c+1] = max(dp2[r][c] + grid[r][c], dp3[r][c+1])






print(dp0[R][C-1])

Solution (Python):
R,C,K=map(int,input().split())
l=[[0] * C for i in range(R)]
for i in range(K):
  a,b,c=map(int,input().split())
  a-=1
  b-=1
  l[a][b]=c
dp=[0]*C
for i in range(R):
  ndp=[0]*C
  kdp=[0]*4
  for j in range(0,C):
    kdp[0]=max(kdp[0],dp[j])
    for k in range(2,-1,-1):
      kdp[k+1]=max(kdp[k+1],kdp[k]+l[i][j])
    ndp[j]=max(kdp)
  dp=ndp
print(dp[C-1])

Solution (Python):
R,C,K=map(int,input().split())
l=[[0] * C for i in range(R)]
for i in range(K):
  a,b,c=map(int,input().split())
  a-=1
  b-=1
  l[a][b]=c
dp=[0]*C
for i in range(R):
  ndp=[0]*C
  kdp=[0]*4
  kdp[0]=dp[0]
  kdp[1]=l[i][0]+dp[0]
  ndp[0]=kdp[1]
  for j in range(1,C):
    kdp[0]=max(kdp[0],dp[j])
    for k in range(2,-1,-1):
      kdp[k+1]=max(kdp[k+1],kdp[k]+l[i][j])
    ndp[j]=max(kdp)
  dp=ndp
print(dp[C-1])

Solution (Python):
import sys
from itertools import islice


def resolve(in_):
    R, C, K = map(int, next(in_).split())
    _rcv = (map(int, line.split()) for line in islice(in_, K))

    R1 = R + 1
    C1 = C + 1
    R2 = R + 2
    C2 = C + 2
    limit_item = 3
    limit_item1 = limit_item + 1
    C2limit_item1 = C2 * limit_item1

    
    grid = [0] * (R2 * C2)
    for r, c, v in _rcv:
        
        grid[(r * C2) + c] = v

    
    
    dp = [0] * (R2 * C2 * limit_item1)
    
    dp[(1 * C2limit_item1) + (1 * limit_item1) + 1] = grid[(1 * C2) + 1]

    for i in range(1, R1):
        for j in range(1, C1):
            for k in range(limit_item1):
                
                current = dp[(i * C2limit_item1) + (j * limit_item1) + k]

                
                left = grid[(i * C2) + (j + 1)]
                
                dp[(i * C2limit_item1) + ((j + 1) * limit_item1) + k] = max(dp[(i * C2limit_item1) + ((j + 1) * limit_item1) + k], current)
                if k < limit_item:
                    
                    dp[(i * C2limit_item1) + ((j + 1) * limit_item1) + (k + 1)] = max(dp[(i * C2limit_item1) + ((j + 1) * limit_item1) + (k + 1)], left + current)

                
                top = grid[((i + 1) * C2) + j]
                
                dp[(i + 1) * C2limit_item1 + (j * limit_item1) + 0] = max(dp[(i + 1) * C2limit_item1 + (j * limit_item1) + 0], current)
                
                dp[(i + 1) * C2limit_item1 + (j * limit_item1) + 1] = max(dp[(i + 1) * C2limit_item1 + (j * limit_item1) + 1], top + current)
    
    return max(dp[(R * C2limit_item1) + (C * limit_item1):((R + 1) * C2limit_item1) + ((C + 1) * limit_item1)])


def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()

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

@jit
def solve():
    
    r,c,k = map(int,input().split())

    value = np.zeros((r,c), dtype=np.int64)
    for i in range(k):
        r_t,c_t,v_t = map(int,input().split())
        value[r_t-1][c_t-1] = v_t

    dp = np.zeros((r,c,4), dtype=np.int64)
    dp[0][0][0] = 0

    for i in range(r):
        for j in range(c):
            for m in range(4):
                if i + 1 < r:
                    dp[i+1][j][0] = max(dp[i+1][j][0],dp[i][j][m])
                if j + 1 < c:
                    dp[i][j+1][m] = max(dp[i][j+1][m],dp[i][j][m])
                if value[i][j] != 0 and m < 3:
                    if i + 1 < r:
                        dp[i+1][j][0] = max(dp[i+1][j][0],dp[i][j][m]+value[i][j])
                    if j + 1 < c:
                        dp[i][j+1][m+1] = max(dp[i][j+1][m+1],dp[i][j][m]+value[i][j])

    for m in range(2,-1,-1):
        dp[r-1][c-1][m+1] = max(dp[r-1][c-1][m+1],dp[r-1][c-1][m]+value[r-1][c-1])
    return max(dp[r-1][c-1])

print(solve())

Solution (Python):
import sys
input = sys.stdin.readline
R, L, K = map(int, input().split())
V = [0]*(R*L)
max2 = lambda x, y: x if x > y else y
for _ in range(K):
    r, c, v = map(int, input().split())
    V[(c-1)*R+(r-1)] = v
A, B, C, D = [[0]*(R+1) for _ in range(4)]
for i in range(L):
    for j in range(R):
        A[j] = max(A[j-1],B[j-1],C[j-1],D[j-1])
        v = V[i*R+j]
        if v != 0:
            D[j], C[j], B[j] = max2(C[j]+v,D[j]), max2(B[j]+v,C[j]), max2(A[j]+v,B[j])
print(max(A[-2],B[-2],C[-2],D[-2]))

Solution (Python):
import sys
input = sys.stdin.readline
R, L, K = map(int, input().split())
V = [0]*(R*L)
for _ in range(K):
    r, c, v = map(int, input().split())
    V[(c-1)*R+(r-1)] = v
A, B, C, D = [[0]*(R+1) for _ in range(4)]
for i in range(L):
    for j in range(R):
        A[j] = max(A[j-1],B[j-1],C[j-1],D[j-1])
        v = V[i*R+j]
        if v != 0:
            D[j], C[j], B[j] = max(C[j]+v,D[j]), max(B[j]+v,C[j]), max(A[j]+v,B[j])
print(max(A[-2],B[-2],C[-2],D[-2]))

Solution (Python):
import sys
mod=10**9+7 ; inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict 

sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  
  
from functools import lru_cache






h,w,k=map(int,input().split())

A=[[0]*w for i in range(h)]
dp=[[[0 for j in range(w)] for i in range(h)] for i in range(4)]

for s in sys.stdin.readlines():
    x,y,v=map(int,s.split())
    x-=1;y-=1
    A[x][y]=v
    
    
    
dp[1][0][0]=A[0][0]
for i in range(h):
    for j in range(w):
        for k in range(4):
            here=dp[k][i][j]
            if i<h-1:
                dp[0][i+1][j] = max(here,dp[0][i+1][j])
                dp[1][i+1][j] = max(here+A[i+1][j], dp[1][i+1][j])
            if j<w-1:
                dp[k][i][j+1] = max(dp[k][i][j+1], here)
                if k<=2:
                    dp[k+1][i][j+1]= max(dp[k+1][i][j+1],here+ A[i][j+1])
ans=0
for i in range(4):
    ans=max(ans, dp[i][-1][-1])
print(ans)

Solution (Python):
import sys

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

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

Solution (Python):
import sys
input = sys.stdin.readline
R, L, K = map(int, input().split())
V = [[0]*R for _ in range(L)]
for _ in range(K):
    r, c, v = map(int, input().split())
    V[c-1][r-1] = v
A, B, C, D = [[0]*(R+1) for _ in range(4)]
for i in range(L):
    for j in range(R):
        A[j] = max(A[j-1],B[j-1],C[j-1],D[j-1])
        v = V[i][j]
        if v != 0:
            D[j], C[j], B[j] = max(C[j]+v,D[j]), max(B[j]+v,C[j]), max(A[j]+v,B[j])
print(max(A[-2],B[-2],C[-2],D[-2]))

Solution (Python):
def max2(x,y):
    return x if x > y else y

R, L, K = map(int, input().split())
V = [[0]*R for _ in range(L)]
for _ in range(K):
    r, c, v = map(int, input().split())
    V[c-1][r-1] = v
A, B, C, D = [[0]*(R+1) for _ in range(4)]
for i in range(L):
    for j in range(R):
        A[j] = max(A[j-1], B[j-1], C[j-1], D[j-1])
        v = V[i][j]
        if v != 0:
            D[j], C[j], B[j] = max2(C[j] + v, D[j]), max2(B[j] + v, C[j]), max2(A[j] + v, B[j])

print(max(A[-2], B[-2], C[-2], D[-2]))

Solution (Python):
R, L, K = map(int, input().split())
V = [[0]*R for _ in range(L)]
for _ in range(K):
    r, c, v = map(int, input().split())
    V[c-1][r-1] = v
A, B, C, D = [[0]*(R+1) for _ in range(4)]
for i in range(L):
    for j in range(R):
        A[j] = max(A[j-1], B[j-1], C[j-1], D[j-1])
        v = V[i][j]
        if v != 0:
            D[j], C[j], B[j] = max(C[j] + v, D[j]), max(B[j] + v, C[j]), max(A[j] + v, B[j])

print(max(A[-2], B[-2], C[-2], D[-2]))

Solution (Python):

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

R, C, K = map(int, readline().split())
data = [[0]*(C+1) for _ in range(R+1)]
for _ in range(K):
    r,c,k = map(int,readline().split())
    data[r][c] = k
    
dp = [0]*(C+1)

for i in range(1,R+1):
    di = data[i]
    ndp = [0]*(C+1)
    kdp = [0]*4
    for j in range(1,C+1):
        kdp[0] = max(kdp[0],dp[j])
        for k in range(2,-1,-1):
            kdp[k+1] = max(kdp[k+1],kdp[k]+di[j])
        ndp[j] = max(kdp)
    dp = ndp
print(dp[C])

Solution (Python):

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

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

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

dp = [0] * (C+1)
dp[0] = 0

for i in range(1,R+1):
    ndp = [0] * (C+1)
    row = V[i]
    ldp = [0] * 4
    for j in range(1,C+1):
        
        ldp[0] = dp[j]
        for k in range(2,-1,-1):
            ldp[k+1] = max(ldp[k+1], ldp[k] + row[j]) 
        ndp[j] = max(ldp)
    dp = ndp
print(dp[C])

Solution (Python):
def max2(x,y):
    return x if x > y else y

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

dp = [[0]*4 for _ in range(R)]
for j in range(R):
    if V[0][j] != 0:
        dp[j][1] = max2(dp[j - 1][1], dp[j - 1][0]) + V[0][j]
    if j != 0:
        dp[j][0] = max2(dp[j - 1][1], dp[j - 1][0])
for i in range(1,C):
    for j in range(R):
        v = V[i][j]
        if v != 0:
            if dp[j][2] != 0:
                dp[j][3] = max2(dp[j][2] + v, dp[j][3])
            if dp[j][1] != 0:
                dp[j][2] = max2(dp[j][1] + v, dp[j][2])
            dp[j][1] = max2(v, dp[j][1])
        if j != 0:
            if v != 0:
                dp[j][1] = max2(max(dp[j - 1][k] for k in range(4)) + v, dp[j][1])
            dp[j][0] = max2(max(dp[j - 1][k] for k in range(4)), dp[j][0])
print(max(dp[-1]))

Solution (Python):
R,C,K= map(int,input().split(" "))
original=[[0]*(C+1) for i in range(R+1)]
for _ in range(K):
    r,c,v= map(int,input().split(" "))
    original[r][c]=v
d1=[[0]*(C+1) for i in range(R+1)]
d2=[[0]*(C+1) for i in range(R+1)]
d3=[[0]*(C+1) for i in range(R+1)]
for i in range(1,R+1):
    for j in range(1,C+1):
        curr= original[i][j]
        d1[i][j]=max(d1[i-1][j]+curr,d2[i-1][j]+curr,d3[i-1][j]+curr,d1[i][j-1],curr)
        d2[i][j]=max(d2[i][j-1],d1[i][j-1]+curr)
        d3[i][j]=max(d3[i][j-1],d2[i][j-1]+curr)
print(max(d1[-1][-1],d2[-1][-1],d3[-1][-1]))

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,m,k = inpl()
value = [[0 for _ in range(m)] for i in range(n)]
for _ in range(k):
    a,b,c = inpl()
    value[a-1][b-1] = c
dp = [0] * (4*(m+1)*(n+1))
def ind(i,j,k): 
    return 4*(m+1)*i + 4*j + k
for i in range(n):
    for j in range(m):
        for k in range(3)[::-1]:
            dp[ind(i,j,k+1)] = max(dp[ind(i,j,k+1)], dp[ind(i,j,k)] + value[i][j])
        for k in range(4):
            dp[ind(i+1,j,0)] = max(dp[ind(i+1,j,0)], dp[ind(i,j,k)])
            dp[ind(i,j+1,k)] = max(dp[ind(i,j+1,k)], dp[ind(i,j,k)])

mx = 0
for k in range(4):
    mx = max(mx, dp[ind(n-1,m-1,k)])
print(mx)

Solution (Python):
import sys
input=sys.stdin.readline
R,C,k=map(int,input().split())
A=[[0]*C for i in range(R)]
for i in range(k):
  r,c,v=map(int,input().split())
  A[r-1][c-1]=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=A[i-1][j-1]
    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]=max(dp0[i][j]+V,dp1[i][j-1])
    dp2[i][j]=max(dp1[i][j-1]+V,dp2[i][j-1])
    dp3[i][j]=max(dp2[i][j-1]+V,dp3[i][j-1])
print(max(dp0[-1][-1],dp1[-1][-1],dp2[-1][-1],dp3[-1][-1]))

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

r, c, k = map(int, input().split())
vals = [[0]*c for _ in range(r)]
for _ in range(k):
    x, y, v = map(int, input().split())
    vals[x-1][y-1] = v
dp = [[0]*4 for j in range(c)]
for j in range(c):
    if j > 0:
        for k in range(4):
            dp[j][k] = dp[j-1][k]
    if vals[0][j] > 0:
        for k in reversed(range(3)):
            if dp[j][k+1] < dp[j][k] + vals[0][j]:
                dp[j][k+1] = dp[j][k] + vals[0][j]
for i in range(1, r):
    tmp = [[max(dp[j]), 0, 0, 0] for j in range(c)]
    for j in range(c):
        if j > 0:
            for k in range(4):
                if tmp[j][k] < tmp[j-1][k]:
                    tmp[j][k] = tmp[j-1][k]
        if vals[i][j] > 0:
            for k in reversed(range(3)):
                if tmp[j][k+1] < tmp[j][k] + vals[i][j]:
                    tmp[j][k+1] = tmp[j][k] + vals[i][j]
    dp = tmp
print(max(dp[-1]))

Solution (Python):
import bisect
import collections
import copy
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
MOD = 10**9+7

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]*4 for _ in range(C)]
preview = [[0]*4 for _ in range(C)]

for i in range(R):
    for j in range(C):
        for k in range(1,4):
            
            if k == 1:
                if i != 0:
                    if j != 0:
                        dp[j][k] = max(dp[j-1][k], dp[j-1][k-1] + item[i][j], max(preview[j]) + item[i][j])
                    else:
                        dp[j][k] = max(0, 0 + item[i][j], max(preview[j]) + item[i][j])
                else:
                    if j != 0:
                        dp[j][k] = max(dp[j-1][k], dp[j-1][k-1] + item[i][j])
                    else:
                        dp[j][k] = max(0, 0 + item[i][j])


            else:
                if j != 0:
                    dp[j][k] = max(dp[j-1][k], dp[j-1][k-1] + item[i][j])
                else:
                    dp[j][k] = max(0, 0 + item[i][j])

            
    preview = dp
print(max(dp[C-1]))

Solution (Python):
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline




def main():
    R, C, K = map(int, input().split())
    A = [[0]*C for _ in range(R)]
    for i in range(K):
        r, c, v = map(int, input().split())
        r, c = r-1, c-1
        A[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(R):
        for j in range(C):
            dp3[i][j] = max(dp3[i][j], dp2[i][j]+A[i][j])
            dp2[i][j] = max(dp2[i][j], dp1[i][j]+A[i][j])
            dp1[i][j] = max(dp1[i][j], dp0[i][j]+A[i][j])

            dp3[i][j+1] = max(dp3[i][j+1], dp3[i][j])
            dp2[i][j+1] = max(dp2[i][j+1], dp2[i][j])
            dp1[i][j+1] = max(dp1[i][j+1], dp1[i][j])
            dp0[i][j+1] = max(dp0[i][j+1], dp0[i][j])

            dp0[i+1][j] = max(dp0[i+1][j], dp0[i][j])
            dp0[i+1][j] = max(dp0[i+1][j], dp1[i][j])
            dp0[i+1][j] = max(dp0[i+1][j], dp2[i][j])
            dp0[i+1][j] = max(dp0[i+1][j], dp3[i][j])
    
    print(max([dp0[R-1][C-1], dp1[R-1][C-1], dp2[R-1][C-1], dp3[R-1][C-1]]))

if __name__ == '__main__':
    main()

Solution (Python):



import sys
input = sys.stdin.buffer.readline

def main():
    R, C, K = map(int, input().split())
    A = [[0]*C for _ in range(R)]
    for i in range(K):
        r, c, v = map(int, input().split())
        r, c = r-1, c-1
        A[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(R):
        for j in range(C):
            dp3[i][j] = max(dp3[i][j], dp2[i][j]+A[i][j])
            dp2[i][j] = max(dp2[i][j], dp1[i][j]+A[i][j])
            dp1[i][j] = max(dp1[i][j], dp0[i][j]+A[i][j])

            dp3[i][j+1] = max(dp3[i][j+1], dp3[i][j])
            dp2[i][j+1] = max(dp2[i][j+1], dp2[i][j])
            dp1[i][j+1] = max(dp1[i][j+1], dp1[i][j])
            dp0[i][j+1] = max(dp0[i][j+1], dp0[i][j])

            dp0[i+1][j] = max(dp0[i+1][j], dp0[i][j])
            dp0[i+1][j] = max(dp0[i+1][j], dp1[i][j])
            dp0[i+1][j] = max(dp0[i+1][j], dp2[i][j])
            dp0[i+1][j] = max(dp0[i+1][j], dp3[i][j])
    
    print(max([dp0[R-1][C-1], dp1[R-1][C-1], dp2[R-1][C-1], dp3[R-1][C-1]]))

if __name__ == '__main__':
    main()

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

r, c, k = LI()
maze = [[0] * (c+1) for _ in range(r+1)]
for _ in range(k):
    R, C, V = LI()
    maze[R][C] = V

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(1, r+1):
    for j in range(1, c+1):
        v = maze[i][j]
        dp1[i][j] = max(dp1[i][j-1], dp1[i-1][j] + v, dp2[i-1][j] + v, dp3[i-1][j] + v)
        dp2[i][j] = max(dp2[i][j-1], dp1[i][j-1] + v)
        dp3[i][j] = max(dp3[i][j-1], dp2[i][j-1] + v)
ans = max(dp1[-1][-1], dp2[-1][-1], dp3[-1][-1])
print(ans)

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

r, c, k = LI()
maze = [[0] * (c+1) for _ in range(r+1)]
for _ in range(k):
    R, C, V = LI()
    maze[R][C] = V

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(1, r+1):
    for j in range(1, c+1):
        dp1[i][j] = max(dp1[i][j-1], dp1[i-1][j] + maze[i][j], dp2[i-1][j] + maze[i][j], dp3[i-1][j] + maze[i][j])
        dp2[i][j] = max(dp2[i][j-1], dp1[i][j-1] + maze[i][j])
        dp3[i][j] = max(dp3[i][j-1], dp2[i][j-1] + maze[i][j])
ans = max(dp1[-1][-1], dp2[-1][-1], dp3[-1][-1])
print(ans)

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

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

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

for x in range(1, 4):
  dp[0][x] = items[0][0]
  for j in range(1, C):
    dp[j][x] = max(dp[j-1][x-1] + items[0][j], dp[j-1][x])




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

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

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


@jit
def main(r, c):
  dp = np.zeros((c+1, 4), np.int64)
  for i in range(r):
    new_dp = np.zeros((c+1, 4), np.int64)
    for j in range(4):
      new_dp[:,0] = np.maximum(new_dp[:,0], dp[:,j])
    dp = new_dp
    for k in range(c):
      for l in range(2, -1, -1):
        dp[k,l+1] = max(dp[k,l+1], dp[k,l]+item_map[i,k])
      for m in range(1,4):
        dp[k+1,m] = max(dp[k+1,m], dp[k,m])
  return max(dp[c-1,:])
 
R, C, K = map(int, input().split())
item_lis = list(list(map(int, input().split())) for i in range(K))
item_map = np.zeros((R, C), np.int64)
for i,j,k in item_lis:
  item_map[i-1,j-1] = k
 
print(main(R, C))

Solution (Python):
R, C, K = map(int, input().split())
grid = [[0]*C for _ in range(R)]
for i in range(K):
    r, c, v= map(int, input().split())
    grid[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 k in range(1,C+1):
        tmp = max(dp[0][i-1][k],dp[1][i-1][k],dp[2][i-1][k],dp[3][i-1][k])
        target = grid[i-1][k-1]
        dp[0][i][k] = max(dp[0][i][k-1],tmp)
        dp[1][i][k] = dp[1][i][k-1]
        dp[2][i][k] = dp[2][i][k-1]
        dp[3][i][k] = dp[3][i][k-1]
        if target != 0:
            dp[1][i][k] = max(dp[0][i][k-1]+target,tmp+target,dp[1][i][k])
            if dp[1][i][k-1] != 0:
                dp[2][i][k] = max(dp[1][i][k-1]+target,dp[2][i][k])
            if dp[2][i][k-1] != 0:
                dp[3][i][k] = max(dp[2][i][k-1]+target,dp[3][i][k])
print(max(dp[0][-1][-1],dp[1][-1][-1],dp[2][-1][-1],dp[3][-1][-1]))

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




def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))



def main():
	r,c,k=MI()
	G=[[0]*(c+1) for _ in range(r+1)]
	dp=[[0]*(c+1) for j in range(4)]
	for _ in range(k):
		rrr,ccc,v=MI()
		G[rrr][ccc]=v
	

	

	for rr in range(1,r+1):
		for cc in range(1,c+1):
			if G[rr][cc]==0:
				for i in range(4):
					dp[i][cc]=max(dp[i][cc-1],dp[3][cc])
			else:
				dp[0][cc]=max(dp[3][cc],dp[0][cc-1])
				dp[1][cc]=max(dp[0][cc]+G[rr][cc],dp[1][cc-1])
				dp[2][cc]=max(dp[1][cc-1]+G[rr][cc],dp[2][cc-1],dp[1][cc])
				dp[3][cc]=max(dp[2][cc-1]+G[rr][cc],dp[3][cc-1],dp[2][cc])
	
	print(dp[-1][-1])















if __name__ == "__main__":
	main()

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




def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))



def main():
	r,c,k=MI()
	G=[[0]*(c+1) for _ in range(r+1)]
	dp=[[[0]*(c+1) for i in range(r+1)] for j in range(4)]
	for _ in range(k):
		rrr,ccc,v=MI()
		G[rrr][ccc]=v
	

	

	for rr in range(1,r+1):
		for cc in range(1,c+1):
			if G[rr][cc]==0:
				for i in range(4):
					dp[i][rr][cc]=max(dp[i][rr][cc-1],dp[3][rr-1][cc])
			else:
				dp[0][rr][cc]=max(dp[3][rr-1][cc],dp[0][rr][cc-1])
				dp[1][rr][cc]=max(dp[0][rr][cc]+G[rr][cc],dp[1][rr][cc-1])
				dp[2][rr][cc]=max(dp[1][rr][cc-1]+G[rr][cc],dp[2][rr][cc-1],dp[1][rr][cc])
				dp[3][rr][cc]=max(dp[2][rr][cc-1]+G[rr][cc],dp[3][rr][cc-1],dp[2][rr][cc])
	
	print(dp[-1][-1][-1])















if __name__ == "__main__":
	main()

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

    
    dp0 = [0] * C
    dp1 = [0] * C
    dp2 = [0] * C
    dp3 = [0] * C

    for i in range(R):
        for j in range(C):
            ct = field[i][j]
            premax = max(dp0[j], dp1[j], dp2[j], dp3[j])

            if ct == 0:
                if j > 0:
                    dp0[j] = max(dp0[j - 1], premax)
                    dp1[j] = dp1[j - 1]
                    dp2[j] = dp2[j - 1]
                    dp3[j] = dp3[j - 1]
                else:
                    dp0[j] = premax

                
                
                
                




            
            
            
            
            
            
            
            
            
            
            else:
                if j > 0:
                    dp0[j] = max(dp0[j - 1], premax)
                    dp1[j] = max(ct + max(dp0[j - 1], premax), dp1[j - 1])
                    dp2[j] = max(dp1[j - 1] + ct, dp2[j - 1])
                    dp3[j] = max(dp2[j - 1] + ct, dp3[j - 1])
                else:
                    dp0[j] =premax
                    dp1[j] = premax+ct

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

if __name__ == "__main__":
    main()

Solution (Python):
import numpy as np
from numba import njit
R,C,K=map(int,input().split())
vl=np.zeros((R,C), np.int64)
for _ in range(K):
  r,c,v=map(int,input().split())
  vl[r-1][c-1]=v
@njit
def main():
  dp=np.zeros((R+1,C+1,4), np.int64)
  for i in range(1,R+1):
    for j in range(1,C+1):
      for k in range(4):
        dp[i][j][k]=max(dp[i][j-1][k],dp[i-1][j][3])
      for k in range(3,0,-1):
        dp[i][j][k]=max(dp[i][j][k],dp[i][j][k-1]+vl[i-1][j-1])
  return dp[R][C][3]
print(main())