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:
# -*- coding: utf-8 -*-
"""
Created on Sun Dec 30 09:04:16 2018

@author: Yamazaki Kenichi
"""
#L,N = map(int, input().split(' '))
#X = [int(input()) for i in range(N) ]

inp = input().split()
inp = [int(i) for i in inp]
L, N = inp[0],inp[1]
X = inp[2:]

X = [0] + X 
temp = L - X[1]
ans =  temp

itr1 = 0
itr2 = N

a = N%2

for i in range(-(N-1),N):
    if (i+a)%2 == 1:
        itr1 += 1
    else:
        itr2 -= 1

    if X[i]-X[i-itr1] >=0:
        minus = X[i]-X[i-itr1]
    else:
        minus = L+(X[i]-X[i-itr1])

    if X[i+itr2]-X[i] >=0:
        plus = X[i+itr2]-X[i]
    else:
        plus = L+(X[i+itr2]-X[i])
    temp = temp - minus + plus
    print(temp)
    ans = max(ans,temp)
print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import numpy as np
L, N = map(int, input().split())
X = np.array([0] + [int(input()) for _ in range(N)])
Y = np.array([0] + [L - x for x in X[1:]][::-1])

if N > 2000:
    print(0)
dp = np.zeros((N + 1, N + 1, 2), dtype=np.int32)
for i in range(N):
    for j in range(N):
        dp[i + 1][j][0] = np.amax(np.array([
                dp[i][j][0] + Y[i + 1] - Y[i],
                dp[i][j][1] + X[j] + Y[i + 1]]))
        dp[i][j + 1][1] = np.amax(np.array([
                dp[i][j][0] + X[j + 1] + Y[i],
                dp[i][j][1] + X[j + 1] - X[j]]))

ans = 0
for i in range(N + 1):
    ans = max(ans, dp[i][N - i][0], dp[i][N - i][1])

print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Dec 30 09:04:16 2018

@author: Yamazaki Kenichi
"""
inp = input().split()

#L,N = map(int, input().split(' '))
L,N = int(inp[0]),int(inp[1])
X = [int(i) for i in inp[2:]]

Xr = [0] + X
Xl = [0]
print(N)
for i in range(-1,-N-1,-1):
    Xl.append(X[N+i] - L)

Yr = ["d"]
for i in range(0,N):
    Yr.append( Xr[i+1] - Xr[i])

Yl = ["d"]+[L-X[N-1]]
Yl += Yr[::-1]

answer = 0
for itr in range(1,7):
    sum = 0
    counter = 1
    while counter <= itr:
        sum += Yr[counter]
        counter += 1
    turn = counter-1
    counter2 = 1
    sum2 = sum
    while counter <= N:
        if counter2 % 2 ==1:
            sum2 += Yl[counter2//2+1]
            sum += sum2 
        else:
            sum2 += Yr[turn + counter2//2]
            sum += sum2
        counter += 1
        counter2 += 1
    answer = max(answer,sum)

for itr in range(1,7):
    sum = 0
    counter = 1
    while counter <= itr:
        sum += Yl[counter]
        counter += 1
    turn = counter-1
    counter2 = 1
    sum2 = sum
    while counter <= N:
        if counter2 % 2 ==1:
            sum2 += Yr[counter2//2+1]
            sum += sum2 
        else:
            sum2 += Yl[turn + counter2//2]
            sum += sum2
        counter += 1
        counter2 += 1
    answer = max(answer,sum)
print(answer)

Submission status: Runtime Error

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

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

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

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

    return a+L-b

MIN=1
MAX=N


ANS=0
while MAX-MIN>1:

    start=(MAX+MIN)//2
    ANSX=0
    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)

    ANSX=max(ANS1,ANS2)
    
    start=(MAX+MIN)//2+1
    
    ANSY=0
    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)

    ANSY=max(ANS1,ANS2)

    if ANSX>ANSY:
        MAX=N//2
    else:
        MIN=N//2+1

    #print(ANSX,ANSY)

print(max(ANSX,ANSY))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Dec 30 09:04:16 2018

@author: Yamazaki Kenichi
"""

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

Xr = [0] + X
Xl = [0]

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

Yr = ["d"]
for i in range(0,N):
    Yr.append( Xr[i+1] - Xr[i])

Yl = ["d"]+[L-X[N-1]]
Yl += Yr[::-1]

answer = 0
for itr in range(1,7):
    sum = 0
    counter = 1
    while counter <= itr:
        sum += Yr[counter]
        counter += 1
    turn = counter-1
    counter2 = 1
    sum2 = sum
    while counter <= N:
        if counter2 % 2 ==1:
            sum2 += Yl[counter2//2+1]
            sum += sum2 
        else:
            sum2 += Yr[turn + counter2//2]
            sum += sum2
        counter += 1
        counter2 += 1
    answer = max(answer,sum)

for itr in range(1,7):
    sum = 0
    counter = 1
    while counter <= itr:
        sum += Yl[counter]
        counter += 1
    turn = counter-1
    counter2 = 1
    sum2 = sum
    while counter <= N:
        if counter2 % 2 ==1:
            sum2 += Yr[counter2//2+1]
            sum += sum2 
        else:
            sum2 += Yl[turn + counter2//2]
            sum += sum2
        counter += 1
        counter2 += 1
    answer = max(answer,sum)
print(answer)

Submission status: Runtime Error

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()
x = [ni() for _ in range(n)]

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

for total in range(1,n+1):
    for ccw in range(total+1):
        cw = total - ccw
        if ccw == 0:
            dp[ccw][cw][1] = dp[ccw][cw-1][1] + (right[cw-1] + l - right[cw]) % l
            
        elif cw == 0:
            dp[ccw][cw][0] = dp[ccw-1][cw][0] + (left[ccw] + l - left[ccw-1]) % l
        
        else:
            dp[ccw][cw][0] = max(dp[ccw-1][cw][1] + (left[ccw] + l - right[cw]) % l,
                                 dp[ccw-1][cw][0] + (left[ccw] + l - left[ccw-1]) % l)

            dp[ccw][cw][1] = max(dp[ccw][cw-1][1] + (right[cw-1] + l - right[cw]) % l,
                                 dp[ccw][cw-1][0] + (left[ccw] + l - right[cw]) % l)
ans = 0
for ccw in range(n+1):
    cw = n - ccw
    ans = max(ans, dp[ccw][cw][0], dp[ccw][cw][1])
    
print(ans)

Submission status: Runtime Error

Solution code:
def main():
    L, N = map(int, input().split())
    lines = sys.stdin.readlines()

    trees_ccw = [None] * N
    for i in range(N):
        trees_ccw[i] = int(lines[i])

    trees_cw = [L - trees_ccw[-(i+1)] for i in range(N)]
    trees_ccw_accum = [0] + [None] * N
    trees_cw_accum = [0] + [None] * N
    for i in range(N):
        trees_ccw_accum[i+1] = trees_ccw_accum[i] + trees_ccw[i]
        trees_cw_accum[i+1] = trees_cw_accum[i] + trees_cw[i]

    #print(trees_ccw)
    #print(trees_cw)
    #print(trees_ccw_accum)
    #print(trees_cw_accum)

    dist_max = 0

    for i in range(1,N+1):
        offset_left = i
        n_left = offset_left + (N-offset_left) // 2 #ccwの数
        n_right = N - n_left    #cwの数



        '''
        [print('L', end='') for _ in range(offset_left-1)]
        print('L', end='_')
        for i_ in range(N-offset_left):
            if i_ % 2 == 0:
                print('R', end='')
            else:
                print('L', end='')
        print()
        print(offset_left, n_left, n_right)
        '''


        dist_1 = 2 * (trees_ccw_accum[n_left] - trees_ccw_accum[i-1]) + 2 * trees_cw_accum[n_right]
        dist_2 = 2 * (trees_cw_accum[n_left] - trees_cw_accum[i-1]) + 2 * trees_ccw_accum[n_right]



        if (N-offset_left) % 2 == 0:
            dist_1 -= trees_ccw[n_left-1]
            dist_2 -= trees_cw[n_left-1]
        else:
            dist_1 -= trees_cw[n_right-1]
            dist_2 -= trees_ccw[n_right-1]

        if dist_max < dist_1:
            dist_max = dist_1

        if dist_max < dist_2:
            dist_max = dist_2

        #print(n_left, dist_1, dist_2, dist_max)

    print(dist_max)
    return

main()

Submission status: Runtime Error

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

X_c = [L - i for i in X]

def f(L, N, X, p, l, r, d_r):
    w = 0
    for _ in range(N - (l + r)):
        if d_r:  # L
            l += 1
            w += X[l] - p
            p = X[l]
            d_r = False
        else:  # R
            r += 1
            w += L - X[-r] + p
            p = X[-r] - L
            d_r = True
    return w

len_l = [X[i] + f(L, N, X, X[i], i, 0, True) for i in range(1, N)]
len_r = [X_c[-i] + f(L, N, X, X[-i] - L, 0, i, False) for i in range(1, N)]
max_l = max(len_l)
max_r = max(len_r)
print(max(max_l, max_r))

Submission status: Runtime Error

Solution code:
a = list(map(int,input().split()))

b = []
su =0 
s = 0
po = 0
for i in range(a[1]):
	b.append(int(input()))
	bbb.append(b[-(i+1)])
k = 0
ppp = 0
for i in range(1,a[1]):
	s = b[i-1]
	k = i
	po = b[i-1]
	s = b[i-1]
	for j in range(a[1]-i):
		if j % 2 == 0:
			s += a[0] - bbb[ppp] + po
			po = bbb[ppp]
			ppp += 1
		else:
			s += a[0] - po + b[k]
			po = b[k]
			k += 1
	su = max(su,s)
	ppp = 0
	s = bbb[i-1]
	k = i
	po = bbb[i-1]
	s = a[0]-bbb[i-1]
	for j in range(a[1]-i):
		if j % 2 != 0:
			s += a[0] - bbb[k] + po
			po = bbb[k]
			k += 1
		else:
			s += a[0] - po + b[ppp]
			po = b[ppp]
			ppp += 1
	su = max(su,s)
	ppp = 0

print(su)

Submission status: Runtime Error

Solution code:
a = list(map(int,input().split()))

b = []
bbb = []
su =0 
s = 0
po = 0
for i in range(a[1]):
	b.append(k)
	bbb.append(b[-1])
k = 0
ppp = 0
for i in range(1,a[1]):
	s = b[i-1]
	k = i
	po = b[i-1]
	s = b[i-1]
	for j in range(a[1]-i):
		if j % 2 == 0:
			s += a[0] - bbb[ppp] + po
			po = bbb[ppp]
			ppp += 1
		else:
			s += a[0] - po + b[k]
			po = b[k]
			k += 1
	su = max(su,s)
	ppp = 0
	s = bbb[i-1]
	k = i
	po = bbb[i-1]
	s = a[0]-bbb[i-1]
	for j in range(a[1]-i):
		if j % 2 != 0:
			s += a[0] - bbb[k] + po
			po = bbb[k]
			k += 1
		else:
			s += a[0] - po + b[ppp]
			po = b[ppp]
			ppp += 1
	su = max(su,s)
	ppp = 0

print(su)

Submission status: Runtime Error

Solution code:
import numpy as np

def solv(l, dp, x, left, right, teban):
	if(teban == 0):
		if(dp[left][right] == 0):
			dp[left][right] = max(solv(l, dp, x, left+1, right, 0)+(x[left+1]-x[left]), solv(l, dp, x, left+1, right, 1)+x[left]+(l-x[right]))
		return dp[left][right]
	else:
		if(dp[right][left] == 0):
			dp[right][left] = max(solv(l, dp, x, left, right-1, 1)+(x[right]-x[right-1]), solv(l, dp, x, left, right-1, 0)+(l-x[right])+x[left])
		return dp[right][left]

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
	
	#print(solv(l, dp, x, 0, n-1, 0)+x[0], solv(l, dp, x, 0, n-1, 1)+(l-x[n-1]))
	#print(dp)
	
	print(int(max(solv(l, dp, x, 0, n-1, 0)+x[0], solv(l, dp, x, 0, n-1, 1)+(l-x[n-1]))))
	#print(dp)
main()

Submission status: Runtime Error

Solution code:
# your code goes here
import numpy as np

def solv(l, dp, x, left, right, teban):
	if(teban == 0):
		if(dp[left][right] == 0):
			dp[left][right] = max(dp[left+1][right]+(x[left+1]-x[left]), dp[right][left+1]+x[left]+(l-x[right]))
		return dp[left][right]
	else:
		if(dp[right][left] == 0):
			dp[right][left] = max(dp[right-1][left]+(x[right]-x[right-1]), dp[left][right-1]+(l-x[right])+x[left])
		return dp[right][left]

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
	
	#print(solv(l, dp, x, 0, n-1, 0)+x[0], solv(l, dp, x, 0, n-1, 1)+(l-x[n-1]))
	#print(dp)
	print(int(max(solv(l, dp, x, 0, n-1, 0)+x[0], solv(l, dp, x, 0, n-1, 1)+(l-x[n-1]))))
	
main()

Submission status: Runtime Error

Solution code:
def evn(X,pos,N):
    #print(X,pos,N)
    if N == 1:
        return 0
    l = abs(X[(pos-1)%N] - X[pos])
    if (pos-1)%N == N-1:
        #print("head l")
        l = abs(M-X[(pos-1)%N]) + X[pos]

    r = abs(X[(pos+1)%N] - X[pos])
    if (pos+1)%N == 0:
        #print("tail r")
        r = X[(pos+1)%N] + abs(M-X[pos])

    del X[pos]

    #print(l,r)
    return max(l + evn(X[:],(pos-1)%(N-1),N-1),r + evn(X[:],(pos)%(N-1),N-1))


M,N = list(map(int,input().split()))
X = [0]
for i in range(N):
    X.append(int(input()))
print(evn(X[:],0,N+1))

Submission status: Runtime Error

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

import bisect


def solve(X, pos, ans):
    if len(X)==0:
        return ans
    tmp = []
    p = bisect.bisect_left(X, pos)
    if p==0:
        #cw
        d = X[0] - pos
        Y = X[:]
        del Y[0]
        tmp.append(solve(Y, X[0], ans+d))
        #ccw
        d = L-X[-1]+pos
        Y = X[:]
        del Y[-1]
        tmp.append(solve(Y, X[-1], ans+d))
    elif p==len(X):
        #cw
        d = X[0]+L-pos
        Y = X[:]
        del Y[0]
        tmp.append(solve(Y, X[0], ans+d))
        #ccw
        d = pos-X[-1]
        Y = X[:]
        del Y[-1]
        tmp.append(solve(Y, X[-1], ans+d))
    else:
        #cw
        d = pos-X[p]
        Y = X[:]
        del Y[p]
        tmp.append(solve(Y, X[p], ans+d))
        #ccw
        d = X[p+1]-pos
        Y = X[:]
        del Y[p+1]
        tmp.append(solve(Y, X[p+1], ans+d))
    return max(tmp)


pos = 0
ans = solve(X, 0, 0)
print(ans)

Submission status: Runtime Error

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

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

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

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

    return a+L-b

MIN=1
MAX=N


ANS=0
while MAX-MIN>1:

    start=N//2
    ANSX=0
    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)

    ANSX=max(ANS,ANS1,ANS2)
    
    start=N//2+1
    
    ANSY=0
    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)

    ANSY=max(ANS,ANS1,ANS2)

    if ANSX>ANSY:
        MAX=N//2
    else:
        MIN=N//2+1

print(max(ANSX,ANSY))

Submission status: Runtime Error

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])
        elif abs(x_now[a_x])<abs(y_now[a_y]) :
            a = a_y + 0
            c += abs(y_now[a_y])
		else :
            if (x_now[1]-x_now[0])>(y_now[n_now -1]-y_now[n_now -2]) :
                a = a_y + 0
                c += abs(y_now[a_y])
            else :
                a = a_x + 0
                c += abs(x_now[a_x])
        
        l_now = x[a] + 0
        x.pop(a)
        n_now -= 1
        
    print(c)

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-1])+abs(X[i]-X[j])
      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[j]-X[i-1])+abs(X[i]-X[j])
      j-=1
print(result)

Submission status: Runtime Error

Solution code:
def hoge(now, lista, ans):
    if abs(lista[0] - now) > abs(lista[-1] - now):
        a = abs(lista[-1] - now)
        b = L - now + lista[0]
    else:
        a = L - lista[-1] + now
        b = abs(lista[0] - now)

    if len(lista) == 1:
        print(ans + max(a, b))
        exit()

    if a > b:
        return hoge(lista[-1], lista[:-1], ans + a)
    elif b > a:
        return hoge(lista[0], lista[1:], ans + b)
    else:
        return max(hoge(lista[-1], lista[:-1], ans + a), hoge(lista[0], lista[1:], ans + b))

L, N = map(int, input().split())
X = [int(input()) for i in range(N)]
if N > 2000:
    print(0)
    exit()
hoge(0, X, 0)

Submission status: Runtime Error

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

Y = [L - x for x in X]
ans = 2*sum(X[:(N-1)//2+1]) + 2*sum(Y[-1:(N-1)//2:-1]) - min(X[(N-1)//2], Y[N//2])

print(ans)

Submission status: Runtime Error

Solution code:
import copy
def A(y):
    a=y[0]
    b=y[1]
    x=y[2]
    if x[a]>b:
        m=x[a]-b
    else:
        m=x[a]+l-b
    if x[a-1]<b:
        n=b-x[a-1]
    else:
        n=b+l-x[a-1]
    if m>n:
        b=x[a]
        x.pop(a)
        return [a,b,x,m]
    elif n>m:
        b=x[a-1]
        x.pop(a-1)
        if a!=0:
            a-=1
        return [a,b,x,n]
    else:
        if len(x)==1:
            return [0,0,0,m]
        x1=copy.copy(x)
        b1=x1[a]
        x1.pop(a)
        y1=A([a,b1,x1,0])
        x2=copy.copy(x)
        b2=x2[a-1]
        x2.pop(a-1)
        if a!=0:
            a2=a-1
        else:
            a2=a
        y2=A([a2,b2,x2,0])
        if y1[3]>y2[3]:
            return [a,b1,x1,m]
        else:
            return [a2,b2,x2,n]
        
l,n=map(int,input().split())
x=[]
for i in range(n):
    x.append(int(input()))
y=[0,0,x,0]
ans=0
for i in range(n):
    y=A(y)
    ans+=y[3]
print(ans)

Submission status: Runtime Error

Solution code:
def main(c, N, lenlist):
  state = 0
  result = 0
  first = 0
  end = len(lenlist) - 1
  while(first < end):
    if(first > 0 and end < len(lenlist)-1):
      if(state == lenlist[end + 1]):
        tofirst = c - state + lenlist[first]
        toend = state - lenlist[end]
      else:
        tofirst = lenlist[first] - state
        toend = c - lenlist[end] + state
    else:
      if(state == 0):
        tofirst = lenlist[first] - state
        toend = c - lenlist[end] 
      else:
        if(first == 0):
          tofirst = c - state + lenlist[first]
          toend = state - lenlist[end]
        else:
          tofirst =lenlist[first] -state
          toend = c -lenlist[end] + state
    if(tofirst > toend):
      result += tofirst
      state = first
      first += 1
    else:
      result += toend
      state = end
      end += 1
  tofirst = lenlist[first] - state
  toend = c - lenlist[end] + state
  result += max(tofirst, toend)
  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: Runtime Error

Solution code:
def solve(L, N, X):
  dp = [0 for i in range(2 ** N)]
  for i in range(2 ** N):
    sumLength = 0
    currentPos = 0
    s = 0
    e = len(X) - 1
    for j in range(N):
      if i >> j & 1 == 0:
        sumLength += X[s] - currentPos + (L if currentPos > X[s] else 0)
        currentPos = X[s]
        s += 1
      else:
        sumLength += currentPos - X[e] + (L if currentPos < X[-1] else 0)
        currentPos = X.pop(-1)
        e -= 1

    dp[i] = sumLength

  return max(dp)


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

print(solve(L, N, X))

Submission status: Runtime Error

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

    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
        nn = i.next
        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

        tmp = pp.next
        pp.next = i.next
        p = dfs(pp, taken + [pp.x]) + p_d
        pp.next = tmp

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

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


# assert (slow_solve(10, 3, [2, 7, 9]) == 15)
# assert (slow_solve(10, 6, [1, 2, 3, 6, 7, 9]) == 27)
# assert (slow_solve(314159265, 7,
#                    [21662711, 77271666, 89022761, 156626166, 160332356, 166902656, 298992265]) == 1204124749)
# print("Test OK")

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= []
for i in range(n):
    x.append(int(input()))
now = 0
i =0
j = 0
ans = 0
while i + j < n:
    if x[i]-now > l + now - x[n-1-j]:
        ans += x[i]-now
        now = x[i]
        print(x)
        i += 1
    else:
        ans += l + now - x[n-1-j]
        now = x[n-1-j]-now
        print(x[i])
        j += 1
print(ans)

Submission status: Runtime Error

Solution code:
def hoge(now, lista, ans):
    if abs(lista[0] - now) > abs(lista[-1] - now):
        a = abs(lista[-1] - now)
        b = L - now + lista[0]
    else:
        a = L - lista[-1] + now
        b = abs(lista[0] - now)

    if len(lista) == 1:
        print(ans + max(a, b))
        exit()

    if a > b:
        return hoge(lista[-1], lista[:-1], ans + a)
    elif b > a:
        return hoge(lista[0], lista[1:], ans + b)
    else:
        return max(hoge(lista[-1], lista[:-1], ans + a), hoge(lista[0], lista[1:], ans + b))

L, N = map(int, input().split())
X = [int(input()) for i in range(N)]
if N > 2000:
    exit()
hoge(0, X, 0)

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
        nn = i.next
        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

        tmp = pp.next
        pp.next = i.next
        p = dfs(pp, taken + [pp.x]) + p_d
        pp.next = tmp

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

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


# assert (slow_solve(10, 3, [2, 7, 9]) == 15)
# assert (slow_solve(10, 6, [1, 2, 3, 6, 7, 9]) == 27)
# assert (slow_solve(314159265, 7,
#                    [21662711, 77271666, 89022761, 156626166, 160332356, 166902656, 298992265]) == 1204124749)
# print("Test OK")

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:

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

ans = 0

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


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


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

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



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

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


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from sys import stdin
import numpy
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])
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 = [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]:
                return [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)