Buggy python submission (verdict: Time Limit Exceeded):
R, C, K = map(int, input().split())
V = [[0 for _ in range(C)] for _ in range(R)]
for _ in range(K):
  r, c, v = map(int, input().split())
  V[r-1][c-1] = v
M = [[[0, 0, 0, 0] for _ in range(C)] for _ in range(R)]
# M[r][c][count in column (c)]
for r in range(R):
  for c in range(C):
    for n_pick in [0, 1] if V[r][c] else [0]:
      M[r][c][n_pick] = max(M[r][c][n_pick], n_pick*V[r][c])
      if r > 0:
        for n_prev in range(4):
          #print('R++', r, c, n_pick, n_prev)
          if M[r-1][c][n_prev] > 0 or n_prev == 0:
            M[r][c][n_pick]=max(M[r][c][n_pick],
              M[r-1][c][n_prev] + n_pick*V[r][c])
      if c > 0:
        for n_prev in range(4 - n_pick):
          #print('C++', r, c, n_pick, n_prev)
          if  M[r][c-1][n_prev]  > 0 or n_prev == 0:
            M[r][c][n_prev+n_pick]=max(M[r][c][n_prev+n_pick],
              M[r][c-1][n_prev] + n_pick*V[r][c])
    #print(candidates)
    #print(r, c, candidates, M)
    #for i in range(4):
    #  M[r][c][i] = max(candidates[i])
    #print(r, c, M)
#print(V, M)
print(max(M[R-1][C-1]))


Fixed submission:
R, C, K = map(int, input().split())
V = [[0 for _ in range(C)] for _ in range(R)]
for _ in range(K):
  r, c, v = map(int, input().split())
  V[r-1][c-1] = v
M = [0] * R * C * 4 
# M[r*C*4 + c*4 + i]
# M[(r-1)*C*4 + c*4 + i]
# M[r*C*4 + (c-1)*4 + i]
# M[r][c][count in column (c)]
for r in range(R):
  for c in range(C):
    for n_pick in [0, 1] if V[r][c] else [0]:
      M[r*C*4 + c*4 +n_pick] = max(M[r*C*4 + c*4 +n_pick], n_pick*V[r][c])
      if r > 0:
        for n_prev in range(4):
          #print('R++', r, c, n_pick, n_prev)
          if M[(r-1)*C*4 + c*4 +n_prev] > 0 or n_prev == 0:
            M[r*C*4 + c*4 +n_pick]=max(M[r*C*4 + c*4 +n_pick],
              M[(r-1)*C*4 + c*4 +n_prev] + n_pick*V[r][c])
      if c > 0:
        for n_prev in range(4 - n_pick):
          #print('C++', r, c, n_pick, n_prev)
          if  M[r*C*4 + (c-1)*4 +n_prev]  > 0 or n_prev == 0:
            M[r*C*4 + c*4 +n_prev+n_pick]=max(M[r*C*4 + c*4 + n_prev+n_pick],
              M[r*C*4 + (c-1)*4 +n_prev] + n_pick*V[r][c])
    #print(candidates)
    #print(r, c, candidates, M)
    #for i in range(4):
    #  M[r][c][i] = max(candidates[i])
    #print(r, c, M)
#print(V, M)
print(max(M[((R-1)*C*4 + (C-1) *4):((R-1)*C*4 + (C-1) *4+4)]))

Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())
P = list(map(lambda x:int(x)-1, input().split()))
C = list(map(int, input().split()))
done = [False] * N
ans = -10**30
must_negative = all([c < 0 for c in C])
for i in range(N):
  if done[i]:
    continue
  loop = [i]
  done[loop[-1]] = True
  while not done[P[loop[-1]]]:
    loop.append(P[loop[-1]])
    done[loop[-1]] = True
    #print(loop, done)
  #print(loop)
  scores = [C[i] for i in loop]
  #print(scores)
  cumsum = [0]
  for s in scores * 2:
    cumsum.append(cumsum[-1] + s)
  #print(cumsum)
  L = len(scores)
  if cumsum[L] >= 0:
    # (L+K) // L  loops - max
    l = max(0, (K - L) // L )
    k_max = K - l * L
    #print(l, k_max)
    base_score = cumsum[L] * l
  else:
    k_max = min(K, L)
    #print(k_max)
    base_score = 0
  for i in range(L):
    for k in range(k_max+1):
      score = base_score + cumsum[i + k] - cumsum[i]
      #print(i, k, base_score, score)
      if must_negative and score == 0:
        continue
      ans = max(ans, score)
print(ans)


Fixed submission:
R, C, K = map(int, input().split())
V = [[0 for _ in range(C)] for _ in range(R)]
for _ in range(K):
  r, c, v = map(int, input().split())
  V[r-1][c-1] = v
M = [0] * R * C * 4 
# M[r*C*4 + c*4 + i]
# M[(r-1)*C*4 + c*4 + i]
# M[r*C*4 + (c-1)*4 + i]
# M[r][c][count in column (c)]
for r in range(R):
  for c in range(C):
    for n_pick in [0, 1] if V[r][c] else [0]:
      M[r*C*4 + c*4 +n_pick] = max(M[r*C*4 + c*4 +n_pick], n_pick*V[r][c])
      if r > 0:
        for n_prev in range(4):
          #print('R++', r, c, n_pick, n_prev)
          if M[(r-1)*C*4 + c*4 +n_prev] > 0 or n_prev == 0:
            M[r*C*4 + c*4 +n_pick]=max(M[r*C*4 + c*4 +n_pick],
              M[(r-1)*C*4 + c*4 +n_prev] + n_pick*V[r][c])
      if c > 0:
        for n_prev in range(4 - n_pick):
          #print('C++', r, c, n_pick, n_prev)
          if  M[r*C*4 + (c-1)*4 +n_prev]  > 0 or n_prev == 0:
            M[r*C*4 + c*4 +n_prev+n_pick]=max(M[r*C*4 + c*4 + n_prev+n_pick],
              M[r*C*4 + (c-1)*4 +n_prev] + n_pick*V[r][c])
    #print(candidates)
    #print(r, c, candidates, M)
    #for i in range(4):
    #  M[r][c][i] = max(candidates[i])
    #print(r, c, M)
#print(V, M)
print(max(M[((R-1)*C*4 + (C-1) *4):((R-1)*C*4 + (C-1) *4+4)]))

Buggy python submission (verdict: Time Limit Exceeded):
R, C, K = map(int, input().split())
V = [[[] for _ in range(C)] for _ in range(R)]
for _ in range(K):
  r, c, v = map(int, input().split())
  V[r-1][c-1].append(v)
M = [[[0, 0, 0, 0] for _ in range(C)] for _ in range(R)]
# M[r][c][count in column (c)]
for r in range(R):
  for c in range(C):
    V[r][c].sort(reverse=True)
    #candidates = [0 for _ in range(4)]
    #print(candidates)
    for n_pick in range(1 + min(3, len(V[r][c]))):
      s = sum(V[r][c][:n_pick])
      M[r][c][n_pick]=max(M[r][c][n_pick],s)
      if r > 0:
        for n_prev in range(4):
          #print('R++', r, c, n_pick, n_prev)
          if M[r-1][c][n_prev] > 0 or n_prev == 0:
            M[r][c][n_pick]=max(M[r][c][n_pick],
              M[r-1][c][n_prev] + s)
      if c > 0:
        for n_prev in range(4 - n_pick):
          #print('C++', r, c, n_pick, n_prev)
          if  M[r][c-1][n_prev]  > 0 or n_prev == 0:
            M[r][c][n_prev+n_pick]=max(M[r][c][n_prev+n_pick],
              M[r][c-1][n_prev] + s)
    #print(candidates)
    #print(r, c, candidates, M)
    #for i in range(4):
    #  M[r][c][i] = max(candidates[i])
    #print(r, c, M)
#print(V, M)
print(max(M[R-1][C-1]))

Fixed submission:
R, C, K = map(int, input().split())
V = [[0 for _ in range(C)] for _ in range(R)]
for _ in range(K):
  r, c, v = map(int, input().split())
  V[r-1][c-1] = v
M = [0] * R * C * 4 
# M[r*C*4 + c*4 + i]
# M[(r-1)*C*4 + c*4 + i]
# M[r*C*4 + (c-1)*4 + i]
# M[r][c][count in column (c)]
for r in range(R):
  for c in range(C):
    for n_pick in [0, 1] if V[r][c] else [0]:
      M[r*C*4 + c*4 +n_pick] = max(M[r*C*4 + c*4 +n_pick], n_pick*V[r][c])
      if r > 0:
        for n_prev in range(4):
          #print('R++', r, c, n_pick, n_prev)
          if M[(r-1)*C*4 + c*4 +n_prev] > 0 or n_prev == 0:
            M[r*C*4 + c*4 +n_pick]=max(M[r*C*4 + c*4 +n_pick],
              M[(r-1)*C*4 + c*4 +n_prev] + n_pick*V[r][c])
      if c > 0:
        for n_prev in range(4 - n_pick):
          #print('C++', r, c, n_pick, n_prev)
          if  M[r*C*4 + (c-1)*4 +n_prev]  > 0 or n_prev == 0:
            M[r*C*4 + c*4 +n_prev+n_pick]=max(M[r*C*4 + c*4 + n_prev+n_pick],
              M[r*C*4 + (c-1)*4 +n_prev] + n_pick*V[r][c])
    #print(candidates)
    #print(r, c, candidates, M)
    #for i in range(4):
    #  M[r][c][i] = max(candidates[i])
    #print(r, c, M)
#print(V, M)
print(max(M[((R-1)*C*4 + (C-1) *4):((R-1)*C*4 + (C-1) *4+4)]))

Buggy python submission (verdict: Time Limit Exceeded):
R, C, K = map(int, input().split())
V = [[[] for _ in range(C)] for _ in range(R)]
for _ in range(K):
  r, c, v = map(int, input().split())
  V[r-1][c-1].append(v)
M = [[[0, 0, 0, 0] for _ in range(C)] for _ in range(R)]
# M[r][c][count in column (c)]
for r in range(R):
  for c in range(C):
    V[r][c].sort(reverse=True)
    candidates = [[0] for _ in range(4)]
    #print(candidates)
    for n_pick in range(1 + min(3, len(V[r][c]))):
      candidates[n_pick].append(sum(V[r][c][:n_pick]))
      if r > 0:
        for n_prev in range(4):
          #print('R++', r, c, n_pick, n_prev)
          if M[r-1][c][n_prev] > 0 or n_prev == 0:
            candidates[n_pick].append(
              M[r-1][c][n_prev] + sum(V[r][c][:n_pick]))
      if c > 0:
        for n_prev in range(4 - n_pick):
          #print('C++', r, c, n_pick, n_prev)
          if  M[r][c-1][n_prev]  > 0 or n_prev == 0:
            candidates[n_prev+n_pick].append(
              M[r][c-1][n_prev] + sum(V[r][c][:n_pick]))
    #print(candidates)
    #print(r, c, candidates, M)
    for i in range(4):
      M[r][c][i] = max(candidates[i])
    #print(r, c, M)
#print(V, M)
print(max(M[R-1][C-1]))

Fixed submission:
R, C, K = map(int, input().split())
V = [[0 for _ in range(C)] for _ in range(R)]
for _ in range(K):
  r, c, v = map(int, input().split())
  V[r-1][c-1] = v
M = [0] * R * C * 4 
# M[r*C*4 + c*4 + i]
# M[(r-1)*C*4 + c*4 + i]
# M[r*C*4 + (c-1)*4 + i]
# M[r][c][count in column (c)]
for r in range(R):
  for c in range(C):
    for n_pick in [0, 1] if V[r][c] else [0]:
      M[r*C*4 + c*4 +n_pick] = max(M[r*C*4 + c*4 +n_pick], n_pick*V[r][c])
      if r > 0:
        for n_prev in range(4):
          #print('R++', r, c, n_pick, n_prev)
          if M[(r-1)*C*4 + c*4 +n_prev] > 0 or n_prev == 0:
            M[r*C*4 + c*4 +n_pick]=max(M[r*C*4 + c*4 +n_pick],
              M[(r-1)*C*4 + c*4 +n_prev] + n_pick*V[r][c])
      if c > 0:
        for n_prev in range(4 - n_pick):
          #print('C++', r, c, n_pick, n_prev)
          if  M[r*C*4 + (c-1)*4 +n_prev]  > 0 or n_prev == 0:
            M[r*C*4 + c*4 +n_prev+n_pick]=max(M[r*C*4 + c*4 + n_prev+n_pick],
              M[r*C*4 + (c-1)*4 +n_prev] + n_pick*V[r][c])
    #print(candidates)
    #print(r, c, candidates, M)
    #for i in range(4):
    #  M[r][c][i] = max(candidates[i])
    #print(r, c, M)
#print(V, M)
print(max(M[((R-1)*C*4 + (C-1) *4):((R-1)*C*4 + (C-1) *4+4)]))