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: Wrong Answer

Solution code:
# encoding: utf-8
L, N = map(int, input().split())
X = [int(input()) for i in range(N)]

def walk(src, dst, right):
    if right == 0:
        ret = dst - src if dst >= src else L + dst - src
    else:
        ret = src - dst if dst <= src else L + src - dst
        # print("#", src, dst, ret) 
    return ret
    
ans = ans_tmp = 0
anss = []

left = 0
right = N - 1
pos = 0
task = []
while True:
    # break or continue
    if left > right: 
        anss.append(ans_tmp)
        if len(task) < 1: break
        else: ans_tmp, left, right, pos = task.pop()
    # walk
    walk_l = walk(pos, X[left], 0)
    walk_r = walk(pos, X[right], 1)
    # judge
    if walk_l > walk_r:
        ans_tmp += walk_l
        pos = X[left]
        left += 1
    elif walk_l < walk_r:
        ans_tmp += walk_r
        pos = X[right]
        right -= 1
    else:
        task.append([ans_tmp + walk_l, left + 1, right, X[left]])
        task.append([ans_tmp + walk_r, left, right + 1, X[right]])
    
print(max(anss))

Submission status: Wrong Answer

Solution code:
l,n = map(int,input().split())
result = 0
tmp = 0
a = [int(input()) for i in range(n)]
while len(a) >= 2:
  result = result + max(min(abs(min(a)-tmp),tmp+l-min(a)),min(abs(max(a)-tmp),tmp+l-max(a)))
  if min(abs(min(a)-tmp),tmp+l-min(a)) >= min(abs(max(a)-tmp),tmp+l-max(a)):
    tmp = min(a)
    a.remove(min(a))
  elif min(abs(min(a)-tmp),tmp+l-min(a)) < min(abs(max(a)-tmp),tmp+l-max(a)):
    tmp = max(a)
    a.remove(max(a))
result = result + max(abs(min(a)-tmp),tmp+l-min(a))
result = result + 1
print(result)

Submission status: Wrong Answer

Solution code:
l,n=map(int,input().split())
x=[]
xx=[]
move1=[]
move2=[]
for _ in range(n):
    x.append(int(input()))
walk1=0
walk2=0
will=0
now=0
a=0
b=0
disa1=0
disa2=0
disb1=0
disb2=0
xx=x[:]
for i in range(n):
    if now==0:
        walk1+=l-max(x)
        now=max(x)
        x.remove(now)
        move1.append(now)
    elif len(x)==2:
        a=max(x)
        b=min(x)
        if now>a:
            disa1=now-a
            disb1=l-now+b
        else:
            disa1=now+l-a
            disb1=b-now
        walk1+=max(disa1,disa2)
        if disa1<disb1:
            now=b
            x.remove(b)
        else:
            now=a
            x.remove(a)
        move1.append(now)
    elif len(x)==1:
        a=max(x)
        if a<now:
            disa1=now-a
            disa2=l-now+a
        else:
            disa1=a-now
            disa2=now+l-a
        walk1+=max(disa1,disa2)
        now=a
        move1.append(now)
    else:
        a=max(x)
        b=min(x)
        if now>a:
            disa1=now-a
            disb1=l-now+b
            if disa1<disb1:
                walk1+=disb1
                now=b
                x.remove(b)
            else:
                walk1+=disa1
                now=a
                x.remove(a)
        else:
            disa1=now+l-a
            disb1=b-now
            if disa1<disb1:
                walk1+=disb1
                now=b
                x.remove(b)
            else:
                walk1+=disa1
                now=a
                x.remove(a)
        move1.append(now)

    a=0
    b=0
    disa1=0
    disa2=0
    disb1=0
    disb2=0
now=0
x=xx[:]
for i in range(n):
    if now==0:
        walk2+=x[0]
        now=x[0]
        x.remove(now)
        move2.append(now)
    elif len(x)==2:
        a=max(x)
        b=min(x)
        if now>a:
          disa1=now-a
          disb1=l-now+b
        else:
          disa1=now+l-a
          disb1=b-now
        if disa1<disb1:
            now=b
            x.remove(b)
        else:
            now=a
            x.remove(a)
        walk2+=max(disa1,disb1)
        move2.append(now)
    elif len(x)==1:
        a=max(x)
        if a<now:
            disa1=now-a
            disa2=l-now+a
        else:
            disa1=a-now
            disa2=now+l-a
        walk2+=max(disa1,disa2)
        now=a
        move2.append(now)

    else:
        a=max(x)
        b=min(x)
        if now>a:
            disa1=now-a
            disb1=l-now+b
            if disa1<disb1:
                walk2+=disb1
                now=b
                x.remove(b)
            else:
                walk2+=disa1
                now=a
                x.remove(a)
        else:
            disa1=now+l-a
            disb1=b-now
            if disa1<disb1:
                walk2+=disb1
                now=b
                x.remove(b)
            else:
                walk2+=disa1
                now=a
                x.remove(a)
        move2.append(now)

    a=0
    b=0
    disa1=0
    disa2=0
    disb1=0
    disb2=0
print(max(walk1,walk2))

Submission status: Wrong Answer

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

l, n = map(int, input().split())
x = [int(input()) for _ in range(n)]


dp = [[0] * (n+1) for i in range(n+1)]

for i in range(n):
    for j in range(n):
        if j > i:
            if i != 0:
                if j != n-1:
                    dp[i][j] = max(dp[i][j], max(dp[i-1][j] + x[i] - x[i-1], dp[j + 1][i] + l - x[j + 1] + x[i]))
                else:
                    dp[i][j] = max(dp[i][j], max(dp[i - 1][j] + x[i] - x[i - 1], dp[i-1][j] + x[i] - x[i-1]))
            elif i == 0 and j != n-1:
                dp[i][j] = max(dp[i][j], x[0] + l - x[j+1])
            else:
                dp[i][j] = max(dp[i][j], x[0])
        elif j < i:
            if i != n-1:
                dp[i][j] = max(dp[i][j], dp[i + 1][j] + x[i + 1] - x[i])
            elif i == n-1 and j-1 >= 0:
                dp[i][j] = max(dp[i][j], x[j-1] + x[j-1] + l - x[n-1])
            else:
                dp[i][j] = l - x[n-1]

ans = 0
for i in range(n):
    if i > 0:
        ans = max(ans, dp[i][i - 1] + max(x[i] - x[i - 1], l - (x[i] - x[i - 1])))
    if i < n-1:
        ans = max(ans, dp[i][i+1] + max(x[i+1] - x[i], l - (x[i+1] - x[i])))

print(ans)

Submission status: Wrong Answer

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

from collections import deque

x = deque(x_)
p = 0
d = 0
while x:
    left = (x[0] - p) % l
    right = (p - x[-1]) % l

    if left > right:
        d += left 
        p = x.popleft()
    else:
        d += right 
        p = x.pop()
print(d)

Submission status: Wrong Answer

Solution code:
#coding:utf-8

import sys
sys.setrecursionlimit(100000)

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

X = []

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


dist = 0
now = 0
for i in range(N):
    left = X[0]
    d = left - now
    left_d = d if d>0 else L+d

    right = X[-1]
    d = now - right
    right_d = d if d>0 else L+d

    if left_d > right_d:
        now = X[0]
        X = X[1:]
        dist += left_d
    else:
        now = X[-1]
        X = X[:-1]
        dist += right_d
       
print(dist)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000000)
ln=list(map(int,input().split()))
l=ln[0]
n=ln[1]
x=[int(input()) for i in range(n)]

def far(x):
    f = len(x)
    if f <3:
        return False
    else:
        s = 0
        while (x[s+1]-x[s]) == (x[f-s-1]-x[f-s-2]) and s < f//2:
            s += 1
        return (x[s+1]-x[s]) >= (x[f-s-1]-x[f-s-2])
    
def burn(x,p,w):
    if len(x) == 1:
        return w + max(abs(x[0]-p),abs(l-abs(x[0]-p)))
    elif p != 0 and p <= l/2:
        y = list(map(lambda t:t-p,x))
        return burn(y,0,w)
    elif p != 0 and p > l/2:
        y = list(map(lambda t:t+l-p,x))
        return burn(y,0,w)
    else:
        if x[0] > (l-x[len(x)-1]) or far(x):
            p = x[0]
            del x[0]
            w2 = w+p
            return burn(x,p,w2)
        else:# x[0] < (l-x[len(x)-1]):
            p = x[len(x)-1]
            del x[len(x)-1]
            w2 = w+p
            return burn(x,p,w2)  

print(burn(x,0,0))

Submission status: Wrong Answer

Solution code:
import numpy as np
import copy

L,N = map(int,input().split())
tree_loc = [int(input()) for i in range(N)]
tree_forward = copy.deepcopy(tree_loc)
tree_loc = np.array(tree_loc)

#スタート向き
forward = np.median(tree_forward)
back = L - forward
tree_forward.append(L)
tree_forward.insert(0,0)
tree_forward = np.array(tree_forward)
tree_back = L - tree_forward
diff_tree_forward = np.diff(tree_forward)

loc = 0
dist = 0
if forward > back :#反時計回り
    back = diff_tree_forward[0]
    dist += diff_tree_forward[0]
    diff_tree_forward = np.delete(diff_tree_forward,0)
    forward = diff_tree_forward[0]
    forward_flag = True
    loc = tree_loc[0]
    tree_loc =  np.delete(tree_loc,0)
else:#時計回り
    forward = diff_tree_forward[-1]
    dist += diff_tree_forward[-1]
    diff_tree_forward = np.delete(diff_tree_forward,-1)
    back = diff_tree_forward[-1]
    forward_flag = False
    loc = tree_loc[0]
    tree_loc =  np.delete(tree_loc,-1)

for i in range(1,N):
    if forward > back :#反時計回り
        if forward_flag:
            pass
        else:
            dist += (L - loc)

        back = diff_tree_forward[0]
        dist += diff_tree_forward[0]
        diff_tree_forward = np.delete(diff_tree_forward,0)
        forward = diff_tree_forward[0]
        forward_flag = True
        loc = tree_loc[0]
        tree_loc =  np.delete(tree_loc,0)

    else:#時計回り
        if forward_flag:
            dist += loc
        else:
            pass
        
        forward = diff_tree_forward[-1]
        dist += diff_tree_forward[-1]
        diff_tree_forward = np.delete(diff_tree_forward,-1)
        back = diff_tree_forward[-1]
        forward_flag = False
        loc = tree_loc[0]
        tree_loc =  np.delete(tree_loc,-1)


print(dist)

Submission status: Wrong Answer

Solution code:
L,N = map(int,input().split(" "))
X = []
for i in range(N):
    X.append(int(input()))
c_p = 0
D = 0
for i in range(N):
    r = X[0] - c_p
    l = L-X[len(X)-1] + c_p
    if r >= l:
        c_p = X[0]
        D += r
        X.remove(X[0])
    else:
        c_p = X[len(X)-1]
        D += l
        X.remove(X[len(X)-1])
print(D)

Submission status: Wrong Answer

Solution code:
l,n = map(int, input().split())

x = [0]*n
for i in range(n) :
    x[i] = int(input())

c = 0

if n>2000 :
    print(0)
else :
    
    l_now = 0
    n_now = n + 0

    while n_now>0 :
        x_now = [0]*n_now
        y_now = [0]*n_now
        
        for i in range(n_now) :
            x_now[i] = (x[i] - l_now)%l
            y_now[i] = (x[i] - l_now)%l - l

        a_x = 0
        a_y = n_now -1
        
        if abs(x_now[a_x])>=abs(y_now[a_y]) :
            a = a_x + 0
            c += abs(x_now[a_x])
        else :
            a = a_y + 0
            c += abs(y_now[a_y])

        l_now = x[a] + 0
        x.pop(a)
        n_now -= 1
        
    print(c)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
L, N = map(int, input().split())
X = [0] + [int(input()) for _ in range(N)]


ans1 = X[1]
used = [True] + [False] * N
used[1] = True
cur = 1
for i in range(N - 1):
    for j in range(1, N + 1):
        r = (cur + j) % (N + 1)
        if used[r]:
            continue
        rv = (X[r] - X[cur] + L) % L
        break
    for j in range(1, N + 1):
        l = (cur - j) % (N + 1)
        if used[l]:
            continue
        lv = (X[cur] - X[l] + L) % L
        break
    cur = [l, r][lv < rv]
    used[cur] = True
    ans1 += max(lv, rv)

ans2 = L - X[-1]
used = [True] + [False] * N
used[-1] = True
cur = N
for i in range(N - 1):
    for j in range(1, N + 1):
        r = (cur + j) % (N + 1)
        if used[r]:
            continue
        rv = (X[r] - X[cur] + L) % L
        break
    for j in range(1, N + 1):
        l = (cur - j) % (N + 1)
        if used[l]:
            continue
        lv = (X[cur] - X[l] + L) % L
        break
    cur = [l, r][lv < rv]
    used[cur] = True
    ans2 += max(lv, rv)

print(max(ans1, ans2))

Submission status: Wrong Answer

Solution code:
import numpy as np
L, N = map(int, input().split())
x = list(map(int, [input() for i in range(N)]))
x.append(L)
y = [x[0]] + [x[i+1]-x[i] for i in range(N)]
s=0
for i in range(int(N/2+1)):
  a = [N-i]*(i+1)
  j = N - i -2
  while j >= 1:
    a = a + [j]
    j -= 2
  if j == -1:
    k = 0
  else:
    a = a + [0]
    k = 1
  while k <= N - i - 1:
    a = a + [k]
    k += 2
  check = s
  s = max([np.dot(y,a),np.dot(y,a[::-1]), s])
  if check == s:
    break
print(s)

Submission status: Wrong Answer

Solution code:
l, n = map(int, input().split())
Xi = []
idx = [0] + [i+1 for i in range(n)]
Xi.append(0)
for i in range(n):
    Xi.append(int(input()))
ans = 0

def Dfwd(next, now):
    # print('in Dfwd, next, now', next, now)
    if next < now:
        return l-(Xi[now]-Xi[next])
    else:
        return Xi[next] - Xi[now]

def Dback(next, now):
    # print('in Dback, next, now', next, now)
    if next > now:
        return l-(Xi[next] -Xi[now])
    else:
        return Xi[now] - Xi[next]

while len(idx)!=1:
    dfwd = Dfwd(idx[0+1], idx[0])
    dback = Dback(idx[-1], idx[0])
    # print('dfwd dback is ',dfwd, dback)
    if dfwd > dback:
        ans += dfwd
        idx.pop(0)
        # print('前に進んだよ')
    else:
        ans += dback
        tmp = idx[-1]
        idx.pop(0)
        idx.pop(len(idx)-1)
        idx = [tmp] + idx
        # print('後に進んだよ')
    # print(ans)
    # print("残っているのは", idx )
print(ans)

Submission status: Wrong Answer

Solution code:
L, N = map(int, input().split())
X_list = [0]
for Ind in range(N):
	X_list.append(int(input()))

len_X_list = len(X_list)
pair = []
xl = X_list[len_X_list - 1] # 

for Ind, x in enumerate(X_list):
	xr = X_list[(Ind + 1) % len_X_list]
	pair.append([ (x - xl + L) % L, (xr - x  + L) % L ])
	xl = x

Index = 0
Sum_dist = 0

while True:
	x = pair.pop(Index) # pop
	if pair == []:
		break
	len_pair = len(pair)
	temp_xr = x[0]
	temp_xl = x[1]
	#pair[Index-1][1] = (pair[Index-1][1] + temp_xl) % L
	pair[Index-1][1] = temp_xr + temp_xl
	#pair[Index % len_pair][0] = (pair[Index % len_pair][0] + temp_xr) % L
	pair[Index % len_pair][0] = temp_xr + temp_xl
	if temp_xr >= temp_xl:
	#if temp_xr > temp_xl:
		Index = (Index - 1 + len_pair) % len_pair
		Sum_dist += temp_xr
	else:
		Index = Index % len_pair
		Sum_dist += temp_xl
print(Sum_dist)

Submission status: Wrong Answer

Solution code:
L, N = map(int, input().split())
X = [0] + [int(input()) for i in range(N)]
ans = 0
queue = [(0, 0, X[1], L-X[-1], 1, -1, 0)]

while queue:
    q = queue.pop()
    pos, path, l_len, r_len, l, r, cnt = q
    if(l-N-1 == r):
        path += max(l_len, r_len)
        ans = max(ans, path)
        continue
    if(l_len >= r_len):
        queue.append((l, path+l_len, X[l+1] - X[l],  l_len + r_len, l + 1, r, cnt+1))
    if(l_len <= r_len):
        queue.append((r, path+r_len, l_len + r_len,  X[r] - X[r-1], l, r - 1, cnt+1))

print(ans)

Submission status: Wrong Answer

Solution code:

L, N = map(int, input().split())
X = [int(input()) for i in range(N)]
if N == 1:
    print(max(X[0], L - X[0]))
    exit()

ans = 0
for i, x in enumerate(X[:-1]):
    if i>3:
        break
    a = x
    l = i
    r = N - 1
    while l != r:
        a += L - X[r] + X[l]
        l += 1
        if l == r: break
        a += L - X[r] + X[l]
        r -= 1
    #print(a)
    ans = max(ans, a)
#print(ans)
for i, x in enumerate(X[1:], 1):
    if i<N-3:
        continue
    a = L - x
    l = 0
    r = i
    while l != r:
        # print(l, r)
        a += L - X[r] + X[l]
        r -= 1
        if l == r: break
        a += L - X[r] + X[l]
        l += 1
    ans = max(ans, a)
    #print(a)

print(ans)

Submission status: Wrong Answer

Solution code:
L, N = map(int, input().split())
X = [0] + [int(input()) for i in range(N)]
ans = 0
queue = [(0, 0, X[1], L-X[-1], 1, -1, 0)]

while queue:
    q = queue.pop()
    pos, path, l_len, r_len, l, r, cnt = q
    print(q)
    if(l-N-1 == r):
        path += max(l_len, r_len)
        ans = max(ans, path)
        continue
    if(l_len >= r_len):
        queue.append((l, path+l_len, X[l+1] - X[l],  l_len + r_len, l + 1, r, cnt+1))
    if(l_len <= r_len):
        queue.append((r, path+r_len, l_len + r_len,  X[r] - X[r-1], l, r - 1, cnt+1))

print(ans)

Submission status: Wrong Answer

Solution code:
l,n=map(int,input().split())
lis=[]
for i in range(n):
  lis.append(int(input()))
frn=0
bac=len(lis)-1
x=0
no=0
su=0
while True:
  if frn>bac:
    break
  if l//2>no:
    if lis[frn]-no>l-lis[bac]+no:
      su+=lis[frn]-no
      no=lis[frn]
      frn+=1
    else:
      su+=l-lis[bac]+no
      no=lis[bac]
      bac-=1
  else:
    if lis[frn]+l-no>no-lis[bac]:
      su+=lis[frn]+l-no
      no=lis[frn]
      frn+=1
    else:
      su+=no-lis[bac]
      no=lis[bac]
      bac-=1
print(su)

Submission status: Wrong Answer

Solution code:
L, N = map( int, input().split())
X = [ int( input()) for _ in range(N)]
anst = 0
l = 0
r = N-1
ans = 0
now = 0
if N > 2000:
    N = 1
for _ in range(N):
    if X[l] - now >= now + (L - X[r]):
        ans += X[l] - now
        now = X[l]
        l += 1
    else:
        ans += L - X[r] + now
        now = -L+X[r]
        r -= 1

anst = max( ans, anst)
for i in range(1,N):
    l = i
    r = N-1
    ans = X[i-1]
    now = X[i-1]
    for _ in range(N-i):
        if X[l] - now >= now + (L - X[r]):
            ans += X[l] - now
            now = X[l]
            l += 1
        else:
            ans += L - X[r] + now
            now = -L+X[r]
            r -= 1
    anst = max( ans, anst)

for i in range(1,N):
    l = 0
    r = N-1-i
    ans = L - X[N-i]
    now = -L + X[N-i]
    for _ in range(N-i):
        if X[l] - now >= now + (L - X[r]):
            ans += X[l] - now
            now = X[l]
            l += 1
        else:
            ans += L - X[r] + now
            now = -L+X[r]
            r -= 1
    anst = max( ans, anst)
print(anst)

Submission status: Wrong Answer

Solution code:
l,n = map(int,input().split())
s = set()
#list = [0 for i in range(l)]
for _ in range(n):
    s.add(int(input()))
curr = 0
w = 0
ll = len(s)
#print(ll)
for _ in range(n):
    pw = 0
    mw = 0
    mi = min(s)
    ma = max(s)
    if mi > curr:
        pw = mi - curr
    else:
        pw = l - curr + mi
        
    if curr > ma:
        mw = curr - ma
    else:
        mw = l - ma + curr
    #print('p m',pw,mw)
    if pw > mw:
        w += pw
        curr = mi
        s.remove(mi)
    else:
        w += mw
        curr = ma
        s.remove(ma)
print(w)

Submission status: Wrong Answer

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

if N == 1:
    print(max(X[0],L-X[0]))
    exit()

if N > 2000: exit()

dp = [[[0,0] for r in range(N+1)] for l in range(N+1)]
dp[1][0][0] = X[0]
dp[0][1][1] = L - X[-1]

for l in range(N):
    for r in range(N):
        if l+r >= N+1: break
        if dp[l][r][0]:
            x = X[l-1]
            dp[l+1][r][0] = max(dp[l+1][r][0], dp[l][r][0] + X[l]-x)
            dp[l][r+1][1] = max(dp[l][r+1][1], dp[l][r][0] + x + L-X[-r-1])
        if dp[l][r][1]:
            x = X[-r]
            dp[l+1][r][0] = max(dp[l+1][r][0], dp[l][r][1] + L-x + X[l])
            dp[l][r+1][1] = max(dp[l][r+1][1], dp[l][r][1] + x-X[-r-1])

ans = max(X[-1], L-X[0])
for l in range(N):
    r = N-l
    ans = max(ans, dp[l][r][0],dp[l][r][1])
print(ans)

Submission status: Wrong Answer

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

if N == 1:
    print(max(N,L-N))
    exit()

if N > 2000: exit()

dp = [[[0,0] for r in range(N+1)] for l in range(N+1)]
dp[1][0][0] = X[0]
dp[0][1][1] = L - X[-1]

for l in range(N):
    for r in range(N):
        if l+r >= N+1: break
        if dp[l][r][0]:
            x = X[l-1]
            dp[l+1][r][0] = max(dp[l+1][r][0], dp[l][r][0] + X[l]-x)
            dp[l][r+1][1] = max(dp[l][r+1][1], dp[l][r][0] + x + L-X[-r-1])
        if dp[l][r][1]:
            x = X[-r]
            dp[l+1][r][0] = max(dp[l+1][r][0], dp[l][r][1] + L-x + X[l])
            dp[l][r+1][1] = max(dp[l][r+1][1], dp[l][r][1] + x-X[-r-1])

ans = max(X[-1], L-X[0])
for l in range(N):
    r = N-l
    ans = max(ans, dp[l][r][0],dp[l][r][1])
print(ans)

Submission status: Wrong Answer

Solution code:
L, N = map(int, input().split())

stack = []
results = []


def burn(T, pos, d_total, flag=False):
    if len(T) == 0:
        results.append(d_total)
        return

    tmin = T[0]
    tmax = T[-1]
    d_ccw = (tmin - pos) % L
    d_cw = (pos - tmax) % L

    if flag:
        stack.append((T[:-1], tmax, d_total + d_cw))
        stack.append((T[1:], tmin, d_total + d_ccw))

    if d_cw > d_ccw:
        stack.append((T[:-1], tmax, d_total + d_cw))
        return

    if d_cw < d_ccw:
        stack.append((T[1:], tmin, d_total + d_ccw))
        return

    if d_cw == d_ccw:
        stack.append((T[:-1], tmax, d_total + d_cw))
        stack.append((T[1:], tmin, d_total + d_ccw))
        return

X = [int(input()) for _ in range(N)]
X.sort()

burn(X, 0, 0, True)

while len(stack) > 0:
    a = stack.pop()
    burn(*a)

print(max(results))

Submission status: Wrong Answer

Solution code:
L,N=map(int,input().split())
A=[]
B=[]
for i in range(N):
    X=int(input())
    A.append(X)
    B.append(X-L)
a=0
k=0
for j in range(N):
    if abs(A[0]-k)<abs(B[-1]-k):
        a+=abs(B[-1]-k)
        k=B[-1]
        A.pop(-1)
        B.pop(-1)
    elif abs(A[0]-k)>abs(B[-1]-k):
        a+=abs(A[0]-k)
        k=A[0]
        A.pop(0)
        B.pop(0)
    else:
        if j==N-1:
            a+=abs(A[0]-k)
            break
        elif abs(A[0]-B[-2])<abs(A[1]-B[-1]):
            a+=abs(A[0]-k)
            k=A[0]
            A.pop(0)
            B.pop(0)
        else:
            a+=abs(B[-1]-k)
            k=B[-1]
            A.pop(-1)
            B.pop(-1)
print(a)

Submission status: Wrong Answer

Solution code:
l,n = map(int, input().split())

x = [0]*n
for i in range(n) :
    x[i] = int(input())

c = 0

if n>2000 :
    print(0)
else :
    
    l_now = 0
    n_now = n + 0

    while n_now>0 :
        x_now = [0]*n_now
        y_now = [0]*n_now
        
        for i in range(n_now) :
            x_now[i] = (x[i] - l_now)%l
            y_now[i] = (x[i] - l_now)%l - l

        for i in range(n_now) :
            a_x = 0
            a_y = 0
            if min(x_now)==x_now[i] :
                a_x = i + 0
            if max(y_now)==y_now[i] :
                a_y = i + 0
        
        if abs(x_now[a_x])>=abs(y_now[a_y]) :
            a = a_x + 0
            c += abs(x_now[a_x])
        else :
            a = a_y + 0
            c += abs(y_now[a_y])

        l_now = x[a] + 0
        x.pop(a)
        n_now -= 1
        
    print(c)

Submission status: Wrong Answer

Solution code:
L, N = map( int, input().split())
X = [ int( input()) for _ in range(N)]
anst = 0
l = 0
r = N-1
ans = 0
now = 0
if N > 2000:
    N = 1
for _ in range(N):
    if X[l] - now >= now + (L - X[r]):
        ans += X[l] - now
        now = X[l]
        l += 1
    else:
        ans += L - X[r] + now
        now = -L+X[r]
        r -= 1

anst = max( ans, anst)
for i in range(1,N):
    l = i
    r = N-1
    ans = X[i-1]
    now = X[i-1]
    for _ in range(N-i):
        if X[l] - now >= now + (L - X[r]):
            ans += X[l] - now
            now = X[l]
            l += 1
        else:
            ans += L - X[r] + now
            now = -L+X[r]
            r -= 1
    anst = max( ans, anst)

for i in range(1,N):
    l = 0
    r = N-1-i
    ans = L - X[N-i]
    now = -L + X[N-i]
    for _ in range(N-i):
        if X[l] - now >= now + (L - X[r]):
            ans += X[l] - now
            now = X[l]
            l += 1
        else:
            ans += L - X[r] + now
            now = -L+X[r]
            r -= 1
    anst = max( ans, anst)
print(anst)

Submission status: Wrong Answer

Solution code:
INF = float('inf')

def max2(x, y): return x if x >= y else y

def solve(L, N, Xs):
    if N == 1:
        return max(Xs[1], L - Xs[1])
    if N > 2000:
        return 0

    dpL = [[-INF] * (N+1) for _ in range(N+1)]
    dpR = [[-INF] * (N+1) for _ in range(N+1)]
    dpL[1][N] = 0
    dpR[1][N] = 0
    for A in range(1, N+1):
        for B in reversed(range(A, N+1)):
            # C=0 ccw
            C = 0
            if B > 1:  # ccw
                dpL[A][B-1] = max2(dpL[A][B-1], dpL[A][B] + Xs[B+1] - Xs[B])
            if A < N:  # cw
                dpR[A+1][B] = max2(dpR[A+1][B], dpL[A][B] + (L - Xs[B+1]) + Xs[A])
            # C=1 cw
            C = 1
            if B > 1:  # ccw
                dpL[A][B-1] = max2(dpL[A][B-1], dpR[A][B] + Xs[A-1] + (L - Xs[B]))
            if A < N:  # cw
                dpR[A+1][B] = max2(dpR[A+1][B], dpR[A][B] + Xs[A] - Xs[A-1])

    maxL = max(map(max, dpL))
    maxR = max(map(max, dpR))
    ans = max(maxL, maxR)
    return ans

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

print(solve(L, N, Xs))

Submission status: Wrong Answer

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

if N == 1:
    print(max(N,L-N))
    exit()

if N > 2000: exit()

dp = [[[0,0] for r in range(N+1)] for l in range(N+1)]
dp[1][0][0] = X[0]
dp[0][1][1] = L - X[-1]

for l in range(N):
    for r in range(N):
        if l+r >= N+1: break
        if dp[l][r][0]:
            x = X[l-1]
            dp[l+1][r][0] = max(dp[l+1][r][0], dp[l][r][0] + X[l]-x)
            dp[l][r+1][1] = max(dp[l][r+1][1], dp[l][r][0] + x + L-X[-r-1])
        if dp[l][r][1]:
            x = X[-r]
            dp[l+1][r][0] = max(dp[l+1][r][0], dp[l][r][1] + L-x + X[l])
            dp[l][r+1][1] = max(dp[l][r+1][1], dp[l][r][1] + x-X[-r-1])

ans = 0
for l in range(N):
    r = N-l
    ans = max(ans, dp[l][r][0],dp[l][r][1])
print(ans)

Submission status: Wrong Answer

Solution code:
l,n=map(int,input().split())
x1=[]
x2=[]
for i in range(n):
    t=int(input())
    x1.append(t)
    x2.append(l-t)
x2.reverse()
ans1=0
ans2=0
z=0
pm=0
u1=0
u2=0

ans1+=x1[0]
z=x1[0]
pm=1
u1+=1

while u1+u2<n:
    if pm==1:
        if x1[u1]-z>x2[u2]+z:
            ans1+=x1[u1]-z
            z=x1[u1]
            pm=1
            u1+=1
        else:
            ans1+=x2[u2]+z
            z=x2[u2]
            pm=-1
            u2+=1
    else:
        if x2[u2]-z>x1[u1]+z:
            ans1+=x2[u2]-z
            z=x2[u2]
            pm=-1
            u2+=1
        else:
            ans1+=x1[u1]+z
            z=x1[u1]
            pm=1
            u1+=1
   # print(ans1)

z=0
pm=0
u1=0
u2=0
ans2+=x2[0]
z=x2[0]
pm=-1
u2+=1
while u1+u2<n:
    if pm==1:
        if x1[u1]-z>x2[u2]+z:
            ans2+=x1[u1]-z
            z=x1[u1]
            pm=1
            u1+=1
        else:
            ans2+=x2[u2]+z
            z=x2[u2]
            pm=-1
            u2+=1
    else:
        if x2[u2]-z>x1[u1]+z:
            ans2+=x2[u2]-z
            z=x2[u2]
            pm=-1
            u2+=1
        else:
            ans2+=x1[u1]+z
            z=x1[u1]
            pm=1
            u1+=1
ans3=0
ans4=0
u1=0
u2=0
ans3+=x1[u1]
z=x1[u1]
u1+=1
pm=1


while u1+u2<n:
    if pm==1:
        
        ans3+=x2[u2]+z
        z=x2[u2]
        u2+=1
        pm=-1
    else:
        
        ans3+=x1[u1]+z
        z=x1[u1]
        u1+=1
        pm=1
u1=0
u2=0
ans4+=x2[u2]
z=x2[u2]
u2+=1
pm=-1
while u1+u2<n:
    if pm==1:
        ans4+=x2[u2]+z
        z=x2[u2]
        u2+=1
        pm=-1
    else:
        ans4+=x1[u1]+z
        z=x1[u1]
        u1+=1
        pm=1
    
ans5=0
ans6=0
z=0
pm=0
u1=0
u2=0

ans5+=x1[0]
z=x1[0]
pm=1
u1+=1

while u1+u2<n:
    if pm==1:
        if x1[u1]-z>=x2[u2]+z:
            ans5+=x1[u1]-z
            z=x1[u1]
            pm=1
            u1+=1
        else:
            ans5+=x2[u2]+z
            z=x2[u2]
            pm=-1
            u2+=1
    else:
        if x2[u2]-z>=x1[u1]+z:
            ans5+=x2[u2]-z
            z=x2[u2]
            pm=-1
            u2+=1
        else:
            ans5+=x1[u1]+z
            z=x1[u1]
            pm=1
            u1+=1
   # print(ans1)

z=0
pm=0
u1=0
u2=0
ans6+=x2[0]
z=x2[0]
pm=-1
u2+=1
while u1+u2<n:
    if pm==1:
        if x1[u1]-z>=x2[u2]+z:
            ans6+=x1[u1]-z
            z=x1[u1]
            pm=1
            u1+=1
        else:
            ans6+=x2[u2]+z
            z=x2[u2]
            pm=-1
            u2+=1
    else:
        if x2[u2]-z>=x1[u1]+z:
            ans6+=x2[u2]-z
            z=x2[u2]
            pm=-1
            u2+=1
        else:
            ans6+=x1[u1]+z
            z=x1[u1]
            pm=1
            u1+=1
print(max(ans1,ans2,ans3,ans4,ans5,ans6))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
L, N = map(int, input().split())
X = [0] + [int(input()) for _ in range(N)]

used = [True] + [False] * N

ans = 0
cur = 0
for i in range(N):
    for j in range(1, N + 1):
        r = (cur + j) % (N + 1)
        if used[r]:
            continue
        rv = (X[r] - X[cur] + L) % L
        break
    for j in range(1, N + 1):
        l = (cur - j) % (N + 1)
        if used[l]:
            continue
        lv = (X[cur] - X[l] + L) % L
        break
    cur = [l, r][lv < rv]
    used[cur] = True
    ans += max(lv, rv)

print(ans)