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

Solution code:
L, N = map(int, input().split())
X=[0]
sumL=[0]
sumR=[0]
for i in range(N):
    X.append(int(input()))
    sumL.append(sumL[-1]+X[-1])
for i in range(N):
    sumR.append(sumR[-1]+L-X[N-i])
sumR.append(0)
sumR.reverse()
#print(X)
#print("sumL",sumL)
#print("sumR",sumR)
ans = 0
for b in range(N+1):
    z = sumL[b] + sumR[b+1]
    if(b > 0):
        if(b <= N-b):
            ans = max(ans, z+sumL[b-1]+sumR[b+1]-2*sumR[N+1-(N-b-b)])
            #print("A", b, z+sumL[b-1]+sumR[b+1]-2*sumR[N+1-(N-b-b)])
        else:
            ans = max(ans, z+sumL[b-1]+sumR[b+1]-2*sumL[b-(N-b)-1])
            #print("B", b, z+sumL[b-1]+sumR[b+1]-2*sumL[b-(N-b)-1])
    if(b < N):
        if(b >= N-b):
            ans = max(ans, z+sumL[b]+sumR[b+2]-2*sumL[b-(N-b)])
            #print("C", b, z+sumL[b]+sumR[b+2]-2*sumL[b-(N-b)])
            #print(b, z, sumR[b+1], sumL[b], sumR[b+2], sumL[b-(N-b)])
        else:
            ans = max(ans, z+sumL[b]+sumR[b+2]-2*sumR[N+1-(N-b-b)+1])
            #print("D", b, z+sumL[b]+sumR[b+2]-2*sumR[N+1-(N-b-b)+1])
    #print("------------------------")
print(ans)

Submission status: Accepted

Solution code:
import math
L, N = map(int, input().split())
X = [None for i in range(N)]
DistAntiClock, DistClock = [0 for i in range(N+1)], [0 for i in range(N+1)]
for i in range(N):
    X[i] = int(input())
    DistAntiClock[i+1] = DistAntiClock[i] + 2 * X[i]
for i in range(N):
    DistClock[i+1] = DistClock[i] + (L - X[-1-i]) * 2

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

print(maxLength)

Submission status: Accepted

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

X = sorted(X)

ma = 0
for k in range(2):
    if k == 1:
        X = [L-X[-i] for i in range(1, N+1)]
    s = X[0]
    for i in range(1, N):
        if i % 2 == 1:
            s += L - X[-(i//2)-1] + X[i//2]
        else:
            s += X[i//2] + (L - X[-(i//2)])

    ma = max(ma, s)
    lt = (N-1) // 2 if N % 2 == 1 else -N//2
    for i in range(1, N):
        if lt > 0:
            if N % 2 == 1:
                s += X[lt] - X[i-1]*2 - (L - X[lt + 1])
            else:
                s += X[lt] - X[i-1] * 2 - (L - X[lt + 1])
            lt = 1 + lt - N
            ma = max(ma, s)
        else:
            if N % 2 == 1:
                s += X[lt] - X[i-1] * 2 - (L - X[lt])
            else:
                s += X[lt]*2 - L - X[i-1] * 2
            lt = N + lt
            ma = max(ma, s)

print(ma)

Submission status: Accepted

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

cum_l = [0]
for x in X:
    cum_l.append(cum_l[-1] + x)

cum_r = [0]
for x in reversed(X):
    cum_r.append(cum_r[-1] + L-x)

ans = 0
for st_l in range(1,N+1):
    m = N - st_l
    r = m - m//2
    l = st_l + m//2
    tmp = (cum_l[l] - cum_l[st_l-1] + cum_r[r]) * 2
    if m%2:
        tmp -= (L - X[-r])
    else:
        tmp -= X[l-1]
    ans = max(ans, tmp)

for st_r in range(1,N+1):
    m = N - st_r
    l = m - m//2
    r = st_r + m//2
    tmp = (cum_r[r] - cum_r[st_r-1] + cum_l[l]) * 2
    if m%2:
        tmp -= X[l-1]
    else:
        tmp -= (L - X[-r])
    ans = max(ans, tmp)

print(ans)

Submission status: Accepted

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

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

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

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

itr1 = 0
itr2 = N

a = N%2

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

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

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

Submission status: 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))

#ans0 = X[0]
## 0, -1, 1, -2, ...
#i = 0
#j = N-1
#direc = 1 # direction: left->1, right->-1
#print('X[0]')
#while i!=j:
#    print('L+X[%d]-X[%d]' % (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
#print('X[1]')
#while i!=j:
#    print('L+X[%d]-X[%d]' % (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
#print('X[2]')
#while i!=j:
#    print('L+X[%d]-X[%d]' % (i, j))
#    direc *= -1
#    ans0 += L+X[i]-X[j]
#    if direc==-1:
#        i += 1
#    elif direc==1:
#        j -= 1
#print(ans0)
#
#ans0 = X[3]
#i = 3
#j = N-1
#direc = 1 # direction: left->1, right->-1
#print('X[3]')
#while i!=j:
#    print('L+X[%d]-X[%d]' % (i, j))
#    direc *= -1
#    ans0 += L+X[i]-X[j]
#    if direc==-1:
#        i += 1
#    elif direc==1:
#        j -= 1
#print(ans0)
#
#ans0 = X[4]
#i = 4
#j = N-1
#direc = 1 # direction: left->1, right->-1
#print('X[4]')
#while i!=j:
#    print('L+X[%d]-X[%d]' % (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, ...



''' N^2 case '''
#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
#    print("L-X[%d]" % k)
#    while i!=j:
#        print("L+X[%d]-X[%d]" % (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('='*80)
#
#print(max(ans0, ans1))

Submission status: Accepted

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

sx = list(accumulate(X))
sy = list(accumulate(Y))

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

    mn = min(i - 1, j)
    now = X[i]
    now += 2 * (sx[i - 1] - sx[i - 1 - mn]) + 2 * (sy[j] - sy[j - mn - (j > mn)])
    ans = max(ans, now)

for i in range(N):
    j = N - i

    mn = min(i, j - 1)
    now = Y[j]
    now += 2 * (sx[i] - sx[i - mn - (i > mn)]) + 2 * (sy[j - 1] - sy[j - 1 - mn])
    ans = max(ans, now)

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from itertools import accumulate
L, N = map(int, input().split())
X = [int(input()) for _ in range(N)]
Y = [L - x for x in X][::-1]

sx = [0] + list(accumulate(X))
sy = [0] + list(accumulate(Y))

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

    now = X[i]
    now += 2 * (sx[i] - sx[i - mn]) + 2 * (sy[j] - sy[j - mn - (i < j)])
    ans = max(ans, now)

    now = Y[j]
    now += 2 * (sx[i] - sx[i - mn - (i > j)]) + 2 * (sy[j] - sy[j - mn])
    ans = max(ans, now)

print(ans)

Submission status: Accepted

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


def partial():
    L, N = [int(elem) for elem in fin().split()]
    X_list = [0]
    X_list.extend([int(fin()) for _ in range(N)])
    X_list.append(L)
    N += 2

    # this does not work in PyPy because of the slowness
    # memo = [[[None] * 2  for _ in range(N + 1)] for _ in range(N + 1)]

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


    # dp[i][j][k] = the longest possible total distance when the trees of X_list[i:j] are available
    # and **coming from k (k == 1 -> forward, otherwise backward)**
    dp = [[[0] * 2 for _ in range(N + 1)] for _ in range(N + 1)]

    for w in range(1, N + 1):
        for start in range(1, N - w):
            end = start + w
            dp[start][end][1] = max(dp[start + 1][end][1] + X_list[start] - X_list[start - 1],
                                    dp[start][end - 1][0] + L + X_list[start - 1] - X_list[end - 1])
            dp[start][end][0] = max(dp[start + 1][end][1] + L + X_list[start] - X_list[end],
                                    dp[start][end - 1][0] + X_list[end] - X_list[end - 1])

    return max(dp[1][N - 1])


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

    # compute the prefix and suffix sums of X_list
    prefix_sum_X = [0] * N
    suffix_reverse_sum_X = [0] * N
    cur_sum = 0
    for i, X in enumerate(X_list):
        cur_sum += X
        prefix_sum_X[i] = cur_sum
    cur_sum = 0
    for i in reversed(range(N)):
        cur_sum += L - X_list[i]
        suffix_reverse_sum_X[i] = cur_sum
    # edge cases: no turning
    max_dist = max(X_list[-1], L - X_list[0])
    # cases when firstly moving counter-clockwisely
    for i in range(N - 1):
        # case when turning at i
        stopping_idx = i + (N - i) // 2
        if (N - i - 1) % 2 == 0:
            dist = 2 * X_list[i] + (prefix_sum_X[stopping_idx] - prefix_sum_X[i]) * 2 \
                                 + (suffix_reverse_sum_X[stopping_idx + 1]) * 2 \
                                 - X_list[stopping_idx]
        else:
            dist = 2 * X_list[i] + (prefix_sum_X[stopping_idx - 1] - prefix_sum_X[i]) * 2 \
                                 + (suffix_reverse_sum_X[stopping_idx]) * 2 \
                                 - (L - X_list[stopping_idx])
        # print(dist)
        max_dist = max(max_dist, dist)
    
    # likewise consider cases when clockwisely starting
    for i in range(1, N):
        stopping_idx = (N - i) // 2
        if (N - i) % 2 == 1:
            dist = 2 * (L - X_list[N - i]) + (suffix_reverse_sum_X[stopping_idx + 1] - suffix_reverse_sum_X[N - i]) * 2 \
                                           + prefix_sum_X[stopping_idx] * 2 \
                                           - X_list[stopping_idx]
        else:
            dist = 2 * (L - X_list[N - i]) + (suffix_reverse_sum_X[stopping_idx] - suffix_reverse_sum_X[N - i]) * 2 \
                                           + prefix_sum_X[stopping_idx - 1] * 2 \
                                           - (L - X_list[stopping_idx])
        # print(dist)
        max_dist = max(max_dist, dist)
    return max_dist


print(perfect())

Submission status: Accepted

Solution code:
(L, N) = map(int, input().split())
X = [0 for i in range(N)]
sumld = [0 for i in range(N)]
sumrd = [0 for i in range(N)]
for i in range(N):
    X[i] = int(input())
    sumld[i] = X[i]*2 if i == 0 else sumld[i-1] + X[i]*2
for i in range(N):
    sumrd[N-1-i] = (L-X[N-1-i])*2 if i == 0 else sumrd[N-1-i+1] + (L-X[N-1-i])*2
#print('X: ', X)
#print('sumld: ', sumld)
#print('sumrd: ', sumrd)

ans = 0
if N == 1:
    ans = max(X[0], L-X[0])
else:
    dmax = 0
    for i in range(1, N):
        l = (N-1+i)%N
        r = i
        lnum = l+1
        rnum = N-lnum
        #print('l: ', l)
        #print('r: ', r)
        #print('lnum: ', lnum)
        #print('rnum: ', rnum)

        # start from l
        d = 0
        # end at l
        if lnum > rnum:
            d = sumld[l] + sumrd[r] - X[l]
            if lnum-rnum > 1:
                d -= sumld[l-rnum-1]
        # end at r
        else:
            d = sumld[l] + sumrd[r] - X[l]
            if rnum-lnum > 0:
                d -= sumrd[r+lnum]
        #print('d from l: ', d)
        if d > dmax:
            dmax = d

        # start from r
        d = 0
        # end at l
        if lnum >= rnum:
            d = sumld[l] + sumrd[r] - (L-X[r])
            if lnum-rnum > 0:
                d -= sumld[l-rnum]
        # end at r
        else:
            d = sumld[l] + sumrd[r] - (L-X[r])
            if rnum-lnum > 1:
                d -= sumrd[r+lnum+1]
        #print('d from r: ', d)
        if d > dmax:
            dmax = d
    ans = dmax

print(ans)

Submission status: Accepted

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


def check(T, N):
    X = [0] + T
    P = [0] * (N + 1)
    Q = [0] * (N + 1)
    for i in range(1, N + 1):
        P[i] = P[i - 1] + X[i]
    for i in range(N, 0, -1):
        Q[i - 1] = Q[i] + L - X[i]
    ans = -1
    for i in range(1, N + 1):
        k = N - i
        if k % 2 == 0:
            a = k // 2
            t = 2 * (P[i + a - 1] - P[i - 1]) + 2 * (Q[i + a]) + X[i + a]
        else:
            a = k // 2
            t = 2 * (P[i + a] - P[i - 1]) + 2 * (Q[i + a + 1]) + L - X[i + a + 1]
        ans = max(ans, t)
        # print(t)
    return ans


print(max(check(X, N), check(Y, N)))

Submission status: Accepted

Solution code:
from itertools import accumulate

def getRangeSum(accXs, iFr, iTo):
    return accXs[iTo+1] - accXs[iFr]

def getAns(accXs, accRevXs, Xs, revXs):
    ans = 0
    for i in range(N):
        num = (N-i)//2
        dist = 2 * getRangeSum(accXs, i, i + num-1)
        dist += 2 * getRangeSum(accRevXs, 0, num-1)
        if (N-i)%2 == 0:
            dist -= revXs[num-1]
        else:
            dist += Xs[i + num]
        ans = max(ans, dist)
    return ans

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

revXs = [L-X for X in reversed(Xs)]
accXs = [0] + list(accumulate(Xs))
accRevXs = [0] + list(accumulate(revXs))

print(max(getAns(accXs, accRevXs, Xs, revXs), getAns(accRevXs, accXs, revXs, Xs)))

Submission status: Accepted

Solution code:
# coding:utf-8

import sys


input = sys.stdin.readline


def inpl(): return list(map(int, input().split()))


L, N = inpl()
X = [int(input()) for _ in range(N)]

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

# 累積和
Xcc = [0]  # 反時計回り
Xc = [0]  # 時計回り
for i in range(N):  #燃やして家まで戻ってきたときの距離の総和
    Xcc.append(Xcc[-1] + X[i] * 2)
    Xc.append(Xc[-1] + (L - X[-(1 + i)]) * 2)

# print(Xcc)
# print(Xc)

ans = 0
if N % 2:
    for i in range(1, N):
        # 反時計回り
        t_ccw = (N + i) // 2  # 反時計回りで最後に燃やす木
        t_cw = N - t_ccw  # 時計回りで最後に燃やす木
        ans_ccw = Xcc[t_ccw] - Xcc[i - 1] + Xc[t_cw]
        ans_ccw -= X[t_ccw - 1] if i % 2 else (L - X[-t_cw])  # 木を燃やし尽くした後家に帰らなくてよいので，その分引く

        # 時計回り
        t_cw = (N + i) // 2
        t_ccw = N - t_cw
        ans_cw = Xc[t_cw] - Xc[i - 1] + Xcc[t_ccw]
        ans_cw -= (L - X[-t_cw]) if i % 2 else X[t_ccw - 1]

        ans = max(ans, ans_ccw, ans_cw)


else:
    for i in range(1, N):
        # 反時計回り
        t_ccw = (N + i) // 2
        t_cw = N - t_ccw
        ans_ccw = Xcc[t_ccw] - Xcc[i - 1] + Xc[t_cw]
        ans_ccw -= (L - X[-t_cw]) if i % 2 else X[t_ccw - 1]

        # 時計回り
        t_cw = (N + i) // 2
        t_ccw = N - t_cw
        ans_cw = Xc[t_cw] - Xc[i - 1] + Xcc[t_ccw]
        ans_cw -= X[t_ccw - 1] if i % 2 else (L - X[-t_cw])

        ans = max(ans, ans_ccw, ans_cw)

print(ans)

Submission status: Accepted

Solution code:
# coding:utf-8

import sys


input = sys.stdin.readline
INF = float('inf')
MOD = 10 ** 9 + 7


def inpl(): return list(map(int, input().split()))


L, N = inpl()
X = [int(input()) for _ in range(N)]

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

# 累積和
Xcc = [0]  # 反時計回り
Xc = [0]  # 時計回り
for i in range(N):
    Xcc.append(Xcc[-1] + X[i] * 2)
    Xc.append(Xc[-1] + (L - X[-(1 + i)]) * 2)

# print(Xcc)
# print(Xc)

ans = 0
if N % 2:
    for i in range(1, N):
        # 反時計回り
        t_ccw = (N + i) // 2
        t_cw = N - t_ccw
        ans_ccw = Xcc[t_ccw] - Xcc[i - 1] + Xc[t_cw]
        ans_ccw -= X[t_ccw - 1] if i % 2 else (L - X[-t_cw])

        # 時計回り
        t_cw = (N + i) // 2
        t_ccw = N - t_cw
        ans_cw = Xc[t_cw] - Xc[i - 1] + Xcc[t_ccw]
        ans_cw -= (L - X[-t_cw]) if i % 2 else X[t_ccw - 1]

        ans = max(ans, ans_ccw, ans_cw)


else:
    for i in range(1, N):
        # 反時計回り
        t_ccw = (N + i) // 2
        t_cw = N - t_ccw
        ans_ccw = Xcc[t_ccw] - Xcc[i - 1] + Xc[t_cw]
        ans_ccw -= (L - X[-t_cw]) if i % 2 else X[t_ccw - 1]

        # 時計回り
        t_cw = (N + i) // 2
        t_ccw = N - t_cw
        ans_cw = Xc[t_cw] - Xc[i - 1] + Xcc[t_ccw]
        ans_cw -= X[t_ccw - 1] if i % 2 else (L - X[-t_cw])

        ans = max(ans, ans_ccw, ans_cw)

print(ans)

Submission status: Accepted

Solution code:
import sys
#区間をN-1個決め、その両端をゴールとして一番遠い点を原点まで選んで距離を求め、最後に最大を出す
def 解():
    L,N=[int(_) for _ in input().split()]
    aX=[int(_) for _ in sys.stdin.readlines()]
    iMax = max(aX[0],L-aX[0],aX[-1],L-aX[-1])
    #accX = [0]*(N+1)
    accX={}
    accX[-1]=0
    accX[0]=aX[0]
    for i in range(1,N):
        accX[i]=accX[i-1]+aX[i]
    dMemo = {}
    def getAccX(iS,iE):
        if (iS,iE) in dMemo:
            return dMemo[(iS,iE)]
        else:
            r = accX[iE]-accX[iS]
            dMemo[(iS,iE)] = r
            return r
    if 1 < N:
        for i in range(N-1):
            lN = min(i,N-i-1)
            rN = min(i+1,N-i-1)
            #R1 = aX[i]+ 2*sum(aX[i-lN:i]) + 2*(rN*L-(sum(aX[i+1:i+rN+1])))
            #R1 = aX[i]+ 2*(accX[i-1]-accX[i-lN-1]) + 2*(rN*L-(accX[i+rN]-accX[i]))
            R1 = aX[i]+ 2*(getAccX(i-lN-1,i-1)) + 2*(rN*L-(getAccX(i,i+rN)))
            i += 1
            lN = min(i,N-i)
            rN = min(i,N-i-1)
            #R2 = (L- aX[i])+ 2*sum(aX[i-lN:i]) + 2*(rN*L-(sum(aX[i+1:i+rN+1])))
            #R2 = (L- aX[i])+ 2*(accX[i-1]-accX[i-lN-1]) + 2*(rN*L-(accX[i+rN]-accX[i]))
            R2 = (L- aX[i])+ 2*(getAccX(i-lN-1,i-1)) + 2*(rN*L-getAccX(i,i+rN))

            iMax = max(R1,R2,iMax)
    print(iMax)
解()

Submission status: Accepted

Solution code:
import sys
def 解():
    L,N=[int(_) for _ in input().split()]
    aX=[int(_) for _ in sys.stdin.readlines()]
    iMax = max(aX[0],L-aX[0],aX[-1],L-aX[-1])
    accX = [0]*(N+1)
    accX[0]=aX[0]
    for i in range(1,N):
        accX[i]=accX[i-1]+aX[i]

    if 1 < N:
        for i in range(N-1):

            lN = min(i,N-i-1)
            rN = min(i+1,N-i-1)
            #R1 = aX[i]+ 2*sum(aX[i-lN:i]) + 2*(rN*L-(sum(aX[i+1:i+rN+1])))
            R1 = aX[i]+ 2*(accX[i-1]-accX[i-lN-1]) + 2*(rN*L-(accX[i+rN]-accX[i]))

            i += 1
            lN = min(i,N-i)
            rN = min(i,N-i-1)
            #R2 = (L- aX[i])+ 2*sum(aX[i-lN:i]) + 2*(rN*L-(sum(aX[i+1:i+rN+1])))
            R2 = (L- aX[i])+ 2*(accX[i-1]-accX[i-lN-1]) + 2*(rN*L-(accX[i+rN]-accX[i]))

            iMax = max(R1,R2,iMax)
    print(iMax)
解()

Submission status: Accepted

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

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

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

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

    dist_max = 0

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



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


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



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

        if dist_max < dist_1:
            dist_max = dist_1

        if dist_max < dist_2:
            dist_max = dist_2

        #print(n_left, dist_1, dist_2, dist_max)

    print(dist_max)
    return

main()

Submission status: Accepted

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


psumL = [0 for i in range(n + 2)]
for i in range(n) :
    psumL[i + 1] = psumL[i] + a[i];
psumR = [0 for i in range(n + 2)]
for i in range(n) :
    psumR[n - i] = psumR[n - i + 1] + L - a[n - i - 1];


ans = max(a[n - 1], L - a[0])
for useL in range(1, n) :
    useR = n - useL
    if (useL == useR) : 
        ans = max(ans, 2 * (psumL[useL] + psumR[n - useR + 1]) - min(a[useL  - 1], L - a[n - useR]))
    if (useL > useR) : 
        skipL = useL - useR 
        ans = max(ans, 2 * (psumL[useL] - psumL[skipL] + psumR[n - useR + 1]) - (L - a[n - useR]))
        ans = max(ans, 2 * (psumL[useL] - psumL[skipL - 1] + psumR[n - useR + 1]) - a[useL - 1])
    if (useR > useL) :
        skipR = useR - useL
        #print(psumR[n - useR + 1] - psumR[n - skipR + 1], psumL[useL])
        ans = max(ans, 2 * (psumL[useL] + psumR[n - useR + 1] - psumR[n - skipR + 1]) - a[useL - 1])
        ans = max(ans, 2 * (psumL[useL] + psumR[n - useR + 1] - psumR[n - skipR + 2]) - (L - a[n - useR]))

print(ans)

Submission status: Accepted

Solution code:
import sys

l, n = map(int, input().split())
x = [int(input()) for _ in range(n)]

x_sum = [0]
for i in range(n):
	x_sum.append(x_sum[-1] + x[i])
ans = x[-1]
for i in range(n-1):
	num = x[i]
	e = (i+n) // 2
	if (n-1-i) % 2 == 1:
		num += l * (n-1-i)
		num += 2 * (x_sum[e] - x_sum[i]) - x[i]
		num -= 2 * (x_sum[n] - x_sum[e]) - x[e]
	else:
		num += l * (n-1-i)
		num += 2 * (x_sum[e] - x_sum[i]) - x[i] + x[e]
		num -= 2 * (x_sum[n] - x_sum[e+1])

	ans = max(ans, num)

x = [l-x[n-i] for i in range(1, n+1)]

x_sum = [0]
for i in range(n):
	x_sum.append(x_sum[-1] + x[i])
for i in range(n-1):
	num = x[i]
	e = (i+n) // 2
	if (n-1-i) % 2 == 1:
		num += l * (n-1-i)
		num += 2 * (x_sum[e] - x_sum[i]) - x[i]
		num -= 2 * (x_sum[n] - x_sum[e]) - x[e]
	else:
		num += l * (n-1-i)
		num += 2 * (x_sum[e] - x_sum[i]) - x[i] + x[e]
		num -= 2 * (x_sum[n] - x_sum[e+1])

	ans = max(ans, num)

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)

Submission status: Accepted

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

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)


def main():
    l,n = LI()
    x = [I() for _ in range(n)]
    if n == 1:
        return max(x[0], l-x[0])

    ir = [0]
    for c in x:
        ir.append(ir[-1] + c*2)
    jr = [0]
    for c in x[::-1]:
        jr.append(jr[-1] + (l-c)*2)
    jr = jr[::-1]

    r = max(x[-1], l-x[0])
    for i in range(n-1):
        k = (n - i) // 2 + i
        t = 0
        if (n-i) % 2 == 0:
            t += ir[k] - ir[i]
            t += jr[k+1] + l - x[k]
        else:
            t += ir[k] - ir[i] + x[k]
            t += jr[k+1]
        if r < t:
            r = t

    x = [l-c for c in x][::-1]
    tr = ir[::-1]
    ir = jr[::-1]
    jr = tr
    for i in range(n-1):
        k = (n - i) // 2 + i
        t = 0
        if (n-i) % 2 == 0:
            t += ir[k] - ir[i]
            t += jr[k+1] + l - x[k]
        else:
            t += ir[k] - ir[i] + x[k]
            t += jr[k+1]
        if r < t:
            r = t

    return r


print(main())

Submission status: Accepted

Solution code:
from sys import stdin
from itertools import repeat
def main():
    L, n = map(int, stdin.readline().split())
    a = map(int, stdin.read().split(), repeat(10, n))
    sr = [0] * (n + 1)
    sl = [0] * (n + 1)
    for i in xrange(n):
        sl[i+1] = sl[i] + a[i]
    for i in xrange(n - 1, 0, -1):
        sr[i-1] = sr[i] + L - a[i]
    ans = 0
    for i in xrange(n):
        l = i
        r = n - 1 - i
        if l < r:
            r = l + 1
        else:
            l = r
        t = (sr[i] - sr[i+r] + sl[i] - sl[i-l]) * 2 + a[i]
        if ans < t:
            ans = t
    for i in xrange(n - 1, -1, -1):
        l = i
        r = n - 1 - i
        if l > r:
            l = r + 1
        else:
            r = l
        t = (sr[i] - sr[i+r] + sl[i] - sl[i-l]) * 2 + L - a[i]
        if ans < t:
            ans = t
    print ans
main()

Submission status: Runtime Error

Solution code:
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)

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)