Problem:


Score : 800 points

Problem Statement

Takahashi Lake has a perimeter of L. On the circumference of the lake, there is a residence of the lake's owner, Takahashi.
Each point on the circumference of the lake has a coordinate between 0 and L (including 0 but not L), which is the distance from the Takahashi's residence, measured counter-clockwise.

There are N trees around the lake; the coordinate of the i-th tree is X_i. There is no tree at coordinate 0, the location of Takahashi's residence.

Starting at his residence, Takahashi will repeat the following action:

If all trees are burnt, terminate the process.

Specify a direction: clockwise or counter-clockwise.

Walk around the lake in the specified direction, until the coordinate of a tree that is not yet burnt is reached for the first time.

When the coordinate with the tree is reached, burn that tree, stay at the position and go back to the first step.

Find the longest possible total distance Takahashi walks during the process.

Partial Score

A partial score can be obtained in this problem:

300 points will be awarded for passing the input satisfying N \leq 2000.

Constraints

2 \leq L \leq 10^9

1 \leq N \leq 2\times 10^5

1 \leq X_1 < ... < X_N \leq L-1

All values in input are integers.

Input

Input is given from Standard Input in the following format:

L N
X_1
:
X_N

Output

Print the longest possible total distance Takahashi walks during the process.

Sample Input 1

10 3
2
7
9

Sample Output 1

15

Takahashi walks the distance of 15 if the process goes as follows:

Walk a distance of 2 counter-clockwise, burn the tree at the coordinate 2 and stay there.

Walk a distance of 5 counter-clockwise, burn the tree at the coordinate 7 and stay there.

Walk a distance of 8 clockwise, burn the tree at the coordinate 9 and stay there.

Sample Input 2

10 6
1
2
3
6
7
9

Sample Output 2

27

Sample Input 3

314159265 7
21662711
77271666
89022761
156626166
160332356
166902656
298992265

Sample Output 3

1204124749



Sample input:
10 3
2
7
9


Sample output:
15

Submission status: Runtime Error

Solution code:
l,n = map(int,input().strip().split(" "))
left = 0
right = n-1
now = 0
X = []
ans = 0
lr = 0

for i in range(n):
    x=int(input())
    X.append(x)

while left<=right:
    if lr==0:
        toLeft = X[left]-now
        toRight = l-X[right]+now
        toLeft2 = X[left+1]-now
        toRight2 = l-X[right-1]+now
    else:
        toLeft = l-now+X[left]
        toRight = now-X[right]
        toLeft2 = l-now+X[left+1]
        toRight2 = now-X[right-1]

    if toLeft2 > toRight2:
        ans += toLeft
        now = X[left]
        left += 1
        lr = 0
    elif toLeft == toRight:
        if X[left+1]-X[left]>X[right]-X[right-1]:
            ans += toLeft
            now = X[left]
            left += 1
            lr = 0
        else:
            ans += toRight
            now=X[right]
            right -= 1
            lr = 1
    else:
        ans += toRight
        now=X[right]
        right -= 1
        lr = 1

print(ans)

Submission status: Runtime Error

Solution code:
#coding:utf-8

L, N = list(map(int, input().split()))

X = []

for i in range(N):
    X.append(int(input()))
    
def recur(now, coord_list, dist, max_dist):
    if len(coord_list) == 0:
        return dist
    else:
        left = coord_list[0]
        d = left-now
        left_max = recur(left, coord_list[1:], dist + d if d>0 else dist+(L + d), max_dist)
    
        right = coord_list[-1]
        d = now - right
        right_max = recur(right, coord_list[:-1], dist+d if d>0 else dist+(L+d), max_dist)
        return max(left_max, right_max)

print(recur(0, X, 0, 0))

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
l,n = input().split()
l = int(l)
n = int(n)
x = [int(input()) for i in range(n)]
def search(x,y,sum,list):
    if x == []:
        list.append(sum)
    else:
        newy1 = x[0]
        newy2 = x[-1]
        if newy1 - y > 0:
            dist1 = newy1 - y
        else:
            dist1 = l + newy1- y
        if y - newy2 > 0:
            dist2 = y - newy2
        else:
            dist2 = l + y - newy2
        if dist1 > dist2:
            x = x[1:]
            sum += dist1
            search(x,newy1,sum,list)
        elif dist1 < dist2:
            x = x[:-1]
            sum += dist2
            search(x,newy2,sum,list)
        else:
            x1 = x[1:]
            sum1 = sum + dist1
            search(x1,newy1,sum1,list)
            x2 = x[:-1]
            sum2 = sum + dist2
            search(x2,newy2,sum2,list)
list = []
search(x,0,0,list)
list.sort()
print(list[-1])

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

L,N=map(int,input().split())
X=[0]+[int(input()) for i in range(N)]

def LENG(a,b,start):
    if b==0:
        if start>a:
            return a
        else:
            return L-a

    if a>b:
        a,b=b,a

    return a+L-b


CANDI=[(N+1)//2,(N+1)//2-1,(N+1)//2+1]
#(i+2)//2*(-1)**i

ANS=0
for start in CANDI:
    if start==0:
        continue

    s=start
    t=(s+(-1)**0)%(N+1)
    ANS1=0


    
    for i in range(2,N+3):
        ANS1+=LENG(X[s],X[t],X[start])
        #print(s,t,i,ANS1)
        
        s,t=t,(t-i*((-1)**i))%(N+1)

        

        if s==0:
            break
    #print(ANS1)

    s=start
    t=(s-(-1)**0)%(N+1)
    ANS2=0
    for i in range(2,N+3):
        ANS2+=LENG(X[s],X[t],X[start])
        #print(s,t,i,ANS2)
        s,t=t,(t+i*((-1)**i))%(N+1)

        if s==0:
            break
    #print(ANS2)

    ANS=max(ANS,ANS1,ANS2)

print(ANS)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
l,n = input().split()
l = int(l)
n = int(n)
x = [int(input()) for i in range(n)]
def search(x,y,sum,list):
    if x == []:
        list.append(sum)
    else:
        newy1 = x[0]
        newy2 = x[-1]
        print(sum)
        if newy1 - y > 0:
            dist1 = newy1 - y
        else:
            dist1 = l + newy1- y
        if y - newy2 > 0:
            dist2 = y - newy2
        else:
            dist2 = l + y - newy2
        print(dist1,dist2)
        if dist1 > dist2:
            x = x[1:]
            sum += dist1
            search(x,newy1,sum,list)
        elif dist1 < dist2:
            x = x[:-1]
            sum += dist2
            search(x,newy2,sum,list)
        else:
            x1 = x[1:]
            sum1 = sum + dist1
            search(x1,newy1,sum1,list)
            x2 = x[:-1]
            sum2 = sum + dist2
            search(x2,newy2,sum2,list)
list = []
search(x,0,0,list)
list.sort()
print(list[-1])

Submission status: Runtime Error

Solution code:
#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#

"""
agc 030 B
"""

from collections import deque
l, n = map(int, input().split())
xli = [int(input()) for i in range(n)]

deq = deque(xli)
ans1 = 0
pos = 0
for i in range(n):
    if i % 2 == 0:
        ne = deq.pop()
        ans1 += pos + l - ne
        pos = ne
    else:
        ne = deq.popleft()
        ans1 += ne + l - pos
        pos = ne

deq = deque(xli)
ne = deq.popleft()
ans2 = ne
pos = ne
for i in range(n-1):
    if i % 2 == 0:
        ne = deq.pop()
        ans2 += pos + l - ne
        pos = ne
    else:
        ne = deq.popleft()
        ans2 += ne + l - pos
        pos = ne

n = n-1

deq = deque(xli)
deq.pop()
ans3 = 0
pos = 0
for i in range(n):
    if i % 2 == 0:
        ne = deq.pop()
        ans3 += pos + l - ne
        pos = ne
    else:
        ne = deq.popleft()
        ans3 += ne + l - pos
        pos = ne

deq = deque(xli)
deq.pop()
ne = deq.popleft()
ans4 = ne
pos = ne
for i in range(n-1):
    if i % 2 == 0:
        ne = deq.pop()
        ans4 += pos + l - ne
        pos = ne
    else:
        ne = deq.popleft()
        ans4 += ne + l - pos
        pos = ne


deq = deque(xli)
deq.popleft()
ans5 = 0
pos = 0
for i in range(n):
    if i % 2 == 0:
        ne = deq.pop()
        ans5 += pos + l - ne
        pos = ne
    else:
        ne = deq.popleft()
        ans5 += ne + l - pos
        pos = ne

deq = deque(xli)
deq.popleft()
ne = deq.popleft()
ans6 = ne
pos = ne
for i in range(n-1):
    if i % 2 == 0:
        ne = deq.pop()
        ans6 += pos + l - ne
        pos = ne
    else:
        ne = deq.popleft()
        ans6 += ne + l - pos
        pos = ne



print(max(ans1, ans2, ans3, ans4, ans5, ans6))

Submission status: Runtime Error

Solution code:
l, n = map(int,input().split())
x = []
for i in range(n):
    x.append(int(input()))

ans = 0
temp = 0
def judge(a,b):
    if x[a+1] >= x[b-1]:
        return 0
    else:
        cw_temp = x[a+1] - x[a]
        acw_temp = x[b] - x[b-1]
        if cw_temp >acw_temp:
            return 0
        elif cw_temp < acw_temp:
            return -1
        else:
            judge(a+1, b-1)

while x:
    if temp <= x[0]:
        cw = x[0] - temp
        acw = temp + l - x[-1]
    else:
        cw = x[0] + l - temp
        acw = temp - x[-1]
    if cw > acw:
        ans += cw
        temp = x[0]
        del x[0]
    elif cw < acw:
        ans += acw
        temp = x[-1]
        del x[-1]
    else:
        jud = judge(0,-1)
        if jud == 0:
            ans += cw
            temp = x[0]
            del x[0]
        else:
            ans += acw
            temp = x[-1]
            del x[-1]

print(int(ans))

Submission status: Runtime Error

Solution code:
l,n = map(int,input().split())
list = [0 for i in range(l)]
for _ in range(n):
    list[int(input())] = 1
#print(list)
curr = 0
w = 0
for _ in range(n):
    pcurr = curr
    pw = 0
    while list[pcurr] == 0:
        pcurr += 1
        pw += 1
        if pcurr > len(list):
            pcurr = 0
        #print('pcu',pcurr)
    #list[pcurr] = 0
    #print('p',pcurr,pw)
    mcurr = curr
    mw = 0
    while list[mcurr] == 0:
        mcurr -= 1
        mw += 1
        if mcurr < 0:
            mcurr = len(list) - 1
        #print('mcu',mcurr)
    #list[mcurr] = 0
    #print('m',mcurr,mw)
    if pw >= mw:
        w += pw
        curr = pcurr
        #print('wp',pw,w,'curr',curr)
        list[curr] = 0
    else:
        w += mw
        curr = mcurr
        #print('wm',mw,w,'curr',curr)
        list[curr] = 0
print(w)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Dec 29 21:03:24 2018

@author: owner
"""

import copy
import sys

sys.setrecursionlimit=10**9

def makeLinkedList(arr):
    linkedList= {}
    N=len(arr)
    for i in range(N):
        linkedList[arr[i]]={'Left':arr[i-1], 'Right':arr[(i+1)%N]}
    return linkedList

def linkedListPop(linkedList, key):
    left=linkedList[key]['Left']
    right=linkedList[key]['Right']
    
    linkedList[left]['Right']=right
    linkedList[right]['Left']=left
    linkedList.pop(key)
    return len(linkedList)

def walk(linkedList, now, dist, L):
    left=linkedList[now]['Left']
    right=linkedList[now]['Right']
    
    listN=linkedListPop(linkedList,now)
    if listN==0:
        return dist
    
    distL=now-left
    distR=right-now
    if distL<0:
        distL+=L
    if distR<0:
        distR+=L

    if distL>distR:
        return walk(linkedList, left, dist+distL,L)
    elif distL<distR:
        return walk(linkedList, right, dist+distR,L)
    else:
        linkedList2=copy.deepcopy(linkedList)
        return max(walk(linkedList, left, dist+distL,L),walk(linkedList2, right, dist+distR,L))

L, N=list(map(int, input().split()))
arr=[0]+[int(input()) for _ in range(N)]
linkedList=makeLinkedList(arr)

ans=walk(linkedList,0,0,L)
print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Dec 29 21:03:24 2018

@author: owner
"""

import copy

def makeLinkedList(arr):
    linkedList= {}
    N=len(arr)
    for i in range(N):
        linkedList[arr[i]]={'Left':arr[i-1], 'Right':arr[(i+1)%N]}
    return linkedList

def linkedListPop(linkedList, key):
    left=linkedList[key]['Left']
    right=linkedList[key]['Right']
    
    linkedList[left]['Right']=right
    linkedList[right]['Left']=left
    linkedList.pop(key)
    return len(linkedList)

def walk(linkedList, now, dist, L):
    left=linkedList[now]['Left']
    right=linkedList[now]['Right']
    
    listN=linkedListPop(linkedList,now)
    if listN==0:
        return dist
    
    distL=now-left
    distR=right-now
    if distL<0:
        distL+=L
    if distR<0:
        distR+=L

    if distL>distR:
        return walk(linkedList, left, dist+distL,L)
    elif distL<distR:
        return walk(linkedList, right, dist+distR,L)
    else:
        linkedList2=copy.deepcopy(linkedList)
        return max(walk(linkedList, left, dist+distL,L),walk(linkedList2, right, dist+distR,L))

L, N=list(map(int, input().split()))
arr=[int(input()) for _ in range(N)]
arr+=[0]
arr=sorted(arr)

linkedList=makeLinkedList(arr)

ans=walk(linkedList,0,0,L)
print(ans)

Submission status: Runtime Error

Solution code:
Lakelen, n = map(int, input().split())
x = [int(input()) for _ in range(n)]
def dis(x,y):
    if x - y < 0:
        return x - y + Lakelen
    else: return x - y
def maxd(p,l,r):
    if l == r:
        return max(dis(p,x[r]),dis(x[r],p))
    return max(maxd(x[l],l+1,r) + dis(x[l],p),maxd(x[r],l,r-1) + dis(p,x[r]))
print(maxd(0,0,n-1))

Submission status: Runtime Error

Solution code:
l,n=map(int,input().split())
x=[[0]  for i in range(n)]
for i in range(n):
    x[i]=int(input())
    
current=0
current_nplus=0
current_nminus=n-1
d=0




for i in range(n-1):      
    d_plus=min(abs(x[current_nplus]-current),abs(l+current-x[current_nplus]))    
    d_minus=min(abs(x[current_nminus]-current),abs(l+current-x[current_nminus]))   
    

    
    
    if d_plus> d_minus:
        current=x[current_nplus]
        d+=d_plus
        current_n+=1
        current_nplus+=1

    else:
        current=x[current_nminus]
        d+=d_minus
        current_n+=-1
        current_nminus+=-1
    


d+=max(abs(x[current_nplus]-current),abs(l+current-x[current_nplus])) 
    
print(d)

Submission status: Runtime Error

Solution code:
L,N=(int(i) for i in input().split())
n = int(input())
X = []
for i in range(0,N):
    a = int(input())
    X.append(a)
result=0
if X[2/L.ceil()]<L/2:
  for i in range (1,L/2):
    for j in range (N,L/2,-1):
      result+=abs(X[j]-X[i])
else:
   for i in range (1,L/2):
    for j in range (N,L/2,-1):
      result+=abs(X[i]-X[j])
print(result)

Submission status: Runtime Error

Solution code:

length, tree_num = list(map(int, input().split()))
location = [int(input()) for i in range(tree_num)]

ans = 0

def sa(your_location, point, kaiten):
    global length
    if kaiten:
        if point > your_location:
            sasa = point - your_location
        else:
            sasa = length + point - your_location
    else:
        if point < your_location:
            sasa = your_location - point
        else:
            sasa = length + your_location - point
    return sasa



    if abs(your_location - point) < abs(length + min([your_location, point])  - max([your_location, point])):
        sasa =  abs(your_location - point)
    else:
        sasa = abs(length + min([your_location, point])  - max([your_location, point]))
    print(your_location, point, length, sasa)

    return sasa


def serch_next(index, arrive_flg):
    global tree_num
    for i in range(1, tree_num):
        if arrive_flg[index - i] == 0:
            pre_locate = index - i
            break
    for i in range(1, tree_num):
        if arrive_flg[(index + i) % tree_num] == 0:
            next_locate = index + i
            break
    return pre_locate, next_locate


def go_tree(index, now_location, sum_walk, arrive_flg_ori, kaiten, pre_kaiten):
    global length, location, tree_num, ans
    arrive_flg = arrive_flg_ori.copy()
    # print(ans)
    sum_walk += sa(now_location, location[index], kaiten)
    arrive_flg[index] = 1
    if all(arrive_flg):
        if sum_walk > ans:
            ans = sum_walk
        return
    pre_locate, next_locate = serch_next(index, arrive_flg)

    if kaiten == 0 and pre_kaiten == 0:
        go_tree(next_locate, location[index], sum_walk, arrive_flg, 1, kaiten)
    elif kaiten == 1 and pre_kaiten == 1:
        go_tree(pre_locate, location[index], sum_walk, arrive_flg, 0, kaiten)
    else:
        go_tree(pre_locate, location[index], sum_walk, arrive_flg, 0, kaiten)
        go_tree(next_locate, location[index], sum_walk, arrive_flg, 1, kaiten)



def main():
    global location, ans
    arrive_flg = [0 for i in range(tree_num)]

    go_tree(-1, 0, 0, arrive_flg, 0, 1)
    go_tree(0, 0, 0, arrive_flg, 1, 0)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    d, n = map(int, input().split())
    x = [int(input()) for _ in range(n)]

    print(solve(0, x, d))

def solve(pos, trees, d):
    if not trees:
        return 0

    a = distance_anticlockwise(pos, trees[0], d) + solve(trees[0], trees[1:], d)
    b = distance_clockwise(pos, trees[-1], d) + solve(trees[-1], trees[:-1], d)
    return max(a, b)

def distance_anticlockwise(a, b, d):
    if a < b:
        return b - a
    else:
        return d - a + b

def distance_clockwise(a, b, d):
    if a > b:
        return a - b
    else:
        return a + d - b

main()

Submission status: Runtime Error

Solution code:
L,N=(int(i) for i in input().split())
n = int(input())
X = [0 for i in range(0,N)]
for i in range(0,N):
    X[i] = int(input())
a=0
if X[2/L.ceil()]<L/2:
  for i in range (1,L/2):
    for j in range (N,L/2,-1):
      a+=abs(X[j]-X[i])
else:
   for i in range (1,L/2):
    for j in range (N,L/2,-1):
      a+=abs(X[i]-X[j])
 
print(a)

Submission status: Runtime Error

Solution code:
L, N = list(map(int, input().split()))
X = [int(input()) for i in range(N)]

ans = 0

begin = 0
end = L
used_begin = 0
used_end = 0

for _ in range(N):
    # print((X[used_begin]-begin), (begin+end-X[N-1-used_end]))
    if (X[used_begin]-begin) > (begin+end-X[N-1-used_end]):
        add = (X[used_begin]-begin)
        begin = X[used_begin]
        used_begin += 1
    elif (X[used_begin]-begin) < (begin+end-X[N-1-used_end]):
        add = begin+end-X[N-1-used_end]
        begin = X[N-1-used_end] - L
        used_end += 1
    else:
        if (X[used_begin + 1]-X[used_begin]) > (X[N-1-used_end] - X[N-2-used_end]):
            add = (X[used_begin]-begin)
            begin = X[used_begin]
            used_begin += 1
        else:
            add = begin+end-X[N-1-used_end]
            begin = X[N-1-used_end] - L
            used_end += 1
    ans += add
    # print(add)
    # print("===")

print(ans)

Submission status: Runtime Error

Solution code:

length, tree_num = list(map(int, input().split()))
location = [int(input()) for i in range(tree_num)]

ans = 0

def sa(your_location, point, kaiten):
    global length
    if kaiten:
        if point > your_location:
            sasa = point - your_location
        else:
            sasa = length + point - your_location
    else:
        if point < your_location:
            sasa = your_location - point
        else:
            sasa = length + your_location - point
    return sasa



    if abs(your_location - point) < abs(length + min([your_location, point])  - max([your_location, point])):
        sasa =  abs(your_location - point)
    else:
        sasa = abs(length + min([your_location, point])  - max([your_location, point]))
    print(your_location, point, length, sasa)

    return sasa


def serch_next(index, arrive_flg):
    global tree_num
    for i in range(1, tree_num):
        if arrive_flg[index - i] == 0:
            pre_locate = index - i
            break
    for i in range(1, tree_num):
        if arrive_flg[(index + i) % tree_num] == 0:
            next_locate = index + i
            break
    return pre_locate, next_locate


def go_tree(index, now_location, sum_walk, arrive_flg_ori, kaiten):
    global length, location, tree_num, ans
    arrive_flg = arrive_flg_ori.copy()
    # print(ans)
    sum_walk += sa(now_location, location[index], kaiten)
    arrive_flg[index] = 1
    if all(arrive_flg):
        if sum_walk > ans:
            ans = sum_walk
        return
    pre_locate, next_locate = serch_next(index, arrive_flg)
    go_tree(pre_locate, location[index], sum_walk, arrive_flg, 0)
    go_tree(next_locate, location[index], sum_walk, arrive_flg, 1)



def main():
    global location, ans
    arrive_flg = [0 for i in range(tree_num)]

    go_tree(-1, 0, 0, arrive_flg, 0)
    go_tree(0, 0, 0, arrive_flg, 1)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
[L, N] = list(map(int, input().split(' ')))

TreeList = []

for i in range(N):
    TreeList.append(int(input()))

maxLengthDict = {}

def maxLength(current, left, right):
    if current in maxLengthDict and left in maxLengthDict[current] and right in maxLengthDict[current][left]:
        return maxLengthDict[current][left][right]

    if left == right:
        if current not in maxLengthDict:
            maxLengthDict[current] = {}
        if left not in maxLengthDict[current]:
            maxLengthDict[current][left] = {}
        leftDist = (TreeList[left] - current) % L
        rightDist = (current - TreeList[right]) % L
        maxLengthDict[current][left][right] = max(leftDist, rightDist)
        return maxLengthDict[current][left][right]

    leftDist = (TreeList[left] - current) % L
    rightDist = (current - TreeList[right]) % L
    if current not in maxLengthDict:
        maxLengthDict[current] = {}
    if left not in maxLengthDict[current]:
        maxLengthDict[current][left] = {}
    maxLengthDict[current][left][right] = max(leftDist + maxLength(TreeList[left], left+1, right), rightDist + maxLength(TreeList[right], left, right-1))
    return maxLengthDict[current][left][right]

left = 0
right = N-1
current = 0

ret = maxLength(current, left, right)

print(ret)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
l,n = input().split()
l = int(l)
n = int(n)
x = [int(input()) for i in range(n)]
def search(x,y,c,sum,list):
    if x == []:
        list.append(sum)
    else:
        if c == 0:
            newy = x[0]
            x = x[1:]
            if newy - y > 0:
                sum += (newy - y)
            else:
                sum += (l + newy - y)
        else:
            newy = x[-1]
            x = x[:-1]
            if y - newy > 0:
                sum += (y - newy)
            else:
                sum += (l + y - newy)
        search(x,newy,0,sum,list)
        search(x,newy,1,sum,list)
list = []
search(x,0,0,0,list)
search(x,0,1,0,list)
list.sort()
print(list[-1])

Submission status: Runtime Error

Solution code:
l, n = map(int, input().split())
trs = [int(input()) for _ in range(n)]

ans = -1


def dfs(lis, count, cur):
    #print(lis)
    if len(lis) == 0:
        global ans
        ans = max(ans, count)
        return

    left = lis[0] - cur if lis[0] > cur else lis[0] + (l - cur)
    dfs(lis[1:], count + left, lis[0])
    right = cur - lis[-1] if cur > lis[-1] else cur + (l - lis[-1])
    dfs(lis[:-1], count + right, lis[-1])

dfs(trs, 0, 0)

print(ans)

Submission status: Runtime Error

Solution code:
L, N = map(int, input().split())
X = []
for i in range(N):
    x = int(input())
    X.append(x)
    X.append(x-L)
X.sort()

if N <= 2000:
    def DP(now, minus, plus, left):
        if left == 0:
            return max(now-X[minus], X[plus] - now)
        else:
            PlusL = X[plus] - now + DP(X[plus], minus, plus+1, left-1)
            MinusL = now - X[minus] + DP(X[minus], minus-1, plus, left-1)
            if PlusL > MinusL:
                return PlusL
            else:
                return MinusL
    print(DP(0, N-1, N, N-1))
else: print(L)