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:
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[3][i][j]
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)))

Submission status: Accepted

Solution code:
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]  # simple down
                else:
                    dp[num][row][col] = max(dp[num-1][row][col],  # str
                                            dp[num][row][col-1],  # right x
                                            dp[3][row-1][col] + \
                                            v[row][col],  # down o
                                            dp[num-1][row][col-1] + \
                                            v[row][col],  # right o
                                            )
    print(dp[3][r][c])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
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: # can go right and pick up
                    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)

Submission status: Accepted

Solution code:
def main():
    R, C, K = list(map(int, input().split()))
    # dp[r][c][n]: r行目でn個のアイテムを拾う場合の(r, c)でのアイテムの価値の合計の最大
    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])
            # dp[r][c][0]
            v1 = 0 if c == 0 else dp_0[r][c - 1]
            dp_0[r][c] = max(v1, max_dp_before_row)
            # dp[r][c][1]
            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[r][c][2], dp[r][c][3]
            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()

Submission status: Accepted

Solution code:


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

Submission status: Accepted

Solution code:
def e_picking_goods():
    # 参考: https://atcoder.jp/contests/abc175/submissions/16044254
    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

    # editorial に対し、行の情報を除去する
    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])  # 上のマスで 0~3 回アイテムを拾っていたときの、価値の最大値
            v = Goods[i][j]

            # 左か上から来て、アイテムを拾わない
            dp_next[j][0] = max(up_max, dp_next[j - 1][0])
            # 上から来て拾う or 左から来て拾う or 左から来て拾わない
            dp_next[j][1] = max(up_max + v, dp_next[j - 1][0] + v, dp_next[j - 1][1])
            # 左から来て k-1 個拾っており、ここで拾う or k 個拾っており、ここで拾わない
            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())

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import copy
R, C, K = map(int, input().split())
item = [[0] * (C + 1) for _ in range(R + 1)]  # dp配列と合わせるために, 0行目, 0列目を追加している.
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)

Submission status: Accepted

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

# 多次元配列を生成する際、使いたい引数を逆順で書くと上手くいく

# dp = [[[0 for _ in range(4)] for _ in range(C + 1)] for _ in range(R + 1)]
# とするとTLEだった。(R+1)*4(C+1)だと通るみたいだが、あまり本質的ではない気がする。
# 以下ではdp0,dp1,dp2,dp3という4つの配列を作ることにする。

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):
        # 何度も使うので変数に格納しておく
        # 以下を省略し、毎回配列を見に行く書き方をしたら少し遅くなった(400ms程度)
        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])

# 最終的にR行で取るアイテムの個数についてそれぞれ調べる、3個が最適とは限らない
ans = max(dp0[-1][-1],
          dp1[-1][-1],
          dp2[-1][-1],
          dp3[-1][-1])

print(ans)

Submission status: Accepted

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

# 多次元配列を生成する際、使いたい引数を逆順で書くと上手くいく

# dp = [[[0 for _ in range(4)] for _ in range(C + 1)] for _ in range(R + 1)]
# とするとTLEだった。(R+1)*4(C+1)だと通るみたいだが、あまり本質的ではない気がする。
# 以下ではdp0,dp1,dp2,dp3という4つの配列を作ることにする。

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])
            # 現在のアイテム数が3未満(0 or 1 or 2)の場合、移動先のアイテムをとることが可能                             [k + 1], now + item[i][j + 1])
            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])

# 最終的にR行で取るアイテムの個数についてそれぞれ調べる、3個が最適とは限らない
ans = max(dp0[-1][-1], dp1[-1][-1], dp2[-1][-1], dp3[-1][-1])
print(ans)

Submission status: Accepted

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

# 多次元配列を生成する際、使いたい引数を逆順で書くと上手くいく

# dp = [[[0 for _ in range(4)] for _ in range(C + 1)] for _ in range(R + 1)]
# とするとTLEだった。(R+1)*4(C+1)だと通るみたいだが、あまり本質的ではない気がする。
# 以下ではdp0,dp1,dp2,dp3という4つの配列を作ることにする。

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]
        # 下に移動する場合、アイテムの個数はリセットされる
        # i == Rの時は下に移動できない
        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])

        # 右に移動する場合、アイテムの個数は維持される
        # j == Cの時は右に移動できない
        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)

            # 現在のkが3未満(0 or 1 or 2)の場合、移動先のアイテムをとることが可能                             [k + 1], now + item[i][j + 1])
            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])

# 最終的にR行で取るアイテムの個数についてそれぞれ調べる、3個が最適とは限らない
ans = max(dp0[-1][-1], dp1[-1][-1], dp2[-1][-1], dp3[-1][-1])
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)
    #print(dp)
    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)

    #print(dp)
    ans=0
    for i in range(4): ans=max(dp[r-1, c-1, i],ans)
    return print(ans)
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
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)
    #print(dp)
    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]=max(dp[i, j, 1],x+val)
                dp[i, j, 0]=max(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(dp[i, j, 2],Y+val,V)
                dp[i, j, 3]=max(dp[i, j, 3],V+val,Z)

    #print(dp)
    ans=0
    for i in range(4): ans=max(dp[r-1, c-1, i],ans)
    return print(ans)
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
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.__dat = [num] * (H * W * D)

    def __getitem__(self, a):
        return self.__dat[a[0]*self.__W*self.__D+a[1]*self.__D + a[2]]

    def __setitem__(self, a, b):
        self.__dat[a[0]*self.__W*self.__D+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)
    #print(dp)
    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]=max(dp[i, j, 1],x+val)
                dp[i, j, 0]=max(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(dp[i, j, 2],Y+val,V)
                dp[i, j, 3]=max(dp[i, j, 3],V+val,Z)

    #print(dp)
    ans=0
    for i in range(4): ans=max(dp[r-1, c-1, i],ans)
    return 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())
    v=[0] * (c * r)
    for _ in range(k):
        ri,ci,a=map(int,input().split())
        v[(ri-1)*c + (ci-1)]=a
    dp= [0] * (c * r * 4)
    #print(dp)
    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
            if i>0:
                dp[x + idx] = max(dp[x + idx], dp[idx2]+v[idx])
                dp[idx] = max(dp[idx],dp[idx2])
                dp[x + idx]=max(dp[x + idx],dp[x + idx2]+v[idx])
                dp[idx]=max(dp[idx],dp[x + idx2])
                dp[x + idx]=max(dp[x + idx],dp[2*x + idx2]+v[idx])
                dp[idx]=max(dp[idx],dp[2*x + idx2])
                dp[x + idx]=max(dp[x + idx],dp[3*x + idx2]+v[idx])
                dp[idx]=max(dp[idx],dp[3*x + idx2])
            if j>0:
                dp[x + idx]=max(dp[x + idx],dp[idx3]+v[idx])
                dp[2*x + idx]=max(dp[2*x + idx],dp[x + idx3]+v[idx])
                dp[3*x + idx]=max(dp[3*x + idx],dp[2*x + idx3]+v[idx])
                dp[idx]=max(dp[idx],dp[idx3])
                dp[x + idx]=max(dp[x + idx],dp[x + idx3])
                dp[2*x + idx]=max(dp[2*x + idx],dp[2*x + idx3])
                dp[3*x + idx]=max(dp[3*x + idx],dp[3*x + idx3])

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

if __name__=="__main__":
    main()