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().split())
x=[]
for i in range(n):
    x.append(int(input()))
def dfs(i,i2,count,ls,t):
    if i==n:
        return count
    else:
        #count=count+max(dfs(i+1,i+1,count+abs(x[i]-t),ls,x[i]),dfs(i+1,i,count+abs(x[ls]-l-t),ls-1,x[ls]))
        return max(dfs(i+1,i+1,count+abs(x[i]-t),ls,x[i]),dfs(i+1,i,count+abs(x[ls]-l-t),ls-1,x[ls]))
print(dfs(0,0,0,(len(x)-1),0))

Submission status: Runtime Error

Solution code:
from sys import stdin
L,N=[int(x) for x in stdin.readline().rstrip().split()]
for i in range(N):
    a.append([int(x) for x in stdin.readline().rstrip().split()])
a.insert(0,0)
a.append(L)
b=list(reversed(a))
a=numpy.array(a)
 
b=numpy.array(b)
 
a=a[1:]-a[:-1]
 
b=abs(b[1:]-b[:-1])
 
import numpy
resa = numpy.cumsum(a)
resb = numpy.cumsum(b)
 
 
ans=0
for i in range(N):
    if resa[0] > resb[0]:
        ans+=resa[0]
        resb=resb+resa[0]
        resa=resa-resa[0]
        resa=resa[resa!=0]
    else :
        ans+=resb[0]
        resb=resb-resb[0]
        resa=resa+resb[0]
        resb=resb[resb!=0]
print(ans)

Submission status: Runtime Error

Solution code:
#!C:\Users\t.kida\vs_code\atcoder\.venv\Scripts\python.exe

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

#distMemo = {}
def dist(p, trees):
#    key = str(p) + ":" + ".".join(map(str,trees))
#    if distMemo.get(key):
#        return distMemo[key]
    if len(trees) == 1:
        d = abs(trees[0] - p)
        return max(d, L - d)

    dl = 0
    dr = 0
    if (trees[0] < p):
        dl = (L - p + trees[0]) + dist(trees[0],trees[1:])
    else:
        dl = (trees[0] - p) +  dist(trees[0],trees[1:])
    
    if (p > trees[-1]):
        dr = (p - trees[-1]) + dist(trees[-1], trees[:-1])
    else:
        dr = (L - trees[-1] + p) + dist(trees[-1], trees[:-1])
#    distMemo[key] = max(dl,dr)
    return max(dl,dr)

print (dist(0,X))

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
L, N = map(int, input().split())
X = []
for i in range(N):
    X.append(int(input()))
left = X[0]
lcount = 0
rcount = -1
right = X[-1]
now = 0
ans = 0
if left >= L - right:
    ans += left
    side = 0
    now = left
    lcount += 1
    left = X[lcount]
    side = 0

else:
    ans += L - right
    side = 1
    now = right
    rcount -= 1
    right = X[rcount]
    side = 1

for i in range(N-1):
    if side == 0:
        
        if left - now > now + (L - right):
            ans += left - now
            now = left
            lcount += 1
            left = X[lcount]
            side = 0
        else:
            ans += now + (L - right)
            now = right
            rcount -= 1
            right = X[rcount]
            side = 1

    else:

        if L + left - now > now - right:
            ans += L + left - now
            now = left
            lcount += 1
            left = X[lcount]
            side = 0
        else:
            ans += now - right
            now = right
            rcount -= 1
            right = X[rcount]
            side = 1

print(ans)

Submission status: Runtime Error

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

Y =X
P =0
result_left=0
result_right=0
result=0
flg= True
flg2=True

if X[0] >L-X[N-1]:
    result_left =X[0]
    result_right=X[0]
    P=X[0]
    X.pop(0)
    Y.pop(0)
else:
    result_left =X[N-1]
    result_right=X[N-1]
    P=X[N-1]
    X.pop(N-1)
    Y.pop(N-1)


for i in range(N-1):
    if flg:
        result_left +=X[0]-P
        P=X[0]
        X.pop(0)
    else:
        result_left += L-X[N-i-2]+P
        P=X[N-i-2]
        X.pop(N-i-2)
    flg =not(flg)

for k in range(N-1):
    if flg:
        result_right += L-Y[N-k-2]+P
        P=Y[N-k-2]
        Y.pop(N-k-2)
    else:
        result_right +=Y[0]-P
        P=Y[0]
        Y.pop(0)
    flg =not(flg)

result =max(result_left,result_right)

print(result)

Submission status: Runtime Error

Solution code:
class obj():
    def __init__(self, x):
        self.x = x
        self.previous = None
        self.next = None

    def objcopy(self):
        o = obj(self.x)
        o.next = self.next
        o.previous = self.previous
        return o

    def __str__(self):
        return "%d (previous : %d, next : %d" % (self.x, self.previous.x, self.next.x)


def slow_solve(L, N, Xs):
    linkedlist = [obj(0)]
    for x in Xs:
        o = obj(x)
        if len(linkedlist):
            o.previous = linkedlist[-1]
            linkedlist[-1].next = o
        linkedlist.append(o)
    linkedlist[0].previous = linkedlist[-1]
    linkedlist[-1].next = linkedlist[0]
    memo = {}

    def dfs(i, taken):
        if len(taken) == N + 1:
            return 0
        key = (i.x, tuple(sorted(taken)))
        if key in memo:
            return memo[key]
        pp = i.previous.objcopy()
        nn = i.next.objcopy()
        p_d = i.x - pp.x if pp.x < i.x else L - pp.x + i.x
        n_d = nn.x - i.x if nn.x > i.x else L - i.x + nn.x

        pp.next = i.next
        nn.previous = i.previous
        p = dfs(pp, taken + [pp.x]) + p_d
        n = dfs(nn, taken + [nn.x]) + n_d
        memo[key] = max(p, n)
        return memo[key]

    return dfs(linkedlist[0], [0])


if __name__ == "__main__":
    l = input().split()
    L, N = int(l[0]), int(l[1])
    Xs = [int(input()) for _ in range(N)]
    print(slow_solve(L, N, Xs))

Submission status: Runtime Error

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

def check(now, x):
    if now < x[-1]:
        if x[0] - now > now + l - x[-1]:
            return [0, x[0], x[0]-now]
        elif x[0] - now < now + l -x[-1]:
            return [1, x[-1], now+l-x[-1]]
        else:
            if check(x[0], x[1:])[2] > check(x[-1], x[:-1])[2]:
                [0, x[0], x[0] - now]
            else:
                return [1, x[-1], now+l-x[-1]]
    elif now > x[-1]:
        if x[0] + l - now > now - x[-1]:
            return [0, x[0], x[0] + l -now]
        elif x[0] + l -now < now - x[-1]:
            return [1, x[-1], now-x[-1]]
        else:
            if check(x[0], x[1:])[2] > check(x[-1], x[:-1])[2]:
                return [0, x[0], x[0]+l-now]
            else:
                return [1, x[-1], now-x[-1]]
now = 0
ans = 0
for _ in range(n):
    flag, now, tmp = check(now, x)
    ans += tmp
    if flag:
        del x[-1]
    else:
        del x[0]

print(ans)

Submission status: Runtime Error

Solution code:
from sys import stdin
L,N=[int(x) for x in stdin.readline().rstrip().split()]
for i in range(N):
    a.append([int(x) for x in stdin.readline().rstrip().split()])
a.insert(0,0)
a.append(L)
b=list(reversed(a))
a=numpy.array(a)

b=numpy.array(b)

a=a[1:]-a[:-1]

b=abs(b[1:]-b[:-1])

import numpy
resa = numpy.cumsum(a)
resb = numpy.cumsum(b)


ans=0
for i in range(N):
    if resa[0] > resb[0]:
        ans+=resa[0]
        resb=resb+resa[0]
        resa=resa-resa[0]
        resa=resa[resa!=0]
    else :
        ans+=resb[0]
        resb=resb-resb[0]
        resa=resa+resb[0]
        resb=resb[resb!=0]
print(ans)

Submission status: Runtime Error

Solution code:
L, N = map(int, input().split())
X = []
for i in range(N):
    X.append(int(input()))
left = X[0]
lcount = 0
rcount = -1
right = X[-1]
now = 0
ans = 0
side = 1
for i in range(N):
    if side == 0:
      
        if left - now > now + (L - right):
            ans += left - now
            now = left
            lcount += 1
            left = X[lcount]
            side = 0
        else:
            ans += now + (L - right)
            now = right
            rcount -= 1
            right = X[rcount]
            side = 1

    else:
       
        if L + left - now > now - right:
            ans += L + left - now
            now = left
            lcount += 1
            left = X[lcount]
            side = 0
        else:
            ans += now - right
            now = right
            rcount -= 1
            right = X[rcount]
            side = 1

print(ans)

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <bitset>
#include <set>
using namespace std;

long long L, N;
vector<long long> X;

long long solve0(long long N, long long L, vector<long long> &X){
    vector<long long> Y(N+2, 0);
    for(long long i=1; i<=N; i++)
        Y[i] = Y[i-1] + X[i];

    long long ret = 0;
    for(long long i=1; i<N; i++){
        long long k = min(i, N-i);
        long long left = 2*(Y[i] - Y[i-k]);
        long long mid = L-X[i+1];
        long long right = 2*(-Y[i+k]+Y[i+1])+2*(k-1)*L;
        ret = max(ret, left+mid+right);
    }
    return ret;
}

long long solve1(long long N, long long L, vector<long long> &X){
    vector<long long> Y(N+2, 0);
    for(long long i=1; i<=N; i++)
        Y[i] = Y[i-1] + X[i];

    long long ret = 0;
    for(long long i=1; i<N; i++){
        long long k = min(i, N-i+1);
        long long left = X[i] + 2*(Y[i-1] - Y[i-k]);
        long long right = 2*(-Y[i+k-1]+Y[i])+2*(k-1)*L;
        ret = max(ret, left+right);
    }
    return ret;
}

int main(){
    cin >> L >> N;
    X.resize(N+2, 0);
    for(long long i=1; i<=N; i++)
        cin >> X[i];

    if(N == 1){
        cout << max(X[1], L-X[1]) << endl;
        return 0;
    }

    long long ans = 0;
    ans = max(ans, solve0(N, L, X));
    ans = max(ans, solve1(N, L, X));
    for(int i=1; i<=N; i++)
        X[i] = L - X[i];
    reverse(X.begin(), X.end());
    ans = max(ans, solve0(N, L, X));
    ans = max(ans, solve1(N, L, X));
    cout << ans << endl;
    return 0;
}

Submission status: Runtime Error

Solution code:
class obj():
    def __init__(self, x):
        self.x = x
        self.previous = None
        self.next = None

    def copy(self):
        o = obj(self.x)
        o.next = self.next
        o.previous = self.previous
        return o

    def __str__(self):
        return "%d (previous : %d, next : %d" % (self.x, self.previous.x, self.next.x)


def slow_solve(L, N, Xs):
    linkedlist = [obj(0)]
    for x in Xs:
        o = obj(x)
        if len(linkedlist):
            o.previous = linkedlist[-1]
            linkedlist[-1].next = o
        linkedlist.append(o)
    linkedlist[0].previous = linkedlist[-1]
    linkedlist[-1].next = linkedlist[0]
    memo = {}

    def dfs(i, taken):
        if len(taken) == N + 1:
            return 0
        key = (i.x, tuple(sorted(taken)))
        if key in memo:
            return memo[key]
        pp = i.previous.copy()
        nn = i.next.copy()
        p_d = i.x - pp.x if pp.x < i.x else L - pp.x + i.x
        n_d = nn.x - i.x if nn.x > i.x else L - i.x + nn.x

        pp.next = i.next
        nn.previous = i.previous
        p = dfs(pp, taken + [pp.x]) + p_d
        n = dfs(nn, taken + [nn.x]) + n_d
        memo[key] = max(p, n)
        return memo[key]

    return dfs(linkedlist[0], [0])

if __name__ == "__main__":
    l = input().split()
    L, N = int(l[0]), int(l[1])
    Xs = [int(input()) for _ in range(N)]
    print(slow_solve(L, N, Xs))

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
L,N = map(int, input().split()) 
X = []
for i in range(N):
    X.append(int(input())) 
P =0
result_left=0
result_right=0
result=0
flg= True
flg2=True

if X[0] >L-X[N-1]:
    result_left =X[0]
    result_right=X[0]
    P=X[0]
    X.pop(0)
else:
    result_left =X[N-1]
    result_right=X[N-1]
    P=X[N-1]
    X.pop(N-1)


for i in range(N-1):
    if flg:
        result_left +=X[0]-P
        P=X[0]
        X.pop(0)
    else:
        result_left += L-X[N-i-2]+P
        P=X[N-i-2]
        X.pop(N-i-2)
    flg =not(flg)

for i in range(N-1):
    if flg:
        result_right += L-X[N-i-2]+P
        P=X[N-i-2]
        X.pop(N-i-2)
    else:
        result_right +=X[0]-P
        P=X[0]
        X.pop(0)
    flg =not(flg)

result =max(result_left,result_right)

print(result)

Submission status: Runtime Error

Solution code:
import numpy as np
 
def solv(dp, x, left, right, teban):
	return 0
 
def main():
	l, n = map(int, input().split())
	x = np.zeros(n)
	for i in range(n):
		x[i] = int(input()) 
	dp = np.zeros((n, n))
	for i in range(n-1):
		init = max(x[i+1]-x[i], l-(x[i+1]-x[i]))
		dp[i][i+1], dp[i+1][i] = init, init
	dp[0][n-1] = x[0]
	dp[n-1][0] = x[n-1]
 
	print(solv(dp, x, 0, n-1, 0))
 
main()

Submission status: Runtime Error

Solution code:
#!C:\Users\t.kida\vs_code\atcoder\.venv\Scripts\python.exe
import numpy
import scipy

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

#distMemo = {}
def dist(p, trees):
    key = str(p) + ":" + ".".join(map(str,trees))
#    if distMemo.get(key):
#        return distMemo[key]
    if len(trees) == 1:
        d = abs(trees[0] - p)
        return max(d, L - d)

    dl = 0
    dr = 0
    if (trees[0] < p):
        dl = (L - p + trees[0]) + dist(trees[0],trees[1:])
    else:
        dl = (trees[0] - p) +  dist(trees[0],trees[1:])
    
    if (p > trees[-1]):
        dr = (p - trees[-1]) + dist(trees[-1], trees[:-1])
    else:
        dr = (L - trees[-1] + p) + dist(trees[-1], trees[:-1])
#    distMemo[key] = max(dl,dr)
    return max(dl,dr)

print (dist(0,X))

Submission status: Runtime Error

Solution code:
L,N = map(int, input().split()) 
X = []
for i in range(N):
    X.append(int(input())) 
P =0
result_left=0
result_right=0
result=0
flg= True
flg2=True

if X[0] >L-X[N-1]:
    result_left =X[0]
    result_right=X[0]
    P=X[0]
    X.pop(0)
else:
    result_left =X[N-1]
    result_right=X[N-1]
    P=X[N-1]
    X.pop(N-1)


for i in range(N-1):
    if flg:
        result_left +=X[0]-P
        P=X[0]
        X.pop(0)
    else:
        result_left += L-X[N-i-1]+P
        P=X[N-i-1]
        X.pop(N-i-1)
    flg =not(flg)

for i in range(N-1):
    if flg:
        result_right += L-X[N-i-1]+P
        P=X[N-i-1]
        X.pop(N-i-1)
    else:
        result_right +=X[0]-P
        P=X[0]
        X.pop(0)
    flg =not(flg)

result =max(result_left,result_right)

print(result)

Submission status: Runtime Error

Solution code:
l,n=map(int,input().split())
x=[int(input()) for i in range(n)]
y=x[::-1]
a=[]
b=[]
for j in x:
    a=abs(0-x[i])
    b=abs(l-y[i])
s=max(a[0],b[0])
for k in range(1,n):
    e+=max(a[k]+b[x])
print(e)

Submission status: Runtime Error

Solution code:
L,N = map(int, input().split()) 
X = []
for i in range(N):
    X.append(int(input())) 
P =0
result_left=0
result_right=0
result=0
flg= True
flg2=True

if X[0] >L-X[N-1]:
    result_left =X[0]
    result_right=X[0]
    P=X[0]
    X.pop(0)
else:
    result_left =X[N-1]
    result_right=X[N-1]
    P=X[N-1]
    X.pop(N-1)


for i in range(N-1):
    if flg:
        result_left +=X[0]-P
        P=X[0]
        X.pop(0)
    else:
        result_left += L-X[N-i-1]+P
        P=X[N-1]
        X.pop(N-1)
    flg =not(flg)

for i in range(N-1):
    if flg:
        result_right += L-X[N-i-1]+P
        P=X[N-1]
        X.pop(N-1)
    else:
        result_right +=X[0]-P
        P=X[0]
        X.pop(0)
    flg =not(flg)

result =max(result_left,result_right)

print(result)

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 right - left >1:
        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
    # else:
    #     if toLeft > toRight:
    #         ans += toLeft
    #         now = X[left]
    #         left += 1
    #         lr = 0
    #     else:
    #         ans += toRight
    #         now=X[right]
    #         right -= 1
    #         lr = 1
# 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:

print(ans)

Submission status: Runtime Error

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

k = 0
sum = 0
while i > 1
    if 10 + k - x[n-i] < x[i] - k:
        k = x[i]
        sum = sum + x[i] - k
        del x[i]
        n = n - 1
    else:
        k = x[n-i]
        sum = sum + 10 + k - x[n-i]
        del x[n-i]
        n = n - 1

print(sum)

Submission status: Runtime Error

Solution code:
L,N = map(int, input().split()) 
X = []
for i in range(N):
    X.append(int(input())) 
P =0
result_left=0
result_right=0
result=0
flg= True
flg2=True

if X[0] >L-X[N-1]:
    result_left =X[0]
    result_right=X[0]
    P=X[0]
    X.pop(0)
else:
    result_left =X[N-1]
    result_right=X[N-1]
    P=X[N-1]
    X.pop(N-1)


for i in range(N-1):
    if flg:
        result_left +=X[0]-P
        P=X[0]
        X.pop(0)
    else:
        result_left += L-X[N-1]+P
        P=X[N-1]
        X.pop(N-1)
    flg =not(flg)

for i in range(N-1):
    if flg:
        result_right += L-X[N-1]+P
        P=X[N-1]
        X.pop(N-1)
    else:
        result_right +=X[0]-P
        P=X[0]
        X.pop(0)
    flg =not(flg)

result =max(result_left,result_right)

print(result)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
L,N = map(int,input().split())
x = []
for _ in range(N):
    x.append(int(input()))
x.sort()
solution = [[[0 for _ in range(N)] for _ in range(N)] for _ in range(N)]
def next(i,d):
    return((i+d)%N)
def prev(i,d):
    return((i-d)%N)
diff = 0
def to(i,j):
    #反時計回りi to j
    return((x[j]-x[i])%L)
for i in range(N):
    k = next(i,1)
    kk = prev(i,1)
    solution[i][diff][k] = max((x[i]-x[k])%L,(x[k]-x[i])%L)
    solution[i][diff][kk] = max((x[i]-x[kk])%L,(x[kk]-x[i])%L)
diff = 1
while diff < N-1:
    for i in range(N):
        j = next(i,diff)
        k = next(i,diff+1)
        kk = prev(i,1)
        l = next(i,diff-1)
        m = next(i,1)
        solution[i][diff][k] = max(solution[m][diff-1][i] + to(k,i),solution[i][diff-1][j] + to(j,k))
        solution[i][diff][kk] = max(solution[m][diff-1][i] + to(kk,i),solution[i][diff-1][j] + to(j,kk))
    diff += 1
right = solution[0][N-2][N-1]
left = solution[1][N-2][0]
answer = max(x[0] + left, L-x[N-1] + right)
print(answer)

Submission status: Runtime Error

Solution code:
#!C:\Users\t.kida\vs_code\atcoder\.venv\Scripts\python.exe
import numpy
import scipy

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

distMemo = {}
def dist(p, trees):
    key = str(p) + ":" + ".".join(map(str,trees))
    if distMemo.get(key):
        return distMemo[key]
    if len(trees) == 1:
        d = abs(trees[0] - p)
        return max(d, L - d)

    dl = 0
    dr = 0
    if (trees[0] < p):
        dl = (L - p + trees[0]) + dist(trees[0],trees[1:])
    else:
        dl = (trees[0] - p) +  dist(trees[0],trees[1:])
    
    if (p > trees[-1]):
        dr = (p - trees[-1]) + dist(trees[-1], trees[:-1])
    else:
        dr = (L - trees[-1] + p) + dist(trees[-1], trees[:-1])
    distMemo[key] = max(dl,dr)
    return distMemo[key]

print (dist(0,X))

Submission status: Runtime Error

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

while(len(sotai)):
    if (sotai[0] == l-sotai[-1]):
        if sotai[1]-sotai[0] > sotai[-1]-sotai[-2]:
            will = sotai[-1]
        else:
            will = sotai[0]
    else:
        will = max(sotai[0], l-sotai[-1])


    counter += will
    now = will

    if will == sotai[0]:
        sotai.pop(sotai.index(will))
        sotai = [num-will for num in sotai]
        print(sotai)
    elif will == l-sotai[-1]:
        sotai.pop(sotai.index(l-will))
        sotai = [num+will for num in sotai]
        print(sotai)
    now = 0

print(counter)

Submission status: Runtime Error

Solution code:
L,N=map(int,input().split())
R = range(N)
Xs = [int(input()) for _ in R]
Visited = [False]*N
def dfs(cur, vst):
    if vst==set():
        return max(dfs(0,{0})+Xs[0], dfs(N-1,{N-1})+L-Xs[-1])
    elif len(vst) == N: return 0
    else:
        i=cur+1
        while 1:
            if i>=N:i -= N
            if i in vst:i += 1
            else:break
        right = Xs[i]-Xs[cur]
        if right<0:right+=L
        j=cur-1
        while 1:
            if j<0:j += N
            if j in vst:j -= 1
            else:break
        left = Xs[cur]-Xs[j]
        if left<0:left+=L
        return max(dfs(i, vst|{i})+right, dfs(j, vst|{j})+left)
        
print(dfs(0, set()))

Submission status: Runtime Error

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

while(len(sotai)):
    if (sotai[0] == l-sotai[-1]):
        if sotai[1]-sotai[0] < sotai[-1]-sotai[-2]:
            will = sotai[-1]
        else:
            will = sotai[0]
    else:
        will = max(sotai[0], l-sotai[-1])


    counter += will
    now = will

    if will == sotai[0]:
        sotai.pop(sotai.index(will))
        sotai = [num-will for num in sotai]
        print(sotai)
    elif will == l-sotai[-1]:
        sotai.pop(sotai.index(l-will))
        sotai = [num+will for num in sotai]
        print(sotai)
    now = 0

print(counter)

Submission status: Runtime Error

Solution code:
import random
import math

from collections import OrderedDict




L,N=[int(i) for i in input().split()]

now=0

start=True

x=[]
rx=[]
check=[]

def mvr(now):
    nr= now-1 if now>0 else len(x)-1
    if(check[nr]):
        return mvr(nr)
    else:
        return nr

def mvl(now):
    nl= now+1 if now<len(x)-1 else 0
    if(check[nl]):
        return mvl(nl)
    else:
        return nl




for i in range(0,N):
    x.append(int(input()))
    rx.append(L-x[i])
    check.append(False)


#x.pop(1)

sum=0
if x[0]>rx[N-1]:
    now=0
    sum+=x[now]
else:
    now=N-1
    sum+=rx[now]
check[now]=True
#x.pop(now)
#rx.pop(now)

for i in range(0,N-1):
    nl=mvl(now)
    nr=mvr(now)
    #print("nl",nl)
    if(nl>now):
        tl=x[nl]-x[now]
    else:
        #print('{} {}'.format(nl,now))
        #print(x[nl])
        #print(x[now])
        tl=x[nl]+rx[now]
    if(nr<now):
        tr=rx[nr]-rx[now]
    else:
        tr=rx[nr]+x[now]

    if(tl>tr):
        now=nl
        sum+=tl
    else:
        now=nr
        sum+=tr
    check[now]=True
    #print('tl={} tr={}'.format(tl,tr))
    #x.pop(now)
    #rx.pop(now)

print(sum)

Submission status: Runtime Error

Solution code:
import random
import math

from collections import OrderedDict




L,N=[int(i) for i in input().split()]

now=0

start=True

x=[]
rx=[]
check=[]

def mvr(now):
    nr= now-1 if now>0 else len(x)-1
    if(check[nr]):
        return mvr(nr)
    else:
        return nr

def mvl(now):
    nl= now+1 if now<len(x)-1 else 0
    if(check[nl]):
        return mvl(nl)
    else:
        return nl




for i in range(0,N):
    x.append(int(input()))
    rx.append(L-x[i])
    check.append(False)


#x.pop(1)

sum=0
if x[0]>rx[N-1]:
    now=0
    sum+=x[now]
else:
    now=N-1
    sum+=rx[now]
check[now]=True
#x.pop(now)
#rx.pop(now)

for i in range(0,N-1):
    nl=mvl(now)
    nr=mvr(now)
    #print("nl",nl)
    if(nl>now):
        tl=x[nl]-x[now]
    else:
        #print('{} {}'.format(nl,now))
        #print(x[nl])
        #print(x[now])
        tl=x[nl]+rx[now]
    if(nr<now):
        tr=rx[nr]-rx[now]
    else:
        tr=rx[nr]+x[now]

    if(tl>tr):
        now=nl
        sum+=tl
    else:
        now=nr
        sum+=tr
    check[now]=True
    print('tl={} tr={}'.format(tl,tr))
    #x.pop(now)
    #rx.pop(now)

print(sum)

Submission status: Runtime Error

Solution code:
print "15"

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


def check(a,b,l):
    


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: Runtime Error

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

Submission status: Runtime Error

Solution code:
L, N = map(int,input().split())
X = [int(input()) for x in range(N)]
RX = [-abs(L - x) for x in reversed(X)]
ans = []
def saiki(pos, lx, rx, cnt, val):
    global ans
    if cnt == N:
        ans.append(val)
    else:
        lx1 = lx[1:]
        rx1 = rx[1:]
        lx2 = lx[:-1]
        rx2 = rx[:-1]
        saiki(lx[0],lx1,rx2 ,cnt + 1,val + abs(pos - lx[0]))
        saiki(rx[0],lx2 ,rx1,cnt + 1,val + abs(pos - rx[0]))

saiki(0, X, RX, 0, 0)
print(max(ans))

Submission status: Runtime Error

Solution code:
import sys
fin = sys.stdin.readline
from queue import deque
from functools import lru_cache
import pdb

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

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

Submission status: Runtime Error

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


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

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

    if flag:
        return max(burn(T[:-1], tmax, d_total + d_cw), burn(T[1:], tmin, d_total + d_ccw))

    if d_cw > d_ccw:
        return burn(T[:-1], tmax, d_total + d_cw)
    if d_cw < d_ccw:
        return burn(T[1:], tmin, d_total + d_ccw)
    if d_cw == d_ccw:
        return max(burn(T[:-1], tmax, d_total + d_cw), burn(T[1:], tmin, d_total + d_ccw))

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

print(burn(X, 0, 0, True))