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



Sample input:
2 2 3
1 1 3
2 1 4
1 2 5


Sample output:
8

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
import bisect
import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal


from numba import jit

@jit
def run_dp(MAP, dp, Rs, Cs):
    for i in range(1, len(Rs)+1):
        for j in range(1, len(Cs)+1):
            for k in range(4):
                dp[i,j,0] = max(dp[i,j,0], dp[i-1,j,k])
                if MAP[i,j]:
                    dp[i,j,1] = max(dp[i,j,1], dp[i-1,j,k]+MAP[i,j])

                dp[i,j,k] = max(dp[i,j,k], dp[i,j-1,k])
                if MAP[i][j] and k < 3:
                    dp[i,j,k+1] = max(dp[i,j,k+1], dp[i,j-1,k] + MAP[i,j])
    return dp[len(Rs), len(Cs)].max()

def run():
    R,C,K = map(int, sysread().split())
    Rs = set()
    Cs = set()
    vals = []
    for i in range(K):
        r, c, v = map(int, sysread().split())
        vals.append((r, c, v))
        Rs.add(r)
        Cs.add(c)
    #Rs = sorted(list(Rs))
    Rs = np.array(sorted(list(Rs)))
    #Cs = sorted(list(Cs))
    Cs = np.array(sorted(list(Cs)))
    r_idx = {r:i+1 for i, r in enumerate(Rs)}
    c_idx = {c:i+1 for i, c in enumerate(Cs)}
    #MAP = [[0] * (len(Cs)+1) for _ in range(len(Rs)+1)]
    MAP = np.zeros((len(Rs)+1, len(Cs)+1), dtype= np.int64)
    for r,c,v in vals:
        rn = r_idx[r]
        cn = c_idx[c]
        MAP[rn][cn] = v

    #dp = [[[0] * 4 for _ in range(len(Cs)+1)] for i in range(len(Rs)+1)]
    dp = np.zeros((len(Rs)+1, len(Cs)+1, 4), dtype= np.int64)

    run_dp(MAP, dp, Rs, Cs)

    #print(dp)
    #for m in MAP:
    #   print(m)
    ans= run_dp(MAP, dp, Rs, Cs)

    print(ans)

if __name__ == "__main__":
    run()

Submission status: Accepted

Solution code:

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

    DP1 = [0 for _ in range(C + 1)]  # c列目までとったとき、最新の行で1個以下とったという条件のもとの最大
    DP2 = [0 for _ in range(C + 1)]  # c列目までとったとき、最新の行で2個以下とったという条件のもとの最大
    DP3 = [0 for _ in range(C + 1)]  # c列目までとったとき、最新の行で3個以下とったという条件のもとの最大

    for r in range(1, R+1):
        for c in range(1, C+1):
            # 更新の順番に注意
            # mid = max(DP1[c], DP2[c], DP3[c]) + I[r][c]
            mid = DP3[c] + G[r][c]
            DP3[c] = max(DP3[c - 1], mid, DP2[c - 1] + G[r][c])  # 3個
            DP2[c] = max(DP2[c - 1], mid, DP1[c - 1] + G[r][c])  # 2個
            DP1[c] = max(DP1[c - 1], mid)  # 1個

    print(DP3[C])

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
import bisect
import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal


from numba import jit

@jit
def run_dp(MAP, dp, Rs, Cs):
    for i in range(1, len(Rs)+1):
        for j in range(1, len(Cs)+1):
            for k in range(4):
                dp[i][j][0] = max(dp[i][j][0], dp[i-1][j][k])
                if MAP[i][j]:
                    dp[i][j][1] = max(dp[i][j][1], dp[i-1][j][k]+MAP[i][j])

                dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k])
                if MAP[i][j] and k < 3:
                    dp[i][j][k+1] = max(dp[i][j][k+1], dp[i][j-1][k] + MAP[i][j])
    return dp

def run():
    R,C,K = map(int, sysread().split())
    Rs = set()
    Cs = set()
    vals = []
    for i in range(K):
        r, c, v = map(int, sysread().split())
        vals.append((r, c, v))
        Rs.add(r)
        Cs.add(c)
    #Rs = sorted(list(Rs))
    Rs = np.array(sorted(list(Rs)))
    #Cs = sorted(list(Cs))
    Cs = np.array(sorted(list(Cs)))
    r_idx = {r:i+1 for i, r in enumerate(Rs)}
    c_idx = {c:i+1 for i, c in enumerate(Cs)}
    #MAP = [[0] * (len(Cs)+1) for _ in range(len(Rs)+1)]
    MAP = np.zeros((len(Rs)+1, len(Cs)+1), dtype= np.int64)
    for r,c,v in vals:
        rn = r_idx[r]
        cn = c_idx[c]
        MAP[rn][cn] = v

    #dp = [[[0] * 4 for _ in range(len(Cs)+1)] for i in range(len(Rs)+1)]
    dp = np.zeros((len(Rs)+1, len(Cs)+1, 4), dtype= np.int64)

    run_dp(MAP, dp, Rs, Cs)

    #print(dp)
    #for m in MAP:
    #   print(m)
    dp = run_dp(MAP, dp, Rs, Cs)

    print(max(dp[len(Rs)][len(Cs)]))

if __name__ == "__main__":
    run()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
R,C,K = map(int,input().split())
RCV = [tuple(map(int,input().split())) for i in range(K)]

goods = [dict() for _ in range(R)]
for r,c,v in RCV:
    r,c = r-1,c-1
    goods[r][c] = v

dp0 = [[0]*4 for _ in range(C)]
dp1 = [[0]*4 for _ in range(C)]
if 0 in goods[0]:
    dp1[0][1] = goods[0][0]
for i in range(R):
    for j in range(C):
        if i:
            pre = max(dp0[j])
            dp1[j][0] = pre
            if j in goods[i]:
                dp1[j][1] = pre + goods[i][j]
        if j:
            for k in range(4):
                dp1[j][k] = max(dp1[j][k], dp1[j-1][k])
            if j in goods[i]:
                for k in reversed(range(3)):
                    dp1[j][k+1] = max(dp1[j][k+1], dp1[j-1][k] + goods[i][j])
    dp0 = dp1
    dp1 = [[0]*4 for _ in range(C)]
print(max(dp0[-1]))

Submission status: Accepted

Solution code:
def main():
    import sys
    my_input = sys.stdin.readline
    H, W, K = map(int, my_input().split())
    V = [[0] * W for _ in range(H)]
    for i in range(K):
        h, w, v = map(int, my_input().split())
        h, w = h - 1, w - 1
        V[h][w] = v

    # dp1 ~ 4[h][w][x] := h行w列にいて、h行からn個アイテムを拾っている時の価値の総和の最大値
    dp1 = [[0] * (W + 1) for _ in range(H + 1)]
    dp2 = [[0] * (W + 1) for _ in range(H + 1)]
    dp3 = [[0] * (W + 1) for _ in range(H + 1)]

    for h in range(1, H + 1):
        for w in range(1, W + 1):
            dp1[h][w] = max(
                dp1[h][w],
                dp3[h - 1][w] + V[h - 1][w - 1],
                dp1[h][w - 1]
            )

            dp2[h][w] = max(
                dp2[h][w],
                dp3[h - 1][w] + V[h - 1][w - 1],
                dp2[h][w - 1],
                dp1[h][w - 1] + V[h - 1][w - 1]
            )

            dp3[h][w] = max(
                dp3[h][w],
                dp3[h - 1][w] + V[h - 1][w - 1],
                dp3[h][w - 1],
                dp2[h][w - 1] + V[h - 1][w - 1]
            )

    print(dp3[-1][-1])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    my_input = sys.stdin.readline
    H, W, K = map(int, my_input().split())
    V = [[0] * W for _ in range(H)]
    for i in range(K):
        h, w, v = map(int, my_input().split())
        h, w = h - 1, w - 1
        V[h][w] = v

    # dp1 ~ 4[h][w][x] := h行w列にいて、h行からn個アイテムを拾っている時の価値の総和の最大値
    dp0 = [[0] * (W + 1) for _ in range(H + 1)]
    dp1 = [[0] * (W + 1) for _ in range(H + 1)]
    dp2 = [[0] * (W + 1) for _ in range(H + 1)]
    dp3 = [[0] * (W + 1) for _ in range(H + 1)]

    for h in range(1, H + 1):
        for w in range(1, W + 1):
            dp1[h][w] = max(
                dp1[h][w],
                dp3[h - 1][w] + V[h - 1][w - 1],
                dp1[h][w - 1],
                dp0[h][w - 1] + V[h - 1][w - 1]
            )

            dp2[h][w] = max(
                dp2[h][w],
                dp3[h - 1][w] + V[h - 1][w - 1],
                dp2[h][w - 1],
                dp1[h][w - 1] + V[h - 1][w - 1]
            )

            dp3[h][w] = max(
                dp3[h][w],
                dp3[h - 1][w] + V[h - 1][w - 1],
                dp3[h][w - 1],
                dp2[h][w - 1] + V[h - 1][w - 1]
            )

    print(dp3[-1][-1])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
r, c, k = map(int, input().split())
item = [[0] * (c + 1) for _ in range(r + 1)]  # dp配列と合わせるために, 0行目, 0列目を追加している.
for _ in range(k):
  i, j, v = map(int, input().split())
  item[i][j] = 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 = max(dp[k][-1][-1] for k in range(4))
print(ans)

Submission status: Accepted

Solution code:
R,C,K = map(int,input().split()) #行、列、個数
G = [[0]*C for _ in range(R)] #G[i][j]でi行目のj番目にある価値
for i in range(K):
  a,b,v = map(int,input().split())
  a-=1;b-=1 #0index
  G[a][b] = v
#print(G)

dp = [[0]*4 for _ in range(C+1)]
#dp[j][k]ある行において、j個目まで見て、その行でk個拾っている
for i in range(R):
  p = [[0]*4 for _ in range(C+1)] #pが前の行、dpが今の行
  p,dp = dp,p
  for j in range(C):
    #print(j+1,dp)
    for k in range(4):
      if k == 0: #その行で一個も取っていなければ上の行から来るだけ
        dp[j+1][k] = max(p[j+1])
      elif k == 1: #一個目をとるということは横からきて取るか、上から来て取るか
        if G[i][j] == 0: #そこにない場合は横から
          dp[j+1][k] = dp[j][k]
        else: #ある場合は横からくるか上から来て一個取るか
          dp[j+1][k] = max(dp[j][k],max(p[j+1])+G[i][j])
      else: #二個以上の場合には上からは来れない。
        if G[i][j] == 0: #そこになければ横からくるだけ
          dp[j+1][k] = dp[j][k]
        else: #あればとったほうがよいか比較
          dp[j+1][k] = max(dp[j][k],dp[j][k-1]+G[i][j])
  #print(p,dp)

ans = max(dp[C])
print(ans)

Submission status: Accepted

Solution code:
R,C,K=map(int, input().split())
M=[[0 for i in range(C)]for i in range(R)]
for i in range(K):
  r,c,v=map(int, input().split())
  r-=1
  c-=1
  M[r][c]=v
dp0=[[0 for j in range(C)] for i in range(R)]
dp1=[[0 for j in range(C)] for i in range(R)]
dp2=[[0 for j in range(C)] for i in range(R)]
dp3=[[0 for j in range(C)] for i in range(R)]
dp1[0][0]+=M[0][0]
for r in range(R):
  for c in range(C):
    if 0<r:
      dp1[r][c]=max(max(dp1[r-1][c],dp2[r-1][c],dp3[r-1][c])+M[r][c],dp1[r][c])
      dp0[r][c]=max(max(dp1[r-1][c],dp2[r-1][c],dp3[r-1][c]),dp0[r][c])
    if 0<c:
      dp3[r][c]=max(dp2[r][c-1]+M[r][c],dp3[r][c],dp3[r][c-1])
      dp2[r][c]=max(dp1[r][c-1]+M[r][c],dp2[r][c],dp2[r][c-1])
      dp1[r][c]=max(dp0[r][c-1]+M[r][c],dp1[r][c],dp1[r][c-1])
      dp0[r][c]=max(dp0[r][c-1],dp0[r][c])
print(max(dp1[-1][-1],dp2[-1][-1],dp3[-1][-1]))

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // math.factorial(r) // math.factorial(n-r)

def make_list(n, *args, default=0): return [make_list(*args, default=default) for _ in range(n)] if len(args) > 0 else [default for _ in range(n)]

alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

sys.setrecursionlimit(1000000)
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007
INF = float("inf")

def main():
    R, C, K = LI()
    rcv = LIR1(K)

    # dp = make_list(R+1, C+1, 4)
    dp = make_list(C+1, 4)
    table = make_list(R, C)

    for r, c, v in rcv: table[r][c] = v + 1

    for r in range(R):
        newdp = [[max(p), 0, 0, 0] for p in dp]
        for c in range(C):
            for i in range(1, 4)[::-1]:
                newdp[c][i] = max(newdp[c][i], newdp[c][i - 1] + table[r][c])
                newdp[c + 1][i] = max(newdp[c + 1][i], newdp[c][i])
            newdp[c + 1][0] = max(newdp[c + 1][0], newdp[c][0])
        dp = newdp

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    R, C, K = map(int, input().split())
    matrix = [[0] * (C+1) for i in range(R+1)]
    for k in range(K):
        ri, ci, vi = map(int, input().split())
        matrix[ri][ci] = vi
    # print(matrix)
    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):
            tmp = matrix[r][c]
            if tmp == 0:
                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] = dp1[r][c-1]
                dp2[r][c] = dp2[r][c-1]
                dp3[r][c] = dp3[r][c-1]
            else:
                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(dp0[r][c-1] + tmp, dp1[r][c-1], 
                                dp0[r-1][c] + tmp, dp1[r-1][c] + tmp, dp2[r-1][c] + tmp, dp3[r-1][c] + tmp)
                dp2[r][c] = max(dp1[r][c-1] + tmp, dp2[r][c-1])
                dp3[r][c] = max(dp2[r][c-1] + tmp, dp3[r][c-1])

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
def main():
  R,C,K=map(int, input().split())
  M=[[0 for i in range(C)]for i in range(R)]
  for i in range(K):
    r,c,v=map(int, input().split())
    r-=1
    c-=1
    M[r][c]=v
  dp0=[[0 for j in range(C)] for i in range(R)]
  dp1=[[0 for j in range(C)] for i in range(R)]
  dp2=[[0 for j in range(C)] for i in range(R)]
  dp3=[[0 for j in range(C)] for i in range(R)]
  dp1[0][0]+=M[0][0]
  for r in range(R):
    for c in range(C):
      if 0<r:
        dp1[r][c]=max(max(dp1[r-1][c],dp2[r-1][c],dp3[r-1][c])+M[r][c],dp1[r][c])
        dp0[r][c]=max(max(dp1[r-1][c],dp2[r-1][c],dp3[r-1][c]),dp0[r][c])
      if 0<c:
        dp3[r][c]=max(dp2[r][c-1]+M[r][c],dp3[r][c],dp3[r][c-1])
        dp2[r][c]=max(dp1[r][c-1]+M[r][c],dp2[r][c],dp2[r][c-1])
        dp1[r][c]=max(dp0[r][c-1]+M[r][c],dp1[r][c],dp1[r][c-1])
        dp0[r][c]=max(dp0[r][c-1],dp0[r][c])
  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)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def main():
    R, C,K = map(int, input().split())
    dp = [[[0]*(C+1) for k in range(R+1)] for _ in range(4)]
    # dp[r][c][j] :=r index c columns already j cnt
    dp[0][0][0] = 0
    D = [[0 for i in range(C+1)] for j in range(R+1)]
    import random
    for i in range(K):
        r, c, v = map(int,input().split())
        D[r][c] = v
    
    for i in range(R+1):
        for j in range(C+1):
            if D[i][j] > 0:
                v = D[i][j]
                M = max(dp[k][i-1][j] for k in range(4))
                dp[0][i][j] = max(dp[0][i][j-1], M)
                dp[1][i][j] = max(dp[0][i][j-1]+v, dp[1][i][j-1], M+v)
                dp[2][i][j] = max(dp[1][i][j-1]+v, dp[2][i][j-1])
                dp[3][i][j] = max(dp[2][i][j-1]+v, dp[3][i][j-1])
    
            else:
                M = max(dp[k][i-1][j] for k in range(4))
                dp[0][i][j] = max(dp[0][i][j-1], M)
                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 = 0
    for i in range(4):
        ans = max(ans, dp[i][-1][-1])
    print(ans)
main()

Submission status: Accepted

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

grid=[[0]*C for _ in range(R)]
for i in range(K):
    x,y,v = map(int,input().split())
    grid[x-1][y-1] = v
dp1 = [[0]*(C+1) for _ in range(R+1)]
dp2 = [[0]*(C+1) for _ in range(R+1)]
dp3 = [[0]*(C+1) for _ in range(R+1)]

for i in range(R):
    for j in range(C):
        dp1[i][j] = max(dp1[i][j-1],dp1[i-1][j]+grid[i][j],
                    dp2[i-1][j]+grid[i][j],dp3[i-1][j]+grid[i][j])
        dp2[i][j] = max(dp2[i][j-1],dp1[i][j-1]+grid[i][j])
        dp3[i][j] = max(dp3[i][j-1],dp2[i][j-1]+grid[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)

Submission status: Accepted

Solution code:
R, C, K = map(int, input().split())
item = {}
for _ in range(K):
    r, c, v = map(int, input().split())
    item[(r, c)] = v

dp = [[0] * 4 for _ in range(3010)]
ndp = [[0] * 4 for _ in range(3010)]
for r in range(1, R+1):
    for c in range(1, C+1):
        prer = max(dp[c])
        ndp[c][0] = max(prer, ndp[c-1][0])
        ndp[c][1] = max(prer, ndp[c-1][1])
        ndp[c][2] = max(prer, ndp[c-1][2])
        ndp[c][3] = max(prer, ndp[c-1][3])
        if item.get((r, c)):
            ndp[c][1] = max(ndp[c][1], max(prer, ndp[c-1][0]) + item[(r,c)])
            ndp[c][2] = max(ndp[c][2], max(prer, ndp[c-1][1]) + item[(r,c)])
            ndp[c][3] = max(ndp[c][3], max(prer, ndp[c-1][2]) + item[(r,c)])
    dp = ndp
    ndp = [[0] * 4 for _ in range(3010)]

#print(dp)
print(max(dp[C]))

Submission status: Accepted

Solution code:
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

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 = items[r][c]
        for fr, to in ((dp2, dp3), (dp1, dp2), (dp0, dp1)):
            to[r][c] = max(to[r][c], fr[r][c] + v)

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

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

print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc175/submissions/15965930

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

    H, W, K = map(int, input().split())

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

    dp0 = [0] * (W + 1)
    dp1 = [0] * (W + 1)
    dp2 = [0] * (W + 1)
    dp3 = [0] * (W + 1)
    # dpx:=行内取得x個以下の最大値
    # <cは更新済の同じ行の値
    # c<=は前の行の値

    for r in range(H):
        for c in range(W):
            v = G[r][c]

            dp0[c] = max(dp0[c], dp3[c])
            up = dp0[c] + v

            dp3[c] = max(dp3[c - 1], dp2[c - 1] + v, up)
            dp2[c] = max(dp2[c - 1], dp1[c - 1] + v, up)
            dp1[c] = max(dp1[c - 1], dp0[c - 1] + v, up)
            # 左から来て取らない
            # 左から来て取る
            # 上から来て取らない:=dp0
            # 上から来て取る:=dpx(x>0)

            # print(f'{dp0=}')
            # print(f'{dp1=}')
            # print(f'{dp2=}')
            # print(f'{dp3=}')
            # print('*******************')

    print(dp3[-2])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline

R, C, K = map(int,input().split())
RC = [[0] * (C+1) for _ in range(R+1)]

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


dp = [[[0] * (C+1) for i in range(R+1)] for j in range(4)]

dp[1][0][0] = RC[0][0]
for r in range(R):
    for c in range(C):
        for i in range(4):
            dp[i][r][c+1] = max(dp[i][r][c], dp[i][r][c+1])
            if i <= 2:
                dp[i+1][r][c+1] = max(dp[i][r][c] + RC[r][c+1], dp[i+1][r][c+1])
            dp[0][r+1][c] = max(dp[i][r][c], dp[0][r+1][c])
        dp[1][r+1][c] = max(dp[1][r+1][c], dp[0][r+1][c] + RC[r+1][c])

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

Submission status: Accepted

Solution code:
R, C, K = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(K)]

items = [[0] * (C + 1) for _ in range(R + 1)]
for r, c, v in X:
    items[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 - 1][j], dp1[i - 1][j], dp2[i - 1][j], dp3[i - 1][j])

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

        if items[i][j]:
            dp3[i][j] = max(dp3[i][j], dp2[i][j] + items[i][j])
            dp2[i][j] = max(dp2[i][j], dp1[i][j] + items[i][j])
            dp1[i][j] = max(dp1[i][j], dp0[i][j] + items[i][j])

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

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
from math import sqrt
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

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

# dp[j][n] j列目にn個まで取った時の最大値
# 蟻本で出てた、前と後のdpを取り替える作業をしないと盛大にTLEる
prev = [[0] * 4 for _ in range(C + 1)]

for i in range(R):
    next = [[0] * 4 for _ in range(C + 1)]
    for j in range(C):
        # ①取った時
        # n = 2, n = 1, n = 0と逆順にやらないとバグる
        # (n = 0の処理を先に行うと、n = 1の時「変更後の」n = 0で計算を行ってしまうため)
        # (つまりpoint[i][j]のアイテムを何回も取得するため）
        
        # ②より扱うjの数が小さくなるので先に処理する
        # (こちらは②でprev[j + 1][n]の計算をする時「変更後の」prev[j][n]で計算する必要があるため）
        for n in range(2, -1, -1):
            prev[j][n + 1] = max(prev[j][n + 1], prev[j][n] + point[i][j])

        # ②取らない時
        for n in range(4):
            prev[j + 1][n] = max(prev[j + 1][n], prev[j][n])

        # ③下段に降りた時
        next[j][0] = max(prev[j])

    # dpの取り替え
    prev = next

print(max(prev[C - 1]))

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
from math import sqrt
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

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

# dp[j][n] j列目にn個まで取った時の最大値
# 蟻本で出た前と後のdpを取り替える作業をしないと盛大にTLEる
prev = [[0] * 4 for _ in range(C + 1)]

for i in range(R):
    next = [[0] * 4 for _ in range(C + 1)]
    for j in range(C):
        # ①取った時
        # n = 2, n = 1, n = 0と逆順にやらないとバグる
        # ②より扱うjの数が小さくなるので先に処理する
        for n in range(2, -1, -1):
            prev[j][n + 1] = max(prev[j][n + 1], prev[j][n] + point[i][j])

        # ②取らない時
        for n in range(4):
            prev[j + 1][n] = max(prev[j + 1][n], prev[j][n])

        # ③下段に降りた時
        next[j][0] = max(prev[j])

    prev = next

print(max(prev[C - 1]))

Submission status: Accepted

Solution code:

R, C, K = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(K)]

items = [[0] * (C + 1) for _ in range(R + 1)]
for r, c, v in X:
    items[r][c] = v

dp = [[0] * 4 for _ in range(C + 1)]
for i in range(1, R + 1):
    # Vertical transition
    for j in range(1, C + 1):
        dp[j][0] = max(dp[j])
        for k in range(1, 4):
            dp[j][k] = 0

    # Horizontal or picking-up transition
    for j in range(1, C + 1):
        for k in reversed(range(4)):
            dp[j][k] = max(dp[j][k], dp[j - 1][k])
            if items[i][j] and k < 3:
                dp[j][k + 1] = max(dp[j][k + 1], dp[j][k] + items[i][j])

print(max(dp[-1]))

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
from math import sqrt
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

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

# dp[j][n] j列目にn個まで取った時の最大値
prev = [[0] * 4 for _ in range(C + 1)]

for i in range(R):
    next = [[0] * 4 for _ in range(C + 1)]
    for j in range(C):
        # 取った時
        for n in range(2, -1, -1):
            prev[j][n + 1] = max(prev[j][n + 1], prev[j][n] + point[i][j])

        # 下段に降りた時
        next[j][0] = max(prev[j])

        # 取らない時
        for n in range(4):
            prev[j + 1][n] = max(prev[j + 1][n], prev[j][n])
    prev = next

print(max(prev[C - 1]))