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 itertools
import copy

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

milemax=0
for i in itertools.product((0,-1),repeat=N):
	takahashi=0
	mile=0
	Xcopy=copy.copy(X)
	for j in range(N):
		if i[j]==0:
			if takahashi<Xcopy[0]:
				mile+=Xcopy[0]-takahashi
				takahashi=Xcopy.pop(0)
			else:
				mile+=Xcopy[0]+L-takahashi
				takahashi=Xcopy.pop(0)
		else:
			if takahashi>Xcopy[-1]:
				mile+=takahashi-Xcopy[-1]
				takahashi=Xcopy.pop(-1)
			else:
				mile+=takahashi+L-Xcopy[-1]
				takahashi=Xcopy.pop(-1)
	if mile>milemax: milemax=mile

print(milemax)

Submission status: Time Limit Exceeded

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

max_num = 0
# 反時計回り
for i in range(N):
    _num = 0
    current = X[i]
    _num += current
    currentIndex = i
    reverseIndex = N - 1
    while True:
        if currentIndex == reverseIndex:
            break
        _num += current+(L - X[reverseIndex])
        currentIndex += 1
        if currentIndex < reverseIndex:
            _num += (L-X[reverseIndex]) + X[currentIndex]
        else:
            break
        current = X[currentIndex]
        reverseIndex -= 1
    if _num > max_num:
        max_num = _num
# 時計回り
X.reverse()
for i in range(N):
    _num = 0
    current = L - X[i]
    _num += current
    currentIndex = i
    reverseIndex = N - 1
    while True:
        if currentIndex == reverseIndex:
            break
        _num += current+X[reverseIndex]
        currentIndex += 1
        if currentIndex < reverseIndex:
            current = L - X[currentIndex]
            _num += X[reverseIndex] + current
        else:
            break
        reverseIndex -= 1
    if _num > max_num:
        max_num = _num

print(max_num)

Submission status: Time Limit Exceeded

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

ans = 0
for i, x in enumerate(X[:-1]):
    a = x
    l = i
    r = N - 1
    while l != r:
        a += L - X[r] + X[l]
        l += 1
        if l == r: break
        a += L - X[r] + X[l]
        r -= 1
    ans = max(ans, a)

for i, x in enumerate(X[1:], 1):
    a = L - x
    l = 0
    r = i
    while l != r:
        #print(l, r)
        a += L - X[r] + X[l]
        r -= 1
        if l == r: break
        a += L - X[r] + X[l]
        l += 1
    ans = max(ans, a)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def dist(lst_, bin_str):
    lst = lst_.copy()
    res_tmp = 0
    tmp_point = 0
    tmp_state = '0'
    for s in bin_str:
        if s == '0':
            tmp = lst.pop(0)
            if tmp_state == '0':
                res_tmp += tmp-tmp_point
            if tmp_state == '1':
                res_tmp += tmp+(L-tmp_point)
            tmp_point = tmp
            tmp_state = '0'
        else:
            tmp = lst.pop(-1)
            if tmp_state == '1':
                res_tmp += tmp_point - tmp
            if tmp_state == '0':
                res_tmp += tmp_point+(L-tmp)
            tmp_point = tmp
            tmp_state = '1'
    return res_tmp
if __name__ =='__main__':
    L, N = map(int, input().split())
    X = [int(input()) for i in range(N)]
    print(max([dist(X,  bin(i)[2:].zfill(N)) for i in range(2**N)]))
#     for i in range(2**N):
#         tmp_bin = bin(i)[2:].zfill(N)
#         print(dist(X, tmp_bin))

Submission status: Accepted

Solution code:
import sys

input=sys.stdin.readline

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

accu1=[X[i] for i in range(N)]
accu2=[X[i] for i in range(N)]
for i in range(1,N):
    accu1[i]+=accu1[i-1]
for i in range(N-2,-1,-1):
    accu2[i]+=accu2[i+1]

ans=max(L-X[0],X[-1])
for i in range(1,N):
    j=N-i
    test=0
    if i<j:
        test1=2*accu1[i-1]-X[i-1]+2*i*L-2*(accu1[2*i-1]-accu1[i-1])
        test2=2*accu1[i-1]+2*(i+1)*L-2*(accu1[2*i]-accu1[i-1])-(L-X[i])
        ans=max(test1,test2,ans)
        #print(test1,test2)
        #print(test1,test2)
    elif j<i:
        test1=2*L*j-2*accu2[-j]-(L-X[-j])+2*(accu2[-2*j]-accu2[-j])
        test2=2*L*j-2*accu2[-j]+2*(accu2[-2*j-1]-accu2[-j])-X[-j-1]
        #test2=2*sum(L-X[-k-1] for k in range(j))+2*sum(X[-k-1] for k in range(j,2*j+1))
        ans=max(test1,test2,ans)
        #print(test1,test2)
        #print(test1,test2)
    else:
        test1=2*accu1[i-1]+2*i*L-2*(accu1[2*i-1]-accu1[i-1])-min(X[i-1],L-X[i])
        #test1=2*sum(X[k] for k in range(i))+2*sum(L-X[k] for k in range(i,2*i))-min(X[i-1],L-X[i])
        ans=max(ans,test1)

print(ans)

Submission status: Accepted

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

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

def solve(A):
    if len(A) == 1:
        return A[0]
    S = [None]*N
    s = 0
    for i, a in enumerate(A):
        s += a
        S[i] = s

    T = [None]*N
    t = 0
    for i in reversed(range(N)):
        t += (L-A[i])
        T[i] = t

    ans = 0
    for i in range(N-1):
        if 2*i+3 < N:
            ans = max(ans, 2*S[i]+2*(T[i+1]-T[2*i+3])-(L-A[i+1]))
        elif 2*i+2 > N:
            ans = max(ans, 2*(S[i]-S[2*i-N+1]) + 2*T[i+1] - (L-A[i+1]))
        else:
            ans = max(ans, 2*S[i]+2*T[i+1]-(L-A[i+1]))
    return ans

a1 = solve(A)
a2 = solve([L-a for a in reversed(A)])
print(max(a1, a2))

Submission status: Accepted

Solution code:

"""
Writer: SPD_9X2
https://atcoder.jp/contests/agc030/tasks/agc030_b

列の左右からとっていく。
移動距離は、連続して同じ方からとった場合と前とは別方向からとった場合で異なる

1.連続してとった場合は、単純に前に取った要素との差が加わる
2.そうでない場合は、原点と前の要素の距離+原点と今回の要素の距離が加わる

左右で撮る場所を決めてしまった場合はどう？
同じ要素を取る場合、1を選んだ時の加算 < 2を選んだ時の加算は確定

多い方では、必ず1をその差分だけ？選ばなくてはいけない
2を選んだ方が得な要素は？

前に何を選んだかによらず、寄与を考える方法を考案する必要がある
2つの山には分けておこう。

なるべく後半に反対の山からもらう方が寄与が大きいのは当然。
よって、まず多い方の山を少ない方と同数にして、交互に行き来すれば最適？
→O(N**2)なので部分点か？

→ここから高速化 or 更に探索空間を減らせないか考える

累積和で高速化可能か？
→とりあえず部分点狙ってみよう

l==rのとき、lの右端 と rの左端のうち最小以外は全て2こ取れる
l>rのとき、lのr個と、rは2回取れる +　lのr+1を1回取れる
r<lの時は逆

dpで解けるのか？
"""

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

X = []

dl = []
dr = []

for i in range(N):

    x = int(input())
    dl.append(x)
    dr.append(L-x)

dls = [0]
drs = [0]

for i in range(N):

    dls.append(dls[-1] + dl[i])
    drs.append(drs[-1] + dr[-1-i])

ans = 0
for l in range(N+1):

    r = N-l
    if l==r:
        ans = max( ans , 2 * (dls[l] + drs[r]) - min(dl[l-1],dr[l]) )
    elif l > r:

        #先にLに行く場合は,lにr+1個行く。

        lsum = 2 * (dls[l] - dls[l-(r+1)]) - dl[l-1]
        rsum = 2 *  drs[r]

        ans = max(ans , lsum + rsum)

        #先にRに行く場合。lにr個いく

        lsum = 2 * (dls[l] - dls[l-r])
        rsum = 2 * (drs[r]) - dr[-1*r]

        ans = max(ans , lsum + rsum)
    else:

        #先にRに行く場合, rにl+1こいく

        rsum = 2 * (drs[r] - drs[r-(l+1)]) - dr[-1*r]
        lsum = 2 * (dls[l])

        ans = max(ans , lsum + rsum)

        #先にL

        rsum = 2 * (drs[r] - drs[r-l])
        lsum = 2 * (dls[l]) - dl[l-1]

        ans = max(ans , lsum + rsum)

print (ans)

Submission status: Accepted

Solution code:
from itertools import accumulate

L, N, *X = map(int, open(0).read().split())

Y = [L - x for x in reversed(X)]

Sx = [0] + list(accumulate(X))
Sy = [0] + list(accumulate(Y))

ans = 0
for i in range(N):
    j = N - i - 1
    mi = min(i, j)

    x = X[i] + 2 * (Sx[i] - Sx[i - mi]) + 2 * (Sy[j] - Sy[j - mi - int(i < j)])
    y = Y[j] + 2 * (Sx[i] - Sx[i - mi - int(i > j)]) + 2 * (Sy[j] - Sy[j - mi])
    ans = max(ans, x, y)

print(ans)

Submission status: Accepted

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

def f(T):
  n = len(T)
  S = [0]*(2*n+1)
  for i in range(2*n):
    S[i+1] = S[i]+T[i%n]
  a = S[n-1]
  ans = a
  for i in range(n-2):
    a += 2*(S[2*n-i*2-3]-S[n-i-1])
    a -= 2*(S[2*n-i-2]-S[2*n-i*2-2])
    a -= T[n-i-2]
    ans = max(ans, a)
  return ans

A = [X[0]]+[X[i+1]-X[i] for i in range(N-1)]+[L-X[-1]]
print max(f(A), f(A[::-1]))

Submission status: Accepted

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

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

Acl = X[:]
for i in range(1, N):
    Acl[i] += Acl[i-1]

Acl += [0]

Acr = [L-x for x in X]
for i in range(N-2, -1, -1):
    Acr[i] += Acr[i+1]

Acr += [0]

res = max(L-X[0], X[-1])

for i in range(N):
    k = min(i+1, N-1-i)
    if i+1 == N-1-i:
        res = max(res, 2*(Acr[i+1] + Acl[i]) - X[i])
    elif i+1 < N-1-i:
        res = max(res, 2*(Acr[i+1] - Acr[i+1+k] + Acl[i]) - X[i])
    else:
        res = max(res, 2*(Acr[i+1] + Acl[i] - Acl[i-k-1]) - X[i])
    
    k = min(i, N-i)
    if i == N-i:
        res = max(res, 2*(Acr[i] + Acl[i-1]) - L + X[i])
    elif i < N-i:
        res = max(res, 2*(Acr[i] - Acr[i+k+1] + Acl[i-1]) - L + X[i])
    else:
        res = max(res, 2*(Acr[i] + Acl[i-1] - Acl[i-1-k]) - L + X[i])
print(res)

Submission status: Accepted

Solution code:
L,N=map(int,input().split())
X=[int(input()) for i in range(N)]
X=[0]+X
Y=[0]
for i in range(N,0,-1):
    Y.append(L-X[i])
sum_X=[0]*(N+1)
sum_Y=[0]*(N+1)
for i in range(1,N+1):
    sum_X[i]=X[i]+sum_X[i-1]
    sum_Y[i]=Y[i]+sum_Y[i-1]
ans=0
for i in range(N//2+1,N+1):
    j=N-i
    num_1=2*(sum_Y[j]+sum_X[i]-sum_X[i-j])-Y[j]
    if i!=j:
        num_2=2*(sum_Y[j]+sum_X[i]-sum_X[i-j-1])-X[i]
    ans=max(ans,num_1,num_2)
X,Y=Y[:],X[:]
sum_X,sum_Y=sum_Y[:],sum_X[:]
for i in range(N//2+1,N+1):
    j=N-i
    num_1=2*(sum_Y[j]+sum_X[i]-sum_X[i-j])-Y[j]
    if i!=j:
        num_2=2*(sum_Y[j]+sum_X[i]-sum_X[i-j-1])-X[i]
    ans=max(ans,num_1,num_2)
if N%2==0:
    num_1=2*(sum_X[N//2]+sum_Y[N//2])-X[N//2]
    num_2=2*(sum_X[N//2]+sum_Y[N//2])-Y[N//2]
    ans=max(ans,num_1,num_2)
print(ans)

Submission status: Accepted

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

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

S=[]

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

#print(S)

DIS=L-S[-1]
ANS=L-S[-1]
MINUS=0
PLUS=L-S[-1]

#print(DIS)

for i in range(N-1):
    if i%2==0:
        MINUS+=S[-i-2]
        PLUS+=S[-i//2-1]-S[-i-2]

    else:
        MINUS+=S[-i-2]-S[-i-1+i//2]
        PLUS-=S[-i-2]

    DIS+=PLUS-MINUS

    if ANS<DIS:
        ANS=DIS

    #print(DIS,PLUS,MINUS)

S=S[::-1]

DIS=L-S[-1]
MINUS=0
PLUS=L-S[-1]

#print(DIS)

for i in range(N-1):
    if i%2==0:
        MINUS+=S[-i-2]
        PLUS+=S[-i//2-1]-S[-i-2]

    else:
        MINUS+=S[-i-2]-S[-i-1+i//2]
        PLUS-=S[-i-2]

    DIS+=PLUS-MINUS

    if ANS<DIS:
        ANS=DIS

    #print(DIS,PLUS,MINUS)

print(ANS)

Submission status: Accepted

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

import numpy as np

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

def F(X):
    max_cost = L-X[0]
    # 負方向を初手で、正方向に密
    Xcum = X.cumsum()
    # 等個数ずつとる場合
    M = N//2
    if M > 0:
        arr = 4*Xcum[:M] + 2*L*np.arange(1,M+1) - 2*Xcum[1:2*M+1:2] - X[:M]
        max_cost = max(max_cost, arr.max())
    # 負にn+1個、正にn個
    M = (N-1)//2
    if M > 0:
        arr = (Xcum[:M] + L*np.arange(1,M+1) - Xcum[2:M+M+2:2] + Xcum[1:M+1])*2 - X[1:M+1] + L
        max_cost = max(max_cost,arr.max())
    return max_cost

answer = max(F(X), F(L-X[::-1]))
print(answer)

Submission status: Accepted

Solution code:
l, n = [int(item) for item in input().split()]
right = []
left = []
for i in range(n):
    a = int(input())
    right.append(a)
    left.append(l - a)
left.reverse()

rsum = [0] * (n+1)
lsum = [0] * (n+1)
for i in range(n):
    rsum[i+1] += rsum[i] + right[i]
    lsum[i+1] += lsum[i] + left[i]

# Take all from left or right
ans = max(right[-1], left[-1])

# Take from left first, then ping pong
for i in range(n-1):
    val = left[i] * 2
    rest = n - (i + 1)
    val += rsum[(rest + 1) // 2] * 2
    val += (lsum[rest // 2 + i + 1] - lsum[i + 1]) * 2
    if rest % 2 == 0:
        val -= left[rest // 2 + i]
    else:
        val -= right[(rest + 1) // 2 - 1]
    ans = max(ans, val)

# Take from right first, then ping pong
for i in range(n-1):
    val = right[i] * 2
    rest = n - (i + 1)
    val += lsum[(rest + 1) // 2] * 2
    val += (rsum[rest // 2 + i + 1] - rsum[i + 1]) * 2
    if rest % 2 == 0:
        val -= right[rest // 2 + i]
    else:
        val -= left[(rest + 1) // 2 - 1]
    ans = max(ans, val)
print(ans)

Submission status: Accepted

Solution code:
def calc(l,n,arr):
  cum1=[0]
  cum2=[0]
  for i in range(n):
    cum1.append(cum1[-1]+arr[i])
  for i in range(n-1,-1,-1):
    cum2.append(cum2[-1]+(l-arr[i]))
  ans=0
  for i in range(n):
    if (n-i-1)%2==0:
      lm=(n-i-1)//2
      rm=(n-i-1)//2
      end=i+rm
      tmp=2*(cum1[rm+i]-cum1[i])+2*cum2[lm]+arr[end]
    else:
      lm=(n-i-1)//2+1
      rm=(n-i-1)//2
      end=n-lm
      tmp=2*(cum1[rm+i+1]-cum1[i])+2*cum2[lm-1]+(l-arr[end])
    ans=max(ans,tmp)
  return ans

l,n=map(int,input().split())
arr=[int(input()) for _ in range(n)]
ans1=calc(l,n,arr)
for i in range(n):
  arr[i]-=l
  arr[i]*=-1
ans2=calc(l,n,arr[::-1])
print(max(ans1,ans2))

Submission status: Accepted

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

def clockwise(X, Y):
    cum_X = [0 for _ in range(N+1)]
    cum_Y = [0 for _ in range(N+1)]
    for i in range(1, N+1):
        cum_X[i] = X[i-1] + cum_X[i-1]
        cum_Y[i] = Y[i-1] + cum_Y[i-1]
    d = 0
    for i in range(N):
        x_last = (N-i-1) // 2
        y_last = N-i-1-x_last
        if (N-i) % 2 == 0:
            last = Y[y_last-1]
        else:
            last = X[i+x_last]
        d = max(d, 2*(X[i]+cum_X[i+x_last+1]-cum_X[i+1]+cum_Y[y_last])-last)
    return d

ans = max(clockwise(X, Y), clockwise(Y, X))
print(ans)

Submission status: Accepted

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

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

y = [l - x[n - i - 1] for i in range(0, n)]
m = 0

def cal(x, y):
    global m
    
    sx = [0] * (n + 1)
    sy = [0] * (n + 1)
    for i in range(1, n + 1):
        sx[i] = sx[i - 1] + x[i - 1]
        sy[i] = sy[i - 1] + y[i - 1]
    for i in range(0, n):
        xc = (n - i - 1) // 2
        yc = (n - i - 1) - xc
        last = 0
        if (n - i) % 2 == 0:
            last = y[yc - 1]
        else:
            last = x[i + xc]
        mt = 2 * x[i] + 2 * (sy[yc] + sx[i + xc + 1] - sx[i + 1]) - last
        #print(i, mt, xc, yc, sx[i + xc + 1] - sx[i + 1], sy[yc], last)
        if mt > m:
            m = mt

cal(x, y)
cal(y, x)
print(m)

Submission status: Accepted

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:
    direc *= -1
    ans0 += L+X[i]-X[j]
    if direc==-1:
        i += 1
    elif direc==1:
        j -= 1
if N%2==0:
    i = N//2
    j = N//2
else:
    i = N//2
    j = N//2+1
tmp_ans = ans0
for k in range(N-1):
    tmp_ans += -L-2*X[k]+X[i]+X[j]
    if i==j:
        j += 1
    else:
        i += 1
    ans0 = max(ans0, tmp_ans)
 
 
''' Start at X[N-1] '''
''' In the case when turn first '''
ans1 = L-X[N-1]
i = 0
j = N-1
direc = -1 # direction: left->1, right->-1
while i!=j:
    direc *= -1
    ans1 += L+X[i]-X[j]
    if direc==-1:
        i += 1
    elif direc==1:
        j -= 1
if N%2==0:
    i = (N-2)//2
    j = (N-2)//2
else:
    i = (N-2)//2
    j = (N-2)//2+1
tmp_ans = ans1
for k in reversed(range(1, N)):
    tmp_ans += -L+2*X[k]-X[i]-X[j]
    if i==j:
        i -= 1
    else:
        j -= 1
    ans1 = max(ans1, tmp_ans)
 
print(max(ans0, ans1))

Submission status: Accepted

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

ans0 = X[0]
# 0, -1, 1, -2, ...
i = 0
j = N-1
direc = 1 # direction: left->1, right->-1
while i!=j:
    direc *= -1
    ans0 += L+X[i]-X[j]
    if direc==-1:
        i += 1
    elif direc==1:
        j -= 1
if N%2==0:
    i = N//2
    j = N//2
else:
    i = N//2
    j = N//2+1
tmp_ans = ans0
for k in range(N-1):
    tmp_ans += -L-2*X[k]+X[i]+X[j]
    if i==j:
        j += 1
    else:
        i += 1
    ans0 = max(ans0, tmp_ans)
 
 
''' Start at X[N-1] '''
''' In the case when turn first '''
ans1 = L-X[N-1]
i = 0
j = N-1
direc = -1 # direction: left->1, right->-1
while i!=j:
    direc *= -1
    ans1 += L+X[i]-X[j]
    if direc==-1:
        i += 1
    elif direc==1:
        j -= 1
if N%2==0:
    i = (N-2)//2
    j = (N-2)//2
else:
    i = (N-2)//2
    j = (N-2)//2+1
tmp_ans = ans1
for k in reversed(range(1, N)):
    tmp_ans += -L+2*X[k]-X[i]-X[j]
    if i==j:
        i -= 1
    else:
        j -= 1
    ans1 = max(ans1, tmp_ans)
 
print(max(ans0, ans1))

Submission status: Accepted

Solution code:
ln, kn, *ki = map(int, open(0).read().split())
# 順回転
pa = ki[-1]
ky = [pa]
kigu = 1
for ys in range(2, kn + 1):
    # 要素数が偶数の場合
    if kigu == 1:
        pa += ki[kn - ys] * 2 + ln - ki[-(ys // 2)] * 2
    # 要素数が奇数の場合
    else:
        pa += ki[kn - ys] * 2 - ki[-(ys // 2) - 1] + ln - ki[-(ys // 2)]
    ky.append(pa)
    kigu *= -1

# 逆回転
pa = ln - ki[0]
ky.append(pa)
kigu = 1
for ys in range(2, kn + 1):
    # 要素数が偶数の場合
    if kigu == 1:
        pa += (ln-ki[ys - 1]) * 2 - ln + ki[ys // 2 - 1] * 2
    # 要素数が奇数の場合
    else:
        pa += (ln-ki[ys - 1]) * 2+ki[ys//2]-ln+ki[ys//2-1]
    ky.append(pa)
    kigu *= -1

print(max(ky))

Submission status: Accepted

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: Accepted

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 = L - X[::-1]
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, x):
    return x[n + (N - n + 1)//2 - 1] - 2 * x[n - 1] - (L - x[N - (N - n + 1)//2])


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

print(ans)

Submission status: Accepted

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

RL = [0]
RSL = [0]
for i in X:
  RL.append(i)
  RSL.append(RSL[-1] + i)

LL = [0]
LSL = [0]
for i in X[::-1]:
  LL.append(L - i)
  LSL.append(LSL[-1] + (L - i))

D = [RSL[i] + LSL[N - i] for i in range(N + 1)]

Ans = max(RL[N], LL[N])
for i in range(1, N):
  if i < (N + 1) // 2:
    k = N - 2 * i
    t = (D[i] - LSL[max(k - 1, 0)]) * 2  - LL[N - i]
    s = (D[i] - LSL[k]) * 2  - RL[i]
    Ans = max(Ans, t, s)
  else:
    k = 2 * i - N
    t = (D[i] - RSL[max(k - 1, 0)]) * 2  - RL[i]
    s = (D[i] - RSL[k]) * 2  - LL[N - i]
    Ans = max(Ans, t, s)
  
print(Ans)

Submission status: Accepted

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

Y = [0]*(N+1)
for i in range(N):
    Y[i+1] = X[i] + Y[i]

ans = max(X[N-1], L - X[0])
for i in range(N-1):
    P = i+1; Q = N - (i+1)
    if P < Q:
        ans = max(ans, 2*Y[i+1] + 2*(L*(P+1) - (Y[i+P+2] - Y[i+1])) - (L - X[i+1]))
    elif P > Q:
        ans = max(ans, 2*(Y[i+1] - Y[i-Q]) - X[i] + 2*(L*Q - (Y[N] - Y[i+1])))
    K = min(P, Q)
    ans = max(ans, 2*(Y[i+1] - Y[i+1-K]) + 2*(L*K - (Y[i+K+1] - Y[i+1])) - min(X[i], L-X[i+1]))
print(ans)

Submission status: Accepted

Solution code:
L,N = list(map(int,input().split()))
X=[]
Y=[]
SX=[0]
SY=[0]
sx=0
sy=0
for i in range(N):
   x=int(input())
   X.append(x)
   sx+=x
   SX.append(sx)
   Y.append(L-x)
   sy+=L-x
   SY.append(sy)   

max_score=0   
for i in range(N):
    if i>N-i-1:
        max_score=max(2*(SX[i]-SX[2*i-N])+2*(SY[N]-SY[i+1])+Y[i],max_score)
    elif i<N-i-1:
        max_score=max(2*(SX[i]-SX[0])+2*(SY[2*i+2]-SY[i+1])+X[i],max_score)

        
    ind = min(i,N-i-1)
    max_score=max(2*(SX[i]-SX[i-ind])+2*(SY[i+ind+1]-SY[i+1])+X[i],max_score)
    max_score=max(2*(SX[i]-SX[i-ind])+2*(SY[i+ind+1]-SY[i+1])+Y[i],max_score)


print(max_score)
#copy code.

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate

circumference, n = map(int, input().split())
lll = list(map(int, sys.stdin.readlines()))
rrr = [circumference - l for l in lll]
rrr.reverse()
lll = [0] + lll
rrr = [0] + rrr
acc_l = list(accumulate(lll))
acc_r = list(accumulate(rrr))

ans = max(lll[-1], rrr[-1])
for take_l in range(1, n):
    take_r = n - take_l

    # l last
    tmp_l = lll[take_l] + 2 * (acc_l[take_l - 1] + acc_r[take_r])
    # r last
    tmp_r = rrr[take_r] + 2 * (acc_r[take_r - 1] + acc_l[take_l])

    if take_l < take_r:
        tmp_l -= 2 * acc_r[take_r - take_l]
        tmp_r -= 2 * acc_r[take_r - 1 - take_l]
    elif take_l > take_r:
        tmp_l -= 2 * acc_l[take_l - 1 - take_r]
        tmp_r -= 2 * acc_l[take_l - take_r]

    ans = max(ans, tmp_l, tmp_r)
print(ans)

Submission status: Accepted

Solution code:
L,n = (int(i) for i in input().split())
x = [int(input()) for i in range(n)]
t,t2,y,a = [0],[0],[],0
for i in range(n):
	t.append(t[-1]+x[i])
	t2.append(L+t2[-1]-x[n-i-1])
	y.append(L-x[n-i-1])
for i in range(n):
	if (n-i-1)%2: a = max(a,y[(n-i-1)//2]+2*(t[i+(n-i-1)//2+1]-t[i]+t2[(n-i-1)//2]))
	else: a = max(a,2*(t[i+(n-i-1)//2+1]-t[i]+t2[(n-i-1)//2])-x[i+(n-i-1)//2])
for i in range(n):
	if (n-i-1)%2: a = max(a,x[(n-i-1)//2]+2*(t2[i+(n-i-1)//2+1]-t2[i]+t[(n-i-1)//2]))
	else: a = max(a,2*(t2[i+(n-i-1)//2+1]-t2[i]+t[(n-i-1)//2])-y[i+(n-i-1)//2])
print(a)

Submission status: Accepted

Solution code:
def run(L, N, X):
    '''
    最初に向きを変える点をsとする
    その後は向きを変えながら最後の点まで行けばよい
    最後の点をfとする
    ある点をiと置く
    0からiの左回りの距離をli, 右回りの距離をriと置くと
    全体の距離は2*liのsからfの和と2*riのNからfの和を加算し
    最後の回りが左回りなら上記からlf+2*rfを減算し、
    右回りなら2*lf+rfを減算すれば全体の距離がでる
    sを1からfの場合すべてを求め、その最大値を出力すればよい
    ただし最初の回る方向が右と左両方を求める必要がある
    累積和を使えば、2*liのsからfの和をO(1)で求められる
    '''
    # 累積和取得
    l_sum = {0: 0}
    r_sum = {N+1: 0}
    for i in range(1, N+1):
        l_sum[i] = l_sum[i-1] + X[i-1]
    for i in range(N, 0, -1):
        r_sum[i] = r_sum[i+1] + L - X[i-1]
    # 開始左回り
    ret = 0
    for s in range(1, N+1):
        # 折り返す点の数
        nodes = (N - s + 1)
        # 最終地点
        f = int(s + (nodes - (nodes % 2)) / 2)
        if nodes % 2 == 1:
            last_dir_l = True
        else:
            last_dir_l = False
        if last_dir_l:
            tmp = 2*(l_sum[f] - l_sum[s-1]) + 2*(r_sum[f+1]) - X[f-1]
        else:
            tmp = 2*(l_sum[f-1] - l_sum[s-1]) + 2*(r_sum[f]) - (L - X[f-1])
        ret = max(ret, tmp)

    # 開始右回り
    for s in range(1, N+1):
        # 折り返す点の数
        nodes = s
        # 最終地点
        f = int((nodes + (nodes % 2)) / 2)
        if nodes % 2 == 1:
            last_dir_r = True
        else:
            last_dir_r = False
        if last_dir_r:
            tmp = 2*(l_sum[f-1]) + 2*(r_sum[f] - r_sum[s+1]) - (L - X[f-1])
        else:
            tmp = 2*(l_sum[f]) + 2*(r_sum[f+1] - r_sum[s+1]) - X[f-1]
        ret = max(ret, tmp)
    return ret


def main():
    L, N = map(int, input().split())
    X = []
    for _ in range(N):
        X.append(int(input()))
    print(run(L, N, X))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def is_even(num):
    return num % 2 == 0
def goback(M, x, Sx):
    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 * Sx[k - 1] - 2 * (Sx[M] - Sx[M - k]) - x[M - k] + L * (2 * k + 1)
    else:
        return 2 * Sx[k - 1] + x[k] - 2 * (Sx[M] - Sx[M - k - 1]) + L * 2 * (k + 1)

L, N = (int(i) for i in input().split())
ans = 0

pl = []
for i in range(N):
    pl.append(int(input()))
sumpl = [pl[0]]
for i in range(1, N):
    sumpl.append(sumpl[i - 1] + pl[i])
for i in range(0, N):
    ans = max(ans, goback(i, pl, sumpl))

revpl = [L - p for p in pl[::-1]]
sumrevpl = [revpl[0]]
for i in range(1, N):
    sumrevpl.append(sumrevpl[i - 1] + revpl[i])
for i in range(0, N):
    ans = max(ans, goback(i, revpl, sumrevpl))

print(ans)

Submission status: Accepted

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

ans=0
for i in range(N):
  a=2*X[i]
  d=(N-i-1)//2
  if (N-i)%2:
    a+=2*(S[i+d+1]-S[i+1])
    a+=2*(L*d-(S[N]-S[N-d]))
    a-=X[i+d]
  else:
    a+=2*(S[i+d+1]-S[i+1])
    a+=2*(L*(d+1)-(S[N]-S[N-d-1]))
    a-=L-X[N-d-1]
  ans=max(ans,a)
X_new=[]
S_new=[0]
for x in X[::-1]:
  X_new.append(L-x)
  S_new.append(S_new[-1]+L-x)

for i in range(N):
  a=2*X_new[i]
  d=(N-i-1)//2
  if (N-i)%2:
    a+=2*(S_new[i+d+1]-S_new[i+1])
    a+=2*(L*d-(S_new[N]-S_new[N-d]))
    a-=X_new[i+d]
  else:
    a+=2*(S_new[i+d+1]-S_new[i+1])
    a+=2*(L*(d+1)-(S_new[N]-S_new[N-d-1]))
    a-=L-X_new[N-d-1]
  ans=max(ans,a)
print(ans)

Submission status: Accepted

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

s = [0] * (N + 1)
t = [0] * (N + 1)
for i in range(1, N + 1):
    s[i] = s[i-1] + X[i]
    t[i] = t[i-1] + (L - X[N - i + 1])
Y = [0] + [L - X[N - i] for i in range(N)]

# i >= 1


def get_d(s, x, i):
    if i == N:
        return x[N]
    a = i + (N - i) // 2
    return (
        2 * (s[a] - s[i-1] + L * (N - a) - s[N] + s[a]) -
        (x[a] if (N - i) % 2 == 0 else (L - x[a + 1]))
    )


ans = 0
for i in range(1, N + 1):
    ans = max(ans, get_d(s, X, i), get_d(t, Y, i))

print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate

def burn(L, l_x):
    l_x.append(L)
    l_x.insert(0, 0)
    r_x = list(L - i for i in reversed(l_x))
    return max(burn_in(L, l_x, r_x), burn_in(L, r_x, l_x))


def burn_in(L, l_x, l_l):
    r_x = list(L - i for i in reversed(l_x))
    l = list(accumulate(l_x))
    r = list(accumulate(r_x))
    n_max = len(l_x)
    ret = 0
    for i in range(n_max - 2):
        n_r = (n_max - 2 - i) // 2
        n_l = n_max - n_r - 2
        res = l_x[n_l] if (n_max - i) % 2 == 1 else r_x[n_r]
        can = (l[n_l] - l[i] + r[n_r]) * 2 - res
        ret = max(ret, can)
    return ret


def main():
    L, N = map(int, input().split())
    x = [int(input()) for _ in range(N)]
    print(burn(L, x))
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math

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

X_r = [L - i for i in reversed(X)]
X_r.insert(0, 0)
X_r.pop()

def lsum(l):
    s = 0
    for i in l:
        s += i
        yield s

X_sum = list(lsum(X))
X_r_sum = list(lsum(X_r))

def f_l(p, n):
    N_tmp = N - n
    a = N_tmp // 2
    if N_tmp == 0:
        return 0
    elif N_tmp % 2 == 0:
        return 2 * X_sum[a] + X_r_sum[a + n] + X_r_sum[a + n - 1] - 2 * X_r_sum[n] + p
    else:
        return X_sum[a+1] + X_sum[a] + 2 * X_r_sum[a + n] - 2 * X_r_sum[n] + p


def f_r(p, n):
    N_tmp = N - n
    a = N_tmp // 2
    if N_tmp == 0:
        return 0
    elif N_tmp % 2 == 0:
        return 2 * X_r_sum[a] + X_sum[a + n] + X_sum[a + n - 1] - 2 * X_sum[n] + p
    else:
        return X_r_sum[a+1] + X_r_sum[a] + 2 * X_sum[a + n] - 2 * X_sum[n] + p

max_l = max(X[i] + f_r(X[i], i) for i in range(1, N+1))
max_r = max(X_r[i] + f_l(X_r[i], i) for i in range(1, N+1))

print(max(max_l, max_r))

Submission status: Accepted

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


def calc(X):
    cumsum = [0]
    for x in X:
        cumsum += [cumsum[-1] + x]
    res = 0
    for i in range(N):
        if (i + N) % 2:
            end = (i + N - 1) // 2
            d = 2 * (cumsum[end + 1] - cumsum[i]) + 2 * L * (
                N - 1 - end) - 2 * (cumsum[N] - cumsum[end + 1]) - X[end]
        else:
            end = (i + N) // 2
            d = 2 * (cumsum[end] - cumsum[i]) + 2 * L * (N - end) - 2 * (
                cumsum[N] - cumsum[end]) - (L - X[end])
        res = max(res, d)
    return res


print(max(calc(X), calc([L - x for x in X[::-1]])))