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:
from sys import stdin
input = stdin.readline

r, c, k = map(int, input().split())
vals = [[0]*c for _ in range(r)]
for _ in range(k):
    x, y, v = map(int, input().split())
    vals[x-1][y-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):
        if vals[i][j] != 0:
            for k in range(3, 0, -1):
                if dp[i][j][k] < dp[i][j][k-1] + vals[i][j]:
                    dp[i][j][k] = dp[i][j][k-1] + vals[i][j]
        if i < r-1:
            tmp = 0
            for k in range(4):
                if tmp < dp[i][j][k]:
                    tmp = dp[i][j][k]
            dp[i+1][j][0] = tmp
        if j < c-1:
            for k in range(4):
                if dp[i][j+1][k] < dp[i][j][k]:
                    dp[i][j+1][k] = dp[i][j][k]
print(max(dp[r-1][c-1]))

Submission status: Time Limit Exceeded

Solution code:
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

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

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect
import collections
import copy
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
MOD = 10**9+7

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

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

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

for i in range(R):
    for j in range(C):
        for k in range(1,4):
            #print(i,j,k)
            if k == 1:
                if i != 0:
                    if j != 0:
                        dp[i][j][k] = max(dp[i][j-1][k], dp[i][j-1][k-1] + item[i][j], max(dp[i-1][j]) + item[i][j])
                    else:
                        dp[i][j][k] = max(0, 0 + item[i][j], max(dp[i-1][j]) + item[i][j])
                else:
                    if j != 0:
                        dp[i][j][k] = max(dp[i][j-1][k], dp[i][j-1][k-1] + item[i][j])
                    else:
                        dp[i][j][k] = max(0, 0 + item[i][j])


            else:
                if j != 0:
                    dp[i][j][k] = max(dp[i][j-1][k], dp[i][j-1][k-1] + item[i][j])
                else:
                    dp[i][j][k] = max(0, 0 + item[i][j])

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

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

r, c, k = map(int, input().split())
vals = [[0]*c for _ in range(r)]
for _ in range(k):
    x, y, v = map(int, input().split())
    vals[x-1][y-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):
        if i > 0:
            tmp = 0
            for k in range(4):
                if tmp < dp[i-1][j][k]:
                    tmp = dp[i-1][j][k]
            dp[i][j][0] = tmp
        if j > 0:
            for k in range(4):
                if dp[i][j][k] < dp[i][j-1][k]:
                    dp[i][j][k] = dp[i][j-1][k]
        if vals[i][j] != 0:
            for k in range(3, 0, -1):
                if dp[i][j][k] < dp[i][j][k-1] + vals[i][j]:
                    dp[i][j][k] = dp[i][j][k-1] + vals[i][j]
print(max(dp[r-1][c-1]))

Submission status: Time Limit Exceeded

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

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

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

for i in range(R):
    for j in range(C):
        for k in range(1,4):
            #print(i,j,k)
            if k == 1:
                if i != 0:
                    if j != 0:
                        dp[i][j][k] = max(dp[i][j-1][k], dp[i][j-1][k-1] + item[i][j], max(dp[i-1][j]) + item[i][j])
                    else:
                        dp[i][j][k] = max(0, 0 + item[i][j], max(dp[i-1][j]) + item[i][j])
                else:
                    if j != 0:
                        dp[i][j][k] = max(dp[i][j-1][k], dp[i][j-1][k-1] + item[i][j])
                    else:
                        dp[i][j][k] = max(0, 0 + item[i][j])


            else:
                if j != 0:
                    dp[i][j][k] = max(dp[i][j-1][k], dp[i][j-1][k-1] + item[i][j])
                else:
                    dp[i][j][k] = max(0, 0 + item[i][j])

            #print(dp)
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())
vals = [[0]*c for _ in range(r)]
for _ in range(k):
    x, y, v = map(int, input().split())
    vals[x-1][y-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):
        if i > 0:
            tmp = 0
            for k in range(4):
                if tmp < dp[i-1][j][k]:
                    tmp = dp[i-1][j][k]
            dp[i][j][0] = tmp
        if j > 0:
            for k in range(4):
                if dp[i][j][k] < dp[i][j-1][k]:
                    dp[i][j][k] = dp[i][j-1][k]
        for k in range(3, 0, -1):
            if dp[i][j][k] < dp[i][j][k-1] + vals[i][j]:
                dp[i][j][k] = dp[i][j][k-1] + vals[i][j]
print(max(dp[r-1][c-1]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def main(r, c):
  dp = np.zeros((c+1, 4), np.int64)
  for i in range(r):
    new_dp = np.zeros((c+1, 4), np.int64)
    for j in range(4):
      new_dp[:,0] = np.maximum(new_dp[:,0], dp[:,j])
    dp = new_dp
    for k in range(c):
      for l in range(2, -1, -1):
        dp[k,l+1] = max(dp[k,l+1], dp[k,l]+item_map[i,k])
      for m in range(1,4):
        dp[k+1,m] = max(dp[k+1,m], dp[k,m])
  return max(dp[c-1,:])
 
R, C, K = map(int, input().split())
item_lis = list(list(map(int, input().split())) for i in range(K))
item_map = np.zeros((R, C), np.int64)
for i,j,k in item_lis:
  item_map[i-1,j-1] = k
 
print(main(R, C))

Submission status: Time Limit Exceeded

Solution code:
def main():
    r, c, k = map(int, input().split())
    vals = [[0]*c for _ in range(r)]
    for _ in range(k):
        x, y, v = map(int, input().split())
        vals[x-1][y-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):
            if i > 0:
                tmp = 0
                for k in range(4):
                    if tmp < dp[i-1][j][k]:
                        tmp = dp[i-1][j][k]
                dp[i][j][0] = tmp
            if j > 0:
                for k in range(4):
                    if dp[i][j][k] < dp[i][j-1][k]:
                        dp[i][j][k] = dp[i][j-1][k]
            for k in range(3, 0, -1):
                if dp[i][j][k] < dp[i][j][k-1] + vals[i][j]:
                    dp[i][j][k] = dp[i][j][k-1] + vals[i][j]
    print(max(dp[r-1][c-1]))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

R, C, K = map(int, sys.stdin.readline().split())

grid = [[-1 for _ in range(C)] for _ in range(R)]
for _ in range(K):
    r, c, v = map(int, sys.stdin.readline().split())
    grid[r-1][c-1] = v

# r行目、c列目にいるときに、その行でアイテムをi個取得している場合の最大価値
# dp = [[[0 for _ in range(3+1)] for _ in range(C+1)] for _ in range(R+1)]
dp = [[[0 for _ in range(R+1)] for _ in range(C+1)] for _ in range(3+1)]
# print(dp)
for r in range(R):
    for c in range(C):
        for i in range(4):
            # 取らない
            if r < R:
                # dp[r+1][c][0] = max(dp[r][c][i], dp[r+1][c][0])
                dp[0][c][r+1] = max(dp[i][c][r], dp[0][c][r+1])
            if c < C:
                # dp[r][c+1][i] = max(dp[r][c][i], dp[r][c+1][i])
                dp[i][c+1][r] = max(dp[i][c][r], dp[i][c+1][r])

            # 取る
            if i < 3:
                # print(r, c, i)
                # dp[r+1][c][0] = max(dp[r][c][i] + grid[r][c], dp[r+1][c][0])
                # dp[r][c+1][i+1] = max(dp[r][c][i] + grid[r][c], dp[r][c+1][i+1])
                dp[0][c][r+1] = max(dp[i][c][r] + grid[r][c], dp[0][c][r+1])
                dp[i+1][c+1][r] = max(dp[i][c][r] + grid[r][c], dp[i+1][c+1][r])

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

Submission status: Time Limit Exceeded

Solution code:
import sys

R, C, K = map(int, sys.stdin.readline().split())

grid = [[-1 for _ in range(C)] for _ in range(R)]
for _ in range(K):
    r, c, v = map(int, sys.stdin.readline().split())
    grid[r-1][c-1] = v

# r行目、c列目にいるときに、その行でアイテムをi個取得している場合の最大価値
dp = [[[0 for _ in range(3+1)] for _ in range(C+1)] for _ in range(R+1)]
# print(dp)
for r in range(R):
    for c in range(C):
        for i in range(4):
            # 取らない
            if r < R:
                dp[r+1][c][0] = max(dp[r][c][i], dp[r+1][c][0])
            if c < C:
                dp[r][c+1][i] = max(dp[r][c][i], dp[r][c+1][i])

            # 取る
            if i < 3:
                # print(r, c, i)
                dp[r+1][c][0] = max(dp[r][c][i] + grid[r][c], dp[r+1][c][0])
                dp[r][c+1][i+1] = max(dp[r][c][i] + grid[r][c], dp[r][c+1][i+1])

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import islice


def resolve(in_):
    R, C, K = map(int, next(in_).split())
    _rcv = (map(int, line.split()) for line in islice(in_, K))

    R1 = R + 1
    C1 = C + 1
    R2 = R + 2
    C2 = C + 2
    grid = [[0] * C2 for _ in range(R2)]
    for r, c, v in _rcv:
        grid[r][c] = v
    limit_item = 3
    limit_item1 = limit_item + 1
    
    dp = [[[0] * limit_item1 for j in range(C2)] for i in range(R2)]
    dp[1][1][1] = grid[1][1]

    for i in range(1, R1):
        for j in range(1, C1):
            for k in range(limit_item1):
                current = dp[i][j][k]

                left = grid[i][j + 1]
                dp[i][j + 1][k] = max(dp[i][j + 1][k], current)
                if k < limit_item:
                    dp[i][j + 1][k + 1] = max(dp[i][j + 1][k + 1], left + current)

                top = grid[i + 1][j]
                dp[i + 1][j][0] = max(dp[i + 1][j][0], current)
                dp[i + 1][j][1] = max(dp[i + 1][j][1], top + current)

    return max(dp[R][C])


def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import islice


def resolve(in_):
    R, C, K = map(int, next(in_).split())
    _rcv = (map(int, line.split()) for line in islice(in_, K))

    R1 = R + 1
    C1 = C + 1
    R2 = R + 2
    C2 = C + 2
    grid = [[0] * C2 for _ in range(R2)]
    for r, c, v in _rcv:
        grid[r][c] = v
    limit_item = 3
    limit_item1 = limit_item + 1
    
    dp = [[[0] * limit_item1 for j in range(C2)] for i in range(R2)]
    dp[1][1][1] = grid[1][1]

    for i in range(1, R1):
        for j in range(1, C1):
            for k in range(limit_item1):
                current = dp[i][j][k]

                left = grid[i][j + 1]
                dp[i][j + 1][k] = max(dp[i][j + 1][k], current)
                if k < limit_item:
                    dp[i][j + 1][k + 1] = max(dp[i][j + 1][k + 1], left + current)

                top = grid[i + 1][j]
                dp[i + 1][j][0] = max(dp[i + 1][j][0], current)
                dp[i + 1][j][1] = max(dp[i + 1][j][1], top + current)

    return max(dp[R][C])

def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin

input = stdin.readline
def main():
    R, C, K = map(int, input().rstrip().split())
    A = [[0] * (C + 2) for _ in range(R + 2)]
    DP = [[[0] * 4 for _ in range(C + 2)] for _ in range(R + 2)]
    for _ in range(K):
        r, c, v = map(int, input().rstrip().split())
        A[r][c] = v
    for r in range(R + 1):
        for c in range(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: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

def ii(): return int(input())
def fi(): return float(input())
def si(): return input()
def lii(): return list(map(int, input().split()))
def lfi(): return list(map(float, input().split()))
def vvi(a,b,d): return [[d] * a for i in range(b)]

inf = 10**18
mod = 10**9+7

r,c,k = lii()
dp = [[[0]*4 for _ in range(c+2)] for _ in range(r+2)]
a = [[0]*(c+2) for _ in range(r+2)]

for i in range(k):
    x,y,t = lii()
    a[x][y] = t

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

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

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

def ii(): return int(input())
def fi(): return float(input())
def si(): return input()
def lii(): return list(map(int, input().split()))
def lfi(): return list(map(float, input().split()))
def vvi(a,b,d): return [[d] * a for i in range(b)]

inf = 10**18
mod = 10**9+7

r,c,k = lii()
dp = [[[0]*4 for _ in range(c+2)] for _ in range(r+2)]
a = [[0]*(c+2) for _ in range(r+2)]

for i in range(k):
    x,y,t = lii()
    a[x][y] = t

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

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

Submission status: Time Limit Exceeded

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

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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()


def main():
	r,c,k=MI()
	G=[[0]*(c+1) for _ in range(r+1)]
	dp=[[[0]*4 for i in range(c+1)] for j in range(r+1)]
	for _ in range(k):
		rrr,ccc,v=MI()
		G[rrr][ccc]=v
	#print(G)

	#print(dp)

	for rr in range(1,r+1):
		for cc in range(1,c+1):
			if G[rr][cc]==0:
				for i in range(4):
					dp[rr][cc][i]=max(dp[rr][cc-1][i],dp[rr-1][cc][3])
			else:
				dp[rr][cc][0]=max(dp[rr-1][cc][3],dp[rr][cc-1][0])
				dp[rr][cc][1]=max(dp[rr][cc][0]+G[rr][cc],dp[rr][cc-1][1])
				dp[rr][cc][2]=max(dp[rr][cc-1][1]+G[rr][cc],dp[rr][cc-1][2],dp[rr][cc][1])
				dp[rr][cc][3]=max(dp[rr][cc-1][2]+G[rr][cc],dp[rr][cc-1][3],dp[rr][cc][2])
	#print(dp)
	print(dp[-1][-1][-1])















if __name__ == "__main__":
	main()

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)]
    dp0 = [0] * C
    dp1 = [0] * C
    dp2 = [0] * C
    dp3 = [0] * C

    for i in range(R):
        for j in range(C):
            ct = field[i][j]
            premax = max(dp0[j], dp1[j], dp2[j], dp3[j])

            if ct == 0:
                if j > 0:
                    dp0[j] = max(dp0[j - 1], premax)
                    dp1[j] = dp1[j - 1]
                    dp2[j] = dp2[j - 1]
                    dp3[j] = dp3[j - 1]
                else:
                    dp0[j] = premax

                # for k in range(1, 4):
                #     if j > 0:
                #         dp[j][k] = dp[j - 1][k]
                #




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

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
R,C,K=map(int,input().split())
vl=np.zeros((R,C), np.int64)
for _ in range(K):
  r,c,v=map(int,input().split())
  vl[r-1][c-1]=v
dp=np.zeros((R+1,C+1,4), np.int64)
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])
    for k in range(3,0,-1):
      dp[i][j][k]=max(dp[i][j][k],dp[i][j][k-1]+vl[i-1][j-1])
print(dp[R][C][3])

Submission status: Time Limit Exceeded

Solution code:
R,C,K=map(int,input().split())
vl=[[0 for _c in range(C)] for _r in range(R)]
for _ in range(K):
  r,c,v=map(int,input().split())
  vl[r-1][c-1]=v
dp=[[[0 for _ in range(4)]for _ in range(C+1)]for _ in range(R+1)]
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])
    for k in range(3,0,-1):
      dp[i][j][k]=max(dp[i][j][k],dp[i][j][k-1]+vl[i-1][j-1])
print(dp[R][C][3])

Submission status: Time Limit Exceeded

Solution code:
INF = float('inf')
R, C, K = map(int, input().split())
item = [[0] * (C+1) for i in range(R+1)]
for i in range(K):
  r, c, v = map(int, input().split())
  item[r][c] = v

dp = [[[-INF] * 4 for i in range(C+1)] for j in range(R+1)]
for i in range(R+1):
  dp[i][0][0] = 0
for i in range(C+1):
  dp[0][i][0] = 0
for i in range(1, R+1):
  for j in range(1, C+1):
    for k in range(4):
      #同じ行の移動
      if(item[i][j] > 0 and k > 0):
        dp[i][j][k] = max(dp[i][j-1][k-1]+item[i][j], dp[i][j-1][k], dp[i][j][k])
      else:
        dp[i][j][k] = max(dp[i][j-1][k], dp[i][j][k])
        
    #同じ列の移動
    X = max(dp[i-1][j])
    if(item[i][j]>0):
      dp[i][j][1] = max(X+item[i][j], dp[i][j][1])
    dp[i][j][0] = max(X, dp[i][j][0])
        
print(max(dp[R][C]))

Submission status: Time Limit Exceeded

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

item_dic={}
for _ in range(K):
  r,c,v=map(int,input().split())
  item_dic[(r,c)]=v
#print(item_dic)

dp=[[[0]*4  for _ in range(C+1)] for _ in range(R+1)]
for i in range(1,R+1):
  for j in range(1,C+1):
    for k in range(4):
      if (i,j) in item_dic:
        if k>0:
          dp[i][j][k]=max(dp[i][j][k],dp[i][j-1][k-1]+item_dic[(i,j)])
        dp[i][j][k]=max(dp[i][j][k],dp[i][j-1][k])
        dp[i][j][1]=max(dp[i][j][1],dp[i-1][j][k]+item_dic[(i,j)])
        dp[i][j][0]=max(dp[i][j][0],dp[i-1][j][k])
      else:
        dp[i][j][k]=max(dp[i][j][k],dp[i][j-1][k])
        dp[i][j][0]=max(dp[i][j][0],dp[i-1][j][k])
          
#print(dp[R][C])
answer=0
for k in range(4):
  answer=max(answer,dp[R][C][k])
    
print(answer)

Submission status: Time Limit Exceeded

Solution code:
R, C, K = list(map(int, input().split()))
L = [tuple(list(map(int, input().split()))) for i in range(K)]
MAP = [[0]*C for j in range(R)]
for x, y, v in L:
    MAP[x-1][y-1] = v
# print(MAP)
dp = [[[0]*4 for _ in range(C+1)] for _ in range(R+1)]

# dp[i][j][a]:(i,j)にi行目でa個拾って辿り着いたときの最大価値

for i in range(1, R+1):
    for j in range(1,C+1):
        dp[i][j][0]=max(dp[i][j-1][0],max(dp[i-1][j]))
        if MAP[i-1][j-1]>0:
            dp[i][j][1] = max(dp[i][j-1][1], \
                              dp[i][j-1][0]+MAP[i-1][j-1], \
                              max(dp[i-1][j])+MAP[i-1][j-1])
            dp[i][j][2] = max(dp[i][j-1][2], dp[i][j-1][1]+MAP[i-1][j-1])
            dp[i][j][3] = max(dp[i][j-1][3], dp[i][j-1][2]+MAP[i-1][j-1])
        else:
            for a in range(1, 4):
                dp[i][j][a] = dp[i][j-1][a]
# print(dp)
print(max(dp[R][C]))

Submission status: Time Limit Exceeded

Solution code:
from math import *
import fractions
import sys
import collections
import itertools
import pprint
from collections import deque
from heapq import *
input=sys.stdin.readline
R,C,K=map(int,input().split())
#R=3000
#C=3000
#table = [[0 for _ in range(3001)] for _ in range(3001)]
table={}
dp = [[[0 for _ in range(4)] for _ in range(C)] for _ in range(R)]
for i in range(K):
    r,c,v=map(int,input().split())
    if table.get(r-1)==None:
        table[r-1]={}
    table[r-1][c-1]=v
    #table[r-1][c-1]=v
#print(table)
for i in range(R):
    for j in range(C):
        num=0
        if table.get(i)==None:
            num=0
        elif table[i].get(j)==None:
            num=0
        else:
            num=table[i][j]
        for k in range(2,-1,-1):
            dp[i][j][k+1]=max(dp[i][j][k+1],dp[i][j][k]+num)
        for k in range(4):
            if i<R-1:
                dp[i+1][j][0]=max(dp[i+1][j][0],dp[i][j][k])
            if j<C-1:
                dp[i][j+1][k]=max(dp[i][j+1][k],dp[i][j][k])
print(max(dp[R-1][C-1]))

Submission status: Time Limit Exceeded

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


@njit(i8(i8, i8, i8[:, :], i8[:, :, :]), cache=True)
def move(R, C, V, point):

    point[0][0][1] = V[0][0]
    point[0][0][0] = 0

    for r in range(R):
        for c in range(C):

            # 列方向に動く
            if c > 0:
                point[r][c][3] = max(point[r][c - 1][2] + V[r][c], point[r][c - 1][3])
                point[r][c][2] = max(point[r][c - 1][1] + V[r][c], point[r][c - 1][2])
                point[r][c][1] = max(point[r][c - 1][0] + V[r][c], point[r][c - 1][1])
                point[r][c][0] = point[r][c - 1][0]

            # 行方向に動く
            m = max(point[r - 1][c])
            if r > 0:
                point[r][c][1] = max(m + V[r][c], point[r][c][1])
                point[r][c][0] = m

    return max(point[R - 1][C - 1])


def main():

    R, C, K = map(int, sys.stdin.readline().rstrip().split())

    V = [[0 for _ in range(C)] for _ in range(R)]
    V = np.array(V)
    point = [[[0, 0, 0, 0] for _ in range(C)] for _ in range(R)]
    point = np.array(point)
    for _ in range(K):
        r, c, v = map(int, sys.stdin.readline().rstrip().split())
        V[r - 1][c - 1] = v

    a = move(R, C, V, point)

    # print(point)
    print(a)


main()

Submission status: Time Limit Exceeded

Solution code:
from math import *
import fractions
import sys
import collections
import itertools
import pprint
from collections import deque
from heapq import *
input=sys.stdin.readline
R,C,K=map(int,input().split())
#R=3000
#C=3000
#table = [[0 for _ in range(3001)] for _ in range(3001)]
table={}
dp = [[[0 for _ in range(4)] for _ in range(3000)] for _ in range(3000)]
for i in range(K):
    r,c,v=map(int,input().split())
    if table.get(r-1)==None:
        table[r-1]={}
    table[r-1][c-1]=v
    #table[r-1][c-1]=v
#print(table)
for i in range(R):
    for j in range(C):
        num=0
        if table.get(i)==None:
            num=0
        elif table[i].get(j)==None:
            num=0
        else:
            num=table[i][j]
        for k in range(2,-1,-1):
            dp[i][j][k+1]=max(dp[i][j][k+1],dp[i][j][k]+num)
        for k in range(4):
            if i<R-1:
                dp[i+1][j][0]=max(dp[i+1][j][0],dp[i][j][k])
            if j<C-1:
                dp[i][j+1][k]=max(dp[i][j+1][k],dp[i][j][k])
print(max(dp[R-1][C-1]))

Submission status: Time Limit Exceeded

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
# from collections import Counter,defaultdict,deque
# from itertools import permutations, combinations
# from heapq import heappop, heappush
# # input = sys.stdin.readline
# sys.setrecursionlimit(10**8)
# mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

r,c,k = inpm()
RCV = inpll(k)

inf=float("inf")
dp=[[[-inf for i in range(r+1)] for j in range(c+1)] for k in range(4)]

q = queue.Queue()
q.put((0,0,0,0))

fielditem = [[-1]*(c+1) for i in range(r+1)]
for rr,cc,vv in RCV:
    fielditem[rr-1][cc-1] = vv
field = [[[-1]*4 for i in range(c)] for k in range(r)]

while not q.empty():
    rr,cc,itemcnt,vv = q.get()

    if fielditem[rr][cc] != -1 and itemcnt < 3:
        field[rr][cc][itemcnt+1] = max(field[rr][cc][itemcnt+1],vv + fielditem[rr][cc])
        field[rr][cc][itemcnt] = max(field[rr][cc][itemcnt],vv)
        if rr < r-1:
            q.put((rr+1,cc,0,vv + fielditem[rr][cc]))
        if cc < c-1:
            q.put((rr,cc+1,itemcnt+1,vv + fielditem[rr][cc]))
            q.put((rr,cc+1,itemcnt,vv))
    else:
        field[rr][cc][itemcnt] = max(field[rr][cc][itemcnt],vv)
        if rr < r-1:
            q.put((rr+1,cc,0,vv))
        if cc < c-1:
            q.put((rr,cc+1,itemcnt,vv))

print(max(field[r-1][c-1]))