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

def main():
    L,N = map(int,input().split())
    pos = [int(input()) for _ in range(N)]
    diff = max(pos[-1],L-pos[0])
    for i in range(N-1):
        u = pos[i:]
        v = pos[:(N-i)]
        d = len(u)
        if d%2 == 0:
            diff = max(diff,(d-1)*L+2*sum(u[:d//2])-2*sum(u[d//2:])+u[d//2],\
                d*L+2*sum(v[:(d//2)])-2*sum(v[(d//2):])-v[d//2-1])
        else:
            diff = max(diff,(d-1)*L+2*sum(u[:(d//2+1)])-2*sum(u[(d//2+1):])-u[d//2],\
                d*L+2*sum(v[:(d//2)])-2*sum(v[(d//2):])+v[d//2])
            
    print(diff)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
import sys
sys.setrecursionlimit(10**7)


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

X.sort()
X = tuple(X)
def dist(fr, to, d):
    if d == 0: #counter clock  
        if fr > to:
            return to + L - fr
        else:
            return to - fr
    else:
        if fr > to:
            return fr - to
        else:
            return fr + L - to

@lru_cache(maxsize = 10 ** 7)
def max_dist(now = 0, subset = X):
    if len(subset) == 1:
        return max(dist(now, subset[0], 0), dist(now, subset[0], 1))
    
    c_clock = dist(now, subset[0], 0) + max_dist(subset[0], subset[1:])
    clock = dist(now, subset[-1], 1) + max_dist(subset[-1], subset[:-1])
    return max(clock, c_clock)

print(max_dist())

Submission status: Time Limit Exceeded

Solution code:
l,n,*ki=map(int,open(0).read().split())
fmax=rmax=0
fl=[]

for ii in range(n):
    f=0
    x=ki[ii:]
    lx=n-ii
    for i in x[:(lx+1)//2]:
        f+=i*2
    for i in x[(lx+1)//2:]:
        f+=(l-i)*2
    if lx%2:
        sa = x[lx//2]
    else:
        sa = l - x[lx // 2]
    f-=sa
    fl.append(f)

for ii in range(n):
    r=0
    x=ki[:n-ii]
    lx=n-ii
    for i in x[:lx//2]:
        r += i * 2
    for i in x[lx//2:]:
        r+=(l-i)*2
    if lx%2:
        sa = l - x[(lx-1) // 2]
    else:
        sa = x[(lx-1)//2]
    r-=sa
    fl.append(r)

print(max(fl))

Submission status: Time Limit Exceeded

Solution code:
l,n,*ki=map(int,open(0).read().split())
fmax=rmax=0

for ii in range(n):
    f=0
    x=ki[ii:]
    lx=n-ii
    for i in x[:(lx+1)//2]:
        f+=i*2
    for i in x[(lx+1)//2:]:
        f+=(l-i)*2
    if lx%2:
        sa = x[lx//2]
    else:
        sa = l - x[lx // 2]
    f-=sa
    fmax=max(fmax,f)

for ii in range(n):
    r=0
    x=ki[:n-ii]
    lx=n-ii
    for i in x[:lx//2]:
        r += i * 2
    for i in x[lx//2:]:
        r+=(l-i)*2
    if lx%2:
        sa = l - x[(lx-1) // 2]
    else:
        sa = x[(lx-1)//2]
    r-=sa
    rmax=max(rmax,r)

print(max(fmax,rmax))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
l,n=map(int,input().split())
tree=[int(input()) for i in range(n)]
def solve(i):
  tree_copy=[i for i in tree]
  if i!=0:
    del tree_copy[:i-1]
  ans=tree_copy.pop(0)
  stack=ans
  flag=False
  while len(tree_copy)>0:
    if flag:
      ans+= stack + tree_copy[0]
      stack= tree_copy.pop(0)
      flag=False
    else:
      ans+= stack + (l-tree_copy[-1])
      stack= l-tree_copy.pop(-1)
      flag=True
  return ans
got=0
for i in range(n):
  got=max(got,solve(i))
tree=[l-i for i in reversed(tree)]
for i in range(n):
  got=max(got,solve(i))
print(got)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import numpy as np
import sys

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


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


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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys

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


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


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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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


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


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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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


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


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


ans = 0
for n in range((N + 1) // 2):
    len_ = np.dot(func1(n), Y)
    ans = max(ans, len_)
    len_ = np.dot(func2(n), Y)
    ans = max(ans, len_)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
L, N = map(int, input().split())
X = [int(input()) for _ in range(N)]
ans = max(X[-1], L - X[0])


def f(l, r):
    nl = len(l)
    nr = len(r)
    if nl > nr:
        return max(
            2 * sum(l[-(nr + 1):-1]) + 2 * sum(r) + l[-1],
            2 * sum(l[-nr:]) + 2 * sum(r) - r[-1]
        )
    elif nl < nr:
        return max(
            2 * sum(r[-(nl + 1):-1]) + 2 * sum(l) + r[-1],
            2 * sum(r[-nl:]) + 2 * sum(l) - l[-1]
        )
    else:
        return 2 * sum(l) + 2 * sum(r) - min(l[-1], r[-1])


for i in range(1, N):
    ans = max(
        ans,
        f(
            X[:i],
            list(reversed([L - x for x in X[i:]]))
        )
    )
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

L,N = map(int, sys.stdin.readline().split())
X = [0]
for i in range(N):
    X.append(int(sys.stdin.readline()))
X.append(0)

# dp[n][a][c] = n本目の木を焼くまでの最大の歩行距離
#            （左にa回移動した状態、c=1なら最後は右）

dp = [[[0 for d in range(2)] for a in range(N+1)] for i in range(N+1)]
dp[0][0][0] = 0
dp[0][0][1] = 0
for n in range(1, N+1):
    for a in range(0, n+1):
        b = N - (n - a) + 1
        if a >= 1:
            dp[n][a][0] = max(dp[n][a][0], dp[n-1][a-1][0] + (X[a]-X[a-1]) % L)
            dp[n][a][0] = max(dp[n][a][0], dp[n-1][a-1][1] + (X[a]-X[b]) % L)
        if n - a >= 1:
            dp[n][a][1] = max(dp[n][a][1], dp[n-1][a][1] + (X[b+1]-X[b]) % L)
            dp[n][a][1] = max(dp[n][a][1], dp[n-1][a][0] + (X[a]-X[b]) % L)
    #print(dp[1:])

print(max(e for d1 in dp[N] for e in d1))

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(1<<N):
  lst = [x for x in X]
  d, pos = 0, 0
  lr = format(i, '0{}b'.format(N))
  for j in range(N):
    num = int(lr[j])
    move = [(lst[0]-pos)%L, (pos-lst[-1])%L]
    pos = lst[-num]
    d += move[num]
    lst.pop(-num)
  ans = max(ans, d)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
import sys

L,N = map(int, input().split())
X = [0]
for i in range(N):
    X.append(int(sys.stdin.readline()))

q = collections.deque()
q.append((0, 0, 0, 0))

max_sc = 0
try:
    while True:
        (n, l, cur, sc) = q.popleft()
        #print((n, l, cur, sc))
        if n == N:
            max_sc = max(max_sc, sc)
        else:
            q.append((n+1, l+1, X[l+1], sc + (X[l+1] - cur) % L))
            q.append((n+1, l,   X[N-(n+1-l)+1], sc + (cur - X[N-(n+1-l)+1]) % L))
except IndexError:
    pass

print(max_sc)

Submission status: Time Limit Exceeded

Solution code:
import collections

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

q = collections.deque()
q.append((0, 0, 0, 0))

max_sc = 0
try:
    while True:
        (n, l, cur, sc) = q.popleft()
        #print((n, l, cur, sc))
        if n == N:
            max_sc = max(max_sc, sc)
        else:
            q.append((n+1, l+1, X[l+1], sc + (X[l+1] - cur) % L))
            q.append((n+1, l,   X[N-(n+1-l)+1], sc + (cur - X[N-(n+1-l)+1]) % L))
except IndexError:
    pass

print(max_sc)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
ln = list(map(int,input().split()))
l = ln[0]
n = ln[1]
x = [0 for i in range(n+1)]
y = [0 for i in range(n+1)]
for i in range(n):
    x[i+1] = int(input())
    y[n-i] = l-x[i+1]
dp = [[[0 for i in range(2)] for i in range(n+1)] for i in range(n+1)]
for i in range(n+1):
    dp[i][0][0] = x[i]
    dp[0][i][1] = y[i]
for i in range(1,n+1):
    for j in range(1,n+1):
        dp[i][j][0] = max(dp[i-1][j][0]+x[i]-x[i-1], dp[i-1][j][1]+x[i]+y[j])
        dp[i][j][1] = max(dp[i][j-1][1]+y[j]-y[j-1], dp[i][j-1][0]+x[i]+y[j])
lmax = 0
for i in range(n):
    lcan = max(dp[i][n-i][0],dp[i][n-i][1])
    if lcan > lmax:
        lmax = lcan
print(lmax)

Submission status: Time Limit Exceeded

Solution code:
import sys

periphery, n = map(int, input().split())
xxx = list(map(int, sys.stdin.readlines()))
xxx.append(xxx[0] + periphery)
xxx.append(periphery - xxx[-2])
dp = [[0, 0] for _ in range(n + 1)]
for w in range(1, n):
    ndp = [[0, 0] for _ in range(n + 1)]
    for l in range(n - w):
        r = l + w
        pos_l, pos_l1, pos_r1, pos_r = xxx[l], xxx[l + 1], xxx[r - 1], xxx[r]
        pos_left_plant_left = dp[l + 1][0] + (pos_l1 - pos_l)
        pos_left_plant_right = dp[l][0] + (periphery - (pos_r - pos_l))
        pos_right_plant_left = dp[l + 1][1] + (periphery - (pos_r - pos_l))
        pos_right_plant_right = dp[l][1] + (pos_r - pos_r1)
        ndp[l][0] = max(pos_left_plant_left, pos_right_plant_left)
        ndp[l][1] = max(pos_left_plant_right, pos_right_plant_right)
    dp = ndp
print(max(dp[0][0] + xxx[0], dp[0][1] + xxx[-1]))

Submission status: Time Limit Exceeded

Solution code:
def is_even(num):
    return num % 2 == 0
def goback(M, x):
    k = M // 2
    if M == 0:
        return L - x[0]
    elif M == 1:
        return 2 * (L - x[1]) + x[0]
    elif is_even(M):
        return 2 * sum(x[0:k]) - 2 * sum(x[M - k + 1:M + 1]) - x[M - k] + L * (2 * k + 1)
    else:
        return 2 * sum(x[0:k]) + x[k] - 2 * sum(x[M - k:M + 1]) + L * 2 * (k + 1)

L, N = (int(i) for i in input().split())
points = []
ans = []
for i in range(0, N):
    points.append(int(input()))

for i in range(0, N):
    ans.append((goback(i, points)))

revpoints = [L - p for p in points[::-1]]
for i in range(0, N):
    ans.append((goback(i, revpoints)))

print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
f = input().split()
L = int(f[0])
N = int(f[1])
ls = []
dis = []
for i in range(N):
  ls.append(int(input()))
for l in ls:
  dis.append(L - l)
for_lst = []
dist_lst = []
for i in range(2**(N-1)):
  dist_lst.append(ls[0])
for i in range(2**(N-1)):
  dist_lst.append(dis[-1])
for i in range(len(dist_lst)):
  for_lst.append(bin(i)[2:].zfill(N))


for i in range(len(dist_lst)):
  dist = dis
  lst = ls
  for j in range(1, N):
    if for_lst[i][j-1] == '0':
      if for_lst[i][j] == '0':
        dist_lst[i] += lst[1]-lst[0]
        dist = dist[1:]
        lst = lst[1:]
      else:
        dist_lst[i] += lst[0]+dist[ - 1]
        dist = dist[1:]
        lst = lst[1:]
    else:
      if for_lst[i][j] == '0':
        dist_lst[i] += lst[0]+dist[ - 1]
        dist = dist[:-1]#len(dist) - 1]
        lst = lst[:-1]#len(dist) - 1]
      else:
        dist_lst[i] += dist[ -2] - dist[ - 1]
        dist = dist[:len(dist) - 1]
        lst = lst[:len(lst) - 1]
print(max(dist_lst))

Submission status: Time Limit Exceeded

Solution code:
f = input().split()
L = int(f[0])
N = int(f[1])
ls = []
dis = []
for i in range(N):
  ls.append(int(input()))
for l in ls:
  dis.append(L - l)
for_lst = []
dist_lst = []
for i in range(2**N):
  dist_lst.append(0)
for i in range(len(dist_lst)):
  for_lst.append(bin(i)[2:].zfill(N))
for i in range(len(dist_lst)):
  dist = dis
  lst = ls
  if for_lst[i][0] == '0': # 時計回りスタート
    dist_lst[i] += ls[0]
  else:
    dist_lst[i] += dis[ - 1]
  for j in range(1, N):
    if for_lst[i][j-1:j+1] == '00':
      dist_lst[i] += lst[1]-lst[0]
      dist = dist[1:]
      lst = lst[1:]
    elif  for_lst[i][j-1:j+1] == '01':
      dist_lst[i] += lst[0]+dist[ - 1]
      dist = dist[1:]
      lst = lst[1:]
    elif  for_lst[i][j-1:j+1] == '10':
      dist_lst[i] += lst[0]+dist[ - 1]
      dist = dist[:-1]#len(dist) - 1]
      lst = lst[:-1]#len(dist) - 1]
    else:
      dist_lst[i] += dist[ -2] - dist[ - 1]
      dist = dist[:len(dist) - 1]
      lst = lst[:len(lst) - 1]
print(max(dist_lst))

Submission status: Time Limit Exceeded

Solution code:
N, n = map(int, input().split())
a = [int(input()) for i in range(n)] 

# 0: Phai 1:trai
d = {(c,i,i):0 for c in range(2) for i in range(len(a))}

for l in range(1, len(a)):
    for i in range(len(a)-l):
        
        T = a[i+1] - a[i] + d[(0,i+1,i+l)]
        P = N - (a[i+l] - a[i]) + d[(1,i+1,i+l)]
        
        d[(0,i,i+l)] = max(T, P)
        
        T = a[i+l] - a[i+l-1] + d[(1,i,i+l-1)]
        P = N - (a[i+l] - a[i]) + d[(0,i,i+l-1)]
        d[(1,i,i+l)] = max(T, P)

print(max(N-a[-1]+d[(1,0,len(a)-1)], a[0] + d[(0,0,len(a)-1)]))

Submission status: Time Limit Exceeded

Solution code:
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][j] + X[i+1] - X[i], dp[1][i][j] + (l - XJ[j]) + X[i+1])
        dp[1][i][j-1] = max(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:
# _*_ coding:utf-8 _*_
#  Atcoder_Grand_Contest030-B
#  TODO  https://atcoder.jp/contests/agc030/tasks/agc030_b

def  maxDistance(pondLong,TreeNumber,leftTreePosition):
	rightTreePosition = [pondLong-x for x in leftTreePosition[::-1]]
	stopTreePositionRange = range(0,TreeNumber,+1)
	sumleftList = []
	sumrightList = []
	for i in stopTreePositionRange:
		sumleftList.append(0)
		sumleftList[i] = leftTreePosition[i]
		returnRange = range(0,TreeNumber-i-1,+1)
		leftPosition = i
		rightPosition = 0
		for x in returnRange:
			sumleftList[i] = sumleftList[i] + leftTreePosition[leftPosition] + rightTreePosition[rightPosition]
			if x % 2 == 0:
				leftPosition = leftPosition + 1
			else:
				rightPosition = rightPosition + 1
	# 時計回りの時の調査
	for i in stopTreePositionRange:
		sumrightList.append(0)
		sumrightList[i] = rightTreePosition[i]
		returnRange = range(0,TreeNumber-i-1,+1)
		leftPosition = 0
		rightPosition = i
		for x in returnRange:
			sumrightList[i] = sumrightList[i] + leftTreePosition[leftPosition] + rightTreePosition[rightPosition]
			if x % 2 == 0:
				rightPosition = rightPosition + 1
			else:
				leftPosition = leftPosition + 1
	leftMax = -1
	rightMax = -1
	for x in range(0,TreeNumber,+1):
		if leftMax <= sumleftList[x]:
			leftMax = sumleftList[x]
		if rightMax <= sumrightList[x]:
			rightMax = sumrightList[x]
	answer = max(leftMax,rightMax)
	return answer


if __name__ == '__main__':
	L,N = map(int,input().strip().split(' '))
	inputLineRange = range(0,N)
	position =[]
	for _ in inputLineRange:
		position.append(int(input().strip()))
	solution=maxDistance(L,N,position)
	print("{}".format(solution))

Submission status: Time Limit Exceeded

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

X.insert(0, 0)
X.append(L)

memo = {}

for n in range(1, N+1):
    new_memo = {}
    for u in range(N-n+1):
        new_memo[(u,1)] = max(memo.get((u+1,1),0)+X[u+1]-X[u], memo.get((u,0),0)+X[u]+L-X[u+n])
        new_memo[(u,0)] = max(memo.get((u+1,1),0)+X[u+1]+L-X[u+n+1], memo.get((u,0),0)+X[u+n+1]-X[u+n])
    memo = new_memo

print(memo[(0,0)])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000)

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

coordinate = [0] + X + [L]
interval = [coordinate[i+1] - coordinate[i] for i in range(N+1)]

def ans(interval):
    if len(interval) == 2:
        return max(interval)
    else:
        forward = interval[1:]
        forward[-1] += interval[0]
        backward = interval[:-1]
        backward[0] += interval[-1]
        return max(interval[0] + ans(forward), interval[-1] + ans(backward))

print(ans(interval))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import math
L, N = map(int, input().split())
XAntiClock, XClock = deque(), deque()
DistAntiClock, DistClock = deque(), deque()
DistAntiClock.append(0)
DistClock.append(0)
for i in range(N):
    x = int(input())
    XAntiClock.append(x)
    XClock.appendleft(L-x)
    DistAntiClock.append(DistAntiClock[-1] + 2 * x)
for i in range(N):
    DistClock.append(DistClock[-1] + XClock[i] * 2)

maxLength = max(XAntiClock[N-1], XClock[N-1])
for i in range(1, N):
    finIndex = math.ceil((i + N)/2)
    if (i + N) % 2 == 0:
        AntiClockLength = DistAntiClock[finIndex] - DistAntiClock[i-1] - XAntiClock[finIndex-1] + DistClock[N - finIndex] 
        ClockLength = DistClock[finIndex] - DistClock[i-1] - XClock[finIndex-1] + DistAntiClock[N - finIndex]
    else:
        AntiClockLength = DistAntiClock[finIndex - 1] - DistAntiClock[i-1] + DistClock[N - finIndex + 1] - XClock[N - finIndex]
        ClockLength = DistClock[finIndex - 1] - DistClock[i-1] + DistAntiClock[N - finIndex + 1] - XAntiClock[N - finIndex]
    maxLength = max(max(AntiClockLength, ClockLength), maxLength)

print(maxLength)

Submission status: Time Limit Exceeded

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

X = sorted(X)
dpl = [[0]*(N+1) for i in range(N+1)]
dpr = [[0]*(N+1) for i in range(N+1)]

for k in range(1, N+1):
    for l in range(k + 1):
        r = k - l
        if l > 0:
            dpl[l][r] = max(dpl[l-1][r] + X[l]-X[l-1], dpr[l-1][r] + X[l] + L - X[-r-1])
        if r > 0:
            dpr[l][r] = max(dpr[l][r-1] + X[-r-1]-X[-r], dpl[l][r-1] + X[l] + L - X[-r-1])
        
ma = 0
for l in range(N+1):
    ma = max(ma, dpl[l][N-l], dpr[l][N-l])

print(ma)

Submission status: Time Limit Exceeded

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

## Y[i] = X[i+1]-X[i]
#Y = [X[i+1]-X[i] if i<N-1 else L+X[0]-X[N-1] for i in range(N)]
#print(Y)

''' Start at X[0] '''

#''' In the case when turn first '''
#ans0 = X[0]
## 0, -1, 1, -2, ...
#i = 0
#j = N-1
#direc = 1 # direction: left->1, right->-1
#while i!=j:
#    print(i, j)
#    direc *= -1
#    ans0 += L+X[i]-X[j]
#    if direc==-1:
#        i += 1
#    elif direc==1:
#        j -= 1
#print(ans0)
#
#ans0 = X[1]
#i = 1
#j = N-1
#direc = 1 # direction: left->1, right->-1
#while i!=j:
#    print(i, j)
#    direc *= -1
#    ans0 += L+X[i]-X[j]
#    if direc==-1:
#        i += 1
#    elif direc==1:
#        j -= 1
#print(ans0)
#
#ans0 = X[2]
#i = 2
#j = N-1
#direc = 1 # direction: left->1, right->-1
#while i!=j:
#    print(i, j)
#    direc *= -1
#    ans0 += L+X[i]-X[j]
#    if direc==-1:
#        i += 1
#    elif direc==1:
#        j -= 1
#print(ans0)
#
## 0, -1, 1, -2, 2, ...
## 0, 1, -1, 2, -2, 3, ...

ans0 = 0
for k in range(N):
    tmp_ans = X[k]
    i = k
    j = N-1
    direc = 1 # direction: left->1, right->-1
    while i!=j:
        direc *= -1
        tmp_ans += L+X[i]-X[j]
        if direc==-1:
            i += 1
        elif direc==1:
            j -= 1
    if ans0<tmp_ans:
        ans0 = tmp_ans

ans1 = 0
for k in reversed(range(N)):
    tmp_ans = L-X[k]
    i = 0
    j = k
    direc = -1 # direction: left->1, right->-1
    while i!=j:
        direc *= -1
        tmp_ans += L+X[i]-X[j]
        if direc==-1:
            i += 1
        elif direc==1:
            j -= 1
    if ans1<tmp_ans:
        ans1 = tmp_ans

print(max(ans0, ans1))