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:
def examA():
    S = SI()
    ans = 0
    if "R" in S:
        ans = 1
    if "RR" in S:
        ans = 2
    if "RRR" in S:
        ans = 3
    print(ans)
    return

def examB():
    N = I()
    L = LI()
    L.sort()
    cnt = 0
    for i in range(N):
        for j in range(i+1,N):
            for k in range(j+1,N):
                if L[i]==L[j]:
                    continue
                if L[j]==L[k]:
                    continue
                if L[i]+L[j]>L[k]:
                    cnt += 1
    ans = cnt
    print(ans)
    return

def examC():
    X, K, D = LI()
    if X<0:
        X = -X
    ans = inf
    if X>K*D:
        ans = X-K*D
        print(ans)
        return

    K -= X//D
    X -= D * (X//D)

    ans = X
    if K>0:
        if K%2==1:
            ans = abs(X-D)
    print(ans)
    return

def examD():
    N, K = LI()
    P = LI()
    C = LI()

    B = [i for i in range(N)]
    for i,p in enumerate(P):
        p -= 1
        B[i] = p

    locat_doubling = [[0]*N for _ in range(31)]
    score_doubling = [[0]*N for _ in range(31)]

    for i in range(N):
        locat_doubling[0][i] = i
        locat_doubling[1][B[i]] = i
        score_doubling[0][i] = 0
        score_doubling[1][B[i]] = C[i]
    for k in range(2,31):
        for i in range(N):
            locat_doubling[k][i] = locat_doubling[k-1][locat_doubling[k-1][i]]
            score_doubling[k][i] = score_doubling[k-1][i] + score_doubling[k - 1][locat_doubling[k - 1][i]]

    score = [[0,-inf] for i in range(N)]
    locate = [[i,i] for i in range(N)]
    ans = max(C)

    if ans<0:
        print(ans)
        return

    for k in range(30)[::-1]:
        for i in range(N):
            #print(score[i],locate[i])
            score[i][1] += score_doubling[k + 1][locate[i][1]]
            if score[i][1] < score[i][0]:
                locate[i][1] = locat_doubling[k + 1][locate[i][1]]
        if K&(1<<k)>0:
            for i in range(N):
                score[i][0] += score_doubling[k+1][locate[i][0]]
                locate[i][0] = locat_doubling[k+1][locate[i][0]]
    for s in score:
        ans = max(ans,s[0],s[1])
    print(ans)
    return

def examE():
    R, C, K = LI()
    V = [[-inf]*C for _ in range(R)]
    for _ in range(K):
        r,c,v = LI()
        V[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 = V[r][c]
            if 0<v:
                dp0[r+1][c+1] = max(dp0[r+1][c],dp0[r][c+1],dp1[r][c+1],dp2[r][c+1],dp3[r][c+1])
                dp1[r+1][c+1] = max(dp1[r+1][c],dp0[r+1][c]+v,dp0[r][c+1]+v,dp1[r][c+1]+v,dp2[r][c+1]+v,dp3[r][c+1]+v)
                dp2[r+1][c+1] = max(dp2[r+1][c],dp1[r+1][c]+v)
                dp3[r+1][c+1] = max(dp3[r+1][c],dp2[r+1][c]+v)
            else:
                dp0[r+1][c+1] = max(dp0[r+1][c],dp0[r][c+1],dp1[r][c+1],dp2[r][c+1],dp3[r][c+1])
                dp1[r+1][c+1] = dp1[r+1][c]
                dp2[r+1][c+1] = dp2[r+1][c]
                dp3[r+1][c+1] = dp3[r+1][c]

    ans = max(dp0[R][C],dp1[R][C],dp2[R][C],dp3[R][C])
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examE()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


r,c,k = list(map(int, input().split()))
d = {}
for i in range(k):
    rr,cc,vv = list(map(int, input().split()))
    d[rr,cc] = vv
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][j-1], dp0[i-1][j], dp1[i-1][j], dp2[i-1][j], dp3[i-1][j])
        dp1[i][j] = dp1[i][j-1]
        dp2[i][j] = dp2[i][j-1]
        dp3[i][j] = dp3[i][j-1]
        if (i,j) in d:
            v = d[i,j]
            dp1[i][j] = max(dp1[i][j], dp0[i][j-1]+v, dp0[i-1][j]+v, dp1[i-1][j]+v,dp2[i-1][j]+v, dp3[i-1][j]+v)
            dp2[i][j] = max(dp2[i][j], dp1[i][j-1]+v)
            dp3[i][j] = max(dp3[i][j], dp2[i][j-1]+v)
ans = max(dp0[r][c], dp1[r][c], dp2[r][c], dp3[r][c])
print(ans)

Submission status: Accepted

Solution code:
def numba_compile(numba_config):
    import os, sys
    if sys.argv[-1] == "ONLINE_JUDGE":
        from numba import njit
        from numba.pycc import CC
        cc = CC("my_module")
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature)(func)
            cc.export(func.__name__, signature)(func)
        cc.compile()
        exit()
    elif os.name == "posix":
        exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
        for func, _ in numba_config:
            globals()[func.__name__] = vars()[func.__name__]
    else:
        from numba import njit
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature, cache=True)(func)
        print("compiled!", file=sys.stderr)

import numpy as np

def solve(R, C, K, RCV):
    # dp[y][x][n]
    M = np.zeros((R+1, C+1), dtype=np.int64)
    for i in range(K):
        r, c, v = RCV[i]
        M[r, c] = v
    dp = np.zeros((R+1, C+1, 4), dtype=np.int64)
    for y in range(1, R+1):
        for x in range(1, C+1):
            for n in range(4):
                if n == 0:
                    dp[y, x, n] = max(
                        dp[y, x-1, 0],
                        dp[y-1, x, :].max()
                    )
                if n > 0:
                    dp[y, x, n] = max(
                        dp[y, x-1, n],
                        dp[y, x-1, n-1] + M[y, x],
                        dp[y-1, x, :].max() + M[y, x]
                    )
    ans = dp[R, C].max()
    print(ans)

numba_compile([
    [solve, "(i8,i8,i8,i8[:,:])"],
])

import sys
def main():
    R, C, K = map(int, input().split())
    RCV = np.array(sys.stdin.read().split(), dtype=np.int64).reshape(K, 3)
    solve(R, C, K, RCV)

main()

Submission status: Accepted

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

print(main())

Submission status: Accepted

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

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

items = [0] * R * C

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

dp = [0] * 4 * R * C

dp[1] = items[0]

def ind(i,j,k):
    return 4 * C * i + 4 * j + k

for row in range(R):
    for col in range(C):
        for pick in range(4):
            curr = dp[ind(row,col,pick)]
            #Go Right
            if col + 1 < C:
                dp[ind(row,col+1,pick)] = max(curr, dp[ind(row,col+1,pick)])
                if pick < 3:
                    dp[ind(row,col+1,pick+1)] = max(curr + items[C * row + col+1], dp[ind(row,col+1,pick+1)])
            #Go Down
            if row + 1 < R:
                dp[ind(row+1,col,0)] = max(curr, dp[ind(row+1,col,0)])
                dp[ind(row+1,col,1)] = max(curr + items[C * (row+1) + col], dp[ind(row+1,col,1)])
                    

print(max(dp))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

h,w,k,*hwk = map(int,read().split())
it = iter(hwk)
b = [[0]*w for _ in range(h+1)]
for hi,wi,ki in zip(it,it,it):
    b[hi-1][wi-1] = ki

dp = [[0]*4 for _ in range(w)]
for i in range(h):
    ndp = [[0]*4 for _ in range(w)]
    for j in range(w):
        if j != 0:
            ndp[j] = ndp[j-1][:]
        ndp[j][0] = max(ndp[j][0],max(dp[j]))
        
        
        for k in range(3,0,-1):
            ndp[j][k] = max(ndp[j][k],ndp[j][k-1]+ b[i][j])
        

    dp = ndp

print(max(dp[-1]))

#print(dp)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(500005)
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().strip()

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

I = -9999999999999999999
dp = [I] * C
dp[0] = 0
for i in range(R):
    ndp = [I] * C
    row = g[i]
    ldp = [I] * 4
    for j in range(C):
        ldp[0] = max(ldp[0], dp[j])
        for k in range(2,-1,-1):
            ldp[k+1] = max(ldp[k+1], ldp[k] + row[j])
        ndp[j] = max(ldp)
    dp = ndp

print(dp[C-1])

Submission status: Accepted

Solution code:
mod = 1000000007
eps = 10**-9
inf = 10**16


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

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

    dp0 = [[-inf] * W for _ in range(H)]
    dp1 = [[-inf] * W for _ in range(H)]
    dp2 = [[-inf] * W for _ in range(H)]
    dp3 = [[-inf] * W for _ in range(H)]
    dp0[0][0] = 0
    if grid[0][0] > 0:
        dp1[0][0] = grid[0][0]
    for h in range(H):
        for w in range(W):
            if w-1 >= 0:
                dp0[h][w] = max(dp0[h][w], dp0[h][w-1])
                dp1[h][w] = max(dp1[h][w], dp1[h][w - 1])
                dp2[h][w] = max(dp2[h][w], dp2[h][w - 1])
                dp3[h][w] = max(dp3[h][w], dp3[h][w - 1])
            if h-1 >= 0:
                dp0[h][w] = max(dp0[h][w], dp0[h-1][w], dp1[h-1][w], dp2[h-1][w], dp3[h-1][w])
            v = grid[h][w]
            if v > 0:
                if w-1 >= 0:
                    dp1[h][w] = max(dp1[h][w], dp0[h][w - 1] + v)
                    dp2[h][w] = max(dp2[h][w], dp1[h][w - 1] + v)
                    dp3[h][w] = max(dp3[h][w], dp2[h][w - 1] + v)
                if h-1 >= 0:
                    dp1[h][w] = max(dp1[h][w], dp0[h-1][w] + v, dp1[h-1][w] + v, dp2[h-1][w]+v, dp3[h-1][w]+v)
    print(max(dp0[-1][-1], dp1[-1][-1], dp2[-1][-1], dp3[-1][-1]))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit((i8, i8, i8, i8[:]), cache=True)
def main(H, W, K, XYV):
    G = np.zeros((H + 1, W + 1), np.int64)
    for i in range(0, 3 * K, 3):
        x, y, v = XYV[i:i + 3]
        G[x - 1, y - 1] = v
    dp = np.zeros((W + 1, 4), np.int64)
    for h in range(H):
        newdp = np.zeros((W + 1, 4), np.int64)
        for n in range(4):
            newdp[:, 0] = np.maximum(newdp[:, 0], dp[:, n])
        dp = newdp
        for w in range(W):
            for n in range(2, -1, -1):
                # ひろう
                dp[w, n + 1] = max(dp[w, n + 1], dp[w, n] + G[h, w])
            for n in range(4):
                dp[w + 1, n] = max(dp[w + 1, n], dp[w, n])
    return dp.max()

H, W, K = map(int, readline().split())
XYV = np.array(read().split(), np.int64)

print(main(H, W, K, XYV))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
R,C,K=map(int, sys.stdin.readline().split())

value=defaultdict(lambda: 0)
value=[ [0 for _ in range(C+1)] for __ in range(R+1) ]
for _ in range(K):
    r,c,v=map(int, sys.stdin.readline().split())
    value[r][c]=v

dp0=[0]*(C+1)
dp1=[0]*(C+1)
dp2=[0]*(C+1)
dp3=[0]*(C+1)

#初期化
for c in range(1,C+1):
    dp0[c]=0
dp1[1]=value[(1,1)]

for r in range(1,R+1):
    for c in range(2,C+1):
        #今のマスにアイテムがある場合
        if 0<value[r][c]:
            #今のマスまでで1個取得=max(左のマスまでで1個取得, 今のマスで0個取得+v )
            dp1[c]=max( dp1[c-1], dp0[c])
            #今のマスまでで2個取得=max(左のマスまでで2個取得, 左のマスまでで1個取得+v)
            dp2[c]=max( dp2[c-1], dp1[c-1])
            #今のマスまでで3個取得=max(左のマスまでで3個取得, 左のマスまでで2個取得+v)
            dp3[c]=max( dp3[c-1], dp2[c-1])
        #今のマスにアイテムがない場合
        else:
            dp1[c]=dp1[c-1]
            dp2[c]=dp2[c-1]
            dp3[c]=dp3[c-1]
        
    #上の行にアイテムをコピー
    #for c in range(1,C+1):
    #    dp0[c]=max(dp0[c],dp1[c],dp2[c],dp3[c])
    #dp1=defaultdict(lambda: float("-inf")) 
    #dp2=defaultdict(lambda: float("-inf")) 
    #dp3=defaultdict(lambda: float("-inf")) 

print dp0[C]

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
R,C,K=map(int, sys.stdin.readline().split())

value=defaultdict(lambda: 0)
value=[ [0 for _ in range(C+1)] for __ in range(R+1) ]
for _ in range(K):
    r,c,v=map(int, sys.stdin.readline().split())
    value[r][c]]=v

dp0=[0]*(C+1)
dp1=[0]*(C+1)
dp2=[0]*(C+1)
dp3=[0]*(C+1)

#初期化
for c in range(1,C+1):
    dp0[c]=0
dp1[1]=value[(1,1)]

for r in range(1,R+1):
    for c in range(2,C+1):
        #今のマスにアイテムがある場合
        if 0<value[r][c]:
            #今のマスまでで1個取得=max(左のマスまでで1個取得, 今のマスで0個取得+v )
            dp1[c]=max( dp1[c-1], dp0[c])
            #今のマスまでで2個取得=max(左のマスまでで2個取得, 左のマスまでで1個取得+v)
            dp2[c]=max( dp2[c-1], dp1[c-1])
            #今のマスまでで3個取得=max(左のマスまでで3個取得, 左のマスまでで2個取得+v)
            dp3[c]=max( dp3[c-1], dp2[c-1])
        #今のマスにアイテムがない場合
        else:
            dp1[c]=dp1[c-1]
            dp2[c]=dp2[c-1]
            dp3[c]=dp3[c-1]
        
    #上の行にアイテムをコピー
    #for c in range(1,C+1):
    #    dp0[c]=max(dp0[c],dp1[c],dp2[c],dp3[c])
    #dp1=defaultdict(lambda: float("-inf")) 
    #dp2=defaultdict(lambda: float("-inf")) 
    #dp3=defaultdict(lambda: float("-inf")) 

print dp0[C]

Submission status: Runtime Error

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

# vis = [[False]*C for _ in range(R)]
mesh = [[0]*C for _ in range(R)]

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

# print(vis)
# print(*mesh,sep='\n')

def dfs(i, j, rows):
    # print('i {} j {} rows {}'.format(i,j,rows))
    # print('i {} j {}'.format(i,j))
    # print(*rows,sep='\n')

    v = 0
    if i == R-1 and j == C-1:
        rows[i].append(mesh[i][j])
        # print('rows {}'.format(rows))
        import heapq
        for row in rows:
            r = []
            for x in row:
                heapq.heappush(r, -x)
            if len(r): v += -heapq.heappop(r)
            if len(r): v += -heapq.heappop(r)
            if len(r): v += -heapq.heappop(r)
        rows[i].pop()
        return v
    if i == R or j == C: return v
    # if vis[i][j]: return v
    # vis[i][j] = True
    rows[i].append(mesh[i][j])
    if j+1 < C: v = dfs(i,   j+1, rows)
    if i+1 < R: v = max(v, dfs(i+1, j  , rows))
    rows[i].pop()
    return v

ans = dfs(0, 0, [[] for _ in range(R)])
print(ans)

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
P = [i-1 for i in map(int, input().split())]
C = list(map(int, input().split()))

ans = -float("inf")

for i in range(N):
    curr = 0
    curr_score = 0


    loop_score = 0
    loop_length = 0
    K_ = K
    j = i
    while True:
        j = P[j]
        loop_score += C[j]
        loop_length += 1
        if j == i:
            break
    if loop_score > 0:
        curr_score += loop_score * (K//loop_length)
        curr = curr_score
        K_ -= loop_length*(K//loop_length)
    for k in range(K_):
        j = P[j]
        curr_score += C[j]
        curr = max(curr, curr_score)
    ans = max(curr, ans)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
r,c,k=map(int, input().split())
v={}

for _ in range(k):
    ri,ci,vi=map(int, input().split())
    v[(ri-1,ci-1)]=vi
    
dp=[[0]*4 for _ in range(c+1)]
for j in range(c):
    if (0,j) in v:
        for t in range(1,4):
            dp[j][t]=max(dp[j-1][t-1]+v[(0,j)],dp[j-1][t])
    else:
        for t in range(1,4):
            dp[j][t]=dp[j-1][t]
for i in range(1,r):
    #dp2=[[0]*4 for _ in range(c+1)]
    dp2=[[dp[j][3] for _ in range(4)] for j in range(c+1)]
    
    #dp2=[[dp[x][3] for _ in range(4)] if (i,x) not in v else [dp[x][3]]+[dp[x][3]+v[(i,x)] for _ in range(3)] for x in range(c+1)]
    for j in range(c):
        if (i,j) in v:
            for t in range(1,4):
                dp2[j][t]=max(dp2[j-1][t-1]+v[(i,j)],dp2[j-1][t],dp2[j][t],dp[j][3]+v[(i,j)])
        else:
            for t in range(1,4):
                dp2[j][t]=max(dp2[j-1][t],dp2[j][t],dp[j][3])
    dp=dp2
print(max(dp2[-2]))

Submission status: Runtime Error

Solution code:

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

rcvs = rcvs

for i in range(len(rcvs)):
    rcvs[i][0] -= 1
    rcvs[i][1] -= 1

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


for rcv in rcvs:
    rewards[rcv[0],rcv[1]] = rcv[2]

dp = [[[0 for _ in range(4)] for _ in range(C+1)] for _ in range(R+1)]
answer = 0

for i in range(R):
    for j in range(C):
        reward = rewards[i][j]
        dp[i+1,j+1,0] = max(dp[i,j+1])
        dp[i+1,j+1,1] = dp[i+1,j+1,0] + reward
        
        for k in range(4): # move downside without selecting
            candidate = dp[i+1,j,k]
            dp[i+1,j+1,k] = max(dp[i+1,j,k], dp[i+1,j+1,k])
        if reward > 0:
            for k in range(3):
                dp[i+1,j+1,k+1] = max(dp[i+1,j,k]+reward,dp[i+1,j+1,k+1])
print(max(dp[-1,-1]))

Submission status: Runtime Error

Solution code:
import numpy as np

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

rcvs = np.array(rcvs, dtype = "int16")

for i in range(len(rcvs)):
    rcvs[i][0] -= 1
    rcvs[i][1] -= 1

rewards = np.array([[0 for _ in range(C)] for _ in range(R)], dtype="int16")


for rcv in rcvs:
    rewards[rcv[0],rcv[1]] = rcv[2]

dp = [[[0 for _ in range(4)] for _ in range(C+1)] for _ in range(R+1)]
dp = np.array(dp)
answer = 0

for i in range(R):
    for j in range(C):
        reward = rewards[i][j]
        dp[i+1,j+1,0] = max(dp[i,j+1])
        dp[i+1,j+1,1] = dp[i+1,j+1,0] + reward
        
        for k in range(4): # move downside without selecting
            candidate = dp[i+1,j,k]
            dp[i+1,j+1,k] = max(dp[i+1,j,k], dp[i+1,j+1,k])
        if reward > 0:
            for k in range(3):
                dp[i+1,j+1,k+1] = max(dp[i+1,j,k]+reward,dp[i+1,j+1,k+1])
print(max(dp[-1,-1]))

Submission status: Runtime Error

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


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

@njit
def solve(rcvs):
    rcvs = np.array(rcvs, dtype=np.int64)
    
    for i in range(len(rcvs)):
        rcvs[i,0] -= 1
        rcvs[i,1] -= 1
    
    rewards = np.array([[0 for _ in range(C)] for _ in range(R)], dtype=np.int64)
    
    for rcv in rcvs:
        rewards[rcv[0],rcv[1]] = rcv[2]
    
    dp = np.array([[[0 for _ in range(4)] for _ in range(C+1)] for _ in range(R+1)], dtype=np.int64)
    
    for i in range(R):
        for j in range(C):
            reward = rewards[i][j]
            dp[i+1,j+1,0] = max(dp[i,j+1])
            dp[i+1,j+1,1] = dp[i+1,j+1,0] + reward
            
            for k in range(4): # move downside without selecting
                dp[i+1,j+1,k] = max(dp[i+1,j,k], dp[i+1,j+1,k])
            for k in range(3):
                dp[i+1,j+1,k+1] = max(dp[i+1,j,k]+reward,dp[i+1,j+1,k+1])
    print(np.max(dp[-1,-1]))

if __name__ == "__main__":
    solve(rcvs)

Submission status: Runtime Error

Solution code:
import numpy as np

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

rcvs = np.array(rcvs, dtype = "int16")

for i in range(len(rcvs)):
    rcvs[i][0] -= 1
    rcvs[i][1] -= 1

rewards = np.array([[0 for _ in range(C)] for _ in range(R)], dtype="int16")


for rcv in rcvs:
    rewards[rcv[0],rcv[1]] = rcv[2]
    
#%%

dp = [[[0 for _ in range(4)] for _ in range(C+1)] for _ in range(R+1)]
dp = np.array(dp)
answer = 0

for i in range(R):
    for j in range(C):
        reward = rewards[i][j]
        dp[i+1,j+1,0] = max(dp[i,j+1])
        dp[i+1,j+1,1] = dp[i+1,j+1,0] + reward
        
        for k in range(4): # move downside without selecting
            candidate = dp[i+1,j,k]
            dp[i+1,j+1,k] = max(dp[i+1,j,k], dp[i+1,j+1,k])
        for k in range(3):
            dp[i+1,j+1,k+1] = max(dp[i+1,j,k]+reward,dp[i+1,j+1,k+1])
print(max(dp[-1,-1]))

Submission status: Runtime Error

Solution code:
import numpy as np
from numba import njit

rr,cc,kk=map(int,input().split())
goods=np.array([list(map(int,input().split())) for _ in range(kk)],dtype=np.int)
gg=np.zeros((rr,cc),dtype=np.int)
for cr,ccc,ck in goods:
    gg[cr-1][ccc-1]=ck

@njit(cache=True)
def calc(r,c,g):
    dp=-1*np.ones((r+1,c+1,4),dtype=np.int)
    maxlst=np.zeros((r+1,c+1),dtype=np.int)

    dp[:,0,0]=0
    dp[0,:,0]=0
    
    for i in range(r):
        for j in range(c):
            tmp=0
            for k in range(3):
                if g[i][j]>0 and dp[i+1][j][k]>=0:
                    dp[i+1][j+1][k+1]=max(dp[i+1][j][k+1],dp[i+1][j][k]+g[i][j])
                else:
                    dp[i+1][j+1][k+1]=dp[i+1][j][k+1]
                tmp=max(tmp,dp[i+1][j+1][k+1])
            
            dp[i+1][j+1][0]=max(maxlst[i][j+1],dp[i+1][j][0])
            tmp=max(tmp,dp[i+1][j+1][0])
            
            if g[i][j]>0 and dp[i+1][j+1][0]>=0:
                dp[i+1][j+1][1]=max(dp[i+1][j+1][1],dp[i+1][j+1][0]+g[i][j])
                tmp=max(tmp,dp[i+1][j+1][1])
            
            maxlst[i+1][j+1]=tmp
    
    return maxlst[r][c]
            
print(calc(rr,cc,gg))

Submission status: Runtime Error

Solution code:
import numpy as np
from numba import njit

rr,cc,kk=map(int,input().split())
goods=np.array([list(map(int,input().split())) for _ in range(kk)],dtype=np.int)
gg=np.zeros((rr,cc),dtype=np.int)
for cr,ccc,ck in goods:
    gg[cr-1][ccc-1]=ck

@njit
def calc(r,c,g):
    dp=-1*np.ones((r+1,c+1,4),dtype=np.int)
    maxlst=np.zeros((r+1,c+1),dtype=np.int)

    dp[:,0,0]=0
    dp[0,:,0]=0
    
    for i in range(r):
        for j in range(c):
            tmp=0
            for k in range(3):
                if g[i][j]>0 and dp[i+1][j][k]>=0:
                    dp[i+1][j+1][k+1]=max(dp[i+1][j][k+1],dp[i+1][j][k]+g[i][j])
                else:
                    dp[i+1][j+1][k+1]=dp[i+1][j][k+1]
                tmp=max(tmp,dp[i+1][j+1][k+1])
            
            dp[i+1][j+1][0]=max(maxlst[i][j+1],dp[i+1][j][0])
            tmp=max(tmp,dp[i+1][j+1][0])
            
            if g[i][j]>0 and dp[i+1][j+1][0]>=0:
                dp[i+1][j+1][1]=max(dp[i+1][j+1][1],dp[i+1][j+1][0]+g[i][j])
                tmp=max(tmp,dp[i+1][j+1][1])
            
            maxlst[i+1][j+1]=tmp
    
    return maxlst[r][c]
            
print(calc(rr,cc,gg))

Submission status: Runtime Error

Solution code:
import numpy as np
from numba import njit

rr,cc,k=map(int,input().split())
goods=np.array([list(map(int,input().split())) for _ in range(kk)],dtype=np.int)
gg=np.zeros((rr,cc),dtype=np.int)
for cr,ccc,ck in goods:
    gg[cr-1][ccc-1]=ck

@njit
def calc(r,c,g):
    dp=-1*np.ones((r+1,c+1,4),dtype=np.int)
    maxlst=np.zeros((r+1,c+1),dtype=np.int)

    dp[:,0,0]=0
    dp[0,:,0]=0
    
    for i in range(r):
        for j in range(c):
            tmp=0
            for k in range(3):
                if g[i][j]>0 and dp[i+1][j][k]>=0:
                    dp[i+1][j+1][k+1]=max(dp[i+1][j][k+1],dp[i+1][j][k]+g[i][j])
                else:
                    dp[i+1][j+1][k+1]=dp[i+1][j][k+1]
                tmp=max(tmp,dp[i+1][j+1][k+1])
            
            dp[i+1][j+1][0]=max(maxlst[i][j+1],dp[i+1][j][0])
            tmp=max(tmp,dp[i+1][j+1][0])
            
            if g[i][j]>0 and dp[i+1][j+1][0]>=0:
                dp[i+1][j+1][1]=max(dp[i+1][j+1][1],dp[i+1][j+1][0]+g[i][j])
                tmp=max(tmp,dp[i+1][j+1][1])
            
            maxlst[i+1][j+1]=tmp
    
    return maxlst[r][c]
            
print(calc(rr,cc,gg))

Submission status: Runtime Error

Solution code:
import numpy as np
from numba import njit

r,c,k=map(int,input().split())
goods=np.array([list(map(int,input().split())) for _ in range(k)],dtype=np.int)
g=np.zeros((r,c),dtype=np.int)
for cr,cc,ck in goods:
    g[cr-1][cc-1]=ck

@njit
def calc(r,c,g):
    dp=-1*np.ones((r+1,c+1,4),dtype=np.int)
    maxlst=np.zeros((r+1,c+1),dtype=np.int)

    dp[:,0,0]=0
    dp[0,:,0]=0
    
    for i in range(r):
        for j in range(c):
            tmp=0
            for k in range(3):
                if g[i][j]>0 and dp[i+1][j][k]>=0:
                    dp[i+1][j+1][k+1]=max(dp[i+1][j][k+1],dp[i+1][j][k]+g[i][j])
                else:
                    dp[i+1][j+1][k+1]=dp[i+1][j][k+1]
                tmp=max(tmp,dp[i+1][j+1][k+1])
            
            dp[i+1][j+1][0]=max(maxlst[i][j+1],dp[i+1][j][0])
            tmp=max(tmp,dp[i+1][j+1][0])
            
            if g[i][j]>0 and dp[i+1][j+1][0]>=0:
                dp[i+1][j+1][1]=max(dp[i+1][j+1][1],dp[i+1][j+1][0]+g[i][j])
                tmp=max(tmp,dp[i+1][j+1][1])
            
            maxlst[i+1][j+1]=tmp
    
    return maxlst[r][c]
            
print(calc(r,c,g))

Submission status: Runtime Error

Solution code:
from numba import njit

r,c,k=map(int,input().split())
goods=[list(map(int,input().split())) for _ in range(k)]
g=[[0]*c for _ in range(r)]
for cr,cc,ck in goods:
    g[cr-1][cc-1]=ck

@njit
def calc(r,c,g):
    dp=[[[-1]*4 for _ in range(c+1)] for _ in range(r+1)]
    maxlst=[[0]*(c+1) for _ in range(r+1)]

    for i in range(r):
        dp[i][0][0]=0
    for j in range(c):
        dp[0][j][0]=0
    
    for i in range(r):
        for j in range(c):
            tmp=0
            for k in range(3):
                if g[i][j]>0 and dp[i+1][j][k]>=0:
                    dp[i+1][j+1][k+1]=max(dp[i+1][j][k+1],dp[i+1][j][k]+g[i][j])
                else:
                    dp[i+1][j+1][k+1]=dp[i+1][j][k+1]
                tmp=max(tmp,dp[i+1][j+1][k+1])
            
            dp[i+1][j+1][0]=max(maxlst[i][j+1],dp[i+1][j][0])
            tmp=max(tmp,dp[i+1][j+1][0])
            
            if g[i][j]>0 and dp[i+1][j+1][0]>=0:
                dp[i+1][j+1][1]=max(dp[i+1][j+1][1],dp[i+1][j+1][0]+g[i][j])
                tmp=max(tmp,dp[i+1][j+1][1])
            
            maxlst[i+1][j+1]=tmp
    
    return maxlst[r][c]
            
print(calc(r,c,g))

Submission status: Runtime Error

Solution code:
R, C, K = map(int, input().split())
a = [[0]*C for _ in range(R)]
dp = [[[0]*4 for _ in range(C)] for _ in range(R)]
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 i in range(4):
    ans = max(ans, dp[R-1][C-1][i])

print(ans)