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:
import numpy as np
l,n=map(int, input().split())
x=[]

for i in range(n):
    x.append(int(input()))

r=[0]
o=[0]
for i in range(n):
    o.append(o[-1]+x[i])
    r.append(r[-1]+l-x[-1-i])

ans=x[-1]
for i in range(n):
    s=x[i]*2
    t=(l-x[-i-1])*2
    ns=n-i-1
    nt=n-i-1
    
    s+=2*r[ns//2+ns%2]+2*(o[ns//2+i+1] - o[i+1]) - (x[n-1-ns//2] if ns%2==1 else x[n-1-ns//2-1])
    t+=2*(r[ns//2+ns%2+i] - r[i+1])+2*o[ns//2] - (x[ns//2] if ns%2==1 else x[ns+1])
    ans=max(ans,s,t)
    print(ans,s,t,ns)

print(ans)
print(x)
print(r)
print(o)

Submission status: Runtime Error

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

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

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

print(answer)

Submission status: Runtime Error

Solution code:
L,N=map(int,input().split())
X=[]
for i in range(N):
    X.append(int(input()))
def f(A):
    if len(A)==1:
        return max(A[0],L-A[0])
    else:
        b=A[0]
        c=L-A[-1]
        A0=A[1:len(A)]
        A1=A[0:len(A)-1]
        B=list(map(lambda x:x-b,A0))
        C=list(map(lambda x:x+c,A1))
        return max(b+f(B),c+f(C))
print(f(X))

Submission status: Runtime Error

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

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

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

Submission status: Runtime Error

Solution code:
import sys
import numpy
from collections import deque
l,n=map(int,input().split())
c=n
tree1=numpy.array[int(i) for i in sys.stdin]
reversed_tree1=numpy.array[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: Runtime Error

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

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
  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[s]+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[s]+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: Runtime Error

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

Submission status: Runtime Error

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

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


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


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


L, N = LI()
#  L = 10**5
#  N = 2000
X = [I() for i in range(N)]
#  X = [random.randint(1, N) for i in range(N)]

#  options = [min(L-i, i) for i in X]
#  print(options)
results = []
#  R_dp = [[0 for j in range(N)] for i in range(N)]
#  L_dp = [[0 for j in range(N)] for i in range(N)]
# 距離と残りの場所を格納
histories = {'R': [X[0], X[1:], X[0]], 'L': [L - X[-1], X[:-1], X[-1]]}
def dfs(history):
    #  print(history)

    if history in histories.keys():
        # 履歴から引っ張る
        pass
    else:
        # ない場合は一個前に戻って計算
        previous = histories[history[:-1]]
        if history[-1] == 'R':
            selected = previous[1][0]
            remaining = previous[1][1:]
            if history[-2] == 'R':
                d = previous[1][0] - previous[2]
            else:
                # 左行ってから右だから0を飛び越える場合
                d = L - (previous[2] - previous[1][0])
        else:
            selected = previous[1][-1]
            remaining = previous[1][:-1]
            if history[-2] == 'R':
                # 右行ってから左の0飛び越えるパターン
                d = L - (previous[1][-1] - previous[2])
            else:
                d = previous[2] - previous[1][-1]
        histories[history] = [previous[0] + d, remaining, selected]

        if len(history) == N:
            results.append(histories[history][0])
            return
        
    dfs(history + 'R')
    dfs(history + 'L')
    #  dfs(count + 1, directions, current_sum, history)

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

dfs('R')
dfs('L')
#  pprint(histories)
print(max(results))

Submission status: Runtime Error

Solution code:
L,N=map(int,input().split())
x=[]
for i in range(N):
    x.append(int(input()))
y=[]
for i in range(N):
    y.append(L-x[N-i-1])
l=0
def f(X,Y):
    if len(X)==0:
        return 0
    if X[0]>Y[0]:
        a=X[0]
        X=[x-a for x in X]
        Y=[x+a for x in Y]
        del Y[len(X)-1]
        del X[0]
        return a+f(X,Y)
    else:
        b=Y[0]
        X=[x+b for x in X]
        Y=[x-b for x in Y]
        del Y[0]
        del X[len(X)-1]    
        return b+f(X,Y)
print(f(x,y))

Submission status: Runtime Error

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

X2 = X[::-1]
Y2 = Y1[::-1]


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


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

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

    print(ans)

Submission status: Runtime Error

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

X2 = X[::-1]
Y2 = Y1[::-1]


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


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

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

    for n, len_ in enumerate(len1):
        if len_ + 50 * L > ans:
            for j in range(100 * n, 100 * n + 100):
                ans = max(np.dot(func(j), Y1), ans)

    for n, len_ in enumerate(len2):
        if len_ + 50 * L > ans:
            for j in range(100 * n, 100 * n + 100):
                ans = max(np.dot(func(j), Y2), ans)
    print(ans)

Submission status: Runtime Error

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

X2 = X[::-1]
Y2 = Y1[::-1]


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


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

    print(ans)
else:
    ans = 0
    cn = (N + 1) // 200
    len1 = [0] * cn
    len2 = [0] * cn
    can1 = [0] * cn
    can2 = [0] * cn
    for n in range(0, (N + 1) // 2, 100):
        a = func(n)
        i = n // 100
        len1[i] = np.dot(a, Y1)
        len2[i] = np.dot(a, Y2)
        can1[i] = (X[n + (N - n + 100)//2] - 2 * X[n] - (L - X[(N - n - 101)//2])) * 100
        can2[i] = (X2[n + (N - n + 100) // 2] - 2 * X2[n] - (L - X2[(N - n - 101) // 2])) * 100
        ans = max(ans, len1[i], len2[i])

    for n, (len_, can) in enumerate(zip(len1, can1)):
        if len_ + can > ans:
            for j in range(100 * n, 100 * n + 100):
                ans = max(np.dot(func(j), Y1), ans)

    for n, (len_, can) in enumerate(zip(len2, can2)):
        if len_ + can > ans:
            for j in range(100 * n, 100 * n + 100):
                ans = max(np.dot(func(j), Y2), ans)
    print(ans)

Submission status: Runtime Error

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

X2 = X[::-1]
Y2 = Y1[::-1]


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


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

    print(ans)
else:
    ans = 0
    cn = (N + 1) // 200
    len1 = [0] * cn
    len2 = [0] * cn
    can1 = [0] * cn
    can2 = [0] * cn
    for n in range(0, (N + 1) // 2, 100):
        a = func(n)
        i = n // 100
        len1[i] = np.dot(a, Y1)
        len2[i] = np.dot(a, Y2)
        can1[i] = X[n + (N - n + 100)//2] - 2 * X[n] - (L - X[(N - n - 101)//2])
        can2[i] = X2[n + (N - n + 100) // 2] - 2 * X2[n] - (L - X2[(N - n - 101) // 2])
        ans = max(ans, len1[i], len2[i])

    for n, (len_, can) in enumerate(zip(len1, can1)):
        if len_ + can > ans:
            for j in range(100 * n, 100 * n + 100):
                ans = max(np.dot(func(j), Y1), ans)

    for n, (len_, can) in enumerate(zip(len2, can2)):
        if len_ + can > ans:
            for j in range(100 * n, 100 * n + 100):
                ans = max(np.dot(func(j), Y2), ans)
    print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
import sys

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


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


if N < 10000:
    ans = 0
    for n in range((N + 1) // 2):
        a = func(n)
        len1 = np.dot(a, Y1)
        len2 = np.dot(a, Y2)
        ans = max(ans, len1, len2)
    
    print(ans)
else:
    ans = 0
    len1 = [0] * (N + 1) // 200
    len2 = [0] * (N + 1) // 200
    can1 = [0] * (N + 1) // 200
    can2 = [0] * (N + 1) // 200
    for n in range(0, (N + 1) // 2, 100):
        a = func(n)
        i = n // 100
        len1[i] = np.dot(a, Y1)
        len2[i] = np.dot(a, Y2)
        can1[i] = X[n + (N - n + 100)//2] - 2 * X[n] - (L - X[(N - n - 101)//2])
        can2[i] = X2[n + (N - n + 100) // 2] - 2 * X2[n] - (L - X2[(N - n - 101) // 2])
        ans = max(ans, len1[n], len2[n])
        
    for n, len_, can in enumerate(zip(len1, can1)):
        if len + can > ans:
            for j in range(100 * n, 100 * n + 100):
                ans = max(np.dot(func(j), Y1), ans)
                
    for n, len_, can in enumerate(zip(len2, can2)):
        if len + can > ans:
            for j in range(100 * n, 100 * n + 100):
                ans = max(np.dot(func(j), Y2), ans)
    print(ans)

Submission status: Runtime Error

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

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

position=0
ans=0
flag=True

def loop(i,j,tf):
    global flag
    global ans
    global position
    position_A=tree[i]
    position_B=l-reverse_tree[j]
    ans_A=0
    ans_B=0
    if (i!=0 or j!=0) and tf:
        ans_A+= tree[i]-tree[i-1]
        ans_B+= reverse_tree[j]+tree[i-1]
    elif i!=0 or j!=0:
        ans_A+= reverse_tree[j-1]+tree[i]
        ans_B+= reverse_tree[j-1]+reverse_tree[j]
    if (tree[i+1]-position_A >= reverse_tree[j]+position_A):
        ans_A+= tree[i+1]-position_A
    else:
        ans_A+= reverse_tree[i]+position_A
    if (l-position_B+tree[i] >= position_B-l+reverse_tree[j+1]):
        ans_B+= l-position_B+tree[i]
    else:
        ans_B+= position_B-l+reverse_tree[j+1]
    if ans_A == ans_B:
        A_1  = ans_A
        B_1  = ans_B
        ans_A = A_1 + loop(i+1,j,True)
        ans_B = B_1 + loop(i,j+1,False)
    if i==0 and j==0 and flag==True:
        if ans_A > ans_B:
            ans+= tree[0]-position
            position=tree.pop(0)
            reverse_tree.pop(-1)
        elif ans_B > ans_A:
            ans+= reverse_tree[0]+position
            position=l-reverse_tree.pop(0)
            tree.pop(-1)
            flag=False
    elif i==0 and j==0 and flag==False:
        if ans_A > ans_B:
            ans+= l-position+tree[0]
            position=tree.pop(0)
            reverse_tree.pop(-1)
            flag=True
        elif ans_B > ans_A:
            ans+= position-l+reverse_tree[0]
            position=l-reverse_tree.pop(0)
            tree.pop(-1)
    return max(ans_A,ans_B)

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

print(ans)

Submission status: Runtime Error

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

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

position=0
ans=0
flag=True

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

print(ans)

Submission status: Runtime Error

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

reverse_tree=[l-i for i in tree]
position=0
ans=0

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

Submission status: Runtime Error

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

def longest(pos, ans, *lst):
  if len(lst) == 0:
    return ans
  left = (pos - lst[-1]) % L
  right = (lst[0] - pos) % L
  return max(longest(lst[-1], ans+left, *lst[:-1]),
             longest(lst[0], ans+right, *lst[1:]))

print(longest(0, 0, *X))

Submission status: Runtime Error

Solution code:
L, N = (int(i) for i in input().split())
X = [int(input(i)) for i in range(N)]
current_space = 0
max_way = 0
while N > 0:
  if abs(current_space - X[1]) >= abs(current_space - X[-1]):
    max_way += abs(current_space - X[1])
    current_space = X[1]
    X.pop(1)
  else
    max_way += abs(current_space - X[-1])
    current_space = X[-1]
    X.pop(-1)
  N -= 1
print(max_way)

Submission status: Runtime Error

Solution code:
l,n = map(int, input().split())
x = []
for i in range(n):
  x.append(int(input()))
y = 0
yy = 0
for i in range(n):
  y += 2*x[((i+1)//2)*(-2*i+1)]
  yy += 2*x[(((i+(-2*(i%2)+1))+1)//2)*(-2*(i+(-2*(i%2)+1))+1)]
print(max[y-x[n//2+1],yy-x[(n+n%2)//2]])

Submission status: Runtime Error

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))
#ls_lst = [ls for r in range(len(dist_lst))]
#dis_lst = [dis for r in range(len(dist_lst))]
dist_lst[int(len(dist_lst)/2):] += ls[0]
dist_lst[:int(len(dist_lst)/2)] += dis[-1]
# 毎回全体の1/4について各操作を行えばいい


for i in range(len(dist_lst)):
  dist = dis
  lst = ls
  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: Runtime Error

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

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

Solution code:
a, b = map(int, input().split())
pos = 0
length = 0
tree=[]

def position(b,i,pos,posA, posB):
    print(posA, posB)
    if(posA == posB):
        for j in range(b-1-i):
            neia, neib = (tree[j+1]-tree[j], tree[b-i-1-j]-tree[b-i-2-j])
            print(neia, neib)
            if(neia > neib):
                posB = 0
                break
            elif(neib > neia):
                posA = 0
                break
    target = max(posA, posB)
    print(posA, posB)
    if(posA == target):
        pos = tree[0]
        del tree[0]
    else:
        pos = tree[b-i-1]
        del tree[b-i-1]
    return (pos, target)

for i in range(b):
    tree.append(int(input()))
for i in range(b):
    print(tree)
    if(pos > tree[b-i-1]):
        pos, target = position(b,i,pos,abs(tree[0]+a-pos),abs(tree[b-i-1]-pos))
    else:
        pos, target = position(b,i,pos,abs(tree[0]-pos),a-abs(tree[b-i-1]-pos))
    length += target
    print(i+1, "----", pos, target, length) 
print(length)

Submission status: Runtime Error

Solution code:
L, N = map(int, input().split())
if N > 2000:
    print(1/0)
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)