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
def input(): return sys.stdin.readline().rstrip()

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


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

Solution (Python):



def next_line():
    return input()


def next_int():
    return int(input())


def next_int_array_one_line():
    return list(map(int, input().split()))


def next_int_array_multi_lines(size):
    return [int(input()) for _ in range(size)]


def next_str_array(size):
    return [input() for _ in range(size)]


def main():
    r, c, k = map(int, input().split())
    dp = [[[0] * (c+1) for i in range(r+1)] for i in range(4)]
    v = [[0] * (c+1) for i in range(r+1)]
    for i in range(k):
        row, col, val = map(int, input().split())
        v[row][col] = val

    for row in range(1, r + 1):
        for col in range(1, c + 1):
            for num in range(0, 4):
                if num == 0:
                    dp[num][row][col] = dp[3][row-1][col]  
                else:
                    
                    dp[num][row][col] = max(dp[num-1][row][col],  
                                            dp[num][row][col-1],  
                                            dp[3][row-1][col] + \
                                            v[row][col],  
                                            dp[num-1][row][col-1] + \
                                            v[row][col],  
                                            )
    print(dp[3][r][c])


if __name__ == '__main__':
    main()

Solution (Python):



def next_line():
    return input()


def next_int():
    return int(input())


def next_int_array_one_line():
    return list(map(int, input().split()))


def next_int_array_multi_lines(size):
    return [int(input()) for _ in range(size)]


def next_str_array(size):
    return [input() for _ in range(size)]


def main():
    r, c, k = map(int, input().split())
    dp = [[[0] * (c+1) for i in range(r+1)] for i in range(4)]
    v = [[0] * (c+1) for i in range(r+1)]
    for i in range(k):
        row, col, val = map(int, input().split())
        v[row][col] = val

    for row in range(1, r + 1):
        for col in range(1, c + 1):
            for num in range(0, 4):
                if num == 0:
                    dp[num][row][col] = dp[3][row-1][col]  
                else:
                    
                    dp[num][row][col] = max(dp[num-1][row][col],  
                                            dp[num][row][col-1],  
                                            dp[3][row-1][col] + \
                                            v[row][col],  
                                            dp[num-1][row][col-1] + \
                                            v[row][col],  
                                            )
    print(dp[3][r][c])


if __name__ == '__main__':
    main()

Solution (Python):



def next_line():
    return input()


def next_int():
    return int(input())


def next_int_array_one_line():
    return list(map(int, input().split()))


def next_int_array_multi_lines(size):
    return [int(input()) for _ in range(size)]


def next_str_array(size):
    return [input() for _ in range(size)]


def main():
    r, c, k = map(int, input().split())
    dp = [[[0] * (c+1) for i in range(r+1)] for i in range(4)]
    v = [[0] * (c+1) for i in range(r+1)]
    for i in range(k):
        row, col, val = map(int, input().split())
        v[row][col] = val

    for row in range(1, r + 1):
        for col in range(1, c + 1):
            for num in range(0, 4):
                if num == 0:
                    dp[num][row][col] = dp[3][row-1][col]  
                else:
                    
                    dp[num][row][col] = max(dp[num-1][row][col],  
                                            dp[num][row][col-1],  
                                            dp[3][row-1][col] + \
                                            v[row][col],  
                                            dp[num-1][row][col-1] + \
                                            v[row][col],  
                                            )
    print(dp[3][r][c])


if __name__ == '__main__':
    main()

Solution (Python):
def next_line():
    return input()


def next_int():
    return int(input())


def next_int_array_one_line():
    return list(map(int, input().split()))


def next_int_array_multi_lines(size):
    return [int(input()) for _ in range(size)]


def next_str_array(size):
    return [input() for _ in range(size)]


def main():
    r, c, k = map(int, input().split())
    dp = [[[0] * (c+1) for i in range(r+1)] for i in range(4)]
    v = [[0] * (c+1) for i in range(r+1)]
    for i in range(k):
        row, col, val = map(int, input().split())
        v[row][col] = val

    for row in range(1, r + 1):
        for col in range(1, c + 1):
            for num in range(0, 4):
                if num == 0:
                    dp[num][row][col] = dp[3][row-1][col]  
                else:
                    dp[num][row][col] = max(dp[num-1][row][col],  
                                            dp[num][row][col-1],  
                                            dp[3][row-1][col] + \
                                            v[row][col],  
                                            dp[num-1][row][col-1] + \
                                            v[row][col],  
                                            )
    print(dp[3][r][c])


if __name__ == '__main__':
    main()

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

R, C, K = map(int, input().split())
G = np.zeros((R+1, C+1), np.int64)
for i in range(K):
    [r, c, v] = list(map(int, input().split()))
    G[r-1][c-1] = v

@jit
def main(G, R, C):
    dp = np.full((R+1, C+1, 4), -1)
    dp[0][0][0] = 0
    if G[0][0] != None: dp[0][0][1] = G[0][0]
    for r in range(R):
        for c in range(C):
            for k in range(4):
                if dp[r][c][k] == -1: continue
                if k < 3: 
                    if dp[r][c+1][k+1] < dp[r][c][k] + G[r][c+1]:
                        dp[r][c+1][k+1] = dp[r][c][k] + G[r][c+1]
                if dp[r][c+1][k] < dp[r][c][k]:
                    dp[r][c+1][k] = dp[r][c][k]
                if dp[r+1][c][0] < dp[r][c][k]:
                    dp[r+1][c][0] = dp[r][c][k]
                if dp[r+1][c][1] < dp[r][c][k] + G[r+1][c]:
                    dp[r+1][c][1] = dp[r][c][k] + G[r+1][c]
    return(max(dp[r][c]))

ret = main(G, R, C)
print(ret)

Solution (Python):
def main():
    R, C, K = list(map(int, input().split()))
    
    dp_0 = [[0 for _ in range(C)] for _ in range(R)]
    dp_1 = [[0 for _ in range(C)] for _ in range(R)]
    dp_2 = [[0 for _ in range(C)] for _ in range(R)]
    dp_3 = [[0 for _ in range(C)] for _ in range(R)]
    V = [[0 for _ in range(C)] for _ in range(R)]
    for _ in range(K):
        r, c, v = list(map(int, input().split()))
        V[r - 1][c - 1] = v
    dp_1[0][0] = V[0][0]
    for r in range(R):
        for c in range(C):
            if r == c == 0:
                continue
            v_rc = V[r][c]
            max_dp_before_row = 0 if r == 0 else max(dp_0[r - 1][c], dp_1[r - 1][c], dp_2[r - 1][c], dp_3[r - 1][c])
            
            v1 = 0 if c == 0 else dp_0[r][c - 1]
            dp_0[r][c] = max(v1, max_dp_before_row)
            
            v1 = 0 if c == 0 else max(dp_1[r][c - 1], dp_0[r][c - 1] + v_rc)
            v2 = 0 if r == 0 else (max_dp_before_row + v_rc)
            dp_1[r][c] = max(v1, v2)
            
            dp_2[r][c] = 0 if c == 0 else max(dp_2[r][c - 1], dp_1[r][c - 1] + v_rc)
            dp_3[r][c] = 0 if c == 0 else max(dp_3[r][c - 1], dp_2[r][c - 1] + v_rc)
    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):


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

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

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

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

    
    dp = [[0] * 4 for _ in range(C + 1)]
    for i in range(1, R + 1):
        dp_next = [[0] * 4 for _ in range(C + 1)]
        for j in range(1, C + 1):
            up_max = max(dp[j])  
            v = Goods[i][j]

            
            dp_next[j][0] = max(up_max, dp_next[j - 1][0])
            
            dp_next[j][1] = max(up_max + v, dp_next[j - 1][0] + v, dp_next[j - 1][1])
            
            for k in range(2, 4):
                dp_next[j][k] = max(dp_next[j - 1][k - 1] + v, dp_next[j - 1][k])
        dp = dp_next  
    return max(dp[-1])

print(e_picking_goods())

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

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

dp = [[[0 for j in range(c)] for i in range(r)] for k in range(4)]

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


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

ans = 0

for k in range(4):
    ans = max(ans, dp[k][r-1][c-1])

print(ans)

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

input = sys.stdin.readline

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


@njit((i8, i8, i8[:, :]), cache=True)
def solve(R, C, table):
    dp0 = np.zeros((R + 1, C + 1), dtype=np.int64)
    dp1 = np.zeros((R + 1, C + 1), dtype=np.int64)
    dp2 = np.zeros((R + 1, C + 1), dtype=np.int64)
    dp3 = np.zeros((R + 1, C + 1), dtype=np.int64)

    for r in range(1, R + 1):
        for c in range(1, C + 1):
            m = max(dp0[r - 1, c], dp1[r - 1, c], dp2[r - 1, c], dp3[r - 1, c])
            dp0[r, c] = max(m, dp0[r, c - 1])
            dp1[r, c] = max(m, dp1[r, c - 1])
            dp2[r, c] = max(m, dp2[r, c - 1])
            dp3[r, c] = max(m, dp3[r, c - 1])
            if t := table[r, c]:
                dp1[r, c] = max(dp1[r, c], m + t, dp0[r, c - 1] + t)
                dp2[r, c] = max(dp2[r, c], m + t, dp1[r, c - 1] + t)
                dp3[r, c] = max(dp3[r, c], m + t, dp2[r, c - 1] + t)
    return max(dp0[-1, -1], dp1[-1, -1], dp2[-1, -1], dp3[-1, -1])


print(solve(R, C, table))

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

dp = [[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):
    dp_next = [[0]*4 for _ in range(C+1)]
    for j in range(1, C+1):
        up_max = max(dp[j])
        p = field[i][j]
        dp_next[j][0] = max(up_max, dp[j-1][0])
        dp_next[j][1] = max(up_max+p, dp_next[j-1][1], dp_next[j-1][0]+p)
        dp_next[j][2] = max(dp_next[j-1][2], dp_next[j-1][1]+p)
        dp_next[j][3] = max(dp_next[j-1][3], dp_next[j-1][2]+p)
    dp = dp_next

print(max(dp[-1]))

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

input = sys.stdin.readline

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


@njit((i8, i8, i8[:, :]), cache=True)
def solve(R, C, table):
    dp0 = np.zeros((R + 1, C + 1), dtype=np.int64)
    dp1 = np.zeros((R + 1, C + 1), dtype=np.int64)
    dp2 = np.zeros((R + 1, C + 1), dtype=np.int64)
    dp3 = np.zeros((R + 1, C + 1), dtype=np.int64)

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


print(solve(R, C, table))

Solution (Python):
import sys

input = sys.stdin.readline

R, C, K = map(int, input().split())
D = dict()
for _ in range(K):
    r, c, v = map(int, input().split())
    D[(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 r in range(1, R + 1):
    for c in range(1, C + 1):
        m = max(dp0[r - 1][c], dp1[r - 1][c], dp2[r - 1][c], dp3[r - 1][c])
        dp0[r][c] = max(m, dp0[r][c - 1])
        dp1[r][c] = max(m, dp1[r][c - 1])
        dp2[r][c] = max(m, dp2[r][c - 1])
        dp3[r][c] = max(m, dp3[r][c - 1])
        if (r, c) in D:
            dp1[r][c] = max(dp1[r][c], m + D[(r, c)], dp0[r][c - 1] + D[(r, c)])
            dp2[r][c] = max(dp2[r][c], m + D[(r, c)], dp1[r][c - 1] + D[(r, c)])
            dp3[r][c] = max(dp3[r][c], m + D[(r, c)], dp2[r][c - 1] + D[(r, c)])
print(max(dp0[-1][-1], dp1[-1][-1], dp2[-1][-1], dp3[-1][-1]))

Solution (Python):
r, c, k = map(int, input().split())
rcv = [list(map(int, input().split())) for i in range(k)]

area = [[0] * (c+1) for i in range(r+1)]
for a, b, v in rcv:
    area[a-1][b-1] = v



dp = [[[-1] * (c+1) for i in range(r+1)] for j in range(4)]
dp[0][0][0] = 0

for rr in range(r+1):
    for cc in range(c+1):
        for i in range(4):
            
            if i+1<4 and cc<c and area[rr][cc]>0:
                dp[i+1][rr][cc+1] = max(dp[i+1][rr][cc+1],
                                        dp[i][rr][cc]+area[rr][cc])
            
            if i+1<4 and rr<r and area[rr][cc]>0:
                dp[0][rr+1][cc] = max(dp[0][rr+1][cc],
                                      dp[i][rr][cc]+area[rr][cc])
            
            if cc<c:
                dp[i][rr][cc+1] = max(dp[i][rr][cc+1],
                                      dp[i][rr][cc])
            
            if rr<r:
                dp[0][rr+1][cc] = max(dp[0][rr+1][cc],
                                      dp[i][rr][cc])

ans = max([dp[i][r][c] for i in range(4)])
print(ans)

Solution (Python):
import sys
import copy
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())
    r -= 1
    c -= 1
    item[r][c] = v
    
dp0 = [[0] * (C+1) for r in range(R+1)]
dp1 = [[0] * (C+1) for r in range(R+1)]
dp2 = [[0] * (C+1) for r in range(R+1)]
dp3 = [[0] * (C+1) for r in range(R+1)]
 
for r in range(R):
   for c in range(C):
      dp3[r][c] = max(dp3[r][c], dp2[r][c] + item[r][c])
      dp2[r][c] = max(dp2[r][c], dp1[r][c] + item[r][c])
      dp1[r][c] = max(dp1[r][c], dp0[r][c] + item[r][c])
      dp1[r][c+1] = max(dp1[r][c], dp1[r][c+1])
      dp2[r][c+1] = max(dp2[r][c], dp2[r][c+1])
      dp3[r][c+1] = max(dp3[r][c], dp3[r][c+1])
      dp0[r+1][c] = max(dp0[r+1][c], dp1[r][c])
      dp0[r+1][c] = max(dp0[r+1][c], dp2[r][c])
      dp0[r+1][c] = max(dp0[r+1][c], dp3[r][c])
ans = max(dp0[R-1][C-1], dp1[R-1][C-1])
ans = max(ans, dp3[R-1][C-1])
ans = max(ans, dp2[R-1][C-1])
print(ans)

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

def main():
    r,c,k=map(int,input().split())
    dp=[[[0 for jj in range(c+1)] for ii in range(r+1)] for kk in range(4)]

    g=[[0 for j in range(c)] for i in range(r)]
    for i in range(k):
        rr,cc,v=map(int,input().split())
        rr-=1
        cc-=1
        g[rr][cc]=v
    for i in range(1,r+1):
        for j in range(1,c+1):
            for k in range(4):
                dp[k][i][j]=max(dp[k][i][j],dp[k][i][j-1])
                dp[0][i][j]=max(dp[0][i][j],dp[k][i-1][j])
                if g[i-1][j-1]>0:
                    if k>0:
                        if dp[k][i][j]<dp[k-1][i][j-1]+g[i-1][j-1]:
                            dp[k][i][j]=dp[k-1][i][j-1]+g[i-1][j-1]
                    if dp[1][i][j]<dp[k][i-1][j]+g[i-1][j-1]:
                        dp[1][i][j]=dp[k][i-1][j]+g[i-1][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 copy
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())
    r -= 1
    c -= 1
    item[r][c] = v
    
dp0 = [[0] * (C+1) for r in range(R+1)]
dp1 = [[0] * (C+1) for r in range(R+1)]
dp2 = [[0] * (C+1) for r in range(R+1)]
dp3 = [[0] * (C+1) for r in range(R+1)]

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

Solution (Python):



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

dp0 = [[0]*4 for c_ in range(3005)]
dp1 = [[0]*4 for c_ in range(3005)]

for i in range(r):
    for j in range(c):
        nowv = itm[i][j]
        dp0[j][3] = max(dp0[j][3], dp0[j][2] + nowv)
        dp0[j][2] = max(dp0[j][2], dp0[j][1] + nowv)
        dp0[j][1] = max(dp0[j][1], dp0[j][0] + nowv)

        dp0[j+1][0] = max(dp0[j+1][0], dp0[j][0])
        dp0[j+1][1] = max(dp0[j+1][1], dp0[j][1])
        dp0[j+1][2] = max(dp0[j+1][2], dp0[j][2])
        dp0[j+1][3] = max(dp0[j+1][3], dp0[j][3])

        dp1[j][0] = max(dp1[j][0], max(dp0[j]))
    dp0 = dp1.copy()

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

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







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 i in range(R + 1):
    for j in range(C + 1):
        
        
        now0 = dp0[i][j]
        now1 = dp1[i][j]
        now2 = dp2[i][j]
        now3 = dp3[i][j]

        
        if i <= R - 1:
            
            dp0[i + 1][j] = max(dp0[i + 1][j],
                                now0,
                                now1,
                                now2,
                                now3)

            
            dp1[i + 1][j] = max(dp1[i + 1][j],
                                now0 + item[i + 1][j],
                                now1 + item[i + 1][j],
                                now2 + item[i + 1][j],
                                now3 + item[i + 1][j])

        
        if j <= C - 1:
            
            dp0[i][j + 1] = max(dp0[i][j + 1],
                                now0)
            dp1[i][j + 1] = max(dp1[i][j + 1],
                                now1)
            dp2[i][j + 1] = max(dp2[i][j + 1],
                                now2)
            dp3[i][j + 1] = max(dp3[i][j + 1],
                                now3)

            
            dp1[i][j + 1] = max(dp1[i][j + 1],
                                now0 + item[i][j + 1])
            dp2[i][j + 1] = max(dp2[i][j + 1],
                                now1 + item[i][j + 1])
            dp3[i][j + 1] = max(dp3[i][j + 1],
                                now2 + item[i][j + 1])


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

print(ans)

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

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







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 i in range(R + 1):
    for j in range(C + 1):

        
        if i <= R - 1:
            
            dp0[i + 1][j] = max(dp0[i + 1][j],
                                dp0[i][j],
                                dp1[i][j],
                                dp2[i][j],
                                dp3[i][j])
            
            dp1[i + 1][j] = max(dp1[i + 1][j],
                                dp0[i][j] + item[i + 1][j],
                                dp1[i][j] + item[i + 1][j],
                                dp2[i][j] + item[i + 1][j],
                                dp3[i][j] + item[i + 1][j])

        
        if j <= C - 1:
            dp0[i][j + 1] = max(dp0[i][j + 1],
                                dp0[i][j])
            dp1[i][j + 1] = max(dp1[i][j + 1],
                                dp1[i][j])
            dp2[i][j + 1] = max(dp2[i][j + 1],
                                dp2[i][j])
            dp3[i][j + 1] = max(dp3[i][j + 1],
                                dp3[i][j])
            
            dp1[i][j + 1] = max(dp1[i][j + 1],
                                dp0[i][j] + item[i][j + 1])
            dp2[i][j + 1] = max(dp2[i][j + 1],
                                dp1[i][j] + item[i][j + 1])
            dp3[i][j + 1] = max(dp3[i][j + 1],
                                dp2[i][j] + item[i][j + 1])


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

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







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 i in range(R + 1):
    for j in range(C + 1):
        now0 = dp0[i][j]
        now1 = dp1[i][j]
        now2 = dp2[i][j]
        now3 = dp3[i][j]
        
        
        if i <= R - 1:
            
            dp0[i + 1][j] = max(dp0[i + 1][j],
                                now0,
                                now1,
                                now2,
                                now3)
            
            dp1[i + 1][j] = max(dp1[i + 1][j],
                                now0 + item[i + 1][j],
                                now1 + item[i + 1][j],
                                now2 + item[i + 1][j],
                                now3 + item[i + 1][j])

        
        
        if j <= C - 1:
            dp0[i][j + 1] = max(dp0[i][j + 1], now0)
            dp1[i][j + 1] = max(dp1[i][j + 1], now1)
            dp2[i][j + 1] = max(dp2[i][j + 1], now2)
            dp3[i][j + 1] = max(dp3[i][j + 1], now3)

            
            dp1[i][j + 1] = max(dp1[i][j + 1], now0 + item[i][j + 1])
            dp2[i][j + 1] = max(dp2[i][j + 1], now1 + item[i][j + 1])
            dp3[i][j + 1] = max(dp3[i][j + 1], now2 + item[i][j + 1])


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

Solution (Python):
import sys

inp = [int(x) for x in sys.stdin.read().split()]
ii = 0

r, c, k = inp[ii:ii+3]
ii += 3
v=[0] * (c * r)
for _ in range(k):
    ri,ci,a = inp[ii:ii+3]
    ii += 3
    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
        val = v[idx]
        if i>0:
            a = max(dp[idx2],dp[x + idx2],dp[2*x+idx2],dp[3*x+idx2])
            dp[idx]= a
            dp[x+idx]= a + val

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


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

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]=x+val
                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(Y+val,V)
                dp[i, j, 3]=max(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()