Buggy python submission (verdict: Runtime Error):
import sys
import math
from collections import defaultdict
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid_int(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    R, C, K = NMI()
    grid = defaultdict(int, 0)
    data = [NMI() for _ in range(K)]
    for r, c, v in data:
        grid[(r-1)*3001 + c-1] = v

    # dp = [[[0]*4 for _ in range(C+2)] for _ in range(R+2)]
    # (r, c, i) -> r * 10**8 + c * 10**4 + i
    def get_point(r, c, i):
        return r * 30010 + c * 10 + i

    dp = defaultdict(int, 0)
    for rc in range(R*(C+1) + C+1):
        r = rc // (C+1)
        c = rc % (C+1)
        if r > R or c > C: continue

        for i in range(4):
            now_point = get_point(r, c, i)
            r_point = get_point(r+1, c, 0)
            c_point_plus = get_point(r, c+1, i+1)
            c_point_non = get_point(r, c+1, i)

            now = dp[now_point]
            val = grid[r*3001 + c]

            if i == 3:
                # 取らずに下
                dp[r_point] = max(now, dp[r_point])
                continue

            # 取って下
            dp[r_point] = max(now + val, dp[r_point])
            # 取らずに下
            dp[r_point] = max(now, dp[r_point])
            # 取って横
            dp[c_point_plus] = max(now + val, dp[c_point_plus])
            # 取らずに横
            dp[c_point_non] = max(now, dp[c_point_non])

    dp_RC = [dp[get_point(R, C, 0) + i] for i in range(4)]
    print(max(dp_RC))


if __name__ == "__main__":
    main()


Fixed submission:
import sys
import math
from collections import defaultdict
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid_int(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    R, C, K = NMI()
    grid = make_grid_int(R, C, 0)
    for i in range(K):
        r, c, v = NMI()
        grid[r-1][c-1] = v

    dp0 = [[0 for _ in range(C + 2)] for _ in range(R + 2)]
    dp1 = [[0 for _ in range(C + 2)] for _ in range(R + 2)]
    dp2 = [[0 for _ in range(C + 2)] for _ in range(R + 2)]
    dp3 = [[0 for _ in range(C + 2)] for _ in range(R + 2)]

    for r in range(R+1):
        for c in range(C+1):
            now0 = dp0[r][c]
            now1 = dp1[r][c]
            now2 = dp2[r][c]
            now3 = dp3[r][c]
            try:
                val = grid[r][c]
            except:
                val = 0

            dp0[r+1][c] = max(now3, dp0[r+1][c])

            # 取って下
            dp0[r+1][c] = max(now0 + val, now1 + val, now2 + val, dp0[r+1][c])
            # 取らずに下
            dp0[r+1][c] = max(now0, now1, now2, now3, dp0[r+1][c])
            # 取って横
            dp1[r][c+1] = max(now0 + val, dp1[r][c+1])
            dp2[r][c+1] = max(now1 + val, dp2[r][c+1])
            dp3[r][c+1] = max(now2 + val, dp3[r][c+1])

            # 取らずに横
            dp1[r][c+1] = max(now1, dp1[r][c+1])
            dp2[r][c+1] = max(now2, dp2[r][c+1])
            dp0[r][c+1] = max(now0, dp0[r][c+1])

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


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
import math
from collections import defaultdict
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid_int(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    R, C, K = NMI()
    grid = make_grid_int(R, C, 0)
    for i in range(K):
        r, c, v = NMI()
        grid[r-1][c-1] = v

    dp0 = [[0 for _ in range(C + 2)] for _ in range(R + 2)]
    dp1 = [[0 for _ in range(C + 2)] for _ in range(R + 2)]
    dp2 = [[0 for _ in range(C + 2)] for _ in range(R + 2)]
    dp3 = [[0 for _ in range(C + 2)] for _ in range(R + 2)]

    for r in range(R+1):
        for c in range(C+1):
            for i in range(4):
                now0 = dp0[r][c]
                now1 = dp1[r][c]
                now2 = dp2[r][c]
                now3 = dp3[r][c]
                try:
                    val = grid[r][c]
                except:
                    val = 0

                dp0[r+1][c] = max(now3, dp0[r+1][c])

                # 取って下
                dp0[r+1][c] = max(now0 + val, now1 + val, now2 + val, dp0[r+1][c])
                # 取らずに下
                dp0[r+1][c] = max(now0, now1, now2, now3, dp0[r+1][c])
                # 取って横
                dp1[r][c+1] = max(now0 + val, dp1[r][c+1])
                dp2[r][c+1] = max(now1 + val, dp2[r][c+1])
                dp3[r][c+1] = max(now2 + val, dp3[r][c+1])

                # 取らずに横
                dp1[r][c+1] = max(now1, dp1[r][c+1])
                dp2[r][c+1] = max(now2, dp2[r][c+1])
                dp0[r][c+1] = max(now0, dp0[r][c+1])

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


if __name__ == "__main__":
    main()


Fixed submission:
import sys
import math
from collections import defaultdict
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid_int(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    R, C, K = NMI()
    grid = make_grid_int(R, C, 0)
    for i in range(K):
        r, c, v = NMI()
        grid[r-1][c-1] = v

    dp0 = [[0 for _ in range(C + 2)] for _ in range(R + 2)]
    dp1 = [[0 for _ in range(C + 2)] for _ in range(R + 2)]
    dp2 = [[0 for _ in range(C + 2)] for _ in range(R + 2)]
    dp3 = [[0 for _ in range(C + 2)] for _ in range(R + 2)]

    for r in range(R+1):
        for c in range(C+1):
            now0 = dp0[r][c]
            now1 = dp1[r][c]
            now2 = dp2[r][c]
            now3 = dp3[r][c]
            try:
                val = grid[r][c]
            except:
                val = 0

            dp0[r+1][c] = max(now3, dp0[r+1][c])

            # 取って下
            dp0[r+1][c] = max(now0 + val, now1 + val, now2 + val, dp0[r+1][c])
            # 取らずに下
            dp0[r+1][c] = max(now0, now1, now2, now3, dp0[r+1][c])
            # 取って横
            dp1[r][c+1] = max(now0 + val, dp1[r][c+1])
            dp2[r][c+1] = max(now1 + val, dp2[r][c+1])
            dp3[r][c+1] = max(now2 + val, dp3[r][c+1])

            # 取らずに横
            dp1[r][c+1] = max(now1, dp1[r][c+1])
            dp2[r][c+1] = max(now2, dp2[r][c+1])
            dp0[r][c+1] = max(now0, dp0[r][c+1])

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


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
import math
from collections import defaultdict
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid_int(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    R, C, K = NMI()
    grid = defaultdict(int)
    data = [NMI() for _ in range(K)]
    for r, c, v in data:
        grid[(r-1)*3001 + c-1] = v

    # dp = [[[0]*4 for _ in range(C+2)] for _ in range(R+2)]
    # (r, c, i) -> r * 10**8 + c * 10**4 + i
    def get_point(r, c, i):
        return r * 30010 + c * 10 + i

    dp = defaultdict(int)
    for rc in range(R*(C+1) + C+1):
        r = rc // (C+1)
        c = rc % (C+1)
        if r > R or c > C: continue

        for i in range(4):
            now_point = get_point(r, c, i)
            r_point = get_point(r+1, c, 0)
            c_point_plus = get_point(r, c+1, i+1)
            c_point_non = get_point(r, c+1, i)

            now = dp[now_point]
            val = grid[r*3001 + c]

            if i == 3:
                # 取らずに下
                dp[r_point] = max(now, dp[r_point])
                continue

            # 取って下
            dp[r_point] = max(now + val, dp[r_point])
            # 取らずに下
            dp[r_point] = max(now, dp[r_point])
            # 取って横
            dp[c_point_plus] = max(now + val, dp[c_point_plus])
            # 取らずに横
            dp[c_point_non] = max(now, dp[c_point_non])

    dp_RC = [dp[get_point(R, C, 0) + i] for i in range(4)]
    print(max(dp_RC))


if __name__ == "__main__":
    main()

Fixed submission:
import sys
import math
from collections import defaultdict
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid_int(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    R, C, K = NMI()
    grid = make_grid_int(R, C, 0)
    for i in range(K):
        r, c, v = NMI()
        grid[r-1][c-1] = v

    dp0 = [[0 for _ in range(C + 2)] for _ in range(R + 2)]
    dp1 = [[0 for _ in range(C + 2)] for _ in range(R + 2)]
    dp2 = [[0 for _ in range(C + 2)] for _ in range(R + 2)]
    dp3 = [[0 for _ in range(C + 2)] for _ in range(R + 2)]

    for r in range(R+1):
        for c in range(C+1):
            now0 = dp0[r][c]
            now1 = dp1[r][c]
            now2 = dp2[r][c]
            now3 = dp3[r][c]
            try:
                val = grid[r][c]
            except:
                val = 0

            dp0[r+1][c] = max(now3, dp0[r+1][c])

            # 取って下
            dp0[r+1][c] = max(now0 + val, now1 + val, now2 + val, dp0[r+1][c])
            # 取らずに下
            dp0[r+1][c] = max(now0, now1, now2, now3, dp0[r+1][c])
            # 取って横
            dp1[r][c+1] = max(now0 + val, dp1[r][c+1])
            dp2[r][c+1] = max(now1 + val, dp2[r][c+1])
            dp3[r][c+1] = max(now2 + val, dp3[r][c+1])

            # 取らずに横
            dp1[r][c+1] = max(now1, dp1[r][c+1])
            dp2[r][c+1] = max(now2, dp2[r][c+1])
            dp0[r][c+1] = max(now0, dp0[r][c+1])

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


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
import math
from collections import defaultdict
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid_int(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    R, C, K = NMI()
    grid = defaultdict(int)
    data = [NMI() for _ in range(K)]
    for r, c, v in data:
        grid[(r-1)*3001 + c-1] = v

    # dp = [[[0]*4 for _ in range(C+2)] for _ in range(R+2)]
    # (r, c, i) -> r * 10**8 + c * 10**4 + i
    def get_point(r, c, i):
        return r * 30010 + c * 10 + i

    dp = defaultdict(int)
    for rc in range(R*3001 + C+1):
        r = rc // 3001
        c = rc % 3001
        if r > R or c > C: continue

        for i in range(4):
            now_point = get_point(r, c, i)
            r_point = get_point(r+1, c, 0)
            c_point_plus = get_point(r, c+1, i+1)
            c_point_non = get_point(r, c+1, i)

            now = dp[now_point]
            val = grid[r*3001 + c]

            if i == 3:
                # 取らずに下
                dp[r_point] = max(now, dp[r_point])
                continue

            # 取って下
            dp[r_point] = max(now + val, dp[r_point])
            # 取らずに下
            dp[r_point] = max(now, dp[r_point])
            # 取って横
            dp[c_point_plus] = max(now + val, dp[c_point_plus])
            # 取らずに横
            dp[c_point_non] = max(now, dp[c_point_non])

    dp_RC = [dp[get_point(R, C, 0) + i] for i in range(4)]
    print(max(dp_RC))


if __name__ == "__main__":
    main()

Fixed submission:
import sys
import math
from collections import defaultdict
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid_int(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    R, C, K = NMI()
    grid = make_grid_int(R, C, 0)
    for i in range(K):
        r, c, v = NMI()
        grid[r-1][c-1] = v

    dp0 = [[0 for _ in range(C + 2)] for _ in range(R + 2)]
    dp1 = [[0 for _ in range(C + 2)] for _ in range(R + 2)]
    dp2 = [[0 for _ in range(C + 2)] for _ in range(R + 2)]
    dp3 = [[0 for _ in range(C + 2)] for _ in range(R + 2)]

    for r in range(R+1):
        for c in range(C+1):
            now0 = dp0[r][c]
            now1 = dp1[r][c]
            now2 = dp2[r][c]
            now3 = dp3[r][c]
            try:
                val = grid[r][c]
            except:
                val = 0

            dp0[r+1][c] = max(now3, dp0[r+1][c])

            # 取って下
            dp0[r+1][c] = max(now0 + val, now1 + val, now2 + val, dp0[r+1][c])
            # 取らずに下
            dp0[r+1][c] = max(now0, now1, now2, now3, dp0[r+1][c])
            # 取って横
            dp1[r][c+1] = max(now0 + val, dp1[r][c+1])
            dp2[r][c+1] = max(now1 + val, dp2[r][c+1])
            dp3[r][c+1] = max(now2 + val, dp3[r][c+1])

            # 取らずに横
            dp1[r][c+1] = max(now1, dp1[r][c+1])
            dp2[r][c+1] = max(now2, dp2[r][c+1])
            dp0[r][c+1] = max(now0, dp0[r][c+1])

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


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
import math
from collections import defaultdict
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid_int(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    R, C, K = NMI()
    grid = defaultdict(int)
    for i in range(K):
        r, c, v = NMI()
        grid[(r-1)*3001 + c-1] = v

    # dp = [[[0]*4 for _ in range(C+2)] for _ in range(R+2)]
    # (r, c, i) -> r * 10**8 + c * 10**4 + i
    def get_point(r, c, i):
        return r * 30010 + c * 10 + i

    dp = defaultdict(int)
    for rc in range(R*3001 + C+1):
        r = rc // 3001
        c = rc % 3001
        if r > R or c > C: continue

        for i in range(4):
            now_point = get_point(r, c, i)
            r_point = get_point(r+1, c, 0)
            c_point_plus = get_point(r, c+1, i+1)
            c_point_non = get_point(r, c+1, i)

            now = dp[now_point]
            val = grid[r*3001 + c]

            if i == 3:
                # 取らずに下
                dp[r_point] = max(now, dp[r_point])
                continue

            # 取って下
            dp[r_point] = max(now + val, dp[r_point])
            # 取らずに下
            dp[r_point] = max(now, dp[r_point])
            # 取って横
            dp[c_point_plus] = max(now + val, dp[c_point_plus])
            # 取らずに横
            dp[c_point_non] = max(now, dp[c_point_non])

    dp_RC = [dp[get_point(R, C, 0) + i] for i in range(4)]
    print(max(dp_RC))


if __name__ == "__main__":
    main()

Fixed submission:
import sys
import math
from collections import defaultdict
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid_int(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    R, C, K = NMI()
    grid = make_grid_int(R, C, 0)
    for i in range(K):
        r, c, v = NMI()
        grid[r-1][c-1] = v

    dp0 = [[0 for _ in range(C + 2)] for _ in range(R + 2)]
    dp1 = [[0 for _ in range(C + 2)] for _ in range(R + 2)]
    dp2 = [[0 for _ in range(C + 2)] for _ in range(R + 2)]
    dp3 = [[0 for _ in range(C + 2)] for _ in range(R + 2)]

    for r in range(R+1):
        for c in range(C+1):
            now0 = dp0[r][c]
            now1 = dp1[r][c]
            now2 = dp2[r][c]
            now3 = dp3[r][c]
            try:
                val = grid[r][c]
            except:
                val = 0

            dp0[r+1][c] = max(now3, dp0[r+1][c])

            # 取って下
            dp0[r+1][c] = max(now0 + val, now1 + val, now2 + val, dp0[r+1][c])
            # 取らずに下
            dp0[r+1][c] = max(now0, now1, now2, now3, dp0[r+1][c])
            # 取って横
            dp1[r][c+1] = max(now0 + val, dp1[r][c+1])
            dp2[r][c+1] = max(now1 + val, dp2[r][c+1])
            dp3[r][c+1] = max(now2 + val, dp3[r][c+1])

            # 取らずに横
            dp1[r][c+1] = max(now1, dp1[r][c+1])
            dp2[r][c+1] = max(now2, dp2[r][c+1])
            dp0[r][c+1] = max(now0, dp0[r][c+1])

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


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
import math
from collections import defaultdict
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid_int(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    R, C, K = NMI()
    grid = defaultdict(int)
    for i in range(K):
        r, c, v = NMI()
        grid[(r-1)*3001 + c-1] = v

    # dp = [[[0]*4 for _ in range(C+2)] for _ in range(R+2)]
    # (r, c, i) -> r * 10**8 + c * 10**4 + i
    def get_point(r, c, i):
        return r * 30010 + c * 10 + i

    dp = defaultdict(int)
    for rc in range(R*3001 + C+1):
        r = rc // 3001
        c = rc % 3001
        if r > R or c > C: continue

        for i in range(4):
            now_point = get_point(r, c, i)
            r_point = get_point(r+1, c, 0)
            c_point_plus = get_point(r, c+1, i+1)
            c_point_non = get_point(r, c+1, i)

            now = dp[now_point]
            val = grid[r*3001 + c]

            if i == 3:
                # 取らずに下
                dp[r_point] = max(now, dp[r_point])
                continue

            # 取って下
            dp[r_point] = max(now + val, dp[r_point])
            # 取らずに下
            dp[r_point] = max(now, dp[r_point])
            # 取って横
            dp[c_point_plus] = max(now + val, dp[c_point_plus])
            # 取らずに横
            dp[c_point_non] = max(now, dp[c_point_non])

    dp_RC = [dp[get_point(R, C, 0) + i] for i in range(4)]
    print(max(dp_RC))


if __name__ == "__main__":
    main()

Fixed submission:
import sys
import math
from collections import defaultdict
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid_int(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    R, C, K = NMI()
    grid = make_grid_int(R, C, 0)
    for i in range(K):
        r, c, v = NMI()
        grid[r-1][c-1] = v

    dp0 = [[0 for _ in range(C + 2)] for _ in range(R + 2)]
    dp1 = [[0 for _ in range(C + 2)] for _ in range(R + 2)]
    dp2 = [[0 for _ in range(C + 2)] for _ in range(R + 2)]
    dp3 = [[0 for _ in range(C + 2)] for _ in range(R + 2)]

    for r in range(R+1):
        for c in range(C+1):
            now0 = dp0[r][c]
            now1 = dp1[r][c]
            now2 = dp2[r][c]
            now3 = dp3[r][c]
            try:
                val = grid[r][c]
            except:
                val = 0

            dp0[r+1][c] = max(now3, dp0[r+1][c])

            # 取って下
            dp0[r+1][c] = max(now0 + val, now1 + val, now2 + val, dp0[r+1][c])
            # 取らずに下
            dp0[r+1][c] = max(now0, now1, now2, now3, dp0[r+1][c])
            # 取って横
            dp1[r][c+1] = max(now0 + val, dp1[r][c+1])
            dp2[r][c+1] = max(now1 + val, dp2[r][c+1])
            dp3[r][c+1] = max(now2 + val, dp3[r][c+1])

            # 取らずに横
            dp1[r][c+1] = max(now1, dp1[r][c+1])
            dp2[r][c+1] = max(now2, dp2[r][c+1])
            dp0[r][c+1] = max(now0, dp0[r][c+1])

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


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
import math
from collections import defaultdict
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid_int(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    R, C, K = NMI()
    grid = defaultdict(int)
    for i in range(K):
        r, c, v = NMI()
        grid[(r-1)*3001 + c-1] = v

    # dp = [[[0]*4 for _ in range(C+2)] for _ in range(R+2)]
    # (r, c, i) -> r * 10**8 + c * 10**4 + i
    def get_point(r, c, i):
        return r * 3001**2 + c * 3001 + i

    dp = defaultdict(int)
    for r in range(R+1):
        for c in range(C+1):
            for i in range(4):
                now_point = get_point(r, c, i)
                r_point = get_point(r+1, c, 0)
                c_point_plus = get_point(r, c+1, i+1)
                c_point_non = get_point(r, c+1, i)

                now = dp[now_point]
                val = grid[r*3001 + c]

                if i == 3:
                    # 取らずに下
                    dp[r_point] = max(now, dp[r_point])
                    continue

                # 取って下
                dp[r_point] = max(now + val, dp[r_point])
                # 取らずに下
                dp[r_point] = max(now, dp[r_point])
                # 取って横
                dp[c_point_plus] = max(now + val, dp[c_point_plus])
                # 取らずに横
                dp[c_point_non] = max(now, dp[c_point_non])

    dp_RC = [dp[get_point(R, C, 0) + i] for i in range(4)]
    print(max(dp_RC))


if __name__ == "__main__":
    main()

Fixed submission:
import sys
import math
from collections import defaultdict
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid_int(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    R, C, K = NMI()
    grid = make_grid_int(R, C, 0)
    for i in range(K):
        r, c, v = NMI()
        grid[r-1][c-1] = v

    dp0 = [[0 for _ in range(C + 2)] for _ in range(R + 2)]
    dp1 = [[0 for _ in range(C + 2)] for _ in range(R + 2)]
    dp2 = [[0 for _ in range(C + 2)] for _ in range(R + 2)]
    dp3 = [[0 for _ in range(C + 2)] for _ in range(R + 2)]

    for r in range(R+1):
        for c in range(C+1):
            now0 = dp0[r][c]
            now1 = dp1[r][c]
            now2 = dp2[r][c]
            now3 = dp3[r][c]
            try:
                val = grid[r][c]
            except:
                val = 0

            dp0[r+1][c] = max(now3, dp0[r+1][c])

            # 取って下
            dp0[r+1][c] = max(now0 + val, now1 + val, now2 + val, dp0[r+1][c])
            # 取らずに下
            dp0[r+1][c] = max(now0, now1, now2, now3, dp0[r+1][c])
            # 取って横
            dp1[r][c+1] = max(now0 + val, dp1[r][c+1])
            dp2[r][c+1] = max(now1 + val, dp2[r][c+1])
            dp3[r][c+1] = max(now2 + val, dp3[r][c+1])

            # 取らずに横
            dp1[r][c+1] = max(now1, dp1[r][c+1])
            dp2[r][c+1] = max(now2, dp2[r][c+1])
            dp0[r][c+1] = max(now0, dp0[r][c+1])

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


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
import math
from collections import defaultdict
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid_int(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    R, C, K = NMI()
    grid = defaultdict(int)
    for i in range(K):
        r, c, v = NMI()
        grid[(r-1)*3001 + c-1] = v

    # dp = [[[0]*4 for _ in range(C+2)] for _ in range(R+2)]
    # (r, c, i) -> r * 10**8 + c * 10**4 + i
    def get_point(r, c, i):
        return r * 3001**2 + c * 3001 + i

    dp = defaultdict(int)
    for r in range(R+1):
        for c in range(C+1):
            for i in range(4):
                now = dp[get_point(r, c, i)]
                val = grid[r*3001 + c]

                if i == 3:
                    # 取らずに下
                    dp[get_point(r+1, c, 0)] = max(now, dp[get_point(r+1, c, 0)])
                    continue

                # 取って下
                dp[get_point(r+1, c, 0)] = max(now + val, dp[get_point(r+1, c, 0)])
                # 取らずに下
                dp[get_point(r+1, c, 0)] = max(now, dp[get_point(r+1, c, 0)])
                # 取って横
                dp[get_point(r, c+1, i+1)] = max(now + val, dp[get_point(r, c+1, i+1)])
                # 取らずに横
                dp[get_point(r, c+1, i)] = max(now, dp[get_point(r, c+1, i)])

    dp_RC = [dp[get_point(R, C, i)] for i in range(4)]
    print(max(dp_RC))


if __name__ == "__main__":
    main()

Fixed submission:
import sys
import math
from collections import defaultdict
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid_int(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    R, C, K = NMI()
    grid = make_grid_int(R, C, 0)
    for i in range(K):
        r, c, v = NMI()
        grid[r-1][c-1] = v

    dp0 = [[0 for _ in range(C + 2)] for _ in range(R + 2)]
    dp1 = [[0 for _ in range(C + 2)] for _ in range(R + 2)]
    dp2 = [[0 for _ in range(C + 2)] for _ in range(R + 2)]
    dp3 = [[0 for _ in range(C + 2)] for _ in range(R + 2)]

    for r in range(R+1):
        for c in range(C+1):
            now0 = dp0[r][c]
            now1 = dp1[r][c]
            now2 = dp2[r][c]
            now3 = dp3[r][c]
            try:
                val = grid[r][c]
            except:
                val = 0

            dp0[r+1][c] = max(now3, dp0[r+1][c])

            # 取って下
            dp0[r+1][c] = max(now0 + val, now1 + val, now2 + val, dp0[r+1][c])
            # 取らずに下
            dp0[r+1][c] = max(now0, now1, now2, now3, dp0[r+1][c])
            # 取って横
            dp1[r][c+1] = max(now0 + val, dp1[r][c+1])
            dp2[r][c+1] = max(now1 + val, dp2[r][c+1])
            dp3[r][c+1] = max(now2 + val, dp3[r][c+1])

            # 取らずに横
            dp1[r][c+1] = max(now1, dp1[r][c+1])
            dp2[r][c+1] = max(now2, dp2[r][c+1])
            dp0[r][c+1] = max(now0, dp0[r][c+1])

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


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
import math
from collections import defaultdict
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid_int(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    R, C, K = NMI()
    grid = defaultdict(int)
    for i in range(K):
        r, c, v = NMI()
        grid[(r-1)*10**4 + c-1] = v

    # dp = [[[0]*4 for _ in range(C+2)] for _ in range(R+2)]
    # (r, c, i) -> r * 10**8 + c * 10**4 + i
    def get_point(r, c, i):
        return r * 10**8 + c * 10**4 + i

    dp = defaultdict(int)
    for r in range(R+1):
        for c in range(C+1):
            for i in range(4):
                now = dp[get_point(r, c, i)]
                val = grid[r*10**4 + c]

                if i == 3:
                    # 取らずに下
                    dp[get_point(r+1, c, 0)] = max(now, dp[get_point(r+1, c, 0)])
                    continue

                # 取って下
                dp[get_point(r+1, c, 0)] = max(now + val, dp[get_point(r+1, c, 0)])
                # 取らずに下
                dp[get_point(r+1, c, 0)] = max(now, dp[get_point(r+1, c, 0)])
                # 取って横
                dp[get_point(r, c+1, i+1)] = max(now + val, dp[get_point(r, c+1, i+1)])
                # 取らずに横
                dp[get_point(r, c+1, i)] = max(now, dp[get_point(r, c+1, i)])

    dp_RC = [dp[get_point(R, C, i)] for i in range(4)]
    print(max(dp_RC))


if __name__ == "__main__":
    main()

Fixed submission:
import sys
import math
from collections import defaultdict
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid_int(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    R, C, K = NMI()
    grid = make_grid_int(R, C, 0)
    for i in range(K):
        r, c, v = NMI()
        grid[r-1][c-1] = v

    dp0 = [[0 for _ in range(C + 2)] for _ in range(R + 2)]
    dp1 = [[0 for _ in range(C + 2)] for _ in range(R + 2)]
    dp2 = [[0 for _ in range(C + 2)] for _ in range(R + 2)]
    dp3 = [[0 for _ in range(C + 2)] for _ in range(R + 2)]

    for r in range(R+1):
        for c in range(C+1):
            now0 = dp0[r][c]
            now1 = dp1[r][c]
            now2 = dp2[r][c]
            now3 = dp3[r][c]
            try:
                val = grid[r][c]
            except:
                val = 0

            dp0[r+1][c] = max(now3, dp0[r+1][c])

            # 取って下
            dp0[r+1][c] = max(now0 + val, now1 + val, now2 + val, dp0[r+1][c])
            # 取らずに下
            dp0[r+1][c] = max(now0, now1, now2, now3, dp0[r+1][c])
            # 取って横
            dp1[r][c+1] = max(now0 + val, dp1[r][c+1])
            dp2[r][c+1] = max(now1 + val, dp2[r][c+1])
            dp3[r][c+1] = max(now2 + val, dp3[r][c+1])

            # 取らずに横
            dp1[r][c+1] = max(now1, dp1[r][c+1])
            dp2[r][c+1] = max(now2, dp2[r][c+1])
            dp0[r][c+1] = max(now0, dp0[r][c+1])

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


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
import math
from collections import defaultdict
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid_int(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    R, C, K = NMI()
    grid = defaultdict(int)
    for i in range(K):
        r, c, v = NMI()
        grid[(r-1, c-1)] = v

    # dp = [[[0]*4 for _ in range(C+2)] for _ in range(R+2)]
    # (r, c, i) -> r * 10**8 + c * 10**4 + i
    def get_point(r, c, i):
        return r * 10**8 + c * 10**4 + i

    dp = defaultdict(int)
    for r in range(R+1):
        for c in range(C+1):
            for i in range(4):
                point = r * 10**8 + c * 10**4 + i
                now = dp[point]
                val = grid[(r, c)]

                if i == 3:
                    # 取らずに下
                    dp[get_point(r+1, c, 0)] = max(now, dp[get_point(r+1, c, 0)])
                    continue

                # 取って下
                dp[get_point(r+1, c, 0)] = max(now + val, dp[get_point(r+1, c, 0)])
                # 取らずに下
                dp[get_point(r+1, c, 0)] = max(now, dp[get_point(r+1, c, 0)])
                # 取って横
                dp[get_point(r, c+1, i+1)] = max(now + val, dp[get_point(r, c+1, i+1)])
                # 取らずに横
                dp[get_point(r, c+1, i)] = max(now, dp[get_point(r, c+1, i)])

    dp_RC = [dp[get_point(R, C, i)] for i in range(4)]
    print(max(dp_RC))


if __name__ == "__main__":
    main()

Fixed submission:
import sys
import math
from collections import defaultdict
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid_int(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    R, C, K = NMI()
    grid = make_grid_int(R, C, 0)
    for i in range(K):
        r, c, v = NMI()
        grid[r-1][c-1] = v

    dp0 = [[0 for _ in range(C + 2)] for _ in range(R + 2)]
    dp1 = [[0 for _ in range(C + 2)] for _ in range(R + 2)]
    dp2 = [[0 for _ in range(C + 2)] for _ in range(R + 2)]
    dp3 = [[0 for _ in range(C + 2)] for _ in range(R + 2)]

    for r in range(R+1):
        for c in range(C+1):
            now0 = dp0[r][c]
            now1 = dp1[r][c]
            now2 = dp2[r][c]
            now3 = dp3[r][c]
            try:
                val = grid[r][c]
            except:
                val = 0

            dp0[r+1][c] = max(now3, dp0[r+1][c])

            # 取って下
            dp0[r+1][c] = max(now0 + val, now1 + val, now2 + val, dp0[r+1][c])
            # 取らずに下
            dp0[r+1][c] = max(now0, now1, now2, now3, dp0[r+1][c])
            # 取って横
            dp1[r][c+1] = max(now0 + val, dp1[r][c+1])
            dp2[r][c+1] = max(now1 + val, dp2[r][c+1])
            dp3[r][c+1] = max(now2 + val, dp3[r][c+1])

            # 取らずに横
            dp1[r][c+1] = max(now1, dp1[r][c+1])
            dp2[r][c+1] = max(now2, dp2[r][c+1])
            dp0[r][c+1] = max(now0, dp0[r][c+1])

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


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
import math
from collections import defaultdict
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid_int(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    R, C, K = NMI()
    grid = defaultdict(int)
    for i in range(K):
        r, c, v = NMI()
        grid[(r-1, c-1)] = v

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

    for r in range(R+1):
        for c in range(C+1):
            for i in range(4):
                now = dp[r][c][i]
                val = grid[(r, c)]

                if i == 3:
                    # 取らずに下
                    dp[r + 1][c][0] = max(now, dp[r + 1][c][0])
                    continue

                # 取って下
                dp[r+1][c][0] = max(now + val, dp[r+1][c][0])
                # 取らずに下
                dp[r+1][c][0] = max(now, dp[r+1][c][0])
                # 取って横
                dp[r][c+1][i+1] = max(now + val, dp[r][c+1][i+1])
                # 取らずに横
                dp[r][c+1][i] = max(now, dp[r][c+1][i])

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


if __name__ == "__main__":
    main()

Fixed submission:
import sys
import math
from collections import defaultdict
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid_int(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    R, C, K = NMI()
    grid = make_grid_int(R, C, 0)
    for i in range(K):
        r, c, v = NMI()
        grid[r-1][c-1] = v

    dp0 = [[0 for _ in range(C + 2)] for _ in range(R + 2)]
    dp1 = [[0 for _ in range(C + 2)] for _ in range(R + 2)]
    dp2 = [[0 for _ in range(C + 2)] for _ in range(R + 2)]
    dp3 = [[0 for _ in range(C + 2)] for _ in range(R + 2)]

    for r in range(R+1):
        for c in range(C+1):
            now0 = dp0[r][c]
            now1 = dp1[r][c]
            now2 = dp2[r][c]
            now3 = dp3[r][c]
            try:
                val = grid[r][c]
            except:
                val = 0

            dp0[r+1][c] = max(now3, dp0[r+1][c])

            # 取って下
            dp0[r+1][c] = max(now0 + val, now1 + val, now2 + val, dp0[r+1][c])
            # 取らずに下
            dp0[r+1][c] = max(now0, now1, now2, now3, dp0[r+1][c])
            # 取って横
            dp1[r][c+1] = max(now0 + val, dp1[r][c+1])
            dp2[r][c+1] = max(now1 + val, dp2[r][c+1])
            dp3[r][c+1] = max(now2 + val, dp3[r][c+1])

            # 取らずに横
            dp1[r][c+1] = max(now1, dp1[r][c+1])
            dp2[r][c+1] = max(now2, dp2[r][c+1])
            dp0[r][c+1] = max(now0, dp0[r][c+1])

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


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
import math
from collections import defaultdict
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid_int(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    R, C, K = NMI()
    grid = make_grid_int(R, C, 0)
    for i in range(K):
        r, c, v = NMI()
        grid[r-1][c-1] = v

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

    for r in range(R+1):
        for c in range(C+1):
            for i in range(4):
                now = dp[r][c][i]
                try:
                    val = grid[r][c]
                except:
                    val = 0

                if i == 3:
                    # 取らずに下
                    dp[r + 1][c][0] = max(now, dp[r + 1][c][0])
                    continue

                # 取って下
                dp[r+1][c][0] = max(now + val, dp[r+1][c][0])
                # 取らずに下
                dp[r+1][c][0] = max(now, dp[r+1][c][0])
                # 取って横
                dp[r][c+1][i+1] = max(now + val, dp[r][c+1][i+1])
                # 取らずに横
                dp[r][c+1][i] = max(now, dp[r][c+1][i])

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


if __name__ == "__main__":
    main()

Fixed submission:
import sys
import math
from collections import defaultdict
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid_int(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    R, C, K = NMI()
    grid = make_grid_int(R, C, 0)
    for i in range(K):
        r, c, v = NMI()
        grid[r-1][c-1] = v

    dp0 = [[0 for _ in range(C + 2)] for _ in range(R + 2)]
    dp1 = [[0 for _ in range(C + 2)] for _ in range(R + 2)]
    dp2 = [[0 for _ in range(C + 2)] for _ in range(R + 2)]
    dp3 = [[0 for _ in range(C + 2)] for _ in range(R + 2)]

    for r in range(R+1):
        for c in range(C+1):
            now0 = dp0[r][c]
            now1 = dp1[r][c]
            now2 = dp2[r][c]
            now3 = dp3[r][c]
            try:
                val = grid[r][c]
            except:
                val = 0

            dp0[r+1][c] = max(now3, dp0[r+1][c])

            # 取って下
            dp0[r+1][c] = max(now0 + val, now1 + val, now2 + val, dp0[r+1][c])
            # 取らずに下
            dp0[r+1][c] = max(now0, now1, now2, now3, dp0[r+1][c])
            # 取って横
            dp1[r][c+1] = max(now0 + val, dp1[r][c+1])
            dp2[r][c+1] = max(now1 + val, dp2[r][c+1])
            dp3[r][c+1] = max(now2 + val, dp3[r][c+1])

            # 取らずに横
            dp1[r][c+1] = max(now1, dp1[r][c+1])
            dp2[r][c+1] = max(now2, dp2[r][c+1])
            dp0[r][c+1] = max(now0, dp0[r][c+1])

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


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
import math
from collections import defaultdict
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid_int(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    R, C, K = NMI()
    grid = make_grid_int(R, C, 0)
    for i in range(K):
        r, c, v = NMI()
        grid[r-1][c-1] = v

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

    for r in range(R+1):
        for c in range(C+1):
            for i in range(4):
                now = dp[r][c][i]
                try:
                    val = grid[r][c]
                except:
                    val = 0

                if i == 3:
                    # 取らずに下
                    dp[r + 1][c][0] = max(now, dp[r + 1][c][0])
                    continue

                # 取って下
                dp[r+1][c][0] = max(now + val, dp[r+1][c][0])
                # 取らずに下
                dp[r+1][c][0] = max(now, dp[r+1][c][0])
                # 取って横
                dp[r][c+1][i+1] = max(now + val, dp[r][c+1][i+1])
                # 取らずに横
                dp[r][c+1][i] = max(now, dp[r][c+1][i])

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


if __name__ == "__main__":
    main()

Fixed submission:
import sys
import math
from collections import defaultdict
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid_int(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    R, C, K = NMI()
    grid = make_grid_int(R, C, 0)
    for i in range(K):
        r, c, v = NMI()
        grid[r-1][c-1] = v

    dp0 = [[0 for _ in range(C + 2)] for _ in range(R + 2)]
    dp1 = [[0 for _ in range(C + 2)] for _ in range(R + 2)]
    dp2 = [[0 for _ in range(C + 2)] for _ in range(R + 2)]
    dp3 = [[0 for _ in range(C + 2)] for _ in range(R + 2)]

    for r in range(R+1):
        for c in range(C+1):
            now0 = dp0[r][c]
            now1 = dp1[r][c]
            now2 = dp2[r][c]
            now3 = dp3[r][c]
            try:
                val = grid[r][c]
            except:
                val = 0

            dp0[r+1][c] = max(now3, dp0[r+1][c])

            # 取って下
            dp0[r+1][c] = max(now0 + val, now1 + val, now2 + val, dp0[r+1][c])
            # 取らずに下
            dp0[r+1][c] = max(now0, now1, now2, now3, dp0[r+1][c])
            # 取って横
            dp1[r][c+1] = max(now0 + val, dp1[r][c+1])
            dp2[r][c+1] = max(now1 + val, dp2[r][c+1])
            dp3[r][c+1] = max(now2 + val, dp3[r][c+1])

            # 取らずに横
            dp1[r][c+1] = max(now1, dp1[r][c+1])
            dp2[r][c+1] = max(now2, dp2[r][c+1])
            dp0[r][c+1] = max(now0, dp0[r][c+1])

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


if __name__ == "__main__":
    main()