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: Time Limit Exceeded

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
from collections import deque
L, N  = list(map(int, input().split()))
X = [int(input()) for _ in range(N)]

X_min = sorted(X)
X_max = sorted(X, reverse=True)

ansMin = 0
Nowpos = 0

from copy import deepcopy

def calc(lst, nowpos):
    x_min  = sorted(lst)
    x_max  = sorted(lst, reverse=True)
    # print("nowpos: ", nowpos, x_min, x_max)

    ansMax = nowpos
    nn = len(lst)
    for i in range(nn//2):
        ansMax += nowpos + 2 * ((L-x_max[i])%L) + x_min[i] 
        nowpos = x_min[i]
    if nn % 2 == 1:
        ansMax += nowpos + ((L-x_max[nn//2]) % L )
    return ansMax


    
# cntclock -----------------------------------------------------
cntclkans = []
for i in range(N):
    Nowpos = X_min[i]
    argList = deepcopy(X_min[i+1:])
    v = calc(argList, Nowpos)
    cntclkans.append(v)
a = max(cntclkans)

X_min = [(L-x)%L for x in sorted(X_min, reverse=True)]
cntclkans = []
for i in range(N):
    Nowpos = X_min[i]
    argList = deepcopy(X_min[i+1:])
    v = calc(argList, Nowpos)
    cntclkans.append(v)
b = max(cntclkans)


# print(cntclkans)
print(max(a,b))
exit(0)



print(X_min, X_max)
for i in range(N//2):
    # print(ansMin, Nowpos %L, 2*X_min[i], (L-X_max[i]) % L )
    ansMin += ((L-Nowpos) % L)  + 2 * X_min[i] + ((L-X_max[i]) % L ) # (X_min[i] - Nowpos) + (X_max[i] - )
    Nowpos = X_max[i]
    print("a: ", ansMin, "nowpos: ", Nowpos)
if N % 2 == 1:
    print("N//2:", N//2, "X_min: ", X_min[N//2])
    ansMin += ((L-Nowpos) % L) + X_min[N//2]


ansMax = 0
Nowpos = 0
for i in range(N//2):
    # print(ansMax, Nowpos %L, 2*X_min[i], (L-X_max[i]) % L )
    # ansMax += ((L-Nowpos) % L)  + 2 * X_min[i] + ((L-X_max[i]) % L ) # (X_min[i] - Nowpos) + (X_max[i] - )
    ansMax += Nowpos + 2 * ((L-X_max[i])%L) + X_min[i]  # (X_min[i] - Nowpos) + (X_max[i] - )
    Nowpos = X_min[i]
    print("a:", ansMax, "Nowpos:", Nowpos)
if N % 2 == 1:
    ansMax += Nowpos + ((L-X_max[N//2]) % L )


print(ansMin, ansMax)

Submission status: Time Limit Exceeded

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

max = 0
for arr in itertools.product([True, False], repeat=N):
  x = list(X)
  total = 0
  now = 0
  for i in arr:
    if i:
      next = 0 if (now+1) >= len(x) else (now+1) 
      total += (x[next] - x[now]) if (x[next] - x[now]) > 0 else x[next] + (L - x[now])
    else:
      next = (len(x)-1) if (now-1) < 0 else (now-1)
      total += (x[now] - x[next]) if (x[now] - x[next]) > 0 else x[now] + (L - x[next])
    x.pop(now)
    now = next if next < now else (next-1)
  max = total if max < total else max

print(max)

Submission status: Time Limit Exceeded

Solution code:

import copy
L,N = map(int,input().split())

xleft = []
xright = []
for i in range(N):
    tmp = int(input())
    xleft.append(tmp)
    xright.append(L-tmp)

def dp(array,now):
    length = len(array)
    arr1 = copy.deepcopy(array)
    arr2 = copy.deepcopy(array)
    left = (arr1[0]-now)%L
    right = (L+now-arr2[-1])%L
    if length ==1:
        return max(left,right)
    elif length > 1:
        return max(dp(arr1[0:-1],arr1.pop(-1)) + right , dp(arr2[1:length],arr2.pop(0)) + left)
    else:
        return 0

print(dp(xleft,0))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Dec 29 18:42:51 2018

@author: Owner
"""


import collections
import scipy.misc
import sys
import numpy as np
import math
from operator import itemgetter
import itertools

def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(int(i))
    i += 1
  if n > 1:
    table.append(int(n))
  return table   

def digit(i):
    if i > 0:
        return digit(i//10) + [i%10]
    else:
        return []
"""
N, X = map(int, input().split())

x = [0]*N
x[:] = map(int, input().split())

P = [0]*M
Y = [0]*M
for m in range(M):
    P[m], Y[m] = map(int, input().split())
    
all(nstr.count(c) for c in '753')
"""

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

X = [0]*N
for n in range(N):
    X[n] = int(input())

lmax = [0]*N
for n in range(2**N):
    p_now = 0
    l=0
    pat = format(n, "b").zfill(N)
    X_cp = X[:]
    #print(pat)
    cnt =0
    for pat_now in pat:
        #print(pat_now)
        #print(X_cp)
        if int(pat_now):              
            if p_now < X_cp[0]:
                l =l + X_cp[0] - p_now
                p_now = X_cp.pop(0)
            else:
                l += L - p_now + X_cp[0]
                p_now = X_cp.pop(0)
        else:
            if p_now < X_cp[-1]:
                l += p_now + L - X_cp[-1]
                p_now = X_cp.pop(-1)
            else:
                l += p_now - X_cp[-1]
                p_now = X_cp.pop(-1) 
        if n == 0:
            pass
        else:
            if lmax[cnt] <= l:
                lmax[cnt] = l
            else:
                break
        cnt += 1
    if lmax[N-1] < l:
        lmax[N-1] = l
    #print(l)
print(lmax[N-1])

Submission status: Time Limit Exceeded

Solution code:
def func(i, j, p):

    global X, dp, used, L, N

    if used[i][j][p]:
        return dp[i][j][p]
    else:
        used[i][j][p] = True
        if i == j:
            return 0
        else:
            if p == 0:
                temp1 = X[i + 1] - X[i] + func(i + 1, j, 0)
                temp2 = X[i] + L - X[j] + func(i + 1, j, 1)
                temp = max(temp1, temp2)
            else:
                temp1 = X[j] - X[j - 1] + func(i, j - 1, 1)
                temp2 = L - X[j] + X[i] + func(i, j - 1, 0)
                temp = max(temp1, temp2)
            dp[i][j][p] = temp
            return temp

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

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

dp = [[[0] * 2 for _ in range(N)] for _ in range(N)]
used = [[[False] * 2 for _ in range(N)] for _ in range(N)]

ans = max(X[0] + func(0, N - 1, 0), L - X[-1] + func(0, N - 1, 1))

print(ans)

Submission status: Time Limit Exceeded

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

def walklen(posN, posT,dir,L):
    if posN < posT:
        if dir == 0:
            return posT - posN
        else:
            return L - (posT - posN)
    else:
        if dir == 0:
            return L - (posN - posT)
        else:
            return posN -posT

cand_num = 2**(N-1)
ans = []
for i in range(cand_num):
    st = "{:>0"+str(N-1)+"}"
    dirs = list(map(int,st.format(bin(i)[2:])))
    dist = 0
    pos = 0
    tempX = X.copy()
    for j in range(N-1):
        dist+= walklen(pos,tempX[dirs[j]*-1],dirs[j],L)
        pos = tempX[dirs[j]*-1]
        _ = tempX.pop(dirs[j]*-1)
    dist+= max(walklen(pos,tempX[0],0,L),walklen(pos,tempX[0],1,L))
    ans.append(dist)

print(max(ans))

Submission status: Time Limit Exceeded

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
    arr = list(X)
    for j in range(N):
      if i >> j & 1 == 0:
        sumLength += arr[0] - currentPos + (L if currentPos > arr[0] else 0)
        currentPos = arr.pop(0)
      else:
        sumLength += currentPos - arr[-1] + (L if currentPos < arr[-1] else 0)
        currentPos = arr.pop(-1)

    dp[i] = sumLength

  return max(dp)


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

print(solve(L, N, X))

Submission status: Time Limit Exceeded

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

d = {}
S = [(0, X, 0)]
ans = 0
def f(res, X, now):
    if len(X) == 0:
        return res

    left = (X[0] - now) % L
    right = (L + now - X[-1]) % L

    now = X[0]
    Y = tuple(X[1:])
    if d.setdefault((Y, now), -1) < res + left:
        d[(Y, now)] = res + left
        S.append((res + left, Y, now))

    now = X[-1]
    Y = tuple(X[:len(X) - 1])
    if d.setdefault((Y, now), -1) < res + right:
        d[(Y, now)] = res + right
        S.append((res + right, Y, now))

    return -1

while S != []:
    s = S.pop(0)
    r = f(s[0], s[1], s[2])
    if r > -1:
        ans = max(ans, r)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

l, n = [int(i) for i in input().split()]
X = [0] + [int(input()) for i in range(n)]
XJ = X[1:] + [l]

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

for j in range(n, 0, -1):
    for i in range(n):
        dp[0][i+1][j] = max(dp[0][i+1][j], dp[0][i][j] + X[i+1] - X[i], dp[1][i][j] + (l - XJ[j]) + X[i+1])
        dp[1][i][j-1] = max(dp[1][i][j-1], dp[0][i][j] + X[i] + (l - XJ[j-1]), dp[1][i][j] + XJ[j] - XJ[j-1])

ans = 0

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
fin = sys.stdin.readline
sys.setrecursionlimit(5000000)
from queue import deque
# from functools import lru_cache

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

# @lru_cache(None)
memo = [[[None] * 2  for _ in range(N + 1)] for _ in range(N + 1)]
def rec(i, j, front):
    if memo[i][j][front] is not None:
        return memo[i][j][front]
    else:
        if i == j:
            max_dist = 0
        else:
            head = X_list[i]
            tail = X_list[j - 1]
            if front == 1:
                k = X_list[i - 1]
                max_dist = max(rec(i + 1, j, 1) + head - k, rec(i, j - 1, 0) + L + k - tail)
            else:
                k = X_list[j]
                max_dist =  max(rec(i + 1, j, 1) + L + head - k, rec(i, j - 1, 0) + k - tail)
        memo[i][j][front] = max_dist
        return max_dist
print(max(rec(1, N, 1) + X_list[0], rec(0, N - 1, 0) + L - X_list[-1]))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8
import sys
sys.setrecursionlimit(100000)

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

X = []

for i in range(N):
    X.append(int(input()))
    
def recur(now, coord_list, dist, max_dist):
    if len(coord_list) == 0:
        return dist
    else:
        c_len = len(coord_list)
        if L * c_len + dist < max_dist:
            return 0
            
        left = coord_list[0]
        d = left-now
        left_max = recur(left, coord_list[1:], dist + d if d>0 else dist+(L + d), max_dist)
    
        right = coord_list[-1]
        d = now - right
        right_max = recur(right, coord_list[:-1], dist+d if d>0 else dist+(L+d), max_dist)
        return max(left_max, right_max)

print(recur(0, X, 0, 0))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
l, n = map(int, input().split())
tree = [int(input()) for i in range(n)]
now = 0
walk = 0

while(len(tree) != 0):
    i = 1
    while(not((now + i) % l in tree)):
        i += 1
    j = -1
    while(not((now + j) % l in tree)):
        j -= 1
    if i > -j: 
      now = (now + i) % l
      walk += i
    else:
      now = (now + j) % l
      walk += -j
    #print(now)
    tree.remove(now)
    
    #print(tree, now, l, walk)
print(walk)

Submission status: Time Limit Exceeded

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

d = {("S", 0, 0, 0): 0}
for _ in range(N):
    d_ = {}
    for (root, p, l, r), w in d.items():
        d_[(root+"L", X[l+1], l+1, r)] = w + X[l+1] - p
        d_[(root+"R", X[-(r+1)] - L, l, r+1)] = w + (L - X[-(r+1)]) + p
    max_d = max(d_.items(), key=lambda x: x[1])[1]
    d = {k: v for k, v in d_.items() if max_d >= v}
#     print(d)
# print(max(d.items(), key=lambda x: x[1]))
print(max(d.items(), key=lambda x: x[1])[1])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
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: Time Limit Exceeded

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

    def get_previous(self, taken):
        p = self.previous
        while p.x in taken:
            p = p.previous
        return p

    def get_next(self, taken):
        n = self.next
        while n.x in taken:
            n = n.next
        return n

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

    def far(self, L):
        p = L - self.previous.x + self.x
        n = self.next.x - self.x
        if p >= n:
            return p, self.previous
        else:
            return n, self.next


def 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.get_previous(taken)
        nn = i.get_next(taken)
        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

        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(solve(L, N, Xs))

Submission status: Time Limit Exceeded

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

d = {("S", 0, 0, 0, 0): 0}
for _ in range(N):
    d_ = {}
    for (root, p, l, r, f), w in d.items():
        if root[-1] == "R":
            if f == 0:
                d_[(root+"R", X[-(r+1)] - L, l, r+1, 1)] = w + (L - X[-(r+1)]) + p
            d_[(root+"L", X[l+1], l+1, r, 0)] = w + X[l+1] - p
        elif root[-1] == "L":
            if f == 0:
                d_[(root+"L", X[l+1], l+1, r, 1)] = w + X[l+1] - p
            d_[(root+"R", X[-(r+1)] - L, l, r+1, 0)] = w + (L - X[-(r+1)]) + p
        else:
            d_[(root+"L", X[l+1], l+1, r, 0)] = w + X[l+1] - p
            d_[(root+"R", X[-(r+1)] - L, l, r+1, 0)] = w + (L - X[-(r+1)]) + p

    d = d_
#     print(d)
# print(max(d.items(), key=lambda x: x[1]))
print(max(d.items(), key=lambda x: x[1])[1])

Submission status: Time Limit Exceeded

Solution code:
import sys
fin = sys.stdin.readline
sys.setrecursionlimit(10000000)
from queue import deque
from functools import lru_cache

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

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

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

    def get_previous(self, taken):
        p = self.previous
        while p.x in taken:
            p = p.previous
        return p

    def get_next(self, taken):
        n = self.next
        while n.x in taken:
            n = n.next
        return n

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

    def far(self, L):
        p = L - self.previous.x + self.x
        n = self.next.x - self.x
        if p >= n:
            return p, self.previous
        else:
            return n, self.next


def 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, ans):
        if len(taken) == len(linkedlist):
            return ans
        key = (i.x, tuple(sorted(taken)), ans)
        if key in memo:
            return memo[key]
        pp = i.get_previous(taken)
        nn = i.get_next(taken)
        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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Dec 29 18:42:51 2018

@author: Owner
"""


import collections
import scipy.misc
import sys
import numpy as np
import math
from operator import itemgetter
import itertools

def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(int(i))
    i += 1
  if n > 1:
    table.append(int(n))
  return table   

def digit(i):
    if i > 0:
        return digit(i//10) + [i%10]
    else:
        return []
"""
N, X = map(int, input().split())

x = [0]*N
x[:] = map(int, input().split())

P = [0]*M
Y = [0]*M
for m in range(M):
    P[m], Y[m] = map(int, input().split())
    
all(nstr.count(c) for c in '753')
"""

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

X = [0]*N
for n in range(N):
    X[n] = int(input())

lmax = 0
for n in range(2**N):
    p_now = 0
    l=0
    pat = format(n, "b").zfill(N)
    X_cp = X[:]
    #print(pat)
    for pat_now in pat:
        #print(pat_now)
        #print(X_cp)
        if int(pat_now):              
            if p_now < X_cp[0]:
                l =l + X_cp[0] - p_now
                p_now = X_cp.pop(0)
            else:
                l += L - p_now + X_cp[0]
                p_now = X_cp.pop(0)
        else:
            if p_now < X_cp[-1]:
                l += p_now + L - X_cp[-1]
                p_now = X_cp.pop(-1)
            else:
                l += p_now - X_cp[-1]
                p_now = X_cp.pop(-1)                                
    if lmax < l:
        lmax = l
    #print(l)
print(lmax)

Submission status: Time Limit Exceeded

Solution code:
import sys
fin = sys.stdin.readline
sys.setrecursionlimit(10000000)
from queue import deque
from functools import lru_cache

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: Time Limit Exceeded

Solution code:
#coding:utf-8
import sys
sys.setrecursionlimit(100000)

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

X = []

for i in range(N):
    X.append(int(input()))
    
def recur(now, coord_list, dist, max_dist):
    if len(coord_list) == 0:
        return dist
    else:
        left = coord_list[0]
        d = left-now
        left_max = recur(left, coord_list[1:], dist + d if d>0 else dist+(L + d), max_dist)
    
        right = coord_list[-1]
        d = now - right
        right_max = recur(right, coord_list[:-1], dist+d if d>0 else dist+(L+d), max_dist)
        return max(left_max, right_max)

print(recur(0, X, 0, 0))

Submission status: Time Limit Exceeded

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

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

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

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

    return a+L-b


#CANDI=[(N+1)//2,(N+1)//2-1,(N+1)//2+1]
#(i+2)//2*(-1)**i

ANS=0
for start in range(1,N+1):
    if start==0:
        continue

    s=start
    t=(s+(-1)**0)%(N+1)
    ANS1=0


    
    for i in range(2,N+3):
        ANS1+=LENG(X[s],X[t],X[start])
        #print(s,t,i,ANS1)
        
        s,t=t,(t-i*((-1)**i))%(N+1)

        

        if s==0:
            break
    #print(ANS1)

    s=start
    t=(s-(-1)**0)%(N+1)
    ANS2=0
    for i in range(2,N+3):
        ANS2+=LENG(X[s],X[t],X[start])
        #print(s,t,i,ANS2)
        s,t=t,(t+i*((-1)**i))%(N+1)

        if s==0:
            break
    #print(ANS2)

    ANS=max(ANS,ANS1,ANS2)

print(ANS)

Submission status: Time Limit Exceeded

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

ans = -1


st = []
cur = 0
left = lis[0] - cur if lis[0] > cur else lis[0] + (l - cur)
st.append([lis[1:], left, lis[0]])
right = cur - lis[-1] if cur > lis[-1] else cur + (l - lis[-1])
st.append([lis[:-1], right, lis[-1]])

while len(st) > 0:
    state = st.pop()
    if len(state[0]) == 0:
        ans = max(ans, state[1])
    else:
        tmp_lis = state[0]
        count = state[1]
        cur = state[2]
        left = tmp_lis[0] - cur if tmp_lis[0] > cur else tmp_lis[0] + (l - cur)
        st.append([tmp_lis[1:], count + left, tmp_lis[0]])
        right = cur - tmp_lis[-1] if cur > tmp_lis[-1] else cur + (l - tmp_lis[-1])
        st.append([tmp_lis[:-1], count + right, tmp_lis[-1]])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

INF = float('inf')

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

if N == 1:
    print(max(Xs[1], L - Xs[1]))
    sys.exit()

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

ans = 0
for A in range(N+1):
    for B in range(N+1):
        for C in range(2):
            ans = max(ans, dp[A][B][C])
print(ans)

Submission status: Time Limit Exceeded

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

d = {("", 0, 0, 0): 0}
for _ in range(N):
    d_ = {}
    for (root, p, l, r), w in d.items():
        d_[(root+"R", X[l+1], l+1, r)] = w + X[l+1] - p
        d_[(root+"L", X[-(r+1)] - L, l, r+1)] = w + (L - X[-(r+1)]) + p
    d = d_
    # print(d)
print(max(d.items(), key=lambda x: x[1])[1])

Submission status: Time Limit Exceeded

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

    def get_previous(self, taken):
        p = self.previous
        while p.x in taken:
            p = p.previous
        return p

    def get_next(self, taken):
        n = self.next
        while n.x in taken:
            n = n.next
        return n

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

    def far(self, L):
        p = L - self.previous.x + self.x
        n = self.next.x - self.x
        if p >= n:
            return p, self.previous
        else:
            return n, self.next


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

    i = linkedlist[0]
    ans = 0
    def dfs(i, taken, linkedlist, ans):
        if len(taken) == len(linkedlist):
            return ans
        pp = i.get_previous(taken)
        nn = i.get_next(taken)
        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

        p = dfs(pp, taken + [pp.x], linkedlist, ans + p_d)
        n = dfs(nn, taken + [nn.x], linkedlist, ans + n_d)
        return max(p, n)
    return dfs(linkedlist[0], [0], linkedlist, 0)

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

Submission status: Time Limit Exceeded

Solution code:
import functools
l, n = map(int, input().split())
xs = [int(input()) for i in range(n)]


@functools.lru_cache(maxsize=None)
def get_dist(x, i):
    return min(abs(xs[i] - x), abs(l + x - xs[i]), abs(l + xs[i] - x))


nearest_dist = max(xs[0], l - xs[-1])

if n == 1:
    print(nearest_dist)
    exit()
elif n == 2:
    print(max(nearest_dist, 2 * nearest_dist +
              min(xs[0], l - xs[-1]), xs[-1], l - xs[0]))
    exit()

max_dist = max(xs[-1], l - xs[0])

for i in range(0, n - 1):
    d = xs[i]
    x = xs[i]
    right = i + 1
    left = n - 1
    move_left = True
    while right != left:
        if move_left:
            d += (l - xs[left]) + x
            x = xs[left]
            left -= 1
        else:
            d += l - x + xs[right]
            x = xs[right]
            right += 1
        move_left = not move_left
    d += abs(xs[left] - x) if abs(xs[left] - x) >= l/2 else l - abs(xs[left] - x)
    max_dist = max(max_dist, d)
for i in range(1, n):
    move_left = False
    d = l - xs[i]
    x = xs[i]
    right = 0
    left = i - 1
    while right != left:
        if move_left:
            d += (l - xs[left]) + x
            x = xs[left]
            left -= 1
        else:
            d += l - x + xs[right]
            x = xs[right]
            right += 1
        move_left = not move_left
    d += abs(xs[left] - x) if abs(xs[left] - x) >= l/2 else l - abs(xs[left] - x)
    max_dist = max(max_dist, d)

print(max_dist)

Submission status: Time Limit Exceeded

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

ans = -1

st = []
cur = 0
left = lis[0] - cur if lis[0] > cur else lis[0] + (l - cur)
st.append([lis[1:], left, lis[0]])
right = cur - lis[-1] if cur > lis[-1] else cur + (l - lis[-1])
st.append([lis[:-1], right, lis[-1]])

while len(st) > 0:
    state = st.pop()
    if len(state[0]) == 0:
        ans = max(ans, state[1])
    else:
        tmp_lis = state[0]
        count = state[1]
        cur = state[2]
        left = tmp_lis[0] - cur if tmp_lis[0] > cur else tmp_lis[0] + (l - cur)
        st.append([tmp_lis[1:], count + left, tmp_lis[0]])
        right = cur - tmp_lis[-1] if cur > tmp_lis[-1] else cur + (l - tmp_lis[-1])
        st.append([tmp_lis[:-1], count + right, tmp_lis[-1]])

print(ans)