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:
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_n=-1
current_nplus=0
current_nminus=n-1
d=0



    


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


  #  if d_plus==d_minus:
        
    
    
    if d_plus> d_minus:
        k=1


    else:
        k=-1
    
    if k==-1:
        current=x[current_nminus]
        d+=d_minus
        current_n=current_nminus
        current_nminus+=-1
        
    if k==1:
        current=x[current_nplus]
        d+=d_plus
        current_n=current_nplus
        current_nplus+=1        
        
        
        
        
    


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

Submission status: Wrong Answer

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

X = [x - L for x in X] + X

ans = 0
taka = 0


def search_longer(now, pre, nex):
    # print((nex - now), (now - pre))
    if (nex - now) > (now - pre):
        return nex - now, True
    else:
        return now-pre, False


while (len(X) != 0):
    nex = int(len(X) / 2)
    # print("nex", nex)
    dist, isnex = search_longer(taka, X[nex - 1], X[nex])
    ans += dist
    # print(taka, dist, ans, isnex)
    # print(X)
    if isnex:
        taka = X[nex]
        X.pop(nex)
        X.pop(0)
    else:
        taka = X[nex-1]
        X.pop(nex - 1)
        X.pop(-1)

print(ans)

Submission status: Wrong Answer

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,(N+1)//2-2,(N+1)//2+2,(N+1)//2-3,(N+1)//2+3]
#(i+2)//2*(-1)**i

ANS=0
for start in CANDI:
    if start==0 or start<0 or start>N:
        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: 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
ll, rr = 0, N-2
f = True
ff = False
while True:
    if f:
        i1, i2 = ll, rr
        f = False
    else:
        i1, i2 = ll + (rr - ll) // 3, ll + 2 * (rr - ll) // 3
    A = []
    for i in [i1, i2]:
        x = X[i]
        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
        ans = max(ans, a)
        A.append(a)
    if A[0] > A[1]:
        rr = i2
    else:
        ll = i1
    #print(ll, rr)
    if i2 - i1 <= 1:
        if ff:
            break
        ff = True

#print("aa")
ll, rr = 1, N-1
f = True
ff = False
while True:
    if f:
        i1, i2 = ll, rr
        f = False
    else:
        i1, i2 = ll + (rr - ll) // 3, ll + 2 * (rr - ll) // 3
    A = []
    for i in [i1, i2]:
        x = X[i]
        a = L - x
        l = 0
        r = i
        while 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)
        A.append(a)
    if A[0] > A[1]:
        rr = i2
    else:
        ll = i1
    if i2 - i1 <= 1:
        if ff:
            break
        ff = True
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [L, N] = [long(input_raw[0]), long(input_raw[1])]
    X = []
    X_rev = deque([])
    for i in range(N):
        input_raw = read_func().strip().split()
        X.append(long(input_raw[0]))
        X_rev.appendleft(L - long(input_raw[0]))

    max_count = 0
    l = N - 1
    r = 0
    now_X = 0


    for i in range(N):
        if X[r] - now_X > abs(X[l] - L - now_X):
            max_count += X[r] - now_X
            now_X = X[r]
            r += 1
        else:
            max_count += abs(X[l] - L - now_X)
            now_X = X[l] - L
            l -= 1

    print max_count


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
L,N = list(map(int,input().split()))
X=[]
Y=[]
SX=[0]
SY=[0]
sx=0
sy=0
for i in range(N):
   x=int(input())
   X.append(x)
   sx+=x
   SX.append(sx)
   Y.append(L-x)
   sy+=L-x
   SY.append(sy)   

max_score=0   
for i in range(N):
    if i>N-i-1:
        max_score=max(2*(SX[i]-SX[2*i-N])+2*(SY[N]-SY[i+1])+Y[i],max_score)
    elif i<N-i-1:
        max_score=max(2*(SX[i]-SX[0])+2*(SY[2*i+2]-SY[i+1])+X[i],max_score)

        
    ind = min(i,N-i-1)
    max_score=max(2*(SX[i]-SX[i-ind])+2*(SY[i+ind]-SY[i+1])+X[i],max_score)
    max_score=max(2*(SX[i]-SX[i-ind])+2*(SY[i+ind]-SY[i+1])+Y[i],max_score)


print(max_score)

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

    dp = [[[-INF] * (2) for B in range(N+1)] for A in range(N+1)]
    dp[1][N][0] = 0
    dp[1][N][1] = 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
                dp[A][B-1][0] = max2(dp[A][B-1][0], dp[A][B][C] + Xs[B+1] - Xs[B])
            if A < N:  # cw
                dp[A+1][B][1] = max2(dp[A+1][B][1], dp[A][B][C] + (L - Xs[B+1]) + Xs[A])
            # C=1 cw
            C = 1
            if B > 1:  # ccw
                dp[A][B-1][0] = max2(dp[A][B-1][0], dp[A][B][C] + Xs[A-1] + (L - Xs[B]))
            if A < N:  # cw
                dp[A+1][B][1] = max2(dp[A+1][B][1], dp[A][B][C] + Xs[A] - Xs[A-1])

    ans = 0
    for A in range(N+1):
        for B in range(N+1):
            for C in range(2):
                ans = max2(ans, dp[A][B][C])
    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:
import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(1000000)


# Debug output
def chkprint(*args):
    names = {
        id(v): k
        for k, v in inspect.currentframe().f_back.f_locals.items()
    }
    print(', '.join(
        names.get(id(arg), '???') + ' = ' + repr(arg) for arg in args))


# Binary converter
def to_bin(x):
    return bin(x)[2:]


def li_input():
    return [int(_) for _ in input().split()]


def gcd(n, m):
    if n % m == 0:
        return m
    else:
        return gcd(m, n % m)


def gcd_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = gcd(v, L[i])

    return v


def lcm(n, m):
    return (n * m) // gcd(n, m)


def lcm_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = lcm(v, L[i])

    return v


# Width First Search (+ Distance)
def wfs_d(D, N, K):
    """
    D: 隣接行列(距離付き)
    N: ノード数
    K: 始点ノード
    """

    dfk = [-1] * (N + 1)
    dfk[K] = 0

    cps = [(K, 0)]
    r = [False] * (N + 1)
    r[K] = True
    while len(cps) != 0:
        n_cps = []
        for cp, cd in cps:
            for i, dfcp in enumerate(D[cp]):
                if dfcp != -1 and not r[i]:
                    dfk[i] = cd + dfcp
                    n_cps.append((i, cd + dfcp))
                    r[i] = True

        cps = n_cps[:]

    return dfk


# Depth First Search (+Distance)
def dfs_d(v, pre, dist):
    """
    v:  現在のノード
    pre: １つ前のノード
    dist: 現在の距離

    以下は別途用意する
    D: 隣接リスト(行列ではない)
    D_dfs_d: dfs_d関数で用いる，始点ノードから見た距離リスト
    """

    global D
    global D_dfs_d

    D_dfs_d[v] = dist

    for next_v, d in D[v]:
        if next_v != pre:
            dfs_d(next_v, v, dist + d)

    return


def sigma(N):
    ans = 0
    for i in range(1, N + 1):
        ans += i
    return ans


def comb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2, r + 1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p - 1, r, p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def bisearch(L, target):
    low = 0
    high = len(L) - 1
    
    while low <= high:
        mid = (low + high) // 2
        guess = L[mid]
        if guess == target:
            return True
        elif guess < target:
            low = mid + 1
        elif guess > target:
            high = mid - 1
    if guess != target:
        return False

# --------------------------------------------

dp = None


def main():
    L, N = li_input()
    X = [int(input()) for _ in range(N)]

    A = [0, 1] * 100000
    B = [1, 0] * 100000
    C = [1] * 100000
    D = [0] * 100000

    finalans = -1
    
    current = X[0]
    li = 1
    ri = len(X) - 1
    ans = X[0]
    N_ = N-1
    ai = 0
    while N_:
        if current < X[li]:
            l_dist = X[li] - current
        else:
            l_dist = (L - current) + X[li]

        if current > X[ri]:
            r_dist = current - X[ri]
        else:
            r_dist = current + (L - X[ri])

        if l_dist > r_dist:
            ans += l_dist
            current = X[li]
            li += 1
        elif l_dist < r_dist:
            ans += r_dist
            current = X[ri]
            ri -= 1
        else:
            if A[ai]:
                ans += l_dist
                current = X[li]
                li += 1
            else:
                ans += r_dist
                current = X[ri]
                ri -= 1
            ai += 1

        N_ -= 1

    finalans = max(finalans, ans)

    current = X[0]
    li = 1
    ri = len(X) - 1
    ans = X[0]
    N_ = N-1
    bi = 0
    while N_:
        if current < X[li]:
            l_dist = X[li] - current
        else:
            l_dist = (L - current) + X[li]

        if current > X[ri]:
            r_dist = current - X[ri]
        else:
            r_dist = current + (L - X[ri])

        if l_dist > r_dist:
            ans += l_dist
            current = X[li]
            li += 1
        elif l_dist < r_dist:
            ans += r_dist
            current = X[ri]
            ri -= 1
        else:
            if B[bi]:
                ans += l_dist
                current = X[li]
                li += 1
            else:
                ans += r_dist
                current = X[ri]
                ri -= 1
            bi += 1
        N_ -= 1

    finalans = max(finalans, ans)

    current = X[-1]
    li = 0
    ri = len(X) - 2
    ans = L - X[-1]    
    N_ = N-1
    ai = 0
    while N_:
        if current < X[li]:
            l_dist = X[li] - current
        else:
            l_dist = (L - current) + X[li]

        if current > X[ri]:
            r_dist = current - X[ri]
        else:
            r_dist = current + (L - X[ri])

        if l_dist > r_dist:
            ans += l_dist
            current = X[li]
            li += 1
        elif l_dist < r_dist:
            ans += r_dist
            current = X[ri]
            ri -= 1
        else:
            if A[ai]:
                ans += l_dist
                current = X[li]
                li += 1
            else:
                ans += r_dist
                current = X[ri]
                ri -= 1
            ai += 1

        N_ -= 1

    finalans = max(finalans, ans)

    current = X[-1]
    li = 0
    ri = len(X) - 2
    ans = L - X[-1]
    N_ = N-1
    bi = 0
    while N_:
        if current < X[li]:
            l_dist = X[li] - current
        else:
            l_dist = (L - current) + X[li]

        if current > X[ri]:
            r_dist = current - X[ri]
        else:
            r_dist = current + (L - X[ri])

        if l_dist > r_dist:
            ans += l_dist
            current = X[li]
            li += 1
        elif l_dist < r_dist:
            ans += r_dist
            current = X[ri]
            ri -= 1
        else:
            if B[bi]:
                ans += l_dist
                current = X[li]
                li += 1
            else:
                ans += r_dist
                current = X[ri]
                ri -= 1
            bi += 1

        N_ -= 1

    finalans = max(finalans, ans)




    current = X[0]
    li = 1
    ri = len(X) - 1
    ans = X[0]
    N_ = N-1
    while N_:
        if current < X[li]:
            l_dist = X[li] - current
        else:
            l_dist = (L - current) + X[li]

        if current > X[ri]:
            r_dist = current - X[ri]
        else:
            r_dist = current + (L - X[ri])

        if l_dist > r_dist:
            ans += l_dist
            current = X[li]
            li += 1
        elif l_dist < r_dist:
            ans += r_dist
            current = X[ri]
            ri -= 1
        else:
            ans += l_dist
            current = X[li]
            li += 1

        N_ -= 1

    finalans = max(finalans, ans)

    current = X[0]
    li = 1
    ri = len(X) - 1
    ans = X[0]
    N_ = N-1
    while N_:
        if current < X[li]:
            l_dist = X[li] - current
        else:
            l_dist = (L - current) + X[li]

        if current > X[ri]:
            r_dist = current - X[ri]
        else:
            r_dist = current + (L - X[ri])

        if l_dist > r_dist:
            ans += l_dist
            current = X[li]
            li += 1
        elif l_dist < r_dist:
            ans += r_dist
            current = X[ri]
            ri -= 1
        else:
            ans += r_dist
            current = X[ri]
            ri -= 1
        N_ -= 1

    finalans = max(finalans, ans)

    



    current = X[-1]
    li = 0
    ri = len(X) - 2
    ans = L - X[-1]    
    N_ = N-1
    while N_:
        if current < X[li]:
            l_dist = X[li] - current
        else:
            l_dist = (L - current) + X[li]

        if current > X[ri]:
            r_dist = current - X[ri]
        else:
            r_dist = current + (L - X[ri])

        if l_dist > r_dist:
            ans += l_dist
            current = X[li]
            li += 1
        elif l_dist < r_dist:
            ans += r_dist
            current = X[ri]
            ri -= 1
        else:
            ans += l_dist
            current = X[li]
            li += 1

        N_ -= 1

    finalans = max(finalans, ans)

    current = X[-1]
    li = 0
    ri = len(X) - 2
    ans = L - X[-1]
    N_ = N-1
    while N_:
        if current < X[li]:
            l_dist = X[li] - current
        else:
            l_dist = (L - current) + X[li]

        if current > X[ri]:
            r_dist = current - X[ri]
        else:
            r_dist = current + (L - X[ri])

        if l_dist > r_dist:
            ans += l_dist
            current = X[li]
            li += 1
        elif l_dist < r_dist:
            ans += r_dist
            current = X[ri]
            ri -= 1
        else:
            ans += r_dist
            current = X[ri]
            ri -= 1

        N_ -= 1

    finalans = max(finalans, ans)

    print(finalans)

main()

Submission status: Wrong Answer

Solution code:
def main(c, N, lenlist):
  state = 0
  result = 0
  first = 0
  end = len(lenlist) - 1
  while(first < end):
    clock_dis = c - lenlist[end] + state
    count_dis = lenlist[first] - state
    if(clock_dis > count_dis):
      result += clock_dis
      state = lenlist[end]
      end -= 1
    else:
      result += count_dis
      state = lenlist[first]
      first += 1
  clock_dis = c -lenlist[end] + state
  count_dis = lenlist[first] - state
  result += max(clock_dis, count_dis)
  return result

if __name__ =='__main__':
  input_str = input()
  c, N = [int(each) for each in input_str.split(' ') ]
  lenlist = []
  for i in range(N):
    lenlist.append(int(input()))
  result = main(c, N, lenlist)
  print(result)

Submission status: Wrong Answer

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

for i in range(N):
    x.append(int(input()))    
total = 0    
pos = 0

while len(x) > 0:
    if x[0] > pos:
        forward = x[0] - pos
    else:
        forward = x[0] + L - pos
    
    if x[-1] > pos:
        backward = L - x[-1] + pos
    else:
        backward = pos - x[-1]

    if forward > backward:
        total += forward
        pos = x[0]
        x.pop(0)
        
    else:
        total += backward
        pos = x[-1]
        x.pop(-1)
        
print(total)

Submission status: Wrong Answer

Solution code:
l,n = map(int,input().split())
x = set()
for i in range(n):
    x.add(int(input()))
cnt = 0
s = 0
p = 1
while len(x)>0: 
    if p ==1:
        if min(x)-s <= l-max(x)+s:
            cnt +=l-max(x)+s
            s = max(x)
            x.remove(max(x))
            p = 0
        else:
            cnt += min(x)-s
            s = min(x)
            x.remove(min(x))
            p = 1
    else:
        if min(x)+l-s <= s-max(x):
            cnt += s-max(x)
            s = max(x)
            x.remove(max(x))
            p = 0
        else:
            cnt += min(x)+l-s
            s = min(x)
            x.remove(min(x))
            p = 1
print(cnt)

Submission status: Wrong Answer

Solution code:
L,N = map(int,input().split())
X = []
now = 0
F = 0
B = N-1
SUM = 0
for i in range(N):
    X.append(int(input()))

while(1):
    if F>B:
        break
    if now <X[F]:
        fabs = X[F] - now
        babs = now + L - X[B]
    else:
        fabs = X[F] + L - now
        babs = now - X[B]
    if fabs >= babs:
        SUM += fabs
        now = X[F]
        F += 1
    else:
        SUM += babs
        now = X[B]
        B -= 1
print(SUM)

Submission status: Wrong Answer

Solution code:
L, N = map(int,input().split())
sp = int(L/2)
Xs = [int(input()) for _ in range(N)]

ln = 0 #現在の座標から最も近い左側の木
rn = N - 1 #現在の座標から最も近い右側の木
cx = 0
result = 0

while True:
  ldist = Xs[ln] - cx
  rdist = L - Xs[rn] + cx
  
  if ldist > rdist:
    result += ldist
    cx = Xs[ln]
    ln += 1
  else:
    result += rdist
    cx = Xs[rn]
    rn -= 1
  if ln > rn: break
    
print(result)

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
print(max(ans1,ans2,ans3,ans4))

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
ll, rr = 0, N-2
f = True
while True:
    #for i, x in enumerate(X[:-1]):
    #if rr-ll==1:
    #    i1, i2 = ll, ll+1
    #else:
    if f:
        i1, i2 = ll, rr
        f = False
    else:
        i1, i2 = ll + (rr - ll) // 3, ll + 2 * (rr - ll) // 3
    A = []
    for i in [i1, i2]:
        x = X[i]
        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)
        A.append(a)
    if A[0] > A[1]:
        rr = i2
    else:
        ll = i1
    if rr - ll <= 2: break
    #print(ll, rr)
#print(ans)

#print("aa")
ll, rr = 1, N-1
f = True
while True:
    #for i, x in enumerate(X[:-1]):
    #if rr-ll==1:
    #    i1, i2 = ll, ll+1
    #else:
    if f:
        i1, i2 = ll, rr
        f = False
    else:
        i1, i2 = ll + (rr - ll) // 3, ll + 2 * (rr - ll) // 3
    A = []
    for i in [i1, i2]:
        x = X[i]
        a = L - x
        l = 0
        r = i
        while 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)
        A.append(a)
    if A[0] > A[1]:
        rr = i2
    else:
        ll = i1
    if rr - ll <= 2: break
    # print(ll, rr)
    #print(a)

print(ans)

Submission status: Wrong Answer

Solution code:

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

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
    else:
        toLeft = l-now+X[left]
        toRight = now-X[right]

    if toLeft > toRight:
        ans += toLeft
        now = X[left]
        left += 1
        lr = 0
    elif toLeft == toRight:
        if X[left]-X[left-1]>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: Wrong Answer

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:
    L = [[0 for j in range(2*N)] for i in range(N)]
    L[0][N-1], L[0][N] = abs(X[N-1]), X[N]
    for i in range(N-1):
        for j in range(2*N):
            if L[i][j]:
                if j < N:
                    L[i+1][j-1] = max(L[i+1][j-1], L[i][j] + X[j]-X[j-1])
                    left = N - j - 1
                    L[i+1][N+i-left] = max(L[i+1][N+i-left], L[i][j] + X[N+i-left]-X[j])
                if j >= N:
                    L[i+1][j+1] = max(L[i+1][j+1], L[i][j] + X[j+1]-X[j])
                    right = j - N
                    L[i+1][N-1-(i-right)] = max(L[i+1][N-1-(i-right)], L[i][j] + X[j]-X[N-1-(i-right)])
    print(max(L[N-1]))

else: print(L)

Submission status: Wrong Answer

Solution code:
l, n = map(int, input().split())
xs = [int(input()) for _ in range(n)]
ans, now, fin = 0, 0, False
i, j = 0, n - 1
while i <= j:
    root1 = xs[i] - now if now < xs[i] else xs[i] + (l - now)
    root2 = now - xs[j] if now > xs[j] else now + (l - xs[j])
    ans += max(root1, root2)
    if root1 > root2:
        now = xs[i]
        i += 1
    else:
        now = xs[j]
        j -= 1
print(ans)