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:
import sys
input = sys.stdin.readline

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

def solve(A):
    S = [None]*N
    s = 0
    for i, a in enumerate(A):
        s += a
        S[i] = s

    T = [None]*N
    t = 0
    for i in reversed(range(N)):
        t += (L-A[i])
        T[i] = t

    ans = 0
    for i in range(N-1):
        if 2*i+3 < N:
            ans = max(ans, 2*S[i]+2*(T[i+1]-T[2*i+3])-(L-A[i+1]))
        elif 2*i+2 > N:
            ans = max(ans, 2*(S[i]-S[2*i-N+1]) + 2*T[i+1] - (L-A[i+1]))
        else:
            ans = max(ans, 2*S[i]+2*T[i+1]-(L-A[i+1]))
    return ans

a1 = solve(A)
a2 = solve([L-a for a in reversed(A)])
print(max(a1, a2))

Submission status: Wrong Answer

Solution code:
import bisect

L,N=map(int,input().split())
xlist=[]
for i in range(N):
  xlist.append(int(input()))

#print(xlist)
pos=0
total_dist=0
while(True):
  #print(pos,xlist)
  if len(xlist)==0:
    break
    
  r=0
  l=bisect.bisect_left(xlist,pos)
  if l==0 or l==len(xlist):
    l=len(xlist)-1
    r=0
  else:
    l-=1
    r=l+1
    
  #print((xlist[l],xlist[r]))
  dist_l=(pos-xlist[l]+L)%L
  dist_r=(xlist[r]-pos+L)%L  
  #print((dist_l,dist_r))
  
  if dist_l>=dist_r:
    pos=xlist[l]
    total_dist+=dist_l
    xlist.pop(l)
  else:
    pos=xlist[r]
    total_dist+=dist_r
    xlist.pop(r)  
  #break
  
print(total_dist)

Submission status: Wrong Answer

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

def f(T):
  n = len(T)
  S = [0]*(2*n+1)
  for i in range(2*n):
    S[i+1] = S[i]+T[i%n]
  a = S[n-1]
  ans = 0
  for i in range(n-1):
    a += 2*(S[2*n-i*2-3]-S[n-i-1])
    a -= 2*(S[2*n-i-2]-S[2*n-i*2-2])
    a -= T[n-i-2]
    ans = max(ans, a)
  return ans

A = [X[0]]+[X[i+1]-X[i] for i in range(N-1)]+[L-X[-1]]
print max(f(A), f(A[::-1]))

Submission status: Wrong Answer

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

def f(T):
  n = len(T)
  S = [0]*(2*n+1)
  for i in range(2*n):
    S[i+1] = S[i]+T[i%n]
  a = S[n-1]
  ans = 0
  for i in range(n-2):
    a += 2*(S[2*n-i*2-3]-S[n-i-1])
    a -= 2*(S[2*n-i-2]-S[2*n-i*2-2])
    a -= T[n-i-2]
    ans = max(ans, a)
  return ans

A = [X[0]]+[X[i+1]-X[i] for i in range(N-1)]+[L-X[-1]]
print max(f(A), f(A[::-1]))

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)]

S=[]

for i in range(N):
    S.append(X[i+1]-X[i])
S.append(L-X[-1])

#print(S)

DIS=L-S[-1]
ANS=L-S[-1]
MINUS=0
PLUS=L-S[-1]

#print(DIS)

for i in range(N-1):
    if i%2==0:
        MINUS+=S[-i-2]
        PLUS+=S[-i-1]-S[-i-2]

    else:
        MINUS+=S[-i-2]-S[-i-1+i//2]
        PLUS-=S[-i-2]

    DIS+=PLUS-MINUS

    if ANS<DIS:
        ANS=DIS

    #print(DIS,PLUS,MINUS)

#print(ANS)

S=S[::-1]

DIS=L-S[-1]
MINUS=0
PLUS=L-S[-1]

#print(DIS)

for i in range(N-1):
    if i%2==0:
        MINUS+=S[-i-2]
        PLUS+=S[-i//2-1]-S[-i-2]

    else:
        MINUS+=S[-i-2]-S[-i-1+i//2]
        PLUS-=S[-i-2]

    DIS+=PLUS-MINUS

    if ANS<DIS:
        ANS=DIS

    #print(DIS,PLUS,MINUS)

print(ANS)

Submission status: Wrong Answer

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

def main():
    L,N = map(int,input().split())
    pos = [int(input()) for _ in range(N)]
    S = [0]
    for i in range(N):
        S.append(S[i]+pos[i])
    diff = max(pos[-1],L-pos[0])
    for i in range(N):
        cl = L*(N-i-1)+2*(S[(N+i)//2]-S[i])+pos[(N+i)//2]-2*(S[-1]-S[(N+i)//2])
        c_cl = L*(N-i)+2*S[(N-i)//2]-pos[(N-i-1)//2]-2*(S[N-i]-S[(N-i+1)//2])
        diff = max(diff,cl,c_cl)

    print(diff)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
from copy import copy

L, N = [int(x) for x in input().split(" ")]
X = deque([int(input()) for x in range(N)])

total = 0
pos = 0
def calc(X, pos, total):
    while X:
        x1 = X[0]
        x2 = X[-1]
        
        if pos < x1:
            x2 = x2 - L
        else:
            x1 = L + x1
        d1 = abs(pos - x1)
        d2 = abs(pos - x2)
        if d1 > d2:
            total += d1
            pos = X.popleft()
        else:
            total += d2
            pos = X.pop()
    return total
        
X1 = copy(X)
pos1 = X1.pop()
total1 = L - pos1

X2 = copy(X)
pos2 = X2.popleft()
total2 = pos2

print(max(calc(X1, pos1, total1), calc(X2, pos2, total2)))

Submission status: Wrong Answer

Solution code:
from collections import deque
from copy import copy

L, N = [int(x) for x in input().split(" ")]
X = deque([int(input()) for x in range(N)])

total = 0
pos = 0
while X:
    # print(X)
    x1 = X[0]
    x2 = X[-1]
    # print("I'm at: ", pos)
    # print("I can go to: ", x1, x2)

    if pos < x1:
        x2 = x2 - L
        # print("I'm to the left, so the right point turns into", x2)
    else:
        x1 = L + x1
        # print("I'm to the right, so the left point turns into", x1)

    # print("Left point", x2)
    # print("Right point", x1)
    d1 = abs(pos - x1)
    d2 = abs(pos - x2)
    # print("Distance to left point is", d2)
    # print("Distance to right point is", d1)
    if d1 > d2:
        total += d1
        pos = X.popleft()
        # print("right to", pos)
    else:
        total += d2
        pos = X.pop()
        # print("left to ", pos)

print(total)

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

l,n = li()

if n > 2000:
    exit()

x = [ni() for _ in range(n)]

dp = [[[0]*2 for _ in range(n+1)] for _ in range(n+1)]
left = [0] + [l-xi for xi in x[::-1]]
right = [0] + [xi for xi in x]

for l in range(n+1):
    dp[l][0][0] = left[l]
for r in range(n+1):
    dp[0][r][1] = right[r]

for l in range(1, n+1):
    for r in range(1, n-l+1):
        dp[l][r][0] = max(dp[l-1][r][0] + (left[l] - left[l-1]),
                          dp[l-1][r][1] + left[l] + right[r])
        dp[l][r][1] = max(dp[l][r-1][1] + (right[r] - right[r-1]),
                          dp[l][r-1][0] + right[r] + left[l])

ans = 0
for l in range(n+1):
    for r in range(n-l+1):
        for lr in [0,1]:
            ans = max(ans, dp[l][r][lr])

print(ans)

Submission status: Wrong Answer

Solution code:
import scipy as sp

L, N = list(map(int, input().split()))
x = sp.array([], dtype = int)

for i in range(N):
    x = sp.append(x, int(input()))

answer = 0
for i in range(N):
    x_1 = x[0]
    x_n = x[-1]
    if x_1 < L-x_n:
        x = sp.delete(x, -1)
        x = x + L + x_1 - x_n
        answer += L-x_n
    else:
        x = sp.delete(x, 0)
        answer += x_1
        x = x - x_1

print(answer)

Submission status: Wrong Answer

Solution code:
import scipy as sp
L, N = list(map(int, input().split()))
x = sp.array([])

for i in range(N):
    x = sp.append(x, int(input()))

answer = 0
for i in range(N):
    x_1 = x[0]
    x_n = x[-1]
    if x_1 < L-x_n:
        x = sp.delete(x, -1)
        x = x + L + x_1 - x_n
        answer += L-x_n
    else:
        x = sp.delete(x, 0)
        answer += x_1
        x = x - x_1

print(answer)

Submission status: Wrong Answer

Solution code:
L,N=map(int,input().split())
x=[int(input()) for i in range(N)]
l=[-L+i+1 for i in range(2*L-1)]
walk=0
tmp=0
f=0
b=0
for i in range(N):
    lf=l[L-1+x[f]]
    lb=l[x[N-1-b]-1]
    if abs(tmp-lf)>abs(tmp-lb):
        walk+=abs(tmp-lf)       
        tmp=lf
        f+=1
    else:
        walk+=abs(tmp-lb)
        tmp=lb
        b+=1
print(walk)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)

L, N = map(int, input().split())
X = [int(input()) for _ in range(N)]
def measure_distance(pos, x, clockwise):
    if clockwise:
        return (pos - x) % L
    else:
        return (x - pos) % L

def rec(pos, b, e, distance, depth, prev_cw):
    if b == e:
        return distance
    else:
        dist_cw = distance + measure_distance(pos, X[e-1], True)
        dist_cc = distance + measure_distance(pos, X[b], False)
        if depth == 0:
            d_cw = rec(X[e-1], b, e - 1, dist_cw, depth + 1, True)
            d_cc = rec(X[b], b + 1, e, dist_cc, depth + 1, False)
            if d_cw > d_cc:
                return d_cw
            else:
                return d_cc
        elif prev_cw == False:
            d_cw = rec(X[e-1], b, e - 1, dist_cw, depth + 1, True)
            return d_cw
        else:
            # prev_cw == True
            d_cc = rec(X[b], b + 1, e, dist_cc, depth + 1, False)
            return d_cc

print(rec(0, 0, len(X), 0, 0, None))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)

L, N = map(int, input().split())
X = [int(input()) for _ in range(N)]
def measure_distance(pos, x, clockwise):
    if clockwise:
        return (pos - x) % L
    else:
        return (x - pos) % L

def rec(pos, b, e, distance, route):
    if b == e:
        #print(distance, route)
        #print(len(route))
        return distance
    else:
        dist_cw = distance + measure_distance(pos, X[e-1], True)
        dist_cc = distance + measure_distance(pos, X[b], False)
        if len(route) == 1 or dist_cw == dist_cc:
            d_cw = rec(X[e-1], b, e - 1, dist_cw, route + [str(X[e-1])])
            d_cc = rec(X[b], b + 1, e, dist_cc, route + [str(X[b])])
            if d_cw > d_cc:
                return d_cw
            else:
                return d_cc
        elif dist_cw > dist_cc:
            d_cw = rec(X[e-1], b, e - 1, dist_cw, route + [str(X[e-1])])
            return d_cw
        else:
            d_cc = rec(X[b], b + 1, e, dist_cc, route + [str(X[b])])
            return d_cc

print(rec(0, 0, len(X), 0, ["0"]))

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
l,n=map(int,input().split())
c=n
tree1=[i for i in range(1,200000)]
reversed_tree1=[l-i for i in reversed(tree1)]
tree=deque(tree1)
reversed_tree=deque(reversed_tree1)
if n%2 == 0:
  ans= sum(tree1)*2 + l*(n-1) +tree1[n//2] - sum(tree1[n//2:])*4
  ans2= sum(reversed_tree1)*2 + l*(n-1) +reversed_tree1[n//2] - sum(reversed_tree1[n//2:])*4
  n-=1
  c-=1
  ans3= ans-tree.popleft()*2-l+tree[n//2]*2
  ans= max(ans,ans3)
  ans4= ans2-reversed_tree.popleft()*2-l+(reversed_tree[n//2])*2
  ans2= max(ans2,ans4)
else:
  ans= sum(tree1)*2 + l*(n-1) - tree1[n//2] - sum(tree1[((n//2)+1):])*4
  ans3=ans
  ans2= sum(reversed_tree1)*2 + l*(n-1) - reversed_tree1[n//2] - sum(reversed_tree1[((n//2)+1):])*4
  ans4=ans2
for i in range(n//2):
  n-=1
  ans_stack= ans3-tree.popleft()*2-l+tree[(n-1)//2]+tree[(n+1)//2]
  ans= max(ans_stack,ans)
  if ans != ans_stack:
    break
  ans3=ans_stack
  n-=1
  ans_stack= ans3-tree.popleft()*2-l+tree[n//2]*2
  ans=max(ans_stack,ans)
  if ans != ans_stack:
    break
  ans3=ans_stack
n=c
for i in range(n//2):
  n-=1
  ans_stack= ans4-reversed_tree.popleft()*2-l+reversed_tree[(n-1)//2]+reversed_tree[(n+1)//2]
  ans2=max(ans_stack,ans2)
  if ans != ans_stack:
    break
  ans4=ans_stack
  n-=1
  ans_stack= ans4-reversed_tree.popleft()*2-l+reversed_tree[n//2]*2
  ans2=max(ans2,ans_stack)
  if ans != ans_stack:
    break
  ans4=ans_stack
print(max(ans,ans2))

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
l,n=map(int,input().split())
c=n
tree1=[int(i) for i in sys.stdin]
reversed_tree1=[l-i for i in reversed(tree1)]
tree=deque(tree1)
reversed_tree=deque(reversed_tree1)
if n%2 == 0:
  ans= sum(tree1)*2 + l*(n-1) +tree1[n//2] - sum(tree1[n//2:])*4
  ans2= sum(reversed_tree1)*2 + l*(n-1) +reversed_tree1[n//2] - sum(reversed_tree1[n//2:])*4
  n-=1
  c-=1
  ans3= ans-tree.popleft()*2-l+tree[n//2]*2
  ans= max(ans,ans3)
  ans4= ans2-reversed_tree.popleft()*2-l+(reversed_tree[n//2])*2
  ans2= max(ans2,ans4)
else:
  ans= sum(tree1)*2 + l*(n-1) - tree1[n//2] - sum(tree1[((n//2)+1):])*4
  ans3=ans
  ans2= sum(reversed_tree1)*2 + l*(n-1) - reversed_tree1[n//2] - sum(reversed_tree1[((n//2)+1):])*4
  ans4=ans2
while n>1:
  n-=1
  ans_stack= ans3-tree.popleft()*2-l+tree[(n-1)//2]+tree[(n+1)//2]
  ans= max(ans_stack,ans)
  ans3=ans_stack
  n-=1
  ans_stack= ans3-tree.popleft()*2-l+tree[n//2]*2
  ans=max(ans_stack,ans)
  ans3=ans_stack
print(max(ans,ans2))

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
l,n=map(int,input().split())
p=n//2
q=(n-1)//2
r=(n+1)//2
tree1=[int(i) for i in sys.stdin]
reversed_tree1=[l-i for i in tree1]
tree=deque(tree1)
reversed_tree=deque(reversed_tree1)
if n%2 == 0:
  ans= 1
  ans2= 1
  p-=1
  ans3= ans-tree.popleft()*2-l+tree[p]*2
  ans= max(ans,ans3)
  ans4= ans2-reversed_tree.popleft()*2-l+(reversed_tree[p])*2
  ans2= max(ans2,ans4)
else:
  ans= 1
  ans3=ans
  ans2= 1
  ans4=ans2
while len(tree)>1:
  q-=1
  r-=1
  ans_stack= ans3-tree.popleft()*2-l+tree[q]+tree[r]
  ans3=ans_stack
  p-=1
  ans_stack= ans3-tree.popleft()*2-l+tree[p]*2
  ans3=ans_stack
p=n//2
q=(n-1)//2
r=(n+1)//2
while len(tree)>1:
  q-=1
  r-=1
  ans_stack= ans4-reversed_tree.popleft()*2-l+reversed_tree[q]+reversed_tree[r]
  ans4=ans_stack
  p-=1
  ans_stack= ans4-reversed_tree.popleft()*2-l+reversed_tree[p]*2
  ans4=ans_stack
print(max(ans,ans2))

Submission status: Wrong Answer

Solution code:
l,n=map(int,input().split())
c=n
tree=[int(input()) for i in range(n)]
reversed_tree=[l-i for i in reversed(tree)]
if n%2 == 0:
  ans= sum(tree)*2 + l*(n-1) +tree[n//2] - sum(tree[n//2:])*4
  ans2= sum(reversed_tree)*2 + l*(n-1) +reversed_tree[n//2] - sum(reversed_tree[n//2:])*4
  n-=1
  c-=1
  ans= max(ans,ans-tree.pop(0)*2-l+tree[n//2]*2)
  ans2= max(ans2,ans2-reversed_tree.pop(0)*2-l+(reversed_tree[n//2])*2)
else:
  ans= sum(tree)*2 + l*(n-1) - tree[n//2] - sum(tree[((n//2)+1):])*4
  ans2= sum(reversed_tree)*2 + l*(n-1) - reversed_tree[n//2] - sum(reversed_tree[((n//2)+1):])*4
while n>1:
  n-=1
  ans= max(ans,ans-tree.pop(0)*2-l+tree[(n-1)//2]+tree[(n+1)//2])
  n-=1
  ans= max(ans,ans-tree.pop(0)*2-l+tree[n//2]*2)
n=c
while n>1:
  n-=1
  ans2= max(ans2,ans2-reversed_tree.pop(0)*2-l+reversed_tree[(n-1)//2]+reversed_tree[(n+1)//2])
  n-=1
  ans2= max(ans2,ans2-reversed_tree.pop(0)*2-l+reversed_tree[n//2]*2)
print(max(ans,ans2))

Submission status: Wrong Answer

Solution code:
l,n=map(int,input().split())
c=n
tree=[int(input()) for i in range(n)]
reversed_tree=[l-i for i in reversed(tree)]
if n%2 == 0:
  ans= sum(tree)*2 + l*(n-1) +tree[n//2] - sum(tree[n//2:])*4
  ans2= sum(reversed_tree)*2 + l*(n-1) +reversed_tree[n//2] - sum(reversed_tree[n//2:])*4
  n-=1
  c-=1
  ans= max(ans,ans-tree.pop(0)*2-l+tree[n//2]*2)
  ans2= max(ans2,ans2-reversed_tree.pop(0)*2-l+reversed_tree[n//2]*2)
else:
  ans= sum(tree)*2 + l*(n-1) - tree[n//2] - sum(tree[(n//2 +1):])*4
  ans2= sum(reversed_tree)*2 + l*(n-1) - reversed_tree[n//2] - sum(reversed_tree[(n//2 +1):])*4
while n>1:
  n-=1
  ans= max(ans,ans-tree.pop(0)*2-l+tree[(n-1)//2]+tree[(n+1)//2])
  n-=1
  ans= max(ans,ans-tree.pop(0)*2-l+tree[n//2]*2)
n=c
while n>1:
  n-=1
  ans2= max(ans2,ans2-reversed_tree.pop(0)*2-l+reversed_tree[(n-1)//2]+reversed_tree[(n+1)//2])
  n-=1
  ans2= max(ans2,ans2-reversed_tree.pop(0)*2-l+reversed_tree[n//2]*2)
print(max(ans,ans2))

Submission status: Wrong Answer

Solution code:
l,n=map(int,input().split())
c=n
tree=[int(input()) for i in range(n)]
reversed_tree=[l-i for i in reversed(tree)]
if n%2 == 0:
  ans= sum(tree)*2 + l*(n-1) +tree[n//2] - sum(tree[n//2:])*4
  ans2= sum(reversed_tree)*2 + l*(n-1) +reversed_tree[n//2] - sum(reversed_tree[n//2:])*4
  n-=1
  c-=1
  ans= max(ans,ans-tree.pop(0)*2-l+tree[n//2]*2)
  ans2= max(ans2,ans2-reversed_tree.pop(0)*2-l+reversed_tree[n//2]*2)
else:
  ans= sum(tree)*2 + l*(n-1) - tree[n//2] - sum(tree[(n//2 +1):])*4
  ans2= sum(reversed_tree)*2 + l*(n-1) - reversed_tree[n//2] - sum(reversed_tree[(n//2 +1):])*4
while n>1:
  n-=1
  ans= max(ans,ans-tree.pop(0)*2-l+tree[(n-1)//2]+tree[(n+1)//2])
  n-=1
  ans= max(ans,ans-tree.pop(0)*2-l+tree[n//2]*2)
n=c
while n>1:
  n-=1
  ans2= max(ans2,ans2-reversed_tree.pop(0)*2-l+reversed_tree[(n-1)//2]+reversed_tree[(n+1)//2])
  n-=1
  ans2= max(ans2,ans2-reversed_tree.pop(0)*2-l+reversed_tree[n//2]*2)
print(max(ans,ans2))

Submission status: Wrong Answer

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools


sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]


def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


L, N = LI()
X = [I() for i in range(N)]

#  options = [min(L-i, i) for i in X]
#  print(options)
results = []
def dfs(count, directions):
    #  print(count, directions)
    if count == N:
        # ここでようやく距離を計算
        result = 0
        options = [_ for _ in X]
        if directions[0] == 0:
            current_position = 0
        else:
            current_position = 10
        for direction in directions:
            if direction == 0:
                # 時計回り
                new_position = options.pop(0)
                if new_position < current_position:
                    result += L - (current_position - new_position)
                else:
                    result += new_position - current_position
            else:
                # 反時計回り
                new_position = options.pop()
                # 周長から時計回りの長さを引く
                if new_position > current_position:
                    result += L - (new_position - current_position)
                else:
                    result += current_position - new_position
            current_position = new_position
        #  print(result)
        results.append(result)
        return
    # 0が時計で1が反時計
    dfs(count + 1, directions + [0])
    dfs(count + 1, directions + [1])

dfs(0, [])
print(max(results))

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys

L, N = map(int, input().split())
X = np.array([int(sys.stdin.readline()) for _ in range(N)])
X2 = X[::-1]
Y1 = np.concatenate(([X[0]], X[1:] - X[:-1], [L - X[-1]]))
Y2 = Y1[::-1]
Z = np.concatenate((np.arange(N, -1, -2), np.arange(N - 1, -1, -2)[::-1]))


def myfunc(n, x):
    return x[n + (N - n + 1)//2 - 1] - 2 * x[n - 1] - (L - x[N - (N - n + 1)//2])


len1 = np.dot(Z, Y1)
len2 = np.dot(Z, Y2)
x1 = X.tolist()
x2 = X2.tolist()
ans = max(len1, len2)
for n in range(1, (N + 1) // 2):
    len1 += myfunc(n, x1)
    len2 += myfunc(n, x2)
    ans = max(ans, len1, len2)

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys

L, N = map(int, input().split())
X = np.array([int(sys.stdin.readline()) for _ in range(N)])
Y1 = np.concatenate(([X[0]], X[1:] - X[:-1], [L - X[-1]]))
Y2 = Y1[::-1]


def func(n):
    return np.concatenate((np.full(n + 1, N - n, dtype=np.int), np.arange(N - n - 2, -1, -2), np.arange(N - n - 1, -1, -2)[::-1]))


if N < 10000:
    ans = 0
    for n in range((N + 1) // 2):
        a = func(n)
        len1 = np.dot(a, Y1)
        len2 = np.dot(a, Y2)
        ans = max(ans, len1, len2)

    print(ans)
else:
    ans = 0
    for n in range(0, (N + 1) // 2, 100):
        a = func(n)
        i = n // 100
        len1 = np.dot(a, Y1)
        len2 = np.dot(a, Y2)
        ans = max(ans, len1, len2)

    print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys

L, N = map(int, input().split())
X = np.array([int(sys.stdin.readline()) for _ in range(N)])
Y1 = np.concatenate(([X[0]], X[1:] - X[:-1], [L - X[-1]]))
Y2 = Y1[::-1]


def func(n):
    return np.concatenate((np.full(n + 1, N - n, dtype=np.int), np.arange(N - n - 2, -1, -2), np.arange(N - n - 1, -1, -2)[::-1]))


ans = 0
flag1 = True
flag2 = True

for n in range(0, (N + 1) // 2):
    a = func(n)
    if flag1:
        len1 = np.dot(a, Y1)
        if ans - len1 > L:
            flag1 = False
            if flag2:
                break
    if flag2:
        len2 = np.dot(a, Y2)
        if ans - len2 > L:
            flag2 = False
            if flag1:
                break
    ans = max(ans, len1, len2)

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys

L, N = map(int, input().split())
X = np.array([int(sys.stdin.readline()) for _ in range(N)])
Y1 = np.concatenate(([X[0]], X[1:] - X[:-1], [L - X[-1]]))
Y2 = Y1[::-1]
Z = np.concatenate((np.arange(N, -1, -2), np.arange(N - 1, -1, -2)[::-1]))


def myfunc(n, Y):
    return np.sum(Y[n:n + (N - n + 1)//2]) - np.sum(Y[:n]) - np.sum(Y[-((N - n + 1)//2):])


len1 = np.dot(Z, Y1)
len2 = np.dot(Z, Y2)
if len1 >= len2:
    Y = Y1
    len_ = len1
else:
    Y = Y2
    len_ = len2
ans = len_
for n in range(1, (N + 1) // 2):
    len_ += myfunc(n, Y)
    ans = max(ans, len_)

print(ans)

Submission status: Wrong Answer

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

reverse_tree=[l-i for i in tree]
reverse_tree.reverse()

position=0
ans=0
flag=True

while len(tree)>0:
    if flag:
        if (tree[0]-position >= reverse_tree[0]+position):
            ans+= tree[0]-position
            position=tree.pop(0)
            reverse_tree.pop(-1)
        else:
            ans+= reverse_tree[0]+position
            position=l-reverse_tree.pop(0)
            tree.pop(-1)
            flag=False
    else:
        if (l-position+tree[0] >= position-l+reverse_tree[0]):
            ans+= l-position+tree[0]
            position=tree.pop(0)
            reverse_tree.pop(-1)
            flag=True
        else:
            ans+= position-l+reverse_tree[0]
            position=l-reverse_tree.pop(0)
            tree.pop(-1)

print(ans)

Submission status: Wrong Answer

Solution code:
l,n=map(int,input().split())
x_mat=[int(input()) for i in range(n)]
def count_walk(walk,now,mat):
    while(len(mat)!=0):
        rw=mat[0]-now if mat[0]>now else mat[0]-now+l
        lw=now-mat[-1]+l if now<mat[-1] else now-mat[-1]
        if rw>lw:
            walk+=rw
            now=mat.pop(0)
        else:
            walk+=lw
            now=mat.pop(-1)
    return walk
x_matr=x_mat[:]
walkr=count_walk(x_matr[0],x_matr.pop(0),x_matr)
x_matl=x_mat[:]
walkl=count_walk(l-x_matl[-1],x_matl.pop(-1),x_matl)
print(walkr if walkr>walkl else walkl)

Submission status: Wrong Answer

Solution code:
import sys
from itertools import accumulate

circumference, n = map(int, input().split())
lll = list(map(int, sys.stdin.readlines()))
rrr = [circumference - l for l in lll]
rrr.reverse()
lll = [0] + lll
rrr = [0] + rrr
acc_l = list(accumulate(lll))
acc_r = list(accumulate(rrr))

# print(lll)
# print(rrr)
# print(acc_l)
# print(acc_r)

ans = max(lll[-1], rrr[-1])
for take_l in range(1, n):
    take_r = n - take_l
    if take_l < take_r:
        # l last
        tmp_l = lll[take_l]
        tmp_l += 2 * acc_l[take_l - 1]
        tmp_l += 2 * (acc_r[take_r] - acc_r[take_r - take_l])
        # r last
        tmp_r = rrr[take_r]
        tmp_r += 2 * (acc_r[take_r - 1] - acc_r[take_r - 1 - take_l])
        tmp_r += 2 * acc_l[take_l]
    else:
        # l last
        tmp_l = lll[take_l]
        tmp_l += 2 * (acc_l[take_l - 1] - acc_l[take_l - 1 - take_r])
        tmp_l += 2 * acc_r[take_r]
        # r last
        tmp_r = rrr[take_r]
        tmp_r += 2 * acc_r[take_r - 1]
        tmp_r += 2 * (acc_l[take_l] - acc_l[take_l - take_r])
    ans = max(ans, tmp_l, tmp_r)
print(ans)

Submission status: Wrong Answer

Solution code:
L,N = map(int,input().split())
XN = list()
for i in range(N):
  XN.append(int(input()))
loc = 0
tidx = 0
bidx = N-1
rtn = 0
def compare_nearest(tj, bj):
  if bj-tj<2:
    return True
  else:
    neartdiff = XN[tj+1]-XN[tj]
    nearbdiff = XN[bj]-XN[bj-1]
    if neartdiff > nearbdiff:
      return True
    elif neartdiff < nearbdiff:
      return False
    else:
      return compare_nearest(tj+1, bj-1)
while tidx != bidx:
  tval = XN[tidx]
  bval = XN[bidx]
  difft = tval-loc
  diffb = loc-bval
  difft = difft if difft>0 else difft+L
  diffb = diffb if diffb>0 else diffb+L
  if difft > diffb:
    rtn += difft
    tidx += 1
    loc = tval
  elif difft < diffb:
    rtn += diffb
    bidx -= 1
    loc = bval
  else:
    if compare_nearest(tidx,bidx):
      rtn += difft
      tidx += 1
      loc = tval
    else:
      rtn += diffb
      bidx -= 1
      loc = bval
last = XN[bidx]-loc
last = abs(last) if last < 0 else L-last
print(rtn+last)

Submission status: Wrong Answer

Solution code:
l,n = map(int, input().split())
x = []
for i in range(n):
  x.append(int(input()))
y = 0
c = 0
for i in range(n):
  if x[0] >= y >= 0:
    if x[0] - y >= l - x[-1] + y:
      c += x[0] - y
      y = x[0]
      x.pop(0)
    else:
      c += l - x[-1] + y
      y = x[-1]
      x.pop(-1)
  else:
    if l - y + x[0] >= y - x[-1]:
      c += l - y + x[0]
      y = x[0]
      x.pop(0)
    else:
      c += y - x[-1]
      y = x[-1]
      x.pop(-1)
print(c)

Submission status: Wrong Answer

Solution code:
L, N = map(int, input().split())
tree_ls = [0]
for i in range(N):
  tree_ls.append(int(input()))
_sum = 0
present_pos = 0
while True:
  if len(tree_ls) < 2:
    break
  if present_pos == -1 or present_pos == len(tree_ls):
      for_dis = tree_ls[present_pos+1] - tree_ls[present_pos] + L
  else:
      for_dis = tree_ls[present_pos+1] - tree_ls[present_pos]
  if present_pos == 0:
      back_dis = L + tree_ls[present_pos] - tree_ls[present_pos-1]
  else:
      back_dis = tree_ls[present_pos] - tree_ls[present_pos-1]
  if for_dis > back_dis:
    _sum += for_dis
    tree_ls.pop(present_pos)
  else:
    _sum += back_dis
    tree_ls.pop(present_pos)
    present_pos -= 0
print(_sum)

Submission status: Wrong Answer

Solution code:
L, N = [int(s) for s in input().split()]
X_array = [int(input()) for _ in range(N)]

def get_distance_clockwise(x1, x2):
  return x2 - x1 if x2 - x1 > 0 else L + x2 - x1
def get_distance_anticlockwise(x1, x2):
  return L + x1 - x2 if x1 - x2 < 0 else x1 - x2

x_now = 0
distance_total = 0
for _ in range(N):
  distance_clockwise = get_distance_clockwise(x_now, X_array[0])
  distance_anticlockwise = get_distance_anticlockwise(x_now, X_array[-1])

  if distance_clockwise >= distance_anticlockwise:
    # print("clockwise %d" % distance_clockwise)
    distance_total += distance_clockwise
    x_now = X_array.pop(0)
  else:
    # print("anticlockwise %d" % distance_anticlockwise)
    distance_total += distance_anticlockwise
    x_now = X_array.pop(-1)
print(distance_total)

Submission status: Wrong Answer

Solution code:
l,n = tuple([int(i) for i in input().split()])
trees = []

for i in range(n):
  tree = int(input())
  trees.append(tree)
  
length = 0
position = 0
num = 0
for i in range(n):
  if abs(position-trees[0]) <= abs(position-trees[-1]):
    num = -1
  length += abs(position-trees[num])
  position = trees[num]
  trees.remove(trees[num])

print(length)

Submission status: Wrong Answer

Solution code:
l,n = tuple([int(i) for i in input().split()])
trees = []

for i in range(n):
  tree = int(input())
  trees.append(tree)
  
length = 0
for tree in trees:
  length += max(tree,l-tree)
  
print(length)

Submission status: Wrong Answer

Solution code:
l,n = tuple([int(i) for i in input().split()])
trees = []

for i in range(n):
  tree = int(input())
  trees.append(tree)
  
length = 0
for tree in trees:
  length += max(tree,10-tree)
print(length)

Submission status: Wrong Answer

Solution code:
l,n = map(int,input().split())
t = []
p = 0
for i in range(n):
    t.append(int(input()))
y = 0
for i in range(n):
    if min(t) >= min(list(map(lambda x: abs(x - l),t))):
        j = min(t)
        y += j
        t.pop(t.index(j))
        t = list(map(lambda x: x - j,t))
    else:
        j = min(list(map(lambda x: abs(x - l),t)))
        y += j
        t.pop(list(map(lambda x: abs(x - l),t)).index(j))
        t = list(map(lambda x: x + j,t))
print(y)

Submission status: Wrong Answer

Solution code:
l,n = map(int,input().split())
t = []
pt = []
p = 0
for i in range(n):
    t.append(int(input()))
pt.append(t)
pt.append(list(map(lambda x: abs(x - l),t)))
y = 0
for i in range(n):
    if min(pt[0]) > min(pt[1]):
        t = min(pt[0])
        y += t
        x = pt[0].index(t)
        pt[0].pop(x)
        pt[1].pop(x)
        pt[0] = list(map(lambda x : abs(x - t),pt[0]))
        pt[1] = list(map(lambda x: abs(x - l),pt[0]))
    else:
        t = min(pt[1])
        y += t
        x = pt[1].index(t)
        pt[0].pop(x)
        pt[1].pop(x)
        pt[0] = list(map(lambda x : abs(x + t),pt[0]))
        pt[1] = list(map(lambda x: abs(x - l),pt[0]))
print(y)