Problem: 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.

Submission attempts (in order):
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8
read = sys.stdin.buffer.read

@njit((i8, i8, i8, i8[:]), cache=True)
def solve(R,C,K,XYV):
  item = np.zeros((H + 1, W + 1), np.int64)
    for i in range(0, 3 * K, 3):
        x, y, v = XYV[i:i + 3]
        item[x - 1, y - 1] = v
  dp = np.zeros((C+1,4), dtype=np.int64)
  for i in range(1,R+1):
    new_dp = np.zeros((C+1,4), dtype=np.int64)
    
    for k in range(4):
      new_dp[:,0] = np.maximum(new_dp[:,0], dp[:,k])
    dp = new_dp
    for j in range(1,C+1):
      
      new_dp[j] = np.maximum(new_dp[j],new_dp[j-1])
      
      for k in range(2,-1,-1):
        dp[j,k+1] = np.maximum(dp[j,k+1],dp[j,k]+item[i-1][j-1])
  ans = dp[-1].max()
  return ans

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


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


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

@njit((i8, i8, i8, i8[:]), cache=True)
def solve(R,C,K,XYV):
  item = np.zeros((R + 1, C + 1), dtype=np.int64)
  for i in range(0, 3 * K, 3):
    x, y, v = XYV[i:i + 3]
    item[x - 1, y - 1] = v
  dp = np.zeros((C+1,4), dtype=np.int64)
  for i in range(1,R+1):
    new_dp = np.zeros((C+1,4), dtype=np.int64)
    
    for k in range(4):
      new_dp[:,0] = np.maximum(new_dp[:,0], dp[:,k])
    dp = new_dp
    for j in range(1,C+1):
      
      new_dp[j] = np.maximum(new_dp[j],new_dp[j-1])
      
      for k in range(2,-1,-1):
        dp[j,k+1] = np.maximum(dp[j,k+1],dp[j,k]+item[i-1,j-1])
  ans = dp[-1].max()
  return ans

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


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

@njit((i8, i8, i8, i8[:,:]), cache=True)
def solve(R,C,K,item):
  dp = np.zeros((C+1,4), dtype=np.int64)
  for i in range(1,R+1):
    new_dp = np.zeros((C+1,4), dtype=np.int64)
    
    for k in range(4):
      new_dp[:,0] = np.maximum(new_dp[:,0], dp[:,k])
    dp = new_dp
    for j in range(1,C+1):
      
      new_dp[j] = np.maximum(new_dp[j],new_dp[j-1])
      
      for k in range(2,-1,-1):
        dp[j,k+1] = np.maximum(dp[j,k+1],dp[j,k]+item[i-1][j-1])
  ans = dp[-1].max()
  return ans

R, C, K = map(int, input().split())
item = np.zeros((R,C), dtype=np.int64)
for i in range(K):
  r,c,v = map(int, input().split())
  item[r-1,c-1] = v
# print(solve(R,C,K,item))


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

@njit((i8, i8, i8, i8[:,:]), cache=True)
def solve(R,C,K,XYV):
  item = np.zeros((H + 1, W + 1), np.int64)
    for i in range(0, 3 * K, 3):
        x, y, v = XYV[i:i + 3]
        item[x - 1, y - 1] = v
  dp = np.zeros((C+1,4), dtype=np.int64)
  for i in range(1,R+1):
    new_dp = np.zeros((C+1,4), dtype=np.int64)
    
    for k in range(4):
      new_dp[:,0] = np.maximum(new_dp[:,0], dp[:,k])
    dp = new_dp
    for j in range(1,C+1):
      
      new_dp[j] = np.maximum(new_dp[j],new_dp[j-1])
      
      for k in range(2,-1,-1):
        dp[j,k+1] = np.maximum(dp[j,k+1],dp[j,k]+item[i-1][j-1])
  ans = dp[-1].max()
  return ans

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


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

@njit((i8, i8, i8, i8[:]), cache=True)
def solve(R,C,K,XYV):
  item = np.zeros((H + 1, W + 1), np.int64)
    for i in range(0, 3 * K, 3):
        x, y, v = XYV[i:i + 3]
        item[x - 1, y - 1] = v
  dp = np.zeros((C+1,4), dtype=np.int64)
  for i in range(1,R+1):
    new_dp = np.zeros((C+1,4), dtype=np.int64)
    
    for k in range(4):
      new_dp[:,0] = np.maximum(new_dp[:,0], dp[:,k])
    dp = new_dp
    for j in range(1,C+1):
      
      new_dp[j] = np.maximum(new_dp[j],new_dp[j-1])
      
      for k in range(2,-1,-1):
        dp[j,k+1] = np.maximum(dp[j,k+1],dp[j,k]+item[i-1][j-1])
  ans = dp[-1].max()
  return ans

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


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

@njit((i8, i8, i8, i8[:]), cache=True)
def solve(R,C,K,XYV):
  item = np.zeros((R + 1, C + 1), np.int64)
    for i in range(0, 3 * K, 3):
        x, y, v = XYV[i:i + 3]
        item[x - 1, y - 1] = v
  dp = np.zeros((C+1,4), dtype=np.int64)
  for i in range(1,R+1):
    new_dp = np.zeros((C+1,4), dtype=np.int64)
    
    for k in range(4):
      new_dp[:,0] = np.maximum(new_dp[:,0], dp[:,k])
    dp = new_dp
    for j in range(1,C+1):
      
      new_dp[j] = np.maximum(new_dp[j],new_dp[j-1])
      
      for k in range(2,-1,-1):
        dp[j,k+1] = np.maximum(dp[j,k+1],dp[j,k]+item[i-1][j-1])
  ans = dp[-1].max()
  return ans

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


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

@njit((i8, i8, i8, i8[:]), cache=True)
def solve(R,C,K,XYV):
  item = np.zeros((R + 1, C + 1), dtype=np.int64)
    for i in range(0, 3 * K, 3):
      x, y, v = XYV[i:i + 3]
      item[x - 1, y - 1] = v
  dp = np.zeros((C+1,4), dtype=np.int64)
  for i in range(1,R+1):
    new_dp = np.zeros((C+1,4), dtype=np.int64)
    
    for k in range(4):
      new_dp[:,0] = np.maximum(new_dp[:,0], dp[:,k])
    dp = new_dp
    for j in range(1,C+1):
      
      new_dp[j] = np.maximum(new_dp[j],new_dp[j-1])
      
      for k in range(2,-1,-1):
        dp[j,k+1] = np.maximum(dp[j,k+1],dp[j,k]+item[i-1,j-1])
  ans = dp[-1].max()
  return ans

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


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

@njit((i8, i8, i8, i8[:]), cache=True)
def solve(R,C,K,XYV):
  item = np.zeros((H + 1, W + 1), np.int64)
    for i in range(0, 3 * K, 3):
        x, y, v = XYV[i:i + 3]
        item[x - 1, y - 1] = v
  dp = np.zeros((C+1,4), dtype=np.int64)
  for i in range(1,R+1):
    new_dp = np.zeros((C+1,4), dtype=np.int64)
    
    for k in range(4):
      new_dp[:,0] = np.maximum(new_dp[:,0], dp[:,k])
    dp = new_dp
    for j in range(1,C+1):
      
      new_dp[j] = np.maximum(new_dp[j],new_dp[j-1])
      
      for k in range(2,-1,-1):
        dp[j,k+1] = np.maximum(dp[j,k+1],dp[j,k]+item[i-1][j-1])
  ans = dp[-1].max()
  return ans

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


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

@njit((i8, i8, i8, i8[:,:]), cache=True)
def solve(R,C,K,item):
  dp = np.zeros((C+1,4), dtype=np.int64)
  for i in range(1,R+1):
    new_dp = np.zeros((C+1,4), dtype=np.int64)
    
    for k in range(4):
      new_dp[:,0] = np.maximum(new_dp[:,0], dp[:,k])
    dp = new_dp
    for j in range(1,C+1):
      
      for k in range(4):
        new_dp[j][k] = np.maximum(new_dp[j,k],new_dp[j-1,k])
      
      for k in range(2,-1,-1):
        dp[j,k+1] = np.maximum(dp[j,k+1],dp[j,k]+item[i-1][j-1])
  ans = dp[-1].max()
  return ans

R, C, K = map(int, input().split())
item = np.zeros((R,C), dtype=np.int64)
for i in range(K):
  r,c,v = map(int, input().split())
  item[r-1,c-1] = v
print(solve(R,C,K,item))


Verdicts: Runtime Error

Wrong Answer

Runtime Error

Wrong Answer

Runtime Error

Runtime Error

Runtime Error

Runtime Error

Runtime Error

Accepted