Problem:


Score : 500 points

Problem Statement

There are K items placed on a grid of squares with R rows and C columns. Let (i, j) denote the square at the i-th row (1 \leq i \leq R) and the j-th column (1 \leq j \leq C). The i-th item is at (r_i, c_i) and has the value v_i.

Takahashi will begin at (1, 1), the start, and get to (R, C), the goal. When he is at (i, j), he can move to (i + 1, j) or (i, j + 1) (but cannot move to a non-existent square).

He can pick up items on the squares he visits, including the start and the goal, but at most three for each row. It is allowed to ignore the item on a square he visits.

Find the maximum possible sum of the values of items he picks up.

Constraints

1 \leq R, C \leq 3000

1 \leq K \leq \min(2 \times 10^5, R \times C)

1 \leq r_i \leq R

1 \leq c_i \leq C

(r_i, c_i) \neq (r_j, c_j) (i \neq j)

1 \leq v_i \leq 10^9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

R C K
r_1 c_1 v_1
r_2 c_2 v_2
:
r_K c_K v_K

Output

Print the maximum possible sum of the values of items Takahashi picks up.

Sample Input 1

2 2 3
1 1 3
2 1 4
1 2 5

Sample Output 1

8

He has two ways to get to the goal:

Visit (1, 1), (1, 2), and (2, 2), in this order. In this case, the total value of the items he can pick up is 3 + 5 = 8.

Visit (1, 1), (2, 1), and (2, 2), in this order. In this case, the total value of the items he can pick up is 3 + 4 = 7.

Thus, the maximum possible sum of the values of items he picks up is 8.

Sample Input 2

2 5 5
1 1 3
2 4 20
1 2 1
1 3 4
1 4 2

Sample Output 2

29

We have four items in the 1-st row. The optimal choices are as follows:

Visit (1, 1) (1, 2), (1, 3), (1, 4), (2, 4), and (2, 5), in this order, and pick up all items except the one on (1, 2). Then, the total value of the items he picks up will be 3 + 4 + 2 + 20 = 29.

Sample Input 3

4 5 10
2 5 12
1 5 12
2 3 15
1 2 20
1 1 28
2 4 26
3 2 27
4 5 21
3 5 10
1 3 10

Sample Output 3

142



Sample input:
2 2 3
1 1 3
2 1 4
1 2 5


Sample output:
8

Submission status: Runtime Error

Solution code:
# Fast IO (only use in integer input)

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

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

for i in range(R):
    DPi = [None] * C
    for j in range(C):
        DPi[j] = [0,0,0,0]
        DPij = DPi[j]
        DPijs1 = DPi[j-1]
        if i != 0 and j != 0:
            DPij[0] = max(DPLast[j][0],DPLast[j][1],DPLast[j][2],DPLast[j][3],DPijs1[0])
            DPij[1] = DPijs1[1]
            DPij[2] = DPijs1[2]
            DPij[3] = DPijs1[3]
            if Gift[i][j]:
                DPij[3] = max(DPij[3],DPij[2] + Gift[i][j])
                DPij[2] = max(DPij[2],DPij[1] + Gift[i][j])
                DPij[1] = max(DPij[1],DPij[0] + Gift[i][j])
        elif i == 0:
            DPij[0] = DPijs1[0]
            DPij[1] = DPijs1[1]
            DPij[2] = DPijs1[2]
            DPij[3] = DPijs1[3]
            if Gift[i][j]:
                DPij[3] = max(DPij[3],DPij[2] + Gift[i][j])
                DPij[2] = max(DPij[2],DPij[1] + Gift[i][j])
                DPij[1] = max(DPij[1],DPij[0] + Gift[i][j])
        elif j == 0:
            DPij[0] = max(DPLast[j][0],DPLast[j][1],DPLast[j][2],DPLast[j][3])
            if Gift[i][j]:
                DPij[3] = max(DPij[3],DPij[2] + Gift[i][j])
                DPij[2] = max(DPij[2],DPij[1] + Gift[i][j])
                DPij[1] = max(DPij[1],DPij[0] + Gift[i][j])
        else:
            DPij[1] = Gift[i][j]
    DPLast = DPi

print(max(DPi[C-1]))

Submission status: Runtime Error

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

dp = [[0]*C for i in range(R)]
for i in range(R):
    base_num = 0
    sum_lst = [0, 0, 0]
    for j in range(C):
        if [i, j] == [0, 0]:
            sum_lst.append(RCV[i][j])
            sum_lst.sort()
            sum_lst = sum_lst[::-1]
            del sum_lst[-1]
            right = base_num + sum(sum_lst)
            dp[i][j] = right
        else:
            sum_lst.append(RCV[i][j])
            sum_lst.sort()
            sum_lst = sum_lst[::-1]
            del sum_lst[-1]
            down = dp[i-1][j] + RCV[i][j]
            right = base_num + sum(sum_lst)
            print(i, j, down, right, sum_lst, base_num)
            if down < right:
                dp[i][j] = right
            else:
                dp[i][j] = down
                base_num = dp[i-1][j]
                sum_lst = [RCV[i][j], 0, 0]
# for i in dp:
#     print(i)
print(dp[-1][-1])

Submission status: Runtime Error

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

loop_list = [] # ([indexes])
loop_score_list = []
loop_index_list = [0]*N
is_included_loop = [0] * N
num_loop = 0

for start in range(N):
    if is_included_loop[start]:
        continue
    now = start
    count = 1
    visited = [-1]*N # count
    visited[now] = 0
    while True:
        now = P[now]
        if visited[now] != -1:
            terminate_count = count
            start_count = visited[now]
            loop_start_idx = now
            break
        visited[now] = count
        count += 1
    
    num_loop += 1
    now = loop_start_idx
    loop_indexes = [now]
    visited = [-1]*N
    visited[now] = 0
    count = 1
    loop_score = 0
    while True:
        now = P[now]
        if visited[now] != -1:
            break
        loop_indexes.append(now)
        visited[now] = count
        loop_index_list[now] = num_loop
        loop_score += C[now]
        is_included_loop[now] = 1
    loop_list.append(loop_indexes)
    loop_score_list.append(loop_score)


scores = []
for start in range(N):
    tmp_score = 0
    rest = K
    now = start
    while not is_included_loop[now] and rest > 0:
        now = P[now]
        rest -= 1
        tmp_score += C[now]
        scores.append(tmp_score)
    
    if rest <= 0:
        scores.append(tmp_score)
        continue
    # loop
    number_of_loop = loop_index_list[now] - 1
    one_cicle_score = loop_score_list[number_of_loop]
    if one_cicle_score < 0:
        continue
    if rest <= len(loop_list[number_of_loop]):
        while rest >= 0:
            now = P[now]
            rest -= 1
            tmp_score += C[now]
            scores.append(tmp_score)
        continue
    else:
        n_l = rest // len(loop_list[number_of_loop])
        tmp_score += n_l * one_cicle_score
        scores.append(tmp_score)
print(max(scores))

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <vector>
#include <cstdio>
#include <string>
#include <cmath>
#include <algorithm>
#include <climits>
#define ll long long
#define MAX 25 * 1e13
#define N  200010

#define SIZE(A) ((int)A.size())
#define LEN(A) ((int)A.length())
#define MP(A,B) make_pair(A,B)
#define PB(X) push_back(X)
#define EB(X) emplace_back(X)
#define REP(i,a) for(int i=0;i<(a);++i)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repr(i, n) for (int i = (n) - 1; i >= 0; i--)
#define range(a) a.begin(), a.end()
#define VI vector<int>;
#define PI 3.14159265358979323846

using namespace std;
int MOD = 1000000007;


int dp[3010][3010][4];
int maxl(ll a,ll b ) {
  if( a > b ) return a;
  return b;
}
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int r,c,k;
  cin >> r >> c >> k;
  vector<vector<ll>> v(r+1, vector<ll>(c+1));
  for(int i = 0; i < k; i++ ){
    ll x,y,c;
    cin >> x >> y >> c;
    v[x][y] = c;
  }
  ll ret = 0;
  dp[1][1][1] = v[1][1];
  for( int i = 1; i <= c; i++ ){
    dp[1][i][1] = maxl( dp[1][i-1][1] , v[1][i] );
  }
  for( int i = 1; i <= c; i++ ){
    dp[1][i][2] = maxl( dp[1][i-1][2] , dp[1][i-1][1] + v[1][i] );
  }
  for( int i = 1; i <= c; i++ ){
    dp[1][i][3] = maxl( dp[1][i-1][3] , dp[1][i-1][2] + v[1][i] );
  }

  for( int i = 2;  i <= r ; i++ ){
    for( int j = 1 ; j <= c; j++ ){
      dp[i][j][1] = maxl(dp[i][j-1][1] ,  dp[i-1][j][3] + v[i][j] );
    }
    for( int j = 1 ; j <= c; j++ ){
      dp[i][j][2] = maxl( dp[i][j-1][2] , dp[i][j-1][1] + v[i][j] );
      dp[i][j][2] = maxl( dp[i][j][2] , dp[i-1][j][3] + v[i][j]);
    }
    for( int j = 1 ; j <= c; j++ ){
      dp[i][j][3] = maxl( dp[i][j-1][3] , dp[i][j-1][2] + v[i][j] );
      dp[i][j][3] = maxl( dp[i][j][3] , dp[i-1][j][3] + v[i][j]);
    }
  }
  cout << dp[r][c][3] << endl;
  /*
  for( int i = 1 ; i <= r ; i++ ){
    for( int j = 1 ; j <= c ; j++ ){
      cout << dp[i][j][1] << " " ;
    }
    cout << "\n";
  }
  */

  return 0;
}

Submission status: Runtime Error

Solution code:
R, C, K = map(int,input().split())
V = [[]for i in range(R)]
for i in range(K):
    r,c,v = map(int,input().split())
    V[r-1].append([c,v])
cost = [0]*C
for r in range(R):
    V[r].sort()
    hoge = [0,0,0,0]
    for c,v in V[r]:
        for i in range(3,-1,-1):
            hoge[i] = max(cost[c],hoge[i-1])
            hoge[i] += v
        hoge[0] -= v
        cost[c] = max(hoge)
    for i in range(1,C):
        cost[i] = max(cost[i],cost[i-1])

print(cost[-1][-1])

Submission status: Runtime Error

Solution code:
R,C,K=map(int,input().split())
rr=[]*k
for _ in range(K):
  r,c,k=map(int,input().split())
  rr[r].appned(k)
ans=0
for i in :
  ans+=rr[-1]+rr[-2]+rr[-3]
print(ans)

Submission status: Runtime Error

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

dp = [[0, []]*C]*R
dp[0][0][0] = item[0][0]
if item[0][0] != 0:
    dp[0][0][1].append(item[0][0])
    dp[0][0][1].sort()

if R == 1:
    if C < 3:
        print(sum(item[0]))
    else:
        print(sum(sorted(item[0], reversed=True)[:3])
elif C == 1:
    print(sum(item(item[:][0])))
else:
    for i in range(1, R):
        dp[i][0][0] = dp[i - 1][0][0] + item[i][0]
        if item[i][0] != 0:
            dp[i][0][1].append(item[i][0])
            dp[i][0][1].sort()

    for j in range(1, C):
        if len(dp[0][j - 1][1]) < 3:
            dp[0][j][0] = dp[0][j - 1][0] + item[0][j]
            if item[0][j] != 0:
                dp[0][j][1] = dp[0][j - 1][1] + [item[0][j]]
                dp[0][j][1].sort()
            else:
                if item[0][j] >= min(dp[0][j - 1][1]):
                    dp[0][j][0] = dp[0][j - 1][0] + (item[0][j] - min(dp[0][j - 1][1]))
                    dp[0][j][1] = dp[0][j - 1][1][1:] + [item[0][j]]
                    dp[0][j][1].sort()
                else:
                    dp[0][j][0] = dp[0][j - 1][0]


    for i in range(1, R):
        for j in range(1, C):
            if len(dp[i][j - 1][1]) < 3:
                tryrow = item[i][j]
            else:
                if item[i][j] >= min(dp[i][j - 1][1]):
                    tryrow = item[i][j] - min(min(dp[i][j - 1][1]))
                else:
                    tryrow = 0
            trycolumn = item[i][j]
            if dp[i][j - 1][0] + tryrow > dp[i - 1][j][0] + trycolumn:
                dp[i][j][0] = dp[i][j - 1][0] + tryrow
                if len(dp[i][j - 1][1]) < 3:
                    dp[i][j][1] = dp[i][j - 1][1] + [item[i][j]]
                    dp[i][j][1].sort()
                else:
                    if tryrow != 0:
                        dp[i][j][1] = dp[i][j - 1][1][1:] + [item[i][j]]
                        dp[i][j][1].sort()
            else:
                dp[i][j][0] = dp[i - 1][j][0] + trycolumn
                if trycolumn != 0:
                    dp[i][j][1].append(item[i][j])
                    dp[i][j][1].sort()

    print(dp[-1][-1][0])

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

R,C,K = MI()
item = [[0]*(C+1) for _ in range(R+1)]
for i in range(K):
    r,c,v = MI()
    item[r][c] = v

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

for i in range(1,R+1):
    for j in range(4):
        for k in range(1,C+1):
            if item[i][k] == 0:
                if i < R and k < C:
                    dp[i][j][k+1] = max(dp[i][j][k+1],dp[i][j][k])
                    dp[i+1][0][k] = max(dp[i+1][0][k],dp[i][j][k])
                elif i < R and k == C:
                    dp[i + 1][0][k] = max(dp[i + 1][0][k], dp[i][j][k])
                elif i == R and K < C:
                    dp[i][j][k + 1] = max(dp[i][j][k + 1], dp[i][j][k])
            else:
                if i < R and k < C:
                    dp[i][j][k + 1] = max(dp[i][j][k + 1], dp[i][j][k])
                    dp[i + 1][0][k] = max(dp[i + 1][0][k], dp[i][j][k])
                elif i < R and k == C:
                    dp[i + 1][0][k] = max(dp[i + 1][0][k], dp[i][j][k])
                elif i == R and K < C:
                    dp[i][j][k + 1] = max(dp[i][j][k + 1], dp[i][j][k])
                if j != 3:
                    dp[i][j+1][k] += item[i][k]
                    if i < R and k < C:
                        dp[i][j+1][k + 1] = max(dp[i][j+1][k + 1], dp[i][j+1][k])
                        dp[i + 1][0][k] = max(dp[i + 1][0][k], dp[i][j+1][k])
                    elif i < R and k == C:
                        dp[i + 1][0][k] = max(dp[i + 1][0][k], dp[i][j+1][k])
                    elif i == R and K < C:
                        dp[i][j+1][k + 1] = max(dp[i][j+1][k + 1], dp[i][j+1][k])
ans = 0
for j in range(4):
    ans = max(ans,dp[R][j][C])
    print(dp[R][j][C])

print(ans)

Submission status: Runtime Error

Solution code:
import sys
import math
import collections
import bisect
import itertools

# import numpy as np

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline().rstrip())
ns = lambda: map(int, sys.stdin.readline().rstrip().split())
na = lambda: list(map(int, sys.stdin.readline().rstrip().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))


# ===CODE===

# https://note.nkmk.me/python-union-find/

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def main():
    r, c, k = ns()

    mat = [[0 for _ in range(r)] for __ in range(c)]
    res = [[[0, 0, 0] for _ in range(r)] for __ in range(c)]
    visited = [[False for _ in range(r)] for __ in range(c)]
    visited[0][0] = True
    for _ in range(k):
        ri, ci, ki = ns()
        ri, ci = ri - 1, ci - 1
        mat[ci][ri] = ki

    que = collections.deque()
    tmp = [0, 0]
    que.append(tmp)

    while que:
        xi, yi = que.popleft()
        if yi + 1 < c:
            if not visited[yi + 1][xi]:
                que.append([yi + 1, xi])
                visited[yi + 1][xi] = True
            for i in range(2, -1, -1):
                if i == 0:
                    res[yi + 1][xi][i] = max(res[yi + 1][xi][i], mat[yi][xi])
                else:
                    if res[yi + 1][xi][i - 1] != 0:
                        res[yi + 1][xi][i] = max(res[yi + 1][xi][i], res[yi + 1][xi][i - 1] + mat[yi][xi])

        if xi + 1 < r:
            if not visited[yi][xi + 1]:
                que.append([yi, xi + 1])
                visited[yi][xi + 1] = True
            for i in range(2, -1, -1):
                if i == 0:
                    res[yi][xi + 1][i] = max(res[yi][xi + 1][i], mat[yi][xi])
                else:
                    if res[yi][xi + 1][i - 1]!= 0:
                        res[yi][xi + 1][i] = max(res[yi][xi + 1][i], res[yi][xi + 1][i - 1] + mat[yi][xi])

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


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
R, C, K = map(int, input().split())
W = 3
value = [[1] * (R+1) for _ in range(C+1)]
for _ in range(K):
  r, c, v = map(int, input().split())
  value[r][c] = v


dp = [[[-1] * (R+1) for _ in range(C+1)] for _ in range(W+1)]
dp[0][0][0] = 0
print(dp)

for r in range(1, R+1):
  for c in range(1, C+1):
    for w in range(W+1):
      dp[r][c][w] = max(dp[r-1][c][w], dp[r][c-1][w], dp[r][c][w])
      if -1 < w-1:
        dp[r][c][w] = max(dp[r][c][w-1] + value[r][c], dp[r][c][w])
print(max(dp[R][C]))

Submission status: Runtime Error

Solution code:
R, C, K = map(int, input().split())
V = [[0 for i in range(C+1)] for j in range(R+1)]
items = [[0 for i in range(C+1)] for j in range(R+1)]

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

for i in range(1, R+1):
    count = 0
    for j in range(1, C+1):
        item = items[i, :j]
        V[i, j] = max(V[i-1, j], V[i, j-1])
        for k in sorted(item)[:3]:
             V[i, j] += k

print(V[R, C])

Submission status: Runtime Error

Solution code:
R,C,K=map(int,input().split())
rr=[]*k
for _ in range(K):
  r,c,k=map(int,input().split())
  rr[r].appned((c,k))
ans=0
for i in range(K):
  ans+=rr[-1]+rr[-2]+rr[-3]
print(ans)

Submission status: Runtime Error

Solution code:
R, C, K = map(int. input().split())
V = [[0 for i in range(C+1)] for j in range(R+1)]
items = [[0 for i in range(C+1)] for j in range(R+1)]

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

for i in range(1, R+1):
    count = 0
    for j in range(1, C+1):
        item = items[i, :j]
        V[i, j] = max(V[i-1, j], V[i, j-1])
        for k in sorted(item)[:3]:
             V[i, j] += k

print(V[R, C])

Submission status: Runtime Error

Solution code:
from functools import lru_cache

# This TLEs, just checking correctness

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

# for row in grid:
#    print(row)


def best3(r, c1, c2):  # c1 inclusive, c2 exclusive
    return sum(sorted(grid[r][c1:c2], reverse=True)[:3])


@lru_cache(maxsize=None)
def dp(r, c):  # inclusive
    if r < 0 or c < 0:
        return 0
    best = 0
    for c1 in range(c + 1):
        best = max(best, dp(r - 1, c1) + best3(r, c1, c + 1))
    return best


print(dp(R - 1, C - 1))

Submission status: Runtime Error

Solution code:
N,K=map(int, input().split())
P=list(map(int, input().split()))
C=list(map(int, input().split()))

F=[0]*N
I=[0]*N
CN=[0]*N

for i in range(N):
  around=0
  cnt=0
  A=[]
  if F[i]==0:
    F[i]=1
    around+=1
    cnt+=C[i]
    nex=P[i]-1
    A.append(i)
    while F[nex]==0:
      A.append(nex)
      F[nex]=1
      around+=1
      cnt+=C[nex]
      nex=P[nex]-1
    for j in A:
      I[j]=around
      CN[j]=cnt
#print(F)
#print(I)
#print(CN)
ans=-(10**9)*2
for i in range(N):
  cnt=C[i]
  #動かす回数が一周に満たない時
  if (K+1)<=I[i]:
    d=0
    nex=i
    for j in range(K+1):
      d+=C[nex]
      nex=P[nex]-1
      cnt=max(d,cnt)
  #動かす回数が一周を超えるとき
  elif CN[i]<=0:
    d=0
    nex=i
    for j in range(I[i]):
      d+=C[nex]
      nex=P[nex]-1
      cnt=max(d,cnt)
  else:
    d=0
    nex=i
    for j in range(I[i]):
      d+=C[nex]
      nex=P[nex]-1
      cnt=max(d,cnt)
    acnt=cnt
    bcnt=C[i]
    syuukai=(K+1)//I[i]
    nokori=(K+1)%I[i]
    syuukai-=1
    nokori+=I[i]
    d=0
    nex=i
    for j in range(nokori-1):
      d+=C[nex]
      nex=P[nex]-1
      bcnt=max(d,bcnt)
    bcnt+=syuukai*CN[i]
    cnt=max(acnt,bcnt,(syuukai+1)*CN[i])
  ans=max(ans,cnt)
print(ans)

Submission status: Runtime Error

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
import numpy as np
sys.setrecursionlimit(10**6)
# INF =  float("inf")
INF = 10**18
import bisect
import statistics
mod = 10**9+7
# mod = 998244353

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

d = defaultdict(int)
for i in range(K):
    a, b, c = list(map(int, stdin.readline().split()))
    d[(a,b)] = c

dp = [[[0 for k in range(4)] for j in range(C+1)] for i in range(R+1)]

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

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


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

Submission status: Runtime Error

Solution code:
r,c,k=map(int,input().split(' '))
R=[]
C=[]
K=[]
start=0
for i in range(k):
    ri,ci,ki=map(int,input().split(' '))
    if(ri==1 and ci==1):
        start=ki
    R.append(ri)
    C.append(ci)
    K.append(ki)
ind=-1
for i in range(len(R)):
    if(R[i]==1 and C[i]==1):
        ind=i
s=start
K.remove(start)
# print(start)
K.sort()
K=K[1:]
# print(K)
s=s+sum(K)
print(s)

Submission status: Runtime Error

Solution code:
// template version 1.12
using namespace std;
#include <iostream>
#include <bits/stdc++.h>

// varibable settings
#define infile "../test/sample-1.in"
#define int long long //{{{
const int INF=1e18;
const int MOD=1e9+7; //}}}

// define basic macro {{{
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define _rrep(i,n) rrepi(i,0,n)
#define rrepi(i,a,b) for(int i=(int)((b)-1);i>=(int)(a);--i)
#define rrep(...) _overload3(__VA_ARGS__,rrepi,_rrep,)(__VA_ARGS__)
#define each(i,a) for (auto&& i : a)
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define pb(a) push_back(a)
#define mp(a, b) make_pair(a, b)
#define uni(x) sort(all(x));x.erase(unique(all(x)),x.end())
#define ub upper_bound
#define lb lower_bound
#define posl(A, x) (lower_bound(all(A), x)-A.begin())
#define posu(A, x) (upper_bound(all(A),x)-A.begin())
template<class T> inline void chmax(T &a, const T &b) { if((a) < (b)) (a) = (b); }
template<class T> inline void chmin(T &a, const T &b) { if((a) > (b)) (a) = (b); }

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef long double ld;
typedef pair<int,int> pii;
typedef tuple<int,int,int> iii;

template<typename T> using PQ = priority_queue<T, vector<T>, greater<T>>;
struct Fast { Fast(){ std::cin.tie(0); ios::sync_with_stdio(false); } } fast;

#if defined(PCM) || defined(LOCAL)
  #include "lib/dump.hpp"
#else
  #define dump(...) 42
  #define dump_1d(...) 42
  #define dump_2d(...) 42
#endif
//}}}

// 隣接リストで使う辺を表す型
struct Edge {
  int to, cost;  // 辺の接続先頂点, 辺の重み
  Edge(int to, int cost) : to(to), cost(cost) {}  // コンストラクタ
};

typedef vector<vector<Edge> > AdjList;  // 隣接リストの型
AdjList graph;  // グラフの辺を格納した構造体
                // graph[v][i]は頂点vから出るi番目の辺Edge

vector<int> dist; // 最短距離

int solve(){
    
    int H=3001;
    int W=3001;
    //int H=10;
    //int W=10;
    ll a,b,x;
    ll h,w,k;cin>>h>>w>>k;
    ll ans=0;
    
    vector<vector<ll>> v(H, vector<int>(W));
    rep(i,k){
        cin>>a>>b>>x;
        v[a][b]=x;
    }
    vector<vector<vector<ll>>> dp(H, vector<vector<ll>>(W, vector<ll>(4)));
    repi(i,1,h+1){
        repi(j,1,w+1){
            
            ll up_max=0;
            rep(x,4){
                if(up_max<dp[i-1][j][x])up_max=dp[i-1][j][x];
            }
            dp[i][j][0]=up_max;
            
            if(v[i][j]!=0 && dp[i][j][1]<up_max+v[i][j])dp[i][j][1]=up_max+v[i][j];
                
            if (dp[i][j][0]<dp[i][j-1][0])dp[i][j][0]=dp[i][j-1][0];
            repi(x,1,4){
                if (dp[i][j][x]<dp[i][j-1][x])dp[i][j][x]=dp[i][j-1][x];
                if (dp[i][j][x]<dp[i][j-1][x-1]+v[i][j])dp[i][j][x]=dp[i][j-1][x-1]+v[i][j];
            }
/*                dp[i][j][x]=max(dp[i][j][x],dp[i][j-1][x],dp[i][j-1][x-1]+v[i][j]);
            }
            
            for x in range(1,4)[::-1]:
                dp[i][j][x]=max(dp[i][j][x],dp[i][j-1][x],dp[i][j-1][x-1]+v[i][j])
            
*/
        }
    }
    
    
    
    rep(x,4){
        if (ans<dp[h][w][x])ans=dp[h][w][x];
    }

    
    
    cout<<ans<<endl;
    
    return 0;
}

signed main() { //{{{
#ifdef INPUT_FROM_FILE
  std::ifstream in(infile);
  std::cin.rdbuf(in.rdbuf());
#endif
  solve();
  return 0;
} //}}}

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
input = sys.stdin.readline
def main():
    r,c,k=map(int,input().split())
    a=[list(map(int,input().split())) for _ in range(k)]
    dp=np.array([[[0,0,0,0,0]for _ in range(c+1)]for _ in range(r+1)])
    b=[[0 for _ in range(c+1)] for _ in range(r+1)]
    for x,y,z in a:
        b[x][y]=z
    for i in range(1,r+1):
        for j in range(1,c+1):
            v=b[i][j]
            if b==0:
                dp[i][j][0]=max(dp[i][j-1][0],dp[i-1][j][0],dp[i-1][j][1],dp[i-1][j][2],dp[i-1][j][3])
                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][0]=max(dp[i][j-1][0],dp[i-1][j][0],dp[i-1][j][1],dp[i-1][j][2],dp[i-1][j][3])
                dp[i][j][1]=max(dp[i][j-1][1],dp[i][j-1][0]+v,dp[i-1][j][0]+v,dp[i-1][j][1]+v,dp[i-1][j][2]+v,dp[i-1][j][3]+v)
                dp[i][j][2]=max(dp[i][j-1][2],dp[i][j-1][1]+v)
                dp[i][j][3]=max(dp[i][j-1][3],dp[i][j-1][2]+v)
    print(max(dp[i][j]))

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(50000)
N,K= [int(v) for v in input().split()]
P = [int(v) - 1 for v in input().split()]
C = [int(v) for v in input().split()]

visited = [True for _ in range(N)]

def dfs(node,total,state,m):
    if visited[node]:
        return total,state,m
    nextM = max(m,total+C[node])
    state.append(C[node])
    total += C[node]
    visited[node] = True
    return dfs(P[node],total,state,nextM)

ans = -float('inf')

def calc(node):
    global visited,ans
    visited = [False for _ in range(N)]
    total,state,ma = dfs(P[node],0,[],-float('inf'))
    ans = max(ma,ans)
    K_ = K
    count = K // len(state)

    tmp = total * count
    for v in state[:K%len(state)]:
        tmp += v
    ans = max(ans,tmp)

    if total > 0:
        tmp = total * (count-1)
        for v in state:
            tmp += v
            ans = max(ans,tmp)






for i in range (N):
    calc(i)

print(ans)

Submission status: Runtime Error

Solution code:
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    R, C, K = map(int, input().split())
    item = [[0 for _ in range(C)] for r in range(R)]
    for _ in range(K):
        r, c, k = map(int, input().split())
        item[r-1][c-1] = k
    
    DP = [[[-1 for _ in range(C)] for r in range(R)] for i in range(4)]
    visited = [[False for c in range(C)] for r in range(R)]
    q = deque()
    DP[0][0][1] = 0
    visited[0][0] = True
    if item[0][0] > 0:
        DP[1][0][1] = item[0][0]
        DP[0][1][0] = item[0][0]
    q.append((0, 1))
    q.append((1, 0))
    while q:
        r, c = q.popleft()
        if not visited[r][c]:
            visited[r][c] = True
            for i in range(4):
                if DP[i][r][c] > -1:
                    if r + 1 < R: 
                        DP[0][r+1][c] = max(DP[0][r+1][c], DP[i][r][c])
                        q.append((r+1, c))
                    if c + 1 < C: 
                        DP[i][r][c+1] = max(DP[i][r][c+1], DP[i][r][c])
                        q.append((r, c+1))
                    if i < 3 and item[r][c] > 0:
                        if r + 1 < R: DP[0][r+1][c] = max(DP[0][r+1][c], DP[i][r][c] + item[r][c])
                        if c + 1 < C: DP[i+1][r][c+1] = max(DP[i+1][r][c+1], DP[i][r][c] + item[r][c])

    ans = DP[3][R-1][C-1]
    for i in range(3): ans = max(ans, DP[i][R-1][C-1] + item[R-1][C-1])
    print(ans)
    return 0

if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

#Educational DP Contest
#H-Grid1


r,c,k = map(int,input().split())
items = [[0]*c for _ in range(r)]
for i in range(k):
    a,b,v = map(int,readline().split())
    a,b = a-1,b-1
    items[a][b] = v

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

#process1
#移動は→↓の２通りのみなので、その方向に探索していけば良い。
for i in range(1,r+1):
    for j in range(1,c+1):
        if items[i-1][j-1]:
            dp[i][j][0] = max(max(dp[i-1][j]),dp[i][j-1][0])
            dp[i][j][1] = max(max(dp[i-1][j])+items[i-1][j-1],dp[i][j-1][1],dp[i][j-1][0]+items[i-1][j-1])
            dp[i][j][2] = max(dp[i][j-1][2],dp[i][j-1][1]+items[i-1][j-1])
            dp[i][j][3] = max(dp[i][j-1][3],dp[i][j-1][2]+items[i-1][j-1])
        else:
            dp[i][j][0] = max(max(dp[i-1][j]),dp[i][j-1][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]
        """if maze[i][j] == "#":
            continue
        if i > 0: #i-1を参照するため端っこは除く
            dp[i][j] += dp[i-1][j]
        if j > 0:
            dp[i][j] += dp[i][j-1]
        dp[i][j] %= mod"""
"""ans = 0
for i in range(c):
    ans = max(ans,max(dp[-1][i]))

print(ans)"""
print(max(dp[-1][-1]))