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):
from numpy import zeros, int64
from numba import njit

R, C, K, *RCV = map(int64, open(0).read().split())
V = zeros((R + 1, C + 1), int64)
for r, c, v in zip(*[iter(RCV)] * 3):
    V[r][c] = v

@njit
def main():
    dp = zeros((R + 1, C + 1, 4), int64)
    for i in range(1, R + 1):
        for j in range(1, C + 1):

            vij = V[i][j]

            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],
                    vij + dp[i][j][k - 1]
                )

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

main()

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):
            for w in range(4):
                dp[i][j][w] = max(dp[i][j - 1][w], dp[i - 1][j][3])
            if items[i][j] > 0:
                for w in range(2, -1, -1):
                    dp[i][j][w + 1] = max(dp[i][j][w + 1], dp[i][j][w] + items[i][j])

    return dp[r][c][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):
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):
            for w in range(4):
                dp[i, j, w] = max(dp[i, j - 1, w], dp[i - 1, j, 3])
            if items[i, j] > 0:
                for w in range(2, -1, -1):
                    dp[i, j, w + 1] = max(dp[i, j, w + 1], dp[i, j, w] + items[i, j])

    return dp[-1, -1, -1]


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):
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):
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):
            v = items[i, j]
            dp[i, j] = np.maximum(dp[i, j - 1], dp[i - 1, j, 3])
            if v > 0:
                dp[i, j, 1:] = np.maximum(dp[i, j, 1:], dp[i, j, :-1] + v)

    return dp[-1, -1, -1]


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):
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((c + 1, 4), dtype=np.int64)

    for i in range(1, r + 1):
        for j in range(1, c + 1):
            v = items[i][j]
            dp[j] = np.maximum(dp[j - 1], dp[j])
            if v > 0:
                dp[j, 1:] = np.maximum(dp[j, 1:], dp[j, :-1] + v)
        dp[:, 0] = dp[:, 1] = dp[:, 2] = dp[:, 3]

    return dp[-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):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def solve():
    dp0 = [0] * (w + 1)
    dp1 = [0] * (w + 1)
    dp2 = [0] * (w + 1)
    dp3 = [0] * (w + 1)
    for i in range(h):
        for j in range(w):
            v = vv[i * w + j]
            if v:
                dp3[j] = max(dp3[j], dp2[j] + v)
                dp2[j] = max(dp2[j], dp1[j] + v)
                dp1[j] = max(dp1[j], dp0[j] + v)
            dp3[j + 1] = max(dp3[j + 1], dp3[j])
            dp2[j + 1] = max(dp2[j + 1], dp2[j])
            dp1[j + 1] = max(dp1[j + 1], dp1[j])
            dp0[j] = max(dp1[j], dp2[j], dp3[j])
    print(dp0[-2])

h, w, k = MI()
vv = [0] * h * w
for _ in range(k):
    i, j, v = MI()
    i, j = i - 1, j - 1
    vv[i * w + j] = v
solve()

Solution (Python):
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())


def main():
    R, C, K = MI()
    item = [[0] * (C + 1) for i in range(R + 1)]

    for i in range(K):
        r_, c_, v_, = MI()
        item[r_ - 1][c_ - 1] = v_

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

    for i in range(R + 1):
        for j in range(C + 1):
            for k in range(4):
                a = dp[k][i][j]
                v = item[i][j]

                if k == 3:
                    dp[0][i + 1][j] = max(a, dp[0][i + 1][j])
                    continue
                dp[0][i + 1][j] = max(a, a + v, dp[0][i + 1][j])
                dp[k][i][j + 1] = max(a, dp[k][i][j + 1])
                dp[k + 1][i][j + 1] = max(a + v, dp[k + 1][i][j + 1])

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

if __name__ == "__main__":
    main()

Solution (Python):
import sys
import math
from collections import defaultdict
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def main():
    R, C, K = NMI()
    item = [[0] * (C + 1) for i in range(R + 1)]

    for i in range(K):
        r_, c_, v_, = NMI()
        item[r_ - 1][c_ - 1] = v_

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

    for i in range(R + 1):
        for j in range(C + 1):
            for k in range(4):
                a = dp[k][i][j]
                v = item[i][j]

                if k == 3:
                    dp[0][i + 1][j] = max(a, dp[0][i + 1][j])
                    continue
                dp[0][i + 1][j] = max(a, a + v, dp[0][i + 1][j])
                dp[k][i][j + 1] = max(a, dp[k][i][j + 1])
                dp[k + 1][i][j + 1] = max(a + v, dp[k + 1][i][j + 1])

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

if __name__ == "__main__":
    main()

Solution (Python):
import sys
import math
from collections import defaultdict
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()
def make_grid_int(h, w, num): return [[int(num)] * w for _ in range(h)]
def main():
    R, C, K = NMI()
    grid = make_grid_int(R, C, 0)

    for i in range(K):
        r_, c_, v_, = NMI()
        grid[r_ - 1][c_ - 1] = v_

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

    for i in range(R + 1):
        for j in range(C + 1):
            for k in range(4):
                a = dp[k][i][j]
                try:
                    v = grid[i][j]
                except:
                    v = 0

                if k == 3:
                    dp[0][i + 1][j] = max(a, dp[0][i + 1][j])
                    continue
                dp[0][i + 1][j] = max(a, a + v, dp[0][i + 1][j])
                dp[k][i][j + 1] = max(a, dp[k][i][j + 1])
                dp[k + 1][i][j + 1] = max(a + v, dp[k + 1][i][j + 1])

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

if __name__ == "__main__":
    main()

Solution (Python):
import sys
import math
from collections import defaultdict
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid_int(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    R, C, K = NMI()
    grid = make_grid_int(R, C, 0)
    for i in range(K):
        r, c, v = NMI()
        grid[r-1][c-1] = v

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

    for r in range(R+1):
        for c in range(C+1):
            for i in range(4):
                now = dp[i][r][c]
                try:
                    val = grid[r][c]
                except:
                    val = 0

                if i == 3:
                    
                    dp[0][r + 1][c] = max(now, dp[0][r + 1][c])
                    continue

                
                dp[0][r+1][c] = max(now + val, dp[0][r+1][c])
                
                dp[0][r+1][c] = max(now, dp[0][r+1][c])
                
                dp[i+1][r][c+1] = max(now + val, dp[i+1][r][c+1])
                
                dp[i][r][c+1] = max(now, dp[i][r][c+1])

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


if __name__ == "__main__":
    main()

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


def main():
    h, w, k = map(int, input().split())
    values = np.zeros((h, w), dtype=np.int64)
    items = np.array([list(map(int, input().split())) for _ in range(k)])
    ys, xs, vs = items[:, 0] - 1, items[:, 1] - 1, items[:, 2]
    values[ys, xs] = vs

    DP = np.zeros(w + 1, dtype=np.int64)
    for line in values:
        DP[1:] += line
        DP = np.maximum.accumulate(DP)
        for _ in range(2):
            DP[1:] = np.maximum(DP[:-1] + line, DP[1:])
            DP = np.maximum.accumulate(DP)
    print(DP[-1])


if __name__ == "__main__":
    main()

Solution (Python):


import math

import itertools
from collections import deque
from collections import Counter
import heapq
from fractions  import gcd



r,c,k=map(int,input().split())
v=[[0]*c for _ in range(r)]
for i in range(k):
    ri,ci,val=map(int,input().split())
    v[ri-1][ci-1]=val
d=[[0]*(c*r) for _ in range(4)]
d[1][0]=v[0][0]
for i in range(1,c):
    d[1][i]=max(d[1][i-1],d[0][i-1]+v[0][i])
    d[2][i]=max(d[2][i-1],d[1][i-1]+v[0][i])
    d[3][i]=max(d[3][i-1],d[2][i-1]+v[0][i])
for i in range(c,r*c):
    m=0
    for j in range(4):
        m=max(m,d[j][i-c])
    cx=i%c
    rx=i//c
    d[0][i]=max(0,m)
    d[1][i]=max(d[1][i-1],m+v[rx][cx],v[rx][cx]+d[0][i-1]) if cx!=0 else max(0,v[rx][cx]+m)
    d[2][i]=max(d[2][i-1],v[rx][cx]+d[1][i-1]) if cx!=0 else 0
    d[3][i]=max(d[3][i-1],v[rx][cx]+d[2][i-1]) if cx!=0 else 0
ans=0
for j in range(4):
  ans=max(ans,d[j][r*c-1])
print(ans)

Solution (Python):
import sys
def main():
    input = sys.stdin.readline
    R, C, k = map(int, input().split())
    s = [[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())
        s[r][c] = v
    for i in range(R):
        for j in range(C):
            m = max(dp[0][i][j + 1], dp[1][i][j + 1], dp[2][i][j + 1], dp[3][i][j + 1])
            for k in range(4):
                if k == 0:
                    dp[k][i + 1][j + 1] = max(dp[k][i + 1][j], m)
                else:
                    dp[k][i + 1][j + 1] = max(dp[k][i + 1][j], dp[k - 1][i + 1][j] + s[i + 1][j + 1])
            dp[1][i + 1][j + 1] = max(dp[1][i + 1][j + 1], s[i + 1][j + 1] + m)
    print(max(dp[0][R][C], dp[1][R][C], dp[2][R][C], dp[3][R][C]))
if __name__ == "__main__":
    main()

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])

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

@jit
def main():
    R, C, K = map(int, input().split())
    scores = np.zeros((R,C), np.int64)
    for _ in range(K):
        r, c, v = map(int, input().split())
        scores[r-1][c-1] = v
    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] + scores[i-1][j-1])

    
    return dp[R][C][3]

print(main())

Solution (Python):
import sys
input=lambda:sys.stdin.readline().rstrip()
r,c,k=map(int,input().split())
dp=[[(c+1)*[0]for _ in range(r+1)]for _ in range(4)]
p=[c*[0]for _ in range(r)]
for _ in range(k):
  rr,cc,u=map(int,input().split())
  rr-=1
  cc-=1
  p[rr][cc]=u
ans=0
for j in range(1,r+1):
  for k in range(1,c+1):
    dp[0][j][k]=max(dp[0][j-1][k],dp[0][j][k-1])
    t=max(dp[0][j-1][k],dp[1][j-1][k],dp[2][j-1][k],dp[3][j-1][k])
    for i in range(1,4):
      dp[i][j][k]=max(dp[i][j][k],t,dp[i][j][k-1])
      if p[j-1][k-1]:
        dp[i][j][k]=max(dp[i][j][k],dp[i-1][j][k-1]+p[j-1][k-1],t+p[j-1][k-1])
      ans=max(ans,dp[i][j][k])
print(ans)

Solution (Python):
import sys
import numpy as np
from collections import defaultdict
from numba import njit
def input(): return sys.stdin.readline().rstrip()

@njit('i8[:](i8[:],i8[:,:])')
def koushin(dp,item):
    dptmp1 = np.copy(dp)
    dptmp2 = np.copy(dp)
    dptmp3 = np.copy(dp)
    for i in range(len(item)):
        dptmp3[item[i][0]:] = np.fmax(dptmp3[item[i][0]:], dptmp2[item[i][0]]+item[i][1])
        dptmp2[item[i][0]:] = np.fmax(dptmp2[item[i][0]:], dptmp1[item[i][0]]+item[i][1])
        dptmp1[item[i][0]:] = np.fmax(dptmp1[item[i][0]:], dp[item[i][0]]+item[i][1])
    return dptmp3

def main():
    R, C, K = map(int, input().split())
    items = defaultdict(list)
    for _ in range(K):
        r, c, v = map(int, input().split())
        items[r-1].append([c-1, v])
    dp = np.zeros(C, dtype='int64')
    for RR in range(R):
        if items[RR]==[]:
          continue
        items[RR].sort(key=lambda x: x[0])
        dp=koushin(dp,np.array(items[RR],dtype='int64'))
    print(dp[-1])


if __name__ == '__main__':
    main()

Solution (Python):
import sys
import numpy as np
from collections import defaultdict
from numba import njit
def input(): return sys.stdin.readline().rstrip()

@njit
def koushin(dp,item):
    dptmp1 = np.copy(dp)
    dptmp2 = np.copy(dp)
    dptmp3 = np.copy(dp)
    for i in range(len(item)):
        dptmp3[item[i][0]:] = np.fmax(dptmp3[item[i][0]:], dptmp2[item[i][0]]+item[i][1])
        dptmp2[item[i][0]:] = np.fmax(dptmp2[item[i][0]:], dptmp1[item[i][0]]+item[i][1])
        dptmp1[item[i][0]:] = np.fmax(dptmp1[item[i][0]:], dp[item[i][0]]+item[i][1])
    return dptmp3

def main():
    R, C, K = map(int, input().split())
    items = defaultdict(list)
    for _ in range(K):
        r, c, v = map(int, input().split())
        items[r-1].append([c-1, v])
    dp = np.zeros(C, dtype=int)
    for RR in range(R):
        if items[RR]==[]:
          continue
        items[RR].sort(key=lambda x: x[0])
        dp=koushin(dp,np.array(items[RR],dtype=int))
    print(dp[-1])


if __name__ == '__main__':
    main()

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

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n) 


def main():
    R, C, K = read_values()
    V = [0] * (R * C)
    for _ in range(K):
        r, c, v = read_values()
        r -= 1
        c -= 1
        V[r * C + c] = v
    
    dp = [[0] * (R * C) for _ in range(4)]
    for i in range(R * C):
        r = i // C
        c = i % C
        if c + 1 < C:
            
            for k in range(4):
                dp[k][i + 1]= max(dp[k][i + 1], dp[k][i])

            
            for k in range(3):
                dp[k + 1][i + 1] = max(dp[k + 1][i + 1], dp[k][i] + V[i])

        
        if r + 1 < R:
            for k in range(4):
                dp[0][i + C] = max(dp[0][i + C], dp[k][i] + (V[i] if k < 3 else 0))

    res = 0
    for k in range(4):
        res = max(res, dp[k][-1] + (V[-1] if k < 3 else 0))
    print(res)


if __name__ == "__main__":
    main()

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

    
    x = max(dp0[i-1][j], dp1[i-1][j], dp2[i-1][j], dp3[i-1][j])
    dp0[i][j] = max(dp0[i][j-1], x)
    if (i,j) in mat:
      m = mat[(i,j)]
      dp1[i][j] = max(dp1[i][j], x+m)
    else:
      dp1[i][j] = max(dp1[i][j], x)

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

Solution (Python):
R, C, K = map(int, input().split())
item = [[0]*(C+1) for _ in range(R+1)]
for _ in range(K):
    r, c, v = map(int, input().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 numpy as np
from numba import njit
def main():
    R, C, K = map(int, input().split())
    field = np.full((R+1,C+1), 0, dtype='int64')
    dpt = np.full((R+1,C+1,4), 0, dtype='int64')
    for i in range(K):
        r, c, v = map(int, input().split())
        field[r][c] = v
    dp(R, C, field, dpt)
    print(max(dpt[-1][-1]))

@njit('i4(i4,i4,i8[:,:],i8[:,:,:])', cache=True)
def dp(R, C, field, dpt):
    for r in range(1, R+1):
        for c in range(1, C+1):
            for taken in range(4):
                max_v = 0
                if taken == 0:
                    max_v = max(dpt[r-1][c])
                    max_v = max(dpt[r][c-1][0], max_v)
                elif taken == 1:
                    max_v = max(dpt[r][c-1][taken-1] + field[r][c],
                                dpt[r][c-1][taken],
                                max(dpt[r-1][c]) + field[r][c])
                else:
                    max_v = max(dpt[r][c-1][taken-1] + field[r][c],
                                dpt[r][c-1][taken])
                dpt[r][c][taken] = max_v
    return 1

if __name__ == '__main__':
    main()

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

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

    
    
    
    value = v[0][0]
    if value == 0:
        dp = [[0] * 4]
    else:
        dp = [[0, value, value, value]]
    for j in range(1, c):
        value = v[0][j]
        if value == 0:
            dp.append(dp[j-1])
            continue
        a = dp[j-1].copy()
        b = [0, a[0]+value, a[1]+value, a[2]+value]
        for k in range(1, 4):
            if a[k] < b[k]:
                a[k] = b[k]
        dp.append(a)

    
    for i in range(1, r):
        pre = dp[0][3]
        value = v[i][0]
        if value == 0:
            new_dp = [[pre] * 4]
        else:
            new_dp = [[pre, pre+value, pre+value, pre+value]]
        for j in range(1, c):
            value = v[i][j]
            if value == 0:
                a = new_dp[j-1].copy()
                b = [dp[j][3]] * 4
                for k in range(4):
                    if a[k] < b[k]:
                        a[k] = b[k]
                new_dp.append(a)
            else:
                a = new_dp[j-1].copy()
                pre = dp[j][3]
                b = [pre, pre+value, pre+value, pre+value]
                d = [a[0], a[0]+value, a[1]+value, a[2]+value]
                for k in range(4):
                    if a[k] < b[k]:
                        a[k] = b[k]
                    if a[k] < d[k]:
                        a[k] = d[k]
                new_dp.append(a)
        dp = new_dp

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

main()

Solution (Python):
def main():
  import sys
  input=sys.stdin.readline
  h,w,k=map(int,input().split())
  H=range(h)
  W=range(w)
  dp=[[[0]*w for j in H] for i in range(4)]
  for _ in range(k):
    r,c,v=map(int,input().split())
    dp[0][r-1][c-1]=v
  if dp[0][0][0]!=0:
    dp[1][0][0]=dp[0][0][0]
    dp[0][0][0]=0
  for y in H:
    for x in W:
      v=dp[0][y][x]
      dp[0][y][x]=0
      for i in range(4):
        if 0<x:
          if dp[i][y][x]<dp[i][y][x-1]:
            dp[i][y][x]=dp[i][y][x-1]
          if 0<i and v!=0 and dp[i][y][x]<dp[i-1][y][x-1]+v:
            dp[i][y][x]=dp[i-1][y][x-1]+v
        if 0<y:
          if dp[0][y][x]<dp[i][y-1][x]:
            dp[0][y][x]=dp[i][y-1][x]
          if v!=0 and dp[1][y][x]<dp[i][y-1][x]+v:
            dp[1][y][x]=dp[i][y-1][x]+v
  print(max([dp[i][h-1][w-1] for i in range(4)]))
main()

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

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def main():
    R, C, K = read_values()
    V = [0] * (R * C)
    for _ in range(K):
        r, c, v = read_values()
        r -= 1
        c -= 1
        V[r * C + c] = v
    
    dp = [0 for _ in range(R * C * 4)]
    for i in range(R * C):
        r = i // C
        c = i % C
        if c + 1 < C:
            
            for k in range(4):
                dp[4 * (i + 1) + k] = max(dp[4 * (i + 1) + k], dp[4 * i + k])

            
            for k in range(3):
                dp[4 * (i + 1) + k + 1] = max(dp[4 * (i + 1) + k + 1], dp[4 * i + k] + V[i])

        
        if r + 1 < R:
            for k in range(4):
                dp[4 * (i + C)] = max(dp[4 * (i + C)], dp[4 * i + k] + (V[i] if k < 3 else 0))

    res = 0
    for k in range(4):
        res = max(res, dp[4 * (R * C - 1) + k] + (V[-1] if k < 3 else 0))

    print(res)


if __name__ == "__main__":
    main()

Solution (Python):
import sys

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

grid = [[0 for _ in range(C+1)] for _ in range(R+1)]
for _ in range(K):
    r, c, v = map(int, sys.stdin.readline().split())
    grid[r][c] = 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(1, R+1):
    for c in range(1, C+1):
        
        dp0[r][c] = max((dp0[r][c-1], dp0[r-1][c], dp1[r-1][c], dp2[r-1][c], dp3[r-1][c]))
        dp1[r][c] = max(dp1[r][c-1], dp1[r][c])
        dp2[r][c] = max(dp2[r][c-1], dp2[r][c])
        dp3[r][c] = max(dp3[r][c-1], dp3[r][c])

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

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






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