Problem p03187 (python)

Fixed submission:
import sys
fin = sys.stdin.readline
sys.setrecursionlimit(5000000)
# from functools import lru_cache


def partial():
    L, N = [int(elem) for elem in fin().split()]
    X_list = [0]
    X_list.extend([int(fin()) for _ in range(N)])
    X_list.append(L)
    N += 2

    # this does not work in PyPy because of the slowness
    # memo = [[[None] * 2  for _ in range(N + 1)] for _ in range(N + 1)]

    # @lru_cache(None)
    # def rec(i, j, front):
    #     if memo[i][j][front] is not None:
    #         return memo[i][j][front]
    #     else:
    #         if i == j:
    #             max_dist = 0
    #         else:
    #             head = X_list[i]
    #             tail = X_list[j - 1]
    #             if front == 1:
    #                 k = X_list[i - 1]
    #                 max_dist = max(rec(i + 1, j, 1) + head - k, rec(i, j - 1, 0) + L + k - tail)
    #             else:
    #                 k = X_list[j]
    #                 max_dist =  max(rec(i + 1, j, 1) + L + head - k, rec(i, j - 1, 0) + k - tail)
    #         memo[i][j][front] = max_dist
    #         return max_dist
    # print(max(rec(1, N, 1) + X_list[0], rec(0, N - 1, 0) + L - X_list[-1]))


    # dp[i][j][k] = the longest possible total distance when the trees of X_list[i:j] are available
    # and **coming from k (k == 1 -> forward, otherwise backward)**
    dp = [[[0] * 2 for _ in range(N + 1)] for _ in range(N + 1)]

    for w in range(1, N + 1):
        for start in range(1, N - w):
            end = start + w
            dp[start][end][1] = max(dp[start + 1][end][1] + X_list[start] - X_list[start - 1],
                                    dp[start][end - 1][0] + L + X_list[start - 1] - X_list[end - 1])
            dp[start][end][0] = max(dp[start + 1][end][1] + L + X_list[start] - X_list[end],
                                    dp[start][end - 1][0] + X_list[end] - X_list[end - 1])

    return max(dp[1][N - 1])


def perfect():
    L, N = [int(elem) for elem in fin().split()]
    X_list = [int(fin()) for _ in range(N)]

    # compute the prefix and suffix sums of X_list
    prefix_sum_X = [0] * N
    suffix_reverse_sum_X = [0] * N
    cur_sum = 0
    for i, X in enumerate(X_list):
        cur_sum += X
        prefix_sum_X[i] = cur_sum
    cur_sum = 0
    for i in reversed(range(N)):
        cur_sum += L - X_list[i]
        suffix_reverse_sum_X[i] = cur_sum
    # edge cases: no turning
    max_dist = max(X_list[-1], L - X_list[0])
    # cases when firstly moving counter-clockwisely
    for i in range(N - 1):
        # case when turning at i
        stopping_idx = i + (N - i) // 2
        if (N - i - 1) % 2 == 0:
            dist = 2 * X_list[i] + (prefix_sum_X[stopping_idx] - prefix_sum_X[i]) * 2 \
                                 + (suffix_reverse_sum_X[stopping_idx + 1]) * 2 \
                                 - X_list[stopping_idx]
        else:
            dist = 2 * X_list[i] + (prefix_sum_X[stopping_idx - 1] - prefix_sum_X[i]) * 2 \
                                 + (suffix_reverse_sum_X[stopping_idx]) * 2 \
                                 - (L - X_list[stopping_idx])
        # print(dist)
        max_dist = max(max_dist, dist)
    
    # likewise consider cases when clockwisely starting
    for i in range(1, N):
        stopping_idx = (N - i) // 2
        if (N - i) % 2 == 1:
            dist = 2 * (L - X_list[N - i]) + (suffix_reverse_sum_X[stopping_idx + 1] - suffix_reverse_sum_X[N - i]) * 2 \
                                           + prefix_sum_X[stopping_idx] * 2 \
                                           - X_list[stopping_idx]
        else:
            dist = 2 * (L - X_list[N - i]) + (suffix_reverse_sum_X[stopping_idx] - suffix_reverse_sum_X[N - i]) * 2 \
                                           + prefix_sum_X[stopping_idx - 1] * 2 \
                                           - (L - X_list[stopping_idx])
        # print(dist)
        max_dist = max(max_dist, dist)
    return max_dist


print(perfect())

Buggy submission (verdict: Runtime Error):
import sys
fin = sys.stdin.readline
from queue import deque
from functools import lru_cache
import pdb

L, N = [int(elem) for elem in fin().split()]
X_list = [int(fin()) for _ in range(N)]

@lru_cache(None)
def rec(i, j, k):
    if i == j:
        return 0
    else:
        head = X_list[i]
        tail = X_list[j - 1]
        if head > k:
            max_dist = max(rec(i + 1, j, head) + head - k, rec(i, j - 1, tail) + L + k - tail)
        else:
            max_dist =  max(rec(i + 1, j, head) + L + head - k, rec(i, j - 1, tail) + k - tail)
        # print(i, j, k, max_dist)
        return max_dist
print(max(rec(1, N, X_list[0]) + X_list[0], rec(0, N - 1, X_list[-1]) + L - X_list[-1]))