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 examA():
    S = SI()
    ans = 0
    if "R" in S:
        ans = 1
    if "RR" in S:
        ans = 2
    if "RRR" in S:
        ans = 3
    print(ans)
    return

def examB():
    N = I()
    L = LI()
    L.sort()
    cnt = 0
    for i in range(N):
        for j in range(i+1,N):
            for k in range(j+1,N):
                if L[i]==L[j]:
                    continue
                if L[j]==L[k]:
                    continue
                if L[i]+L[j]>L[k]:
                    cnt += 1
    ans = cnt
    print(ans)
    return

def examC():
    X, K, D = LI()
    if X<0:
        X = -X
    ans = inf
    if X>K*D:
        ans = X-K*D
        print(ans)
        return

    K -= X//D
    X -= D * (X//D)

    ans = X
    if K>0:
        if K%2==1:
            ans = abs(X-D)
    print(ans)
    return

def examD():
    N, K = LI()
    P = LI()
    C = LI()

    B = [i for i in range(N)]
    for i,p in enumerate(P):
        p -= 1
        B[i] = p

    locat_doubling = [[0]*N for _ in range(31)]
    score_doubling = [[0]*N for _ in range(31)]

    for i in range(N):
        locat_doubling[0][i] = i
        locat_doubling[1][B[i]] = i
        score_doubling[0][i] = 0
        score_doubling[1][B[i]] = C[i]
    for k in range(2,31):
        for i in range(N):
            locat_doubling[k][i] = locat_doubling[k-1][locat_doubling[k-1][i]]
            score_doubling[k][i] = score_doubling[k-1][i] + score_doubling[k - 1][locat_doubling[k - 1][i]]

    score = [[0,-inf] for i in range(N)]
    locate = [[i,i] for i in range(N)]
    ans = max(C)

    if ans<0:
        print(ans)
        return

    for k in range(30)[::-1]:
        for i in range(N):
            
            score[i][1] += score_doubling[k + 1][locate[i][1]]
            if score[i][1] < score[i][0]:
                locate[i][1] = locat_doubling[k + 1][locate[i][1]]
        if K&(1<<k)>0:
            for i in range(N):
                score[i][0] += score_doubling[k+1][locate[i][0]]
                locate[i][0] = locat_doubling[k+1][locate[i][0]]
    for s in score:
        ans = max(ans,s[0],s[1])
    print(ans)
    return

def examE():
    R, C, K = LI()
    V = [[-inf]*C for _ in range(R)]
    for _ in range(K):
        r,c,v = LI()
        V[r-1][c-1] = 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 r in range(R):
        for c in range(C):
            v = V[r][c]
            if 0<v:
                dp0[r+1][c+1] = max(dp0[r+1][c],dp0[r][c+1],dp1[r][c+1],dp2[r][c+1],dp3[r][c+1])
                dp1[r+1][c+1] = max(dp1[r+1][c],dp0[r+1][c]+v,dp0[r][c+1]+v,dp1[r][c+1]+v,dp2[r][c+1]+v,dp3[r][c+1]+v)
                dp2[r+1][c+1] = max(dp2[r+1][c],dp1[r+1][c]+v)
                dp3[r+1][c+1] = max(dp3[r+1][c],dp2[r+1][c]+v)
            else:
                dp0[r+1][c+1] = max(dp0[r+1][c],dp0[r][c+1],dp1[r][c+1],dp2[r][c+1],dp3[r][c+1])
                dp1[r+1][c+1] = dp1[r+1][c]
                dp2[r+1][c+1] = dp2[r+1][c]
                dp3[r+1][c+1] = dp3[r+1][c]

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

def examF():
    ans = 0
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examE()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


r,c,k = list(map(int, input().split()))
d = {}
for i in range(k):
    rr,cc,vv = list(map(int, input().split()))
    d[rr,cc] = vv
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(1, r+1):
    for j in range(1, c+1):
        dp0[i][j] = max(dp0[i][j-1], dp0[i-1][j], dp1[i-1][j], dp2[i-1][j], dp3[i-1][j])
        dp1[i][j] = dp1[i][j-1]
        dp2[i][j] = dp2[i][j-1]
        dp3[i][j] = dp3[i][j-1]
        if (i,j) in d:
            v = d[i,j]
            dp1[i][j] = max(dp1[i][j], dp0[i][j-1]+v, dp0[i-1][j]+v, dp1[i-1][j]+v,dp2[i-1][j]+v, dp3[i-1][j]+v)
            dp2[i][j] = max(dp2[i][j], dp1[i][j-1]+v)
            dp3[i][j] = max(dp3[i][j], dp2[i][j-1]+v)
ans = max(dp0[r][c], dp1[r][c], dp2[r][c], dp3[r][c])
print(ans)

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

X = [[0] * 4 for _ in range(R + 1)]
for i in range(1, C + 1):
    Vi = V[i]
    for j in range(1, R + 1):
        v = Vi[j]
        Xj = X[j]
        if v:
            Xj[3] = max(Xj[3], Xj[2] + v)
            Xj[2] = max(Xj[2], Xj[1] + v)
            Xj[0] = max(Xj[0], max(X[j-1]))
            Xj[1] = max(Xj[1], Xj[0] + v)
        else:
            Xj[0] = max(Xj[0], max(X[j-1]))

print(max(X[R]))

Solution (Python):
import os
import sys

import numpy as np


def solve(inp):
    r, c, k = inp[:3]
    items = np.zeros((r + 1, c + 1), dtype=np.int64)
    rrr = inp[3::3]
    ccc = inp[4::3]
    vvv = inp[5::3]
    for r_, c_, v in zip(rrr, ccc, vvv):
        items[r_][c_] = v

    dp = np.zeros((r + 1, c + 1, 4), dtype=np.int64)

    for i in range(1, r + 1):
        for j in range(1, c + 1):
            up = dp[i - 1][j][3]
            for w in range(4):
                dp[i][j][w] = max(dp[i][j - 1][w], up)
            v = items[i][j]
            if v == 0:
                continue
            for w in range(2, -1, -1):
                dp[i][j][w + 1] = max(dp[i][j][w + 1], dp[i][j][w] + v)

    return dp[-1][-1][3]


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print(ans)

Solution (Python):
def numba_compile(numba_config):
    import os, sys
    if sys.argv[-1] == "ONLINE_JUDGE":
        from numba import njit
        from numba.pycc import CC
        cc = CC("my_module")
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature)(func)
            cc.export(func.__name__, signature)(func)
        cc.compile()
        exit()
    elif os.name == "posix":
        exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
        for func, _ in numba_config:
            globals()[func.__name__] = vars()[func.__name__]
    else:
        from numba import njit
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature, cache=True)(func)
        print("compiled!", file=sys.stderr)

import numpy as np

def solve(R, C, K, RCV):
    
    M = np.zeros((R+1, C+1), dtype=np.int64)
    for i in range(K):
        r, c, v = RCV[i]
        M[r, c] = v
    dp = np.zeros((R+1, C+1, 4), dtype=np.int64)
    for y in range(1, R+1):
        for x in range(1, C+1):
            for n in range(4):
                if n == 0:
                    dp[y, x, n] = max(
                        dp[y, x-1, 0],
                        dp[y-1, x, :].max()
                    )
                if n > 0:
                    dp[y, x, n] = max(
                        dp[y, x-1, n],
                        dp[y, x-1, n-1] + M[y, x],
                        dp[y-1, x, :].max() + M[y, x]
                    )
    ans = dp[R, C].max()
    print(ans)

numba_compile([
    [solve, "(i8,i8,i8,i8[:,:])"],
])

import sys
def main():
    R, C, K = map(int, input().split())
    RCV = np.array(sys.stdin.read().split(), dtype=np.int64).reshape(K, 3)
    solve(R, C, K, RCV)

main()

Solution (Python):
def main():
    R, C, K = map(int, input().split())
    l = {}
    for _ in range(K):
        r, c, v = map(int, input().split())
        l[(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(1, R+1):
        for j in range(1, C+1):
            dp0[i][j] = max(dp0[i][j-1], dp0[i-1][j], dp1[i-1][j], dp2[i-1][j], dp3[i-1][j])
            if (i, j) in l:
                dp1[i][j] = max(dp1[i][j-1], l[(i, j)] + max(dp0[i-1][j], dp1[i-1][j], dp2[i-1][j], dp3[i-1][j], dp0[i][j-1]))
                dp2[i][j] = max(dp2[i][j-1], l[(i, j)] + dp1[i][j-1])
                dp3[i][j] = max(dp3[i][j-1], l[(i, j)] + dp2[i][j-1])
            else:
                dp1[i][j] = dp1[i][j-1]
                dp2[i][j] = dp2[i][j-1]
                dp3[i][j] = dp3[i][j-1]
    return max(dp0[-1][-1], dp1[-1][-1], dp2[-1][-1], dp3[-1][-1])

print(main())

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

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

items = [0] * R * C

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

dp = [0] * 4 * R * C

dp[1] = items[0]

def ind(i,j,k):
    return 4 * C * i + 4 * j + k

for row in range(R):
    for col in range(C):
        for pick in range(4):
            curr = dp[ind(row,col,pick)]
            
            if col + 1 < C:
                dp[ind(row,col+1,pick)] = max(curr, dp[ind(row,col+1,pick)])
                if pick < 3:
                    dp[ind(row,col+1,pick+1)] = max(curr + items[C * row + col+1], dp[ind(row,col+1,pick+1)])
            
            if row + 1 < R:
                dp[ind(row+1,col,0)] = max(curr, dp[ind(row+1,col,0)])
                dp[ind(row+1,col,1)] = max(curr + items[C * (row+1) + col], dp[ind(row+1,col,1)])
                    

print(max(dp))

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

R,C,K=map(int,input().split())
J=[tuple(map(int,input().split())) for i in range(K)]


DP1=[[0]*(C+2) for i in range(R+2)]
DP2=[[0]*(C+2) for i in range(R+2)]
DP3=[[0]*(C+2) for i in range(R+2)]

MAP=[[0]*C for i in range(R)]

for x,y,v in J:
    MAP[x-1][y-1]=v

for i in range(R):
    for j in range(C):
        DP1[i][j]=max(DP1[i][j-1],DP1[i-1][j]+MAP[i][j],DP2[i-1][j]+MAP[i][j],DP3[i-1][j]+MAP[i][j])
        DP2[i][j]=max(DP2[i][j-1],DP1[i][j-1]+MAP[i][j])
        DP3[i][j]=max(DP3[i][j-1],DP2[i][j-1]+MAP[i][j])

ANS=0
for i in range(R):
    for j in range(C):
        ANS=max(ANS,DP1[i][j],DP2[i][j],DP3[i][j])
print(ANS)

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

def main():
    r, c, k = map(int, input().split())
    item = [[0]*c for _ in range(r)]
    
    for i in range(k):
        a, b, v = map(int, input().split())
        item[a-1][b-1] = 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):
        for j in range(c):
            if item[i][j] == 0:
                dp0[i+1][j+1] = max([dp0[i][j+1], dp0[i+1][j], dp1[i][j+1], dp2[i][j+1], dp3[i][j+1]])
                dp1[i+1][j+1] = dp1[i+1][j]
                dp2[i+1][j+1] = dp2[i+1][j]
                dp3[i+1][j+1] = dp3[i+1][j]
                continue
            dp0[i+1][j+1] = max([dp0[i][j+1], dp0[i+1][j], dp1[i][j+1], dp2[i][j+1], dp3[i][j+1]])
            dp1[i+1][j+1] = max(dp0[i+1][j]+item[i][j], dp1[i+1][j], dp0[i][j+1]+item[i][j], dp1[i][j+1]+item[i][j], dp2[i][j+1]+item[i][j], dp3[i][j+1]+item[i][j])
            dp2[i+1][j+1] = max(dp1[i+1][j]+item[i][j], dp2[i+1][j])
            dp3[i+1][j+1] = max(dp2[i+1][j]+item[i][j], dp3[i+1][j])
    
    ans = max([dp0[r][c], dp1[r][c], dp2[r][c], dp3[r][c]])
    print(ans)
            
    
    
if __name__ == "__main__":
    main()

Solution (Python):


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

h,w,k,*hwk = map(int,read().split())
it = iter(hwk)
b = [[0]*w for _ in range(h+1)]
for hi,wi,ki in zip(it,it,it):
    b[hi-1][wi-1] = ki

dp = [[0]*4 for _ in range(w)]
for i in range(h):
    ndp = [[0]*4 for _ in range(w)]
    for j in range(w):
        if j != 0:
            ndp[j] = ndp[j-1][:]
        ndp[j][0] = max(ndp[j][0],max(dp[j]))
        
        
        for k in range(3,0,-1):
            ndp[j][k] = max(ndp[j][k],ndp[j][k-1]+ b[i][j])
        

    dp = ndp

print(max(dp[-1]))

Solution (Python):
import sys

sys.setrecursionlimit(500005)
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().strip()

R, C, K = na()
g = [[0] * C for _ in range(R)]
for i in range(K):
    r, c, v = na()
    g[r-1][c-1] = v

I = -9999999999999999999
dp = [I] * C
dp[0] = 0
for i in range(R):
    ndp = [I] * C
    row = g[i]
    ldp = [I] * 4
    for j in range(C):
        ldp[0] = max(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-1])

Solution (Python):
mod = 1000000007
eps = 10**-9
inf = 10**16


def main():
    import sys
    input = sys.stdin.buffer.readline

    H, W, K = map(int, input().split())
    grid = [[0] * W for _ in range(H)]
    for _ in range(K):
        h, w, v = map(int, input().split())
        grid[h-1][w-1] = v

    dp0 = [[-inf] * W for _ in range(H)]
    dp1 = [[-inf] * W for _ in range(H)]
    dp2 = [[-inf] * W for _ in range(H)]
    dp3 = [[-inf] * W for _ in range(H)]
    dp0[0][0] = 0
    if grid[0][0] > 0:
        dp1[0][0] = grid[0][0]
    for h in range(H):
        for w in range(W):
            if w-1 >= 0:
                dp0[h][w] = max(dp0[h][w], dp0[h][w-1])
                dp1[h][w] = max(dp1[h][w], dp1[h][w - 1])
                dp2[h][w] = max(dp2[h][w], dp2[h][w - 1])
                dp3[h][w] = max(dp3[h][w], dp3[h][w - 1])
            if h-1 >= 0:
                dp0[h][w] = max(dp0[h][w], dp0[h-1][w], dp1[h-1][w], dp2[h-1][w], dp3[h-1][w])
            v = grid[h][w]
            if v > 0:
                if w-1 >= 0:
                    dp1[h][w] = max(dp1[h][w], dp0[h][w - 1] + v)
                    dp2[h][w] = max(dp2[h][w], dp1[h][w - 1] + v)
                    dp3[h][w] = max(dp3[h][w], dp2[h][w - 1] + v)
                if h-1 >= 0:
                    dp1[h][w] = max(dp1[h][w], dp0[h-1][w] + v, dp1[h-1][w] + v, dp2[h-1][w]+v, dp3[h-1][w]+v)
    print(max(dp0[-1][-1], dp1[-1][-1], dp2[-1][-1], dp3[-1][-1]))


if __name__ == '__main__':
    main()

Solution (Python):
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

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

@njit((i8, i8, i8, i8[:]), cache=True)
def main(H, W, K, XYV):
    G = np.zeros((H + 1, W + 1), np.int64)
    for i in range(0, 3 * K, 3):
        x, y, v = XYV[i:i + 3]
        G[x - 1, y - 1] = v
    dp = np.zeros((W + 1, 4), np.int64)
    for h in range(H):
        newdp = np.zeros((W + 1, 4), np.int64)
        for n in range(4):
            newdp[:, 0] = np.maximum(newdp[:, 0], dp[:, n])
        dp = newdp
        for w in range(W):
            for n in range(2, -1, -1):
                
                dp[w, n + 1] = max(dp[w, n + 1], dp[w, n] + G[h, w])
            for n in range(4):
                dp[w + 1, n] = max(dp[w + 1, n], dp[w, n])
    return dp.max()

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

print(main(H, W, K, XYV))