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: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()

R, C, k = (int(x) for x in input().split())
RCV = [tuple(int(x) for x in input().split()) for _ in range(k)]
V = [[0] * (C + 5) for _ in range(R + 5)]
for r, c, v in RCV:
    V[r][c] = v
# dp[i][j][3]
dp = [[[0] * 4 for _ in range(C + 5)] for _ in range(R + 5)]
for i in range(1, R + 3):
    for j in range(1, C + 3):
        for k in range(4):
            # 行移動
            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])+V[i][j])
            # 列移動
            if k > 0:
                dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k - 1] + V[i][j])
            dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k])
print(max(dp[R][C]))

Submission status: Time Limit Exceeded

Solution code:
R, C, k = (int(x) for x in input().split())
RCV = [tuple(int(x) for x in input().split()) for _ in range(k)]
V = [[0] * (C + 5) for _ in range(R + 5)]
for r, c, v in RCV:
    V[r][c] = v
# dp[i][j][3]
dp = [[[0] * 4 for _ in range(C + 5)] for _ in range(R + 5)]
for i in range(1, R + 3):
    for j in range(1, C + 3):
        for k in range(4):
            # 行移動
            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])+V[i][j])
            # 列移動
            if k > 0:
                dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k - 1] + V[i][j])
            dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k])
print(max(dp[R][C]))

Submission status: Time Limit Exceeded

Solution code:
R, C, K = map(int, input().split())
C_L = [[0] * (C+1) for _ in range(R+1)]
for _ in range(K):
    _r, _c, _v = map(int, input().split())
    C_L[_r][_c] = _v

# dp[i][j][k] : (i,j)の位置にいるとき、i行目でk個アイテムを拾っている場合の最大値
dp = [[[float("-Inf")] * 4 for _ in range(C+1)] for __ in range(R+1)]

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

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

Submission status: Time Limit Exceeded

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)] for _ in range(R+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):
    for j in range(1, C+1):
        up_max = max(dp[i-1][j])
        p = field[i][j]
        dp[i][j][0] = max(up_max, dp[i][j-1][0])
        dp[i][j][1] = max(up_max+p, dp[i][j-1][1], dp[i][j-1][0]+p)
        dp[i][j][2] = max(dp[i][j-1][2], dp[i][j-1][1]+p)
        dp[i][j][3] = max(dp[i][j-1][3], dp[i][j-1][2]+p)

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

Submission status: Time Limit Exceeded

Solution code:
import sys


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


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

    field = [[0 for j in range(C)] for i in range(R)]

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

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

    for i in range(R):
        for j in range(C):
            ct = field[i][j]
            premax = max(dp[i - 1][j][0], dp[i - 1][j][1], dp[i - 1][j][2], dp[i - 1][j][3])
            if ct == 0:
                dp[i][j][0] = max(dp[i][j - 1][0], premax)

                for k in range(1, 4):
                    if j > 0:
                        dp[i][j][k] = dp[i][j - 1][k]
            else:
                dp[i][j][0] = max(dp[i][j - 1][0], premax)
                dp[i][j][1] = max(ct + max(dp[i][j - 1][0], premax), dp[i][j - 1][1])
                for k in range(2, 4):
                    if j > 0:
                        dp[i][j][k] = max(dp[i][j - 1][k - 1] + ct, dp[i][j - 1][k])

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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
R, C, K = map(int, input().split())
L = 4
items = [[0 for c in range(C+1)] for r in range(R+1)]
for k in range(K):
    r, c, v = map(int, input().split())
    items[r][c] = v
dp = [[[0 for limit in range(L)] for c in range(C+1)] for r in range(R+1)]
for r in range(1, R+1):
    for c in range(1, C+1):
        upper = max(dp[r-1][c])
        left = dp[r][c-1]
        item = items[r][c]
        dp[r][c][0] = max(upper, left[0])
        dp[r][c][1] = max(upper+item, left[1])
        dp[r][c][2] = max(left[1] + item, left[2])
        dp[r][c][3] = max(left[2] + item, left[3])
print(max(dp[R][C]))

Submission status: Time Limit Exceeded

Solution code:
R, C, K = map(int, input().split())
L = 4
items = [[0 for c in range(C)] for r in range(R)]
for k in range(K):
    r, c, v = map(int, input().split())
    items[r-1][c-1] = v
dp = [[[0 for limit in range(L)] for c in range(C)] for r in range(R)]
for r in range(R):
    for c in range(C):
        upper = 0 if r == 0 else max(dp[r-1][c])
        left = [0]*L if c == 0 else dp[r][c-1]
        item = items[r][c]
        dp[r][c][0] = max(upper, left[0])
        dp[r][c][1] = max(upper+item, left[1])
        dp[r][c][2] = max(left[1] + item, left[2])
        dp[r][c][3] = max(left[2] + item, left[3])
print(max(dp[R-1][C-1]))

Submission status: Time Limit Exceeded

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

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


val = dict()
for _ in range(k):
    rr,cc,vv = map(int,input().split())
    rr -= 1
    cc -= 1
    val[rr*C + cc] = vv

dp = [[0,0,0,0] for i in range(R*C)]

for i in range(R):
    for j in range(C):
        idx  = i*C + j
        if idx in val:
            v = val[idx]
        else:
            v = 0

        if i == 0:
            if j == 0:
                dp[idx][1] = v
            else:
                dp[idx][1] = max(dp[idx-1][1],v)
                dp[idx][2] = max(dp[idx-1][2],dp[idx-1][1] + v)
                dp[idx][3] = max(dp[idx-1][3],dp[idx-1][2] + v)
        else:
            if j == 0:
                dp[idx][0] = max(dp[idx-C][0],dp[idx-C][1],dp[idx-C][2],dp[idx-C][3])
                dp[idx][1] = dp[idx][0] + v
            else:
                dp[idx][0] = max(dp[idx-C][0],dp[idx-C][1],dp[idx-C][2],dp[idx-C][3],dp[idx-1][0])
                dp[idx][1] = max(dp[idx-1][1],dp[idx][0] + v)
                dp[idx][2] = max(dp[idx-1][2],dp[idx-1][1] + v)
                dp[idx][3] = max(dp[idx-1][3],dp[idx-1][2] + v)

print(max(dp[-1]))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))


r,c,k = readints()
a = [[0]*(c+1) for i in range(r+1)]

for i in range(k):
    R,C,V = readints()
    a[R][C] = V

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

for i in range(1,r+1):
    for j in range(1,c+1):
        for l in range(4):
            if l == 0:
                dp[i][j][l] = max(dp[i][j-1][l], dp[i-1][j][3])
            else:
                dp[i][j][l] = max(dp[i][j-1][l], dp[i-1][j][3]+a[i][j], dp[i][j-1][l-1]+a[i][j])


print(dp[r][c][3])

Submission status: Time Limit Exceeded

Solution code:
def solve():
    R,C,K = map(int, input().split())
    #value = [[0 for _ in range(C)] for _ in range(R)]
    dp = [[[0,0,0,0,0] for _ in range(C+1)] for _ in range (R+1)]
    for _ in range(K):
        r,c,v = map(int, input().split())
        dp[r][c][4] = v

    #print(value)
    #print(dp)

    for r in range(1, R+1):
        for c in range(1, C+1):
            v = dp[r][c][4]
            prow = max(dp[r-1][c][:4])
            if v == 0: # no item
                dp[r][c][0] = max(prow, dp[r][c-1][0])
                dp[r][c][1] = dp[r][c-1][1]
                dp[r][c][2] = dp[r][c-1][2]
                dp[r][c][3] = dp[r][c-1][3]
            else:
                dp[r][c][0] = max(prow, dp[r][c-1][0])
                dp[r][c][1] = max(dp[r][c-1][1], dp[r][c-1][0] + v, prow + v)
                dp[r][c][2] = max(dp[r][c-1][2], dp[r][c-1][1] + v)
                dp[r][c][3] = max(dp[r][c-1][3], dp[r][c-1][2] + v)

    #print(dp)
    print(max(dp[R][C][:4]))

solve()

Submission status: Time Limit Exceeded

Solution code:
def solve():
    R,C,K = map(int, input().split())
    value = [[0 for _ in range(C)] for _ in range(R)]
    dp = [[[0,0,0,0] for _ in range(C+1)] for _ in range (R+1)]
    for _ in range(K):
        r,c,v = map(int, input().split())
        value[r-1][c-1] = v

    #print(value)
    #print(dp)

    for r in range(1, R+1):
        for c in range(1, C+1):
            v = value[r-1][c-1]
            if v == 0: # no item
                dp[r][c][0] = max(max(dp[r-1][c]), dp[r][c-1][0])
                dp[r][c][1] = dp[r][c-1][1]
                dp[r][c][2] = dp[r][c-1][2]
                dp[r][c][3] = dp[r][c-1][3]
            else:
                dp[r][c][0] = max(max(dp[r - 1][c]), dp[r][c-1][0])
                dp[r][c][1] = max(dp[r][c-1][1], dp[r][c-1][0] + v, max(dp[r - 1][c]) + v)
                dp[r][c][2] = max(dp[r][c-1][2], dp[r][c-1][1] + v)
                dp[r][c][3] = max(dp[r][c-1][3], dp[r][c-1][2] + v)

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

solve()

Submission status: Time Limit Exceeded

Solution code:
r,c,k=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(k)]
dp=[[[0 for _ in range(c+1)]for _ in range(r+1)]for _ in range(5)]
for x,y,z in a:
    dp[4][x][y]=z
for i in range(1,r+1):
    for j in range(1,c+1):
        v=dp[4][i][j]
        dp[0][i][j]=max(dp[0][i][j-1],dp[0][i-1][j],dp[1][i-1][j],dp[2][i-1][j],dp[3][i-1][j])
        dp[1][i][j]=max(dp[1][i][j-1],dp[0][i][j-1]+v,dp[0][i-1][j]+v,dp[1][i-1][j]+v,dp[2][i-1][j]+v,dp[3][i-1][j]+v)
        dp[2][i][j]=max(dp[2][i][j-1],dp[1][i][j-1]+v)
        dp[3][i][j]=max(dp[3][i][j-1],dp[2][i][j-1]+v)
print(max([dp[i][r][c] for i in range(4)]))

Submission status: Time Limit Exceeded

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

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 reversed(range(3)):
            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)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
R,C,K = map(int,input().split())
lis = [[0] * (C+1) for i in range(R+1)]
for _ in range(K):
    r,c,v = map(int,input().split())
    lis[r][c] = v

dp = [[[0] * 4 for _ in range(C+1)] for _ in range(R+1)]
#print(dp)
for i in range(1,R+1):
    for j in range(1,C+1):
        for k in range(4):
            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] + lis[i][j])

            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] + lis[i][j])
# print(dp[0])
# print(dp[1])
# print(dp[2])
# print(dp[3])
print(max(dp[R][C][0],dp[R][C][1],dp[R][C][2],dp[R][C][3]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
R,C,K = map(int,input().split())
a = np.zeros((R+5,C+5),dtype=np.int)
dp = np.zeros((R+5,C+5,4),dtype=np.int)
def chmax(x,y):
    x = max(x,y)
    return x
 
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 reversed(range(3)):
            #chmax(dp[i][j][k+1],dp[i][j][k]+a[i][j])
            dp[i][j][k+1] = max(dp[i][j][k+1],dp[i][j][k]+a[i][j])
            
        for k in range(4):
            #chmax(dp[i+1][j][0],dp[i][j][k])
            #chmax(dp[i][j+1][k],dp[i][j][k])
            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):
    #chmax(ans,dp[R-1][C-1][i])
    ans =  max(ans,dp[R-1][C-1][i])
print(ans)

Submission status: Time Limit Exceeded

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

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 reversed(range(3)):
            #chmax(dp[i][j][k+1],dp[i][j][k]+a[i][j])
            dp[i][j][k+1] = max(dp[i][j][k+1],dp[i][j][k]+a[i][j])
            
        for k in range(4):
            #chmax(dp[i+1][j][0],dp[i][j][k])
            #chmax(dp[i][j+1][k],dp[i][j][k])
            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):
    #chmax(ans,dp[R-1][C-1][i])
    ans =  max(ans,dp[R-1][C-1][i])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
R,C,K = map(int,input().split())
a = np.zeros((3005,3005),dtype=np.int)
dp = np.zeros((3005,3005,4),dtype=np.int)
def chmax(x,y):
    x = max(x,y)
    return x

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 reversed(range(3)):
            #chmax(dp[i][j][k+1],dp[i][j][k]+a[i][j])
            dp[i][j][k+1] = max(dp[i][j][k+1],dp[i][j][k]+a[i][j])
            
        for k in range(4):
            #chmax(dp[i+1][j][0],dp[i][j][k])
            #chmax(dp[i][j+1][k],dp[i][j][k])
            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):
    #chmax(ans,dp[R-1][C-1][i])
    ans =  max(ans,dp[R-1][C-1][i])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


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

    items = np.zeros((R+1, C+1), dtype='int64')
    for item in rcv:
        items[item[0]][item[1]] = item[2]

    dp = np.zeros((R+1, C+1), dtype='int64')

    # まずは3個の制約がない場合での実装
    for j in range(1, R+1):
        for i in range(1, C+1):
            # 下に行く遷移
            dp[j][i] = max(dp[j][i], dp[j-1][i] + items[j][i])

            # 右に行く遷移
            dp[j][i] = max(dp[j][i], dp[j][i-1] + items[j][i])

    print(dp[R][C])


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

    items = np.zeros((R+1, C+1), dtype=np.int64)
    for item in rcv:
        items[item[0]][item[1]] = item[2]

    dp = np.zeros((4, R+1, C+1), dtype=np.int64)

    # 3個の制約がある場合の実装
    for i in range(1, R+1):
        for j in range(1, C+1):
            for k in range(4):
                # 下に行く遷移
                # 取らない場合
                dp[0][i][j] = max(dp[0][i][j], dp[k][i-1][j])
                # 取る場合
                dp[1][i][j] = max(dp[1][i][j], dp[k][i-1][j] + items[i][j])

                # 右に行く遷移
                # 取らない場合
                dp[k][i][j] = max(dp[k][i][j], dp[k][i][j-1])
                # 取る場合
                if k > 0:
                    dp[k][i][j] = max(dp[k][i][j], dp[k-1]
                                      [i][j-1] + items[i][j])

    ans = 0
    for k in range(4):
        if ans < dp[k][R][C]:
            ans = dp[k][R][C]

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import heapq
r, c, k = map(int, input().split())
itm = [[0]*(c+1) for _ in range(r+1)]
for i in range(k):
  ri, ci, vi = map(int, input().split())
  itm[ri][ci] = vi
dp = [[[0]*4 for c_ in range(c+1)] for r_ in range(r+1)]
for i in range(1, r+1):
  for j in range(1, c+1):
    nowv = itm[i][j]
    dp[i][j][0] = max(dp[i][j-1][0], max(dp[i-1][j]))
    if nowv == 0:
      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]
    else:
      dp[i][j][1] = max(dp[i][j-1][1], dp[i][j][0] + nowv)
      dp[i][j][2] = max(dp[i][j-1][2], dp[i][j-1][1] + nowv)
      dp[i][j][3] = max(dp[i][j-1][3], dp[i][j-1][2] + nowv)
print(max(dp[r][c]))

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import product
input = lambda:sys.stdin.buffer.readline().rstrip()

m, n, k = map(int, input().split())
item = {}
for _ in range(k):
    i, j, v = map(int, input().split())
    i -= 1; j -= 1
    item[i, j] = v

dp = [[0] * 4 for _ in range(n)]
for i in range(m):
    ndp = [[0] * 4 for _ in range(n)]
    for j, k in product(range(n), range(4)):
        # from top
        ndp[j][0] = max(ndp[j][0], dp[j][k])
        if (i, j) in item:
            ndp[j][1] = max(ndp[j][1], dp[j][k] + item[i, j])
        # from left
        if j > 0:
            ndp[j][k] = max(ndp[j][k], ndp[j - 1][k])
            if k > 0 and (i, j) in item:
                ndp[j][k] = max(ndp[j][k], ndp[j - 1][k - 1] + item[i, j])
    dp = ndp

print(max(dp[-1]))

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline

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

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

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

Submission status: Time Limit Exceeded

Solution code:
from numpy import zeros

def main():
    R, C, K, *RCV = map(int, open(0).read().split())

    V = zeros((R + 1, C + 1), int)
    for r, c, v in zip(*[iter(RCV)] * 3):
        V[r][c] = v

    dp = zeros((R + 1, C + 1, 4), int)
    for i in range(1, R + 1):
        for j in range(1, C + 1):

            vij = V[i][j]

            for k in range(4):
                dp[i][j][k] = max(
                    dp[i][j - 1][k],
                    dp[i - 1][j][3]
                )
            for k in reversed(range(1, 4)):
                dp[i][j][k] = max(
                    dp[i][j][k],
                    vij + dp[i][j][k - 1]
                )

    print(dp[R][C][3])

main()

Submission status: Time Limit Exceeded

Solution code:
from numpy import zeros

R, C, K, *RCV = map(int, open(0).read().split())

V = zeros((R + 1, C + 1), int)
for r, c, v in zip(*[iter(RCV)] * 3):
    V[r][c] = v

dp = zeros((R + 1, C + 1, 4), int)
for i in range(1, R + 1):
    for j in range(1, C + 1):

        vij = V[i][j]

        for k in range(4):
            dp[i][j][k] = max(
                dp[i][j - 1][k],
                dp[i - 1][j][3]
            )
        for k in reversed(range(1, 4)):
            dp[i][j][k] = max(
                dp[i][j][k],
                vij + dp[i][j][k - 1]
            )

print(dp[R][C][3])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
input = sys.stdin.readline

def main():
    r,c,k=map(int, input().split())
    cl=np.zeros((r+1,c+1),dtype=np.int64)
    vls=np.array([list(map(int,input().split())) for _ in range(k)])
    x,y,z=vls[:,0],vls[:,1],vls[:,2]
    cl[x,y]=z
    dp=np.zeros((r+1,c+1,4),dtype=np.int64)
    for i in np.arange(1,r+1):
        for j in np.arange(1,c+1):
            #0,1,2でそれぞれ最大化を考える
            kk=np.zeros((4),dtype=np.int64)
            for k in np.arange(4):
                #前の行のk=3か、前の列からスライド
                if k==0:
                    kk[0]=max(dp[i-1][j][3],dp[i][j-1][0])
                #k-1か前の列からスライド
                elif k==1:
                    kk[1]=max(kk[0]+cl[i][j],dp[i][j-1][1])
                elif k==2:
                    kk[2]=max(kk[1],dp[i][j-1][1]+cl[i][j],dp[i][j-1][2])
                elif k==3:
                    kk[3]=max(kk[2],dp[i][j-1][2]+cl[i][j],dp[i][j-1][3])
            dp[i][j]=kk
                    
    print(dp[r][c][3])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
input = sys.stdin.readline

def main():
    r,c,k=map(int, input().split())
    cl=np.zeros((r+1,c+1),dtype=np.int64)
    vls=np.array([list(map(int,input().split())) for _ in range(k)])
    x,y,z=vls[:,0],vls[:,1],vls[:,2]
    cl[x,y]=z
    dp=np.zeros((r+1,c+1,4),dtype=np.int64)
    for i in np.arange(1,r+1):
        for j in np.arange(1,c+1):
            #0,1,2でそれぞれ最大化を考える
            for k in np.arange(4):
                #前の行のk=3か、前の列からスライド
                if k==0:
                    dp[i][j][k]=max(dp[i-1][j][3],dp[i][j-1][0])
                #k-1か前の列からスライド
                elif k==1:
                    dp[i][j][k]=max(dp[i][j][0]+cl[i][j],dp[i][j-1][1])
                elif k==2:
                    dp[i][j][k]=max(dp[i][j-1][1]+cl[i][j],dp[i][j-1][2],dp[i][j][1])
                elif k==3:
                    dp[i][j][k]=max(dp[i][j-1][2]+cl[i][j],dp[i][j-1][3],dp[i][j][2])
    print(dp[r][c][3])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
input=sys.stdin.readline

def main():
    r,c,k=[int(x) for x in input().split()]
    cl=np.zeros((r+1,c+1),dtype=np.int64)
    for _ in range(k):
        x,y,z=[int(x) for x in input().split()]
        cl[x][y]=z
    dp=np.zeros((r+1,c+1,4),dtype=np.int64)
    for i in np.arange(1,r+1):
        for j in np.arange(1,c+1):
            #0,1,2でそれぞれ最大化を考える
            for k in np.arange(4):
                #前の行のk=3か、前の列からスライド
                if k==0:
                    dp[i][j][k]=max(dp[i-1][j][3],dp[i][j-1][0])
                #k-1か前の列からスライド
                elif k==1:
                    dp[i][j][k]=max(dp[i][j][0]+cl[i][j],dp[i][j-1][1])
                elif k==2:
                    dp[i][j][k]=max(dp[i][j-1][1]+cl[i][j],dp[i][j-1][2],dp[i][j][1])
                elif k==3:
                    dp[i][j][k]=max(dp[i][j-1][2]+cl[i][j],dp[i][j-1][3],dp[i][j][2])
    print(dp[r][c][3])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def main():
    r,c,k=[int(x) for x in input().split()]
    cl=np.zeros((r+1,c+1),dtype=np.int64)
    for _ in range(k):
        x,y,z=[int(x) for x in input().split()]
        cl[x][y]=z
    dp=np.zeros((r+1,c+1,4),dtype=np.int64)
    for i in np.arange(1,r+1):
        for j in np.arange(1,c+1):
            #0,1,2でそれぞれ最大化を考える
            for k in np.arange(4):
                #前の行のk=3か、前の列からスライド
                if k==0:
                    dp[i][j][k]=max(dp[i-1][j][3],dp[i][j-1][0])
                #k-1か前の列からスライド
                elif k==1:
                    dp[i][j][k]=max(dp[i][j][0]+cl[i][j],dp[i][j-1][1])
                elif k==2:
                    dp[i][j][k]=max(dp[i][j-1][1]+cl[i][j],dp[i][j-1][2],dp[i][j][1])
                elif k==3:
                    dp[i][j][k]=max(dp[i][j-1][2]+cl[i][j],dp[i][j-1][3],dp[i][j][2])
    print(dp[r][c][3])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

r,c,k=[int(x) for x in input().split()]
cl=np.zeros((r+1,c+1),dtype=np.int64)
for _ in range(k):
    x,y,z=[int(x) for x in input().split()]
    cl[x][y]=z
dp=np.zeros((r+1,c+1,4),dtype=np.int64)
for i in np.arange(1,r+1):
    for j in np.arange(1,c+1):
        #0,1,2でそれぞれ最大化を考える
        for k in np.arange(4):
            #前の行のk=3か、前の列からスライド
            if k==0:
                dp[i][j][k]=max(dp[i-1][j][3],dp[i][j-1][0])
            #k-1か前の列からスライド
            elif k==1:
                dp[i][j][k]=max(dp[i][j][0]+cl[i][j],dp[i][j-1][1])
            elif k==2:
                dp[i][j][k]=max(dp[i][j-1][1]+cl[i][j],dp[i][j-1][2],dp[i][j][1])
            elif k==3:
                dp[i][j][k]=max(dp[i][j-1][2]+cl[i][j],dp[i][j-1][3],dp[i][j][2])
print(dp[r][c][3])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

r,c,k=[int(x) for x in input().split()]
cl=[[0]*(c+1) for _ in range(r+1)]
for _ in range(k):
    x,y,z=[int(x) for x in input().split()]
    cl[x][y]=z
dp=np.zeros((r+1,c+1,4),dtype=np.int64)
for i in np.arange(1,r+1):
    for j in np.arange(1,c+1):
        #0,1,2でそれぞれ最大化を考える
        for k in np.arange(4):
            #前の行のk=3か、前の列からスライド
            if k==0:
                dp[i][j][k]=max(dp[i-1][j][3],dp[i][j-1][0])
            #k-1か前の列からスライド
            elif k==1:
                dp[i][j][k]=max(dp[i][j][0]+cl[i][j],dp[i][j-1][1])
            elif k==2:
                dp[i][j][k]=max(dp[i][j-1][1]+cl[i][j],dp[i][j-1][2],dp[i][j][1])
            elif k==3:
                dp[i][j][k]=max(dp[i][j-1][2]+cl[i][j],dp[i][j-1][3],dp[i][j][2])
print(dp[r][c][3])