Buggy python submission (verdict: Time Limit Exceeded):
R, C, K = map(int, input().split())

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

max_p = [0]*(C+1)
for i in range(R+1):
    now0 = [0]*(C+1)
    now1 = [0]*(C+1)
    now2 = [0]*(C+1)
    now3 = [0]*(C+1)
    for j in range(C+1):
        v = V[i][j]
        la = lb = 0
        if j > 0:
            la = now0[j-1]
            lb = now1[j-1]
            now2[j] = max(now2[j], now2[j-1], lb + v)
            now3[j] = max(now3[j], now3[j-1], now2[j-1] + v)
        if i > 0:
            now0[j] = max(now0[j], max_p[j], la)
            now1[j] = max(now1[j], max_p[j] + v, la + v, lb)
        max_p[j] = max(now0[j], now1[j], now2[j], now3[j])

print(max(now0[C], now1[C], now2[C], now3[C]))


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

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

pre = [[0]*(3+1) for _ in range(C+1)]
for i in range(R+1):
    now = [[0]*(3+1) for _ in range(C+1)]
    for j in range(C+1):
        for k in range(3+1):
            if i-1 >= 0:
                now[j][0] = max(now[j][0], pre[j][k])
                now[j][1] = max(now[j][1], pre[j][k] + V[i][j])

            if j-1 >= 0:
                now[j][k] = max(now[j][k], now[j-1][k])
                if k-1 >= 0:
                    now[j][k] = max(now[j][k], now[j-1][k-1] + V[i][j])
    pre = now

print(max(now[C]))

Buggy python submission (verdict: Time Limit Exceeded):
R, C, K = map(int, input().split())

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

pre0 = [0]*(C+1)
pre1 = [0]*(C+1)
pre2 = [0]*(C+1)
pre3 = [0]*(C+1)
for i in range(R+1):
    now0 = [0]*(C+1)
    now1 = [0]*(C+1)
    now2 = [0]*(C+1)
    now3 = [0]*(C+1)
    for j in range(C+1):
        v = V[i][j]
        la = lb = 0
        if j > 0:
            la = now0[j-1]
            lb = now1[j-1]
            now2[j] = max(now2[j], now2[j-1], lb + v)
            now3[j] = max(now3[j], now3[j-1], now2[j-1] + v)
        if i > 0:
            max_p = max(pre0[j], pre1[j], pre2[j], pre3[j])
            now0[j] = max(now0[j], max_p, la)
            now1[j] = max(now1[j], max_p + v, la + v, lb)
    pre0 = now0
    pre1 = now1
    pre2 = now2
    pre3 = now3

print(max(now0[C], now1[C], now2[C], now3[C]))


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

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

pre = [[0]*(3+1) for _ in range(C+1)]
for i in range(R+1):
    now = [[0]*(3+1) for _ in range(C+1)]
    for j in range(C+1):
        for k in range(3+1):
            if i-1 >= 0:
                now[j][0] = max(now[j][0], pre[j][k])
                now[j][1] = max(now[j][1], pre[j][k] + V[i][j])

            if j-1 >= 0:
                now[j][k] = max(now[j][k], now[j-1][k])
                if k-1 >= 0:
                    now[j][k] = max(now[j][k], now[j-1][k-1] + V[i][j])
    pre = now

print(max(now[C]))

Buggy python submission (verdict: Time Limit Exceeded):
R, C, K = map(int, input().split())

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

dp0 = [[0]*(C+1) for _ in range(R+1)]
dp1 = [[0]*(C+1) for _ in range(R+1)]
dp2 = [[0]*(C+1) for _ in range(R+1)]
dp3 = [[0]*(C+1) for _ in range(R+1)]
for i in range(R+1):
    for j in range(C+1):
        v = V[i][j]

        la = lb = lc = ld = 0
        if j > 0:
            la = dp0[i][j-1]
            lb = dp1[i][j-1]
            lc = dp2[i][j-1]
            ld = dp3[i][j-1]
            dp2[i][j] = max(dp2[i][j], lc, lb + v)
            dp3[i][j] = max(dp3[i][j], ld, lc + v)

        if i > 0:
            max_p = max(dp0[i-1][j], dp1[i-1][j], dp2[i-1][j], dp3[i-1][j])
            dp0[i][j] = max(dp0[i][j], max_p, la)
            dp1[i][j] = max(dp0[i][j], max_p + v, lb, la + v)

print(max(dp0[R][C], dp1[R][C], dp2[R][C], dp3[R][C]))


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

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

pre = [[0]*(3+1) for _ in range(C+1)]
for i in range(R+1):
    now = [[0]*(3+1) for _ in range(C+1)]
    for j in range(C+1):
        for k in range(3+1):
            if i-1 >= 0:
                now[j][0] = max(now[j][0], pre[j][k])
                now[j][1] = max(now[j][1], pre[j][k] + V[i][j])

            if j-1 >= 0:
                now[j][k] = max(now[j][k], now[j-1][k])
                if k-1 >= 0:
                    now[j][k] = max(now[j][k], now[j-1][k-1] + V[i][j])
    pre = now

print(max(now[C]))

Buggy python submission (verdict: Time Limit Exceeded):
R, C, K = map(int, input().split())

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

dp0 = [[0]*(C+1) for _ in range(R+1)]
dp1 = [[0]*(C+1) for _ in range(R+1)]
dp2 = [[0]*(C+1) for _ in range(R+1)]
dp3 = [[0]*(C+1) for _ in range(R+1)]
for i in range(R+1):
    for j in range(C+1):
        v = V[i][j]

        a = dp0[i][j]
        b = dp0[i][j]
        c = dp0[i][j]
        d = dp0[i][j]

        pa = pb = pc = pd = 0
        if i > 0:
            pa = dp0[i-1][j]
            pb = dp1[i-1][j]
            pc = dp2[i-1][j]
            pd = dp3[i-1][j]

        la = lb = lc = ld = 0
        if j > 0:
            la = dp0[i][j-1]
            lb = dp1[i][j-1]
            lc = dp2[i][j-1]
            ld = dp3[i][j-1]

        a = max(a, pa)
        b = max(b, pa+v)
        a = max(a, la)

        a = max(a, pb)
        b = max(b, pb+v)
        b = max(b, lb, la+v)

        a = max(a, pc)
        b = max(b, pc+v)
        c = max(c, lc, lb+v)

        a = max(a, pd)
        b = max(b, pd+v)
        d = max(d, ld, lc+v)

        dp0[i][j] = a
        dp1[i][j] = b
        dp2[i][j] = c
        dp3[i][j] = d

print(max(dp0[R][C], dp1[R][C], dp2[R][C], dp3[R][C]))


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

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

pre = [[0]*(3+1) for _ in range(C+1)]
for i in range(R+1):
    now = [[0]*(3+1) for _ in range(C+1)]
    for j in range(C+1):
        for k in range(3+1):
            if i-1 >= 0:
                now[j][0] = max(now[j][0], pre[j][k])
                now[j][1] = max(now[j][1], pre[j][k] + V[i][j])

            if j-1 >= 0:
                now[j][k] = max(now[j][k], now[j-1][k])
                if k-1 >= 0:
                    now[j][k] = max(now[j][k], now[j-1][k-1] + V[i][j])
    pre = now

print(max(now[C]))

Buggy python submission (verdict: Time Limit Exceeded):
R, C, K = map(int, input().split())

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

pre = [[0]*(3+1) for _ in range(C+1)]
for i in range(R+1):
    now = [[0]*(3+1) for _ in range(C+1)]
    for j in range(C+1):
        for k in range(3+1):
            if i-1 >= 0:
                now[j][0] = max(now[j][0], pre[j][k])
                now[j][1] = max(now[j][1], pre[j][k] + V[i][j])

            if j-1 >= 0:
                now[j][k] = max(now[j][k], now[j-1][k])
                if k-1 >= 0:
                    now[j][k] = max(now[j][k], now[j-1][k-1] + V[i][j])
    pre = now

print(max(now[C]))


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

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

pre = [[0]*(3+1) for _ in range(C+1)]
for i in range(R+1):
    now = [[0]*(3+1) for _ in range(C+1)]
    for j in range(C+1):
        for k in range(3+1):
            if i-1 >= 0:
                now[j][0] = max(now[j][0], pre[j][k])
                now[j][1] = max(now[j][1], pre[j][k] + V[i][j])

            if j-1 >= 0:
                now[j][k] = max(now[j][k], now[j-1][k])
                if k-1 >= 0:
                    now[j][k] = max(now[j][k], now[j-1][k-1] + V[i][j])
    pre = now

print(max(now[C]))

Buggy python submission (verdict: Time Limit Exceeded):
R, C, K = map(int, input().split())

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

# print(*V,sep='\n',end='\n\n')

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

# for r in dp:
#     for c in r:
#         print('[',end='')
#         for x in c:
#             print(x,end=' ')
#         print(']',end='')
#     print()
# print()

for i in range(R+1):
    for j in range(C+1):
        for k in range(3+1):
            if i-1 >= 0:
                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] + V[i][j])

            if j-1 >= 0:
                dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k])
                if k-1 >= 0:
                    dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k-1] + V[i][j])

# for r in dp:
#     for c in r:
#         print('[',end='')
#         for x in c:
#             print(x,end=' ')
#         print(']',end='')
#     print()
# print()

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


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

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

pre = [[0]*(3+1) for _ in range(C+1)]
for i in range(R+1):
    now = [[0]*(3+1) for _ in range(C+1)]
    for j in range(C+1):
        for k in range(3+1):
            if i-1 >= 0:
                now[j][0] = max(now[j][0], pre[j][k])
                now[j][1] = max(now[j][1], pre[j][k] + V[i][j])

            if j-1 >= 0:
                now[j][k] = max(now[j][k], now[j-1][k])
                if k-1 >= 0:
                    now[j][k] = max(now[j][k], now[j-1][k-1] + V[i][j])
    pre = now

print(max(now[C]))

Buggy python submission (verdict: Time Limit Exceeded):
R, C, K = map(int, input().split())

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

# print(*V,sep='\n',end='\n\n')

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

# for r in dp:
#     for c in r:
#         print('[',end='')
#         for x in c:
#             print(x,end=' ')
#         print(']',end='')
#     print()
# print()

for i in range(R+1):
    for j in range(C+1):
        for k in range(3+1):
            if i-1 >= 0:
                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] + V[i][j])

            if j-1 >= 0:
                dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k])
                if k-1 >= 0:
                    dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k-1] + V[i][j])

# for r in dp:
#     for c in r:
#         print('[',end='')
#         for x in c:
#             print(x,end=' ')
#         print(']',end='')
#     print()
# print()

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


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

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

pre = [[0]*(3+1) for _ in range(C+1)]
for i in range(R+1):
    now = [[0]*(3+1) for _ in range(C+1)]
    for j in range(C+1):
        for k in range(3+1):
            if i-1 >= 0:
                now[j][0] = max(now[j][0], pre[j][k])
                now[j][1] = max(now[j][1], pre[j][k] + V[i][j])

            if j-1 >= 0:
                now[j][k] = max(now[j][k], now[j-1][k])
                if k-1 >= 0:
                    now[j][k] = max(now[j][k], now[j-1][k-1] + V[i][j])
    pre = now

print(max(now[C]))

Buggy python submission (verdict: Time Limit Exceeded):
R, C, K = map(int, input().split())

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

# print(*mesh,sep='\n',end='\n\n')

def big3(d): return sorted(d, reverse=True)[:3]

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

for i in range(1, R+1):
    for j in range(1, C+1):
        b3 = []
        for k in range(j, C+1):
            b3 = big3(b3 + [mesh[i][k]])
            # print('{} [{}:{}] b3 {} s3 {}'.format(i,j,k,b3,sum(b3)))
            dp[i][k] = max(\
                dp[i][k],\
                dp[i-1][j] + sum(b3),\
                dp[i-1][k] + mesh[i][k]\
                )
        # print('-----')
    # print('{} ['.format(i), end='')
    # for x in dp[i]: print('{:>2} '.format(x),end='')
    # print(']')
# print('===')
print(dp[R][C])


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

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

pre = [[0]*(3+1) for _ in range(C+1)]
for i in range(R+1):
    now = [[0]*(3+1) for _ in range(C+1)]
    for j in range(C+1):
        for k in range(3+1):
            if i-1 >= 0:
                now[j][0] = max(now[j][0], pre[j][k])
                now[j][1] = max(now[j][1], pre[j][k] + V[i][j])

            if j-1 >= 0:
                now[j][k] = max(now[j][k], now[j-1][k])
                if k-1 >= 0:
                    now[j][k] = max(now[j][k], now[j-1][k-1] + V[i][j])
    pre = now

print(max(now[C]))

Buggy python submission (verdict: Time Limit Exceeded):
import sys
# print(sys.getrecursionlimit())
sys.setrecursionlimit(3000000)
# print(sys.getrecursionlimit())

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

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

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

# print(*mesh,sep='\n')

def big3(d):
    return sorted(d, reverse=True)[:3]

def dfs(i, j, k, s):
    # print('i {} j {} k {} s {}'.format(i,j,k,s))

    if i == R-1 and j == C-1:
        r = big3(k + [mesh[i][j]])
        # print('r {}'.format(r))
        return s + sum(r)

    # if i == R or j == C: return val

    # nx_k = k + [mesh[i][j]] if mesh[i][j] > 0 else k
    nx_k = big3(k + [mesh[i][j]])

    val = 0
    if j+1 <= C-1:
        val = dfs(i, j+1, nx_k, s)

    if i+1 <= R-1:
        pre = sum(nx_k)
        v = dfs(i+1, j, [], s + pre)
        val = max(val, v)
        # print('pre {} v {}'.format(pre,v))

    return val

# ans = dfs(0, 0, 1 if mesh[0][0] > 0 else 0)
ans = dfs(0, 0, [], 0)
print(ans)


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

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

pre = [[0]*(3+1) for _ in range(C+1)]
for i in range(R+1):
    now = [[0]*(3+1) for _ in range(C+1)]
    for j in range(C+1):
        for k in range(3+1):
            if i-1 >= 0:
                now[j][0] = max(now[j][0], pre[j][k])
                now[j][1] = max(now[j][1], pre[j][k] + V[i][j])

            if j-1 >= 0:
                now[j][k] = max(now[j][k], now[j-1][k])
                if k-1 >= 0:
                    now[j][k] = max(now[j][k], now[j-1][k-1] + V[i][j])
    pre = now

print(max(now[C]))

Buggy python submission (verdict: Runtime Error):
R, C, K = map(int, input().split())
# print(R,C,K)

# vis = [[False]*C for _ in range(R)]
mesh = [[0]*C for _ in range(R)]

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

# print(vis)
# print(*mesh,sep='\n')

def dfs(i, j, rows):
    # print('i {} j {} rows {}'.format(i,j,rows))
    # print('i {} j {}'.format(i,j))
    # print(*rows,sep='\n')

    v = 0
    if i == R-1 and j == C-1:
        rows[i].append(mesh[i][j])
        # print('rows {}'.format(rows))
        import heapq
        for row in rows:
            r = []
            for x in row:
                heapq.heappush(r, -x)
            if len(r): v += -heapq.heappop(r)
            if len(r): v += -heapq.heappop(r)
            if len(r): v += -heapq.heappop(r)
        rows[i].pop()
        return v
    if i == R or j == C: return v
    # if vis[i][j]: return v
    # vis[i][j] = True
    rows[i].append(mesh[i][j])
    if j+1 < C: v = dfs(i,   j+1, rows)
    if i+1 < R: v = max(v, dfs(i+1, j  , rows))
    rows[i].pop()
    return v

ans = dfs(0, 0, [[] for _ in range(R)])
print(ans)


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

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

pre = [[0]*(3+1) for _ in range(C+1)]
for i in range(R+1):
    now = [[0]*(3+1) for _ in range(C+1)]
    for j in range(C+1):
        for k in range(3+1):
            if i-1 >= 0:
                now[j][0] = max(now[j][0], pre[j][k])
                now[j][1] = max(now[j][1], pre[j][k] + V[i][j])

            if j-1 >= 0:
                now[j][k] = max(now[j][k], now[j-1][k])
                if k-1 >= 0:
                    now[j][k] = max(now[j][k], now[j-1][k-1] + V[i][j])
    pre = now

print(max(now[C]))