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 sys import stdin
readline = stdin.readline

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

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

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

print(max(cur))

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

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

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

n = [0] * (C + 1)
for i in range(R):
    c = [0] * 4
    c[0] = n[0]
    for j in range(C):
        if goods[i][j] != 0:
            for k in range(2, -1, -1):
                if c[k] + goods[i][j] > c[k + 1]:
                    c[k + 1] = c[k] + goods[i][j]
        for k in range(4):
            if c[k] > n[j]:
                n[j] = c[k]
        if n[j + 1] > c[0]:
            c[0] = n[j + 1]

print(max(c))

Solution (Python):
"""
dp[i][j]　=> i行目j列目がゴールの場合の最大値
"""
def main():
    import sys
    input = sys.stdin.readline
    R,C,K = map(int,input().split())
    items = [[0]*(C) for _ in range(R)]

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

    dp = [[0]*4 for _ in range(C)]
    dp[0][1] = items[0][0]
    for i in range(R):
        for j in range(C):
            v = items[i][j]
            if i==0 and j == 0:
                continue

            if i!=0:
                
                dp[j][0] = max(dp[j])
                if v:
                    dp[j][1] = dp[j][0]+v

            if j!=0:
                
                dp[j][0] = max(dp[j][0],dp[j-1][0])
                if v:
                    
                    for k in range(1,4):
                        dp[j][k] = max(dp[j][k],dp[j-1][k-1]+v,dp[j-1][k])
                else:
                    for k in range(1,4):
                        dp[j][k] = max(dp[j][k],dp[j-1][k])
    print(max(dp[-1]))
main()

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

dp=[[[0]*C for _ in range(R)] for _ in range(4)]
dp[1][0][0]=point[0][0]
for i in range(R):
    for j in range(C-1):
        for k in range(4):
            dp[k][i][j+1]=max(dp[k][i][j+1],dp[k][i][j])
            if k!=0:
                dp[k][i][j+1]=max(dp[k][i][j+1],dp[k-1][i][j]+point[i][j+1])
    if i==R-1:
        break
    for j in range(C):
        mx=0
        for k in range(4):
            mx=max(dp[k][i][j],mx)
        dp[0][i+1][j]=mx
        dp[1][i+1][j]=mx+point[i+1][j]
ans=0
for i in range(4):
    ans=max(ans,dp[i][R-1][C-1])
print(ans)

Solution (Python):
import numpy as np
import numba

@numba.njit("(i8,i8,i8,i8[:,:])", cache=True)
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)

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):
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):
H,W,k = map(int, input().split())

fs = [[0]*(W+1) for i in range(H+1)]
for i in range(k):
    h, w, v = map(int, input().split())
    h -= 1
    w -= 1
    fs[h][w] = v

mvs = [(0,1),(1,0)]
dp = [[[-1<<50 for i in range(W+1)] for j in range(H+1)] for k in range(4)]

from collections import deque
q = deque([])
q.append((0,0))
dp[0][0][0] = 0
dp[1][0][0] = fs[0][0]
for h in range(H):
    for w in range(W):
        dp[0][h][w+1] = max(dp[0][h][w+1], dp[0][h][w])
        dp[1][h][w+1] = max(dp[1][h][w+1], dp[1][h][w], dp[0][h][w] + fs[h][w+1])
        dp[2][h][w+1] = max(dp[2][h][w+1], dp[2][h][w], dp[1][h][w] + fs[h][w+1])
        dp[3][h][w+1] = max(dp[3][h][w+1], dp[3][h][w], dp[2][h][w] + fs[h][w+1])
    for w in range(W):
        mx = 0
        for i in range(4):
            
            mx = max(mx,dp[i][h][w])
        dp[0][h+1][w] = mx
        dp[1][h+1][w] = mx + fs[h+1][w]

H -= 1
W -= 1
ans0 = dp[0][H][W]
ans1 = dp[1][H][W]
ans2 = dp[2][H][W]
ans3 = dp[3][H][W]






print(max(ans1,ans2,ans3))

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

Solution (Python):
import sys

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

dp = [[[0] * (C + 1) for _ in range(R + 1)] for _ in range(4)]
for i in range(R):
    for j in range(C):
        for k in range(2, -1, -1):
            dp[k + 1][i][j] = max(dp[k + 1][i][j], dp[k][i][j] + xs[i][j])
        for k in range(4):
            dp[k][i][j + 1] = max(dp[k][i][j + 1], dp[k][i][j])
            dp[0][i + 1][j] = max(dp[0][i + 1][j], dp[k][i][j])
ans = 0
for k in range(4):
    ans = max(ans, dp[k][R - 1][C - 1])
print(ans)

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

dp = [[[0] * (C + 1) for _ in range(R + 1)] for _ in range(4)]
for i in range(R):
    for j in range(C):
        for k in range(2, -1, -1):
            dp[k + 1][i][j] = max(dp[k + 1][i][j], dp[k][i][j] + xs[i][j])
        for k in range(4):
            dp[k][i][j + 1] = max(dp[k][i][j + 1], dp[k][i][j])
            dp[0][i + 1][j] = max(dp[0][i + 1][j], dp[k][i][j])
ans = 0
for k in range(4):
    ans = max(ans, dp[k][R - 1][C - 1])
print(ans)

Solution (Python):


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

for r in range(R):

    ndp = [0] * C
    elm = [0] * 4
    for c in range(C):
        elm[0] = max(elm[0], dp[c])
        value = grids[r][c]
        if value:
            nelm = [0] * 4
            nelm[0] = elm[0]



            for i in range(3)[::-1]:
                nelm[i + 1] = max(elm[i + 1], elm[i] + value)



            elm = nelm
        ndp[c] = max(elm)
    dp = ndp
 

print(dp[-1])

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

dp = [[[0] * (C + 1) for _ in range(R + 1)] for _ in range(4)]
for cy in range(R + 1) :
  for cx in range(C + 1) :
    if cx < C :
      dp[0][cy][cx + 1] = max(dp[0][cy][cx + 1], dp[0][cy][cx])
      dp[1][cy][cx + 1] = max(dp[1][cy][cx + 1], dp[0][cy][cx] + xy[cy][cx], dp[1][cy][cx])
      dp[2][cy][cx + 1] = max(dp[2][cy][cx + 1], dp[1][cy][cx] + xy[cy][cx], dp[2][cy][cx])
      dp[3][cy][cx + 1] = max(dp[3][cy][cx + 1], dp[2][cy][cx] + xy[cy][cx], dp[3][cy][cx])
    if cy < R :
      dp[0][cy + 1][cx] = max(dp[i][cy][cx] for i in range(3)) + xy[cy][cx]
      dp[0][cy + 1][cx] = max(dp[0][cy + 1][cx], dp[3][cy][cx])

print(max(dp[i][-1][-1] for i in range(4)))

Solution (Python):
import sys

readline = sys.stdin.readline

def solve():
    R, C, K = map(int, readline().split())
    items = [[0] * C for i in range(R)]
    for i in range(K):
        r,c,k = map(int, readline().split())
        items[r - 1][c - 1] = k
    
    dp = [[[0] * C for i in range(R)] for j in range(4)]

    for i in range(R):
        for j in range(C):
            for k in range(4):
                if i == 0 and j == 0:
                    if k == 0:
                        dp[k][i][j] = 0
                    else:
                        dp[k][i][j] = items[i][j]
                elif i == 0:
                    if k == 0:
                        dp[k][i][j] = dp[k][i][j - 1]
                    else:
                        dp[k][i][j] = max(dp[k - 1][i][j - 1] + items[i][j], dp[k][i][j - 1])
                elif j == 0:
                    if k == 0:
                        dp[k][i][j] = dp[3][i - 1][j]
                    else:
                        dp[k][i][j] = dp[3][i - 1][j] + items[i][j]
                else:
                    if k == 0:
                        dp[k][i][j] = max(dp[3][i - 1][j], dp[k][i][j - 1])
                    else:
                        dp[k][i][j] = max(
                            dp[3][i - 1][j] + items[i][j],
                            dp[k - 1][i][j - 1] + items[i][j],
                            dp[k][i][j - 1]
                        )

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

solve()

Solution (Python):



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

item = [0] * (R*C+1)
for i in range(K):
    index = (rcv[i][0] - 1) * C + (rcv[i][1] - 1) 
    
    item[index] = rcv[i][2]





def solver(R,C,K):
    empty = []
    prev = []
    for i in range(C):
        empty.append([0] * 4)
        prev.append([0] * 4)
    
    for i in range(R):
        
        now = []
        
        zero = max(prev[0])
        now.append([zero, zero+item[i*C], 0, 0]) 
        for j in range(1, C):
            index = i * C + j
            point = item[index]
            
            ret = []
            left = now[-1]
            zero = max(left[0], max(prev[j])) 
            ret.append(zero) 
            one = max(zero + point, left[1]) 
            two = max(left[1] + point, left[2])
            three = max(left[2] + point, left[3])
            ret.append(one)
            ret.append(two)
            ret.append(three)
            now.append(ret)
        prev = now
        
    
    print(max(now[-1]))


solver(R,C,K)

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

def solve():
    INF = float('inf')

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

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

    dpMax = [0]*(C+1)
    for i in range(1, R+1):
        dp0 = [0]*(C+1)
        dp1 = [-INF]*(C+1)
        dp2 = [-INF]*(C+1)
        dp3 = [-INF]*(C+1)
        for j in range(1, C+1):
            V = Vss[i][j]
            dp0[j] = max2(dp0[j-1], dpMax[j])
            dp1[j] = max2(dp0[j] + V, dp1[j-1])
            dp2[j] = max2(dp1[j-1] + V, dp2[j-1])
            dp3[j] = max2(dp2[j-1] + V, dp3[j-1])
            dpMax[j] = max(dp0[j], dp1[j], dp2[j], dp3[j])

    ans = dpMax[C]
    print(ans)


solve()

Solution (Python):
from collections import defaultdict
import sys


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


r, c, K = map(int, input().split())

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


d = [[0 for i in range(c+1)] for j in range(r+1)]

for _ in range(K):
    r_, c_, v = map(int, input().split())
    d[r_][c_] = v
for i in range(1, r+1):
    for j in range(1, c+1):
        v = d[i][j]
        if v > 0:
            maxi = max(dp[k][i-1][j] for k in range(4))
            dp[0][i][j] = max(maxi, dp[0][i][j-1])
            dp[1][i][j] = max(dp[1][i][j-1], dp[0][i][j-1]+v, maxi+v)
            dp[2][i][j] = max(dp[2][i][j-1], dp[1][i][j-1]+v)
            dp[3][i][j] = max(dp[3][i][j-1], dp[2][i][j-1]+v)

        elif v == 0:
            maxi = max(dp[k][i-1][j] for k in range(4))
            dp[0][i][j] = max(dp[0][i][j-1], maxi)
            dp[1][i][j] = dp[1][i][j-1]
            dp[2][i][j] = dp[2][i][j-1]
            dp[3][i][j] = dp[3][i][j-1]


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

print(ans)

Solution (Python):
r, c, k = map(int, input().split())

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

for i in range(k):
  x, y, v = map(int, input().split())
  atlas[x-1][y-1] = v
  
def max_sum(r, c, atlas):
  global dp

  if atlas[0][0] > 0:
    dp[1][0][0] = atlas[0][0]
    
  for i in range(r):
    for j in range(c):
      for h in range(4):
        
        if j+1 < c:
          dp[h][i][j+1] = max(dp[h][i][j+1], dp[h][i][j])
          if atlas[i][j+1] > 0 and h < 3:
            dp[h+1][i][j+1] = max(dp[h+1][i][j+1], dp[h][i][j]+atlas[i][j+1])
            
        if i+1 < r:
          dp[0][i+1][j] = max(dp[0][i+1][j], dp[h][i][j])
          if atlas[i+1][j] > 0:
            dp[1][i+1][j] = max(dp[1][i+1][j], dp[h][i][j]+atlas[i+1][j])
          
            
  return dp

max_sum(r, c, atlas)

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

Solution (Python):
def main():
    import sys
    from copy import deepcopy
    input = sys.stdin.readline
    R, C, K = [int(x) for x in input().strip().split()]
    G = [[0] * (C+1) for r in range(R+1)]
    for k in range(K):
        r, c, v = [int(x) for x in input().strip().split()]
        G[r][c] = v
    
    
    ans = [[[0] * 4 for _ in range(C+1)] for _ in range(2)]
    for r in range(1, R+1):
        for c in range(1, C+1):
            ans[r%2][c][0] = max(ans[(r-1)%2][c][-1], ans[r%2][c-1][0])
            for i in range(1, 4):
                ans[r%2][c][i] = max(ans[(r-1)%2][c][3], ans[r%2][c-1][i], ans[(r-1)%2][c][3]+G[r][c], ans[r%2][c-1][i-1]+G[r][c])

    print(max(ans[R%2][-1]))

if __name__ == '__main__':
    main()

Solution (Python):
import sys
import copy
from collections import deque

sys.setrecursionlimit(10**6)
input = sys.stdin.readline


def main():
    global field
    R, C, K = map(int, input().split())
    field = []
    for _ in range(R):
        tmp = [0] * C
        field.append(tmp)
    DP1 = copy.deepcopy(field)
    DP2 = copy.deepcopy(field)
    DP3 = copy.deepcopy(field)

    for _ in range(K):
        r, c, k = map(int, input().split())
        field[r-1][c-1] = k
    
    i = 0
    DP1[0][0] = field[0][0]
    for j in range(1, C):
        DP3[i][j] = max(DP2[i][j-1] + field[i][j], DP3[i][j-1])
        DP2[i][j] = max(DP1[i][j-1] + field[i][j], DP2[i][j-1])
        DP1[i][j] = max(field[i][j], DP1[i][j-1])

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

    ans = max(DP3[R-1][C-1], DP2[R-1][C-1], DP1[R-1][C-1])
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
from itertools import accumulate
R, C, K = map(int, input().split())
vss = [[None]*C for _ in range(R)]
for _ in range(K):
    r, c, v = map(int, input().split())
    vss[r-1][c-1] = v

dp = []

for y in range(R):
    ndp = []
    for x in range(C):
        tmp = []
        uemax = 0
        if y > 0:
            uemax = max(dp[x])
        if vss[y][x] is None:
            if x > 0:
                left = ndp[-1]
                tmp.append(left[0] if left[0] > uemax else uemax)
                tmp.append(left[1])
                tmp.append(left[2])
                tmp.append(left[3])
            else:
                tmp.append(uemax)
                tmp.append(0)
                tmp.append(0)
                tmp.append(0)
        else:
            v = vss[y][x]
            if x > 0:
                left = ndp[-1]
                tmp.append(left[0] if left[0] > uemax else uemax)
                tmp.append(max(left[0]+v, left[1], uemax+v))
                tmp.append(left[1]+v if left[1]+v > left[2] else left[2])
                tmp.append(left[2]+v if left[2]+v > left[3] else left[3])
            else:
                tmp.append(uemax)
                tmp.append(uemax + v)
                tmp.append(0)
                tmp.append(0)
        ndp.append(tmp)
    dp = ndp

print(max(dp[-1]))