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: Runtime Error

Solution code:
"""
dp[i][j][k] => i行目、j列のマスまで見る。k個取る時の最高値。
"""
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)]for _ in range(R)]

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

            #上から降りてくる場合の価値を求める
            if i != 0:
                #i行目j列のアイテムを取らない場合
                dp[i][j][0] = max(dp[i-1][j])
                #i行目j列のアイテムを取る場合
                if v!=0:
                    dp[i][j][1] = max(dp[i-1][j]) + v

            #左から入ってくる場合の価値を求める
            if j != 0:
                if v == 0:
                    for k in range(4):
                        dp[i][j][k] = max(dp[i][j][k],dp[i][j-1][k])
                else:
                    for k in range(1,4):
                        dp[i][j][k] = max(dp[i][j][k],dp[i][j-1][k],dp[i][j-1][k-1]+v)
        if i > 0:
            del(dp[i-1])
    print(max(dp[-1][-1]))
main()

Submission status: Runtime Error

Solution code:
"""
dp[i][j][k] => i行目、j列のマスまで見る。k個取る時の最高値。
"""
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)]for _ in range(R)]

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

            #上から降りてくる場合の価値を求める
            if i != 0:
                #i行目j列のアイテムを取らない場合
                dp[i][j][0] = max(dp[i-1][j])
                #i行目j列のアイテムを取る場合
                if v!=0:
                    dp[i][j][1] = max(dp[i-1][j]) + v

            #左から入ってくる場合の価値を求める
            if j != 0:
                if v == 0:
                    for k in range(4):
                        dp[i][j][k] = max(dp[i][j][k],dp[i][j-1][k])
                else:
                    for k in range(1,4):
                        dp[i][j][k] = max(dp[i][j][k],dp[i][j-1][k],dp[i][j-1][k-1]+v)
        if i > 0:
            dp[i] = []
    print(max(dp[-1][-1]))
main()

Submission status: Runtime Error

Solution code:
a = [[0] * 3005 for i in range(3005)]
dp = [[[0] * 3005 for i in range(3005)] for j in range(5)]
R,C,K = map(int, input().split())

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

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

Submission status: Runtime Error

Solution code:
a = [[0] * 3001 for i in range(3001)]
dp = [[[0] * 3001 for i in range(3001)] for j in range(5)]
R,C,K = map(int, input().split())

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

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

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8
read = sys.stdin.buffer.read

@njit((i8, i8, i8, i8[:]), cache=True)
def solve(R,C,K,XYV):
  item = np.zeros((R + 1, C + 1), dtype=np.int64)
  for i in range(0, 3 * K, 3):
    x, y, v = XYV[i:i + 3]
    item[x - 1, y - 1] = v
  dp = np.zeros((C+1,4), dtype=np.int64)
  for i in range(1,R+1):
    new_dp = np.zeros((C+1,4), dtype=np.int64)
    #上から移動
    for k in range(4):
      new_dp[:,0] = np.maximum(new_dp[:,0], dp[:,k])
    dp = new_dp
    for j in range(1,C+1):
      #横から移動
      new_dp[j] = np.maximum(new_dp[j],new_dp[j-1])
      #アイテムを取る
      for k in range(2,-1,-1):
        dp[j,k+1] = np.maximum(dp[j,k+1],dp[j,k]+item[i-1,j-1])
  ans = dp[-1].max()
  return ans

R, C, K = map(int, input().split())
XYV = np.array(read().split(), np.int64)
print(solve(R,C,K,XYV))

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8
read = sys.stdin.buffer.read

@njit((i8, i8, i8, i8[:]), cache=True)
def solve(R,C,K,XYV):
  item = np.zeros((R + 1, C + 1), dtype=np.int64)
    for i in range(0, 3 * K, 3):
      x, y, v = XYV[i:i + 3]
      item[x - 1, y - 1] = v
  dp = np.zeros((C+1,4), dtype=np.int64)
  for i in range(1,R+1):
    new_dp = np.zeros((C+1,4), dtype=np.int64)
    #上から移動
    for k in range(4):
      new_dp[:,0] = np.maximum(new_dp[:,0], dp[:,k])
    dp = new_dp
    for j in range(1,C+1):
      #横から移動
      new_dp[j] = np.maximum(new_dp[j],new_dp[j-1])
      #アイテムを取る
      for k in range(2,-1,-1):
        dp[j,k+1] = np.maximum(dp[j,k+1],dp[j,k]+item[i-1,j-1])
  ans = dp[-1].max()
  return ans

R, C, K = map(int, input().split())
XYV = np.array(read().split(), np.int64)
print(solve(R,C,K,XYV))

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8
read = sys.stdin.buffer.read

@njit((i8, i8, i8, i8[:]), cache=True)
def solve(R,C,K,XYV):
  item = np.zeros((R + 1, C + 1), np.int64)
    for i in range(0, 3 * K, 3):
        x, y, v = XYV[i:i + 3]
        item[x - 1, y - 1] = v
  dp = np.zeros((C+1,4), dtype=np.int64)
  for i in range(1,R+1):
    new_dp = np.zeros((C+1,4), dtype=np.int64)
    #上から移動
    for k in range(4):
      new_dp[:,0] = np.maximum(new_dp[:,0], dp[:,k])
    dp = new_dp
    for j in range(1,C+1):
      #横から移動
      new_dp[j] = np.maximum(new_dp[j],new_dp[j-1])
      #アイテムを取る
      for k in range(2,-1,-1):
        dp[j,k+1] = np.maximum(dp[j,k+1],dp[j,k]+item[i-1][j-1])
  ans = dp[-1].max()
  return ans

R, C, K = map(int, input().split())
XYV = np.array(read().split(), np.int64)
print(solve(R,C,K,XYV))

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8
read = sys.stdin.buffer.read

@njit((i8, i8, i8, i8[:]), cache=True)
def solve(R,C,K,XYV):
  item = np.zeros((H + 1, W + 1), np.int64)
    for i in range(0, 3 * K, 3):
        x, y, v = XYV[i:i + 3]
        item[x - 1, y - 1] = v
  dp = np.zeros((C+1,4), dtype=np.int64)
  for i in range(1,R+1):
    new_dp = np.zeros((C+1,4), dtype=np.int64)
    #上から移動
    for k in range(4):
      new_dp[:,0] = np.maximum(new_dp[:,0], dp[:,k])
    dp = new_dp
    for j in range(1,C+1):
      #横から移動
      new_dp[j] = np.maximum(new_dp[j],new_dp[j-1])
      #アイテムを取る
      for k in range(2,-1,-1):
        dp[j,k+1] = np.maximum(dp[j,k+1],dp[j,k]+item[i-1][j-1])
  ans = dp[-1].max()
  return ans

R, C, K = map(int, input().split())
XYV = np.array(read().split(), np.int64)
print(solve(R,C,K,XYV))

Submission status: Runtime Error

Solution code:
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8
read = sys.stdin.buffer.read

@njit((i8, i8, i8, i8[:]), cache=True)
def solve(R,C,K,XYV):
  item = np.zeros((H + 1, W + 1), np.int64)
    for i in range(0, 3 * K, 3):
        x, y, v = XYV[i:i + 3]
        item[x - 1, y - 1] = v
  dp = np.zeros((C+1,4), dtype=np.int64)
  for i in range(1,R+1):
    new_dp = np.zeros((C+1,4), dtype=np.int64)
    #上から移動
    for k in range(4):
      new_dp[:,0] = np.maximum(new_dp[:,0], dp[:,k])
    dp = new_dp
    for j in range(1,C+1):
      #横から移動
      new_dp[j] = np.maximum(new_dp[j],new_dp[j-1])
      #アイテムを取る
      for k in range(2,-1,-1):
        dp[j,k+1] = np.maximum(dp[j,k+1],dp[j,k]+item[i-1][j-1])
  ans = dp[-1].max()
  return ans

R, C, K = map(int, input().split())
XYV = np.array(read().split(), np.int64)
print(solve(R,C,K,XYV))

Submission status: Runtime Error

Solution code:
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

@njit((i8, i8, i8, i8[:]), cache=True)
def solve(R,C,K,XYV):
  item = np.zeros((H + 1, W + 1), np.int64)
    for i in range(0, 3 * K, 3):
        x, y, v = XYV[i:i + 3]
        item[x - 1, y - 1] = v
  dp = np.zeros((C+1,4), dtype=np.int64)
  for i in range(1,R+1):
    new_dp = np.zeros((C+1,4), dtype=np.int64)
    #上から移動
    for k in range(4):
      new_dp[:,0] = np.maximum(new_dp[:,0], dp[:,k])
    dp = new_dp
    for j in range(1,C+1):
      #横から移動
      new_dp[j] = np.maximum(new_dp[j],new_dp[j-1])
      #アイテムを取る
      for k in range(2,-1,-1):
        dp[j,k+1] = np.maximum(dp[j,k+1],dp[j,k]+item[i-1][j-1])
  ans = dp[-1].max()
  return ans

R, C, K = map(int, input().split())
XYV = np.array(read().split(), np.int64)
print(solve(R,C,K,XYV))

Submission status: Runtime Error

Solution code:
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

@njit((i8, i8, i8, i8[:,:]), cache=True)
def solve(R,C,K,XYV):
  item = np.zeros((H + 1, W + 1), np.int64)
    for i in range(0, 3 * K, 3):
        x, y, v = XYV[i:i + 3]
        item[x - 1, y - 1] = v
  dp = np.zeros((C+1,4), dtype=np.int64)
  for i in range(1,R+1):
    new_dp = np.zeros((C+1,4), dtype=np.int64)
    #上から移動
    for k in range(4):
      new_dp[:,0] = np.maximum(new_dp[:,0], dp[:,k])
    dp = new_dp
    for j in range(1,C+1):
      #横から移動
      new_dp[j] = np.maximum(new_dp[j],new_dp[j-1])
      #アイテムを取る
      for k in range(2,-1,-1):
        dp[j,k+1] = np.maximum(dp[j,k+1],dp[j,k]+item[i-1][j-1])
  ans = dp[-1].max()
  return ans

R, C, K = map(int, input().split())
XYV = np.array(read().split(), np.int64)
print(solve(R,C,K,XYV))

Submission status: Runtime Error

Solution code:
from namba 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) #後のために余分に作っておく、scoresの配列は別なのでindexに注意
  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]) #同じ行ですでに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())

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
from sys import stdin
import numpy as np
from numba import jit

# stdin = open('/Users/dhesusan/workspace/com_pro/atcoder/python3/abc/abc175/e_1.txt')

input = stdin.buffer.readline

@jit(cache=True)
def main():
    R, C, K = map(int, input().rstrip().split())
    A = np.zeros((R + 1, C + 1), np.int64)
    DP = np.zeros((R + 1, C + 1, 4), np.int64)
    for _ in range(K):
        r, c, v = map(int, input().rstrip().split())
        A[r, c] = v
    for r in range(1, R + 1):
        for c in range(1, C + 1):
            for k in range(2, -1, -1):
                DP[r, c, k + 1] = max(DP[r, c, k + 1], DP[r, c, k] + A[r, c])
            for k in range(4):
                DP[r + 1, c, 0] = max(DP[r + 1, c, 0], DP[r, c, k])
                DP[r, c + 1, k] = max(DP[r, c + 1, k], DP[r, c, k])
    print(max(DP[R, C]))

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from sys import stdin
import numpy as np
from numba import jit

# stdin = open('/Users/dhesusan/workspace/com_pro/atcoder/python3/abc/abc175/e_1.txt')

input = stdin.readline

@jit
def main():
    R, C, K = map(int, input().rstrip().split())
    A = np.zeros((R + 1, C + 1), np.int64)
    DP = np.zeros((R + 1, C + 1, 4), np.int64)
    for _ in range(K):
        r, c, v = map(int, input().rstrip().split())
        A[r][c] = v
    for r in range(1, R + 1):
        for c in range(1, C + 1):
            for k in range(2, -1, -1):
                DP[r][c][k + 1] = max(DP[r][c][k + 1], DP[r][c][k] + A[r][c])
            for k in range(4):
                DP[r + 1][c][0] = max(DP[r + 1][c][0], DP[r][c][k])
                DP[r][c + 1][k] = max(DP[r][c + 1][k], DP[r][c][k])
    ans = 0
    for k in range(4):
        ans = max(DP[R][C][k], ans)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from bisect import bisect_right, bisect_left, insort
it = lambda: list(map(int, input().strip().split()))
INF = float('inf')


def main():
    R, C, K = it()
    items = [[] for _ in range(C)]
    for _ in range(K):
        r, c, v = it()
        items[r - 1].append((c - 1, v))
    if not C - 1 in items[R - 1]:
        items[R - 1].append((C - 1, 0))

    pos = []
    mem = defaultdict(lambda: -INF)
    pos.append(-1)
    mem[-1, 0] = 0
    for i in range(R):
        if items[i]:
            cur = []
            items[i].sort()
            for c, v in items[i]:
                a = b = e = d = -INF
                k = bisect_right(pos, c)
                if k > 0:
                    p = pos[k - 1]
                    l = max(mem[p, 0], mem[p, 1], mem[p, 2], mem[p, 3])
                    a = max(0, l)
                    b = max(b, l + v)
                if cur:
                    a = max(a, cur[-1][0])
                    b = max(b, cur[-1][1], cur[-1][0] + v)
                    e = max(e, cur[-1][2], cur[-1][1] + v)
                    d = max(d, cur[-1][3], cur[-1][2] + v)
                cur.append([a, b, e, d, c])
            for a, b, e, d, c in cur:
                k = bisect_left(pos, c)
                mem[c, 0] = max(mem[c, 0], a)
                mem[c, 1] = max(mem[c, 1], b)
                mem[c, 2] = max(mem[c, 2], e)
                mem[c, 3] = max(mem[c, 3], d)
                if k >= len(pos) or pos[k] != c:
                    pos[k:k] = [c]
    return max(mem.values())
        

def solve():
    R, C, K = it()
    grid = [[0] * C for _ in range(R)]
    for _ in range(K):
        r, c, v = it()
        grid[r - 1][c - 1] = v
    
    dp = [[[-INF] * 4 for _ in range(C + 1)] for _ in range(R + 1)]

    for i in range(R + 1):
        dp[i][0][0] = 0
    
    for j in range(C + 1):
        dp[0][j][0] = 0
    
    for i in range(1, R + 1):
        for j in range(1, C + 1):
            dp[i][j][0] = max(max(dp[i - 1][j]), dp[i][j - 1][0])
            if grid[i - 1][j - 1] > 0:
                dp[i][j][1] = max(max(dp[i - 1][j]) + grid[i - 1][j - 1], dp[i][j - 1][0] + grid[i - 1][j - 1], dp[i][j - 1][1])
                dp[i][j][2] = max(dp[i][j - 1][1] + grid[i - 1][j - 1], dp[i][j - 1][2])
                dp[i][j][3] = max(dp[i][j - 1][2] + grid[i - 1][j - 1], dp[i][j - 1][3])
            else:
                dp[i][j][1] = dp[i][j - 1][1]
                dp[i][j][2] = dp[i][j - 1][2]
                dp[i][j][3] = dp[i][j - 1][3]
    return max(dp[R][C])


if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Runtime Error

Solution code:
import sys
from numba import njit

R, C, K = map(int, input().split())
item = [[0]*C for _ in range(R)]
for s in sys.stdin.readlines():
    r, c, v = map(int, s.split())
    item[r-1][c-1] = v

@njit
def solve(R, C, K, item):
    DP = [[[0, 0, 0, 0] for _ in range(C)] for _ in range(R)]

    DP[0][0][1] = item[0][0]

    for i in range(R):
        for j in range(C):
            for k in range(4):
                if i > 0:  # 前の行から
                    DP[i][j][0] = max(DP[i][j][0], max(DP[i-1][j]))  # 取らない
                    DP[i][j][1] = max(DP[i][j][1], max(DP[i-1][j])+item[i][j])  # 取る

                if j > 0:  # 前の列から
                    DP[i][j][k] = max(DP[i][j][k], DP[i][j-1][k])  # 取らない
                    if k >= 1:
                        DP[i][j][k] = max(DP[i][j][k], DP[i][j-1][k-1]+item[i][j])  # 取る

    print(max(DP[R-1][C-1]))

solve(R, C, K, item)

Submission status: Runtime Error

Solution code:
from numba import jit

@jit
def solver(R, C, K, value, dp):
    # dp[行][列][その列で取った個数] = 価値の最大値
    dp = [[[0]*4 for _ in range(C+1)] for _ in range(R+1)]
    for r in range(R):
        for c in range(C):
            # アイテムを拾った個数と価値の対応を更新
            for i in range(3, 0, -1):
                dp[r][c][i] = max(dp[r][c][i], dp[r][c][i-1] + value[r][c])
            # 移動先に反映
            for k in range(4):
                dp[r+1][c][0] = max(dp[r+1][c][0], dp[r][c][k])
                dp[r][c+1][k] = max(dp[r][c+1][k], dp[r][c][k])
    return max(dp[R-1][C-1])


R, C, K = list(map(int, input().split()))
value = [[0]*C for _ in range(R)]
# 価値テーブルの作成
for i in range(K):
    r, c, v = list(map(int, input().split()))
    value[r-1][c-1] = v

print(solver(R, C, K, value))

Submission status: Runtime Error

Solution code:
from numba import jit

@jit
def solver(R, C, K, value, dp):
    # dp[行][列][その列で取った個数] = 価値の最大値
    dp = [[[0]*4 for _ in range(C+1)] for _ in range(R+1)]
    for r in range(R):
        for c in range(C):
            # アイテムを拾った個数と価値の対応を更新
            for i in range(3, 0, -1):
                dp[r][c][i] = max(dp[r][c][i], dp[r][c][i-1] + value[r][c])
            # 移動先に反映
            for k in range(4):
                dp[r+1][c][0] = max(dp[r+1][c][0], dp[r][c][k])
                dp[r][c+1][k] = max(dp[r][c+1][k], dp[r][c][k])
    return max(dp[R-1][C-1])


R, C, K = list(map(int, input().split()))
value = [[0]*C for _ in range(R)]
# 価値テーブルの作成
for i in range(K):
    r, c, v = list(map(int, input().split()))
    value[r-1][c-1] = v

print(solver(R, C, K, value, dp))

Submission status: Runtime Error

Solution code:
import sys

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

DP = [[[0, 0, 0, 0] for _ in range(C)] for _ in range(R)]

DP[0][0][1] = item[0][0]

for i in range(R):
    for j in range(C):
        for k in range(4):
            if i > 0:  # 前の行から
                DP[i][j][0] = max(DP[i][j][0], max(DP[i-1][j]))  # 取らない
                DP[i][j][1] = max(DP[i][j][1], max(DP[i-1][j])+item[i][j])  # 取る

            if j > 0:  # 前の列から
                DP[i][j][k] = max(DP[i][j][k], DP[i][j-1][k])  # 取らない
                if k >= 1:
                    DP[i][j][k] = max(DP[i][j][k], DP[i][j-1][k-1]+item[i][j])  # 取る

print(max(DP[R-1][C-1]))

Submission status: Runtime Error

Solution code:
import numpy as np
from numba import njit
@njit
def main():
    r,c,k=map(int,input().split())
    a=np.zeros((r,c),int)
    for _ in range(k):
        R,C,V=map(int,input().split())
        a[R-1][C-1]=V
    dp=np.zeros((r,c,4),int)
    dp[0][0][1]=a[0][0]
    for i in range(r):
        for j in range(c):
            for k in range(4):
                if i>0:#上
                    dp[i][j][0]=max(dp[i][j][0],dp[i-1][j][k])
                    dp[i][j][1]=max(dp[i][j][1],dp[i-1][j][k]+a[i][j])
                if j>0:#右
                    dp[i][j][k]=max(dp[i][j][k],dp[i][j-1][k])
                    if k>0:
                        dp[i][j][k]=max(dp[i][j][k],dp[i][j-1][k-1]+a[i][j])
    print(max(dp[-1][-1]))
main()

Submission status: Runtime Error

Solution code:
import numpy as np
from numba import njit
r,c,k=map(int,input().split())
a=np.zeros((r,c),int)
for _ in range(k):
    R,C,V=map(int,input().split())
    a[R-1][C-1]=V
@njit
def f():
    dp=np.zeros((r,c,4),int)
    dp[0][0][1]=a[0][0]
    for i in range(r):
        for j in range(c):
            for k in range(4):
                if i>0:#上
                    dp[i][j][0]=max(dp[i][j][0],dp[i-1][j][k])
                    dp[i][j][1]=max(dp[i][j][1],dp[i-1][j][k]+a[i][j])
                if j>0:#右
                    dp[i][j][k]=max(dp[i][j][k],dp[i][j-1][k])
                    if k>0:
                        dp[i][j][k]=max(dp[i][j][k],dp[i][j-1][k-1]+a[i][j])
    return max(dp[-1][-1])
print(f())

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# silviase copy
import numpy as np


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


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3

import numpy as np


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: Runtime Error

Solution code:
# rem = [0, 3]
def dp(r, c, rem):
  if r == R or c == C:
    return 0

  if rcd[r][c][rem] != -1:
    return rcd[r][c][rem]

  maxv = 0

  """if take"""

  if grid[r][c] and rem != 0:
    # max(right, bot)
    maxv = max(dp(r, c+1, rem-1) + grid[r][c], dp(r+1, c, 3) + grid[r][c])

  """if not take"""
  maxv = max(maxv, max(dp(r, c+1, rem), dp(r+1, c, 3)) )
  
  rcd[r][c][rem] = maxv
  return maxv

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

# gird with all value 0
grid = [ [0 for c in range(C)] for r in range(R) ]

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

# record [1-3]
rcd = [ [ [-1 for w in range(3 + 1)] for c in range(C) ] for r in range(R) ]

print(dp(0, 0, 3))

Submission status: Runtime Error

Solution code:
# rem = [0, 3]
def dp(r, c, rem):
  if r == R or c == C:
    return 0

  if rcd[r][c][rem] != -1:
    return rcd[r][c][rem]

  maxv = 0

  """if take"""

  if grid[r][c] and rem != 0:
    # right
    maxv = max(maxv, dp(r, c+1, rem-1) + grid[r][c])
    # bot
    maxv = max(maxv, dp(r+1, c, 3) + grid[r][c])

  """if not take"""
  
  # right
  maxv = max(maxv, dp(r, c+1, rem))
  # bot
  maxv = max(maxv, dp(r+1, c, 3))
  
  rcd[r][c][rem] = maxv
  return maxv


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

# gird with all value 0
grid = [ [0 for c in range(C)] for r in range(R) ]

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

# record [1-3]
rcd = [ [ [-1 for w in range(3 + 1)] for c in range(C) ] for r in range(R) ]

print(dp(0, 0, 3))

Submission status: Runtime Error

Solution code:
import sys

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


def main():
    R, C, N = map(int, input().split())
    a = [[0] * C for _ in range(R)]
    dp = [[[0] * 4 for i in range(C)] for j in range(R)]

    for i in range(N):
        r, c, v = map(int, input().split())
        a[r - 1][c - 1] = v

    """
    dp[i][j][k] := (i,j)にいるときの最大価値。その行ですでにk個選んだとき
    """

    for i in range(R):
        for j in range(C):
            for k in range(2, -1, -1):
                # アイテムを拾う遷移を最初にやる
                dp[i][j][k + 1] = max(dp[i][j][k + 1], dp[i][j][k] + a[i][j])
            for k in range(4):
                # 移動の遷移
                dp[i + 1][j][0] = max(dp[i + 1][j][0], dp[i][j][k])
                dp[i][j + 1][k] = max(dp[i][j + 1][k], dp[i][j][k])

    ans = 0
    for k in range(4):
        ans = max(ans, dp[R - 1][C - 1][k])
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from numba import njit

@njit
def resolve():
  R,C,K=map(int,input().split())
  V=[[0]*C for _ in range(R)]
  for i in range(K):
    r,c,v=map(int,input().split())
    V[r-1][c-1]=v
  dp=[[[0]*4 for _ in range(3005)] for _ in range(3005)]
  for i in range(R):
    for j in range(C):
      v=V[i][j]
      for k in range(2,-1,-1):
        dp[i][j][k+1]=max(dp[i][j][k+1],dp[i][j][k]+v)
      for k in range(4):
        dp[i+1][j][0]=max(dp[i+1][j][0],dp[i][j][k])
        dp[i][j+1][k]=max(dp[i][j+1][k],dp[i][j][k])
  print(max(dp[R-1][C-1]))

if __name__ == '__main__':
    resolve()

Submission status: Runtime Error

Solution code:
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 j in range(1,r+1):
        for k in range(1,c+1):
            for i in range(4):
                dp[i][j][k]=max(dp[i][j][k],dp[i][j-1][k])#,dp[i][j-1][k])
                dp[i][j][0]=max(dp[i][j][0],dp[i-1][j][k])
                if g[i-1][j-1]>0:
                    if k>0:
                        if dp[i][j][k]<dp[i][j-1][k-1]+g[i-1][j-1]:
                            dp[i][j][k]=dp[i][j-1][k-1]+g[i-1][j-1]
                    if dp[i][j][1]<dp[i-1][j][k]+g[i-1][j-1]:
                        dp[i][j][1]=dp[i-1][j][k]+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()

Submission status: Runtime Error

Solution code:
from numba import jit
@jit
def main():
	r,c,k=map(int,input().split())
	item=[[0]*c for i in range(r)]
	for i in range(k):
    	x,y,z=map(int,input().split())
    	item[x-1][y-1]=z
	dp=[[[0,0,0,0] for j in range(c)] for i in range(r)]
	if item[0][0]>0:
    	dp[0][0]=[0,item[0][0],0,0]
	for i in range(r):
    	for j in range(c):
        	for l in range(4):
            	if l<3:
                	#した行く分にはOK
                	if i!=r-1:
                    	dp[i+1][j][0]=max(dp[i+1][j][0],dp[i][j][l])
                    	if item[i+1][j]>0:
                        	dp[i+1][j][1]=max(dp[i+1][j][0],dp[i][j][l])+item[i+1][j]
                	#右は？
                	if j!=c-1:
                    	dp[i][j+1][l]=max(dp[i][j+1][l],dp[i][j][l])
                    	if item[i][j+1]>0:
                        	dp[i][j+1][l+1]=max(dp[i][j+1][l+1],dp[i][j][l]+item[i][j+1])
            	else:
                	#した行く分にはOK
                	if i!=r-1:
                    	dp[i+1][j][0]=max(dp[i+1][j][0],dp[i][j][l])
                    	if item[i+1][j]>0:
                        	dp[i+1][j][1]=max(dp[i+1][j][0],dp[i][j][l])+item[i+1][j]
                	#右は？
                	if j!=c-1:
                    	dp[i][j+1][l]=max(dp[i][j+1][l],dp[i][j][l])
	print(max(dp[r-1][c-1]))
main()