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: Wrong Answer

Solution code:
def dis_right(a,b,l):#右回りの距離を求める
    if a > b:
        return a - b
    else:
	    return l - (b - a)
def dis_left(a,b,l):#左回りの距離を求める
    if b > a:
        return b - a
    else:
        return l - (a - b)

L, N = (int(i) for i in input().split())  
#L = 10
#N = 6
#X = [1,2,3,6,7,9]
X = []
for i in range(N):
    X.append(int(input()))

now_x = 0

steps = 0
for _ in range(N):
    #print(X)
    #print(now_x)
    dis_l = dis_left(now_x,X[0],L)
    dis_r = dis_right(now_x,X[-1],L)
    if dis_l > dis_r:
        steps += dis_l
        now_x = X[0]
        X.pop(0)
    else:
        steps += dis_r
        now_x = X[-1]
        X.pop()
print(steps)

Submission status: Wrong Answer

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 - 3):
        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: Wrong Answer

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

cur = 0
s   = 0

while(len(a)>0):
    if cur < a[0]:
        if a[0] - cur > cur + N - a[-1]:
            s += a[0] - cur
            cur = a[0]
            a.pop(0)
            
        else:
            s += cur + N - a[-1]
            cur = a[-1]
            a.pop()
                
    else:
        if cur - a[-1] > N - cur + a[0]:
            s  += cur - a[-1]
            cur = a[-1]
            a.pop()
        else:
            s  += N - cur + a[0]
            cur = a[0]
            a.pop(0)
print(s)

Submission status: Wrong Answer

Solution code:
i=input()
i_s=i.split(" ")
L=int(i_s[0])
N=int(i_s[1])
x=[]
for y in range(N):
  x.append(int(input()))
x.append(0)
sum=0
cmin=0
cmax=N-1
cnow=N
for y in range(N):
  if((x[cmin]-x[cnow])%L<(x[cnow]-x[cmax])%L):
    sum+=(x[cnow]-x[cmax])%L
    cnow=cmax
    cmax-=1
  else:
    sum+=(x[cmin]-x[cnow])%L
    cnow=cmin
    cmin+=1
print(sum)

Submission status: Wrong Answer

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

def goback(points, pos):
    limit = len(points) - 1; half = len(points) // 2
    dt = 0;
    for i in range(0, half):
        dt += points[i] - pos + L
        dt += (points[i] - points[limit - i] + L)
        pos = points[limit - i]
    if (len(points) % 2) == 1: dt += points[half] - pos + L
    return(dt)

for i in range(0, N):
    dtotall.append((L - x[N - 1 - i]) + goback(x[0:N - 1 - i], x[N - 1 - i]))

for i in range(0, N - 1):
    dtotalr.append(x[i] + (x[i] + L - x[N - 1]) + goback(x[i + 1:N - 1 - i], x[N - 1]))
dtotalr.append(x[N - 1])

print(max(dtotall + dtotalr))

Submission status: Wrong Answer

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

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

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

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

    return a+L-b


CANDI=list(range(max(1,N//2-100),min(N+1,N//2+100)))
#print(CANDI)

ANS=0
for start in CANDI:
    if start==0 or start<0 or start>N:
        continue

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


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

        

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

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

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

    ANS=max(ANS,ANS1,ANS2)

print(ANS)

Submission status: Wrong Answer

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

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

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

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

    return a+L-b


CANDI=list(range(max(1,N//2-100),min(N+1,N//2+100)))
print(CANDI)

ANS=0
for start in CANDI:
    if start==0 or start<0 or start>N:
        continue

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


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

        

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

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

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

    ANS=max(ANS,ANS1,ANS2)

print(ANS)

Submission status: Wrong Answer

Solution code:
a, b = map(int, input().split())
ans = 0
tree=[]
for i in range(b):
    tree.append(int(input()))
for i in range(b):
    treeman = [tree[i] for i in range(b)]
    pos = 0
    length = 0
    for j in range(b):
        if(j>=i):
            if((j-i)%2 == 0):
                walk = a - treeman[-1] + pos
                length = length + walk
                pos = treeman[-1]
                del treeman[-1]
            else:
                walk = abs(treeman[0] - pos)
                length = length + walk
                pos = treeman[0]
                del treeman[0]
            #print(j,pos,walk,length)
        else:
            del treeman[-1]
    if(ans < length):
        ans = length
    #print(length, ans)
    #print("------------------------")
for i in range(b):
    treeman = [tree[i] for i in range(b)]
    pos = 10
    length = 0
    for j in range(b):
        if(j>=i):
            if((j-i)%2 == 0):
                walk = a - pos + treeman[0]
                length = length + walk
                pos = treeman[0]
                del treeman[0]
            else:
                walk = abs(a-treeman[-1] + pos)
                length = length + walk
                pos = treeman[-1]
                del treeman[-1]
            #print(j,pos,walk,length)
        else:
            del treeman[0]
    if(ans < length):
        ans = length
    #print(length, ans)
    #print("------------------------")
print(ans)

Submission status: Wrong Answer

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[lt-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: Wrong Answer

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[N - lt])
            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[lt-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: Wrong Answer

Solution code:
L,N=map(int,input().split())
X=[]
for i in range(N):
    X.append(int(input()))
distance=0
x=0
r=x-X[-1]+L
l=X[0]-x
for i in range(N):
    if l>r:
        distance+=l
        x=X[0]
        X=X[1:]
        if X:
            r=x-X[-1]+L
            l=X[0]-x
    else:
        distance+=r
        x=X[-1]
        X=X[:-1]
        if X:
            l=X[0]-x+L
            r=x-X[-1]
print(distance)

Submission status: Wrong Answer

Solution code:
L,N=map(int,input().split())
X=[]
for i in range(N):
    X.append(int(input()))
distance=0
x=0
r=x-X[-1]+L
l=X[0]-x
for i in range(N):
    if l>r:
        distance+=l
        x=X[0]
        del X[0]
        if X:
            r=x-X[-1]+L
            l=X[0]-x
    else:
        distance+=r
        x=X[-1]
        del X[-1]
        if X:
            l=X[0]-x+L
            r=x-X[-1]
    
print(distance)

Submission status: Wrong Answer

Solution code:
ln=[int(x) for x in input().split()]
za=[int(input()) for y in range(ln[1])]
s=[0]*ln[1]
for y in range(ln[1]-1):
        for a in range(y,y+int(((ln[1]-y)/2)+0.5)):
            s[y]+=za[a]*2
        for b in range(y+int(((ln[1]-y)/2)+0.5),ln[1]):
            s[y]+=(ln[0]-za[b])*2
        s[y]-=(ln[0]-za[ln[1]-1])*((ln[1]-y+1)%2)
        s[y]-=za[y+int(((ln[1]-y)/2)+0.5)-1]*((ln[1]-y)%2)
print(max(s))

Submission status: Wrong Answer

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: Wrong Answer

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

    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: Wrong Answer

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)])
    print(i - mn)
    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: Wrong Answer

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

Xr = [0] + X

Yr = ["d"]
for i in range(0,N):
    Yr.append( Xr[i+1] - Xr[i])

Yl = ["d"]+[L-X[N-1]]
Yl += Yr[::-1]

answer = 0
for itr in range(1,N):
    sum = 0
    counter = 1
    while counter <= itr:
        sum += Yr[counter]
        counter += 1
    turn = counter-1
    counter2 = 1
    sum2 = sum
    while counter <= N:
        if counter2 % 2 ==1:
            sum2 += Yl[counter2//2+1]
            sum += sum2 
        else:
            sum2 += Yr[turn + counter2//2]
            sum += sum2
        counter += 1
        counter2 += 1
    answer = max(answer,sum)

for itr in range(1,N):
    sum = 0
    counter = 1
    while counter <= itr:
        sum += Yl[counter]
        counter += 1
    turn = counter-1
    counter2 = 1
    sum2 = sum
    while counter <= N:
        if counter2 % 2 ==1:
            sum2 += Yr[counter2//2+1]
            sum += sum2 
        else:
            sum2 += Yl[turn + counter2//2]
            sum += sum2
        counter += 1
        counter2 += 1
    answer = max(answer,sum)
print(answer)

Submission status: Wrong Answer

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
    # import pdb; pdb.set_trace()
    # cases when firstly moving counter-clockwisely
    max_dist = 0
    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)
        # dist = (L - X_list[i]) + prefix_sum_X[i - 1] + (suffix_reverse_sum_X[0] - suffix_reverse_sum_X[i])
        # max_dist = max(max_dist, dist)
    
    return max_dist


print(perfect())

Submission status: Wrong Answer

Solution code:
n = [int(x) for x in input().split()]
L = n[0]
N = n[1]

X = []
for x in range(0,int(N)):
    X.append(int(input()))

stopped = 0
score = 0
for i,x in enumerate(X):
    if i == 0:
        score += x
        stopped = x
    else:
        score += max([L - x + stopped, x - stopped])
        stopped = x

print(score)

Submission status: Wrong Answer

Solution code:
import sys
L,N=map(int,input().split())
X=[int(input()) for i in range(N)]
if N>=3000:
    print(0)
    sys.exit()
dp0=[[0]*(N+1)for i in range(N+1)]
dp1=[[0]*(N+1)for i in range(N+1)]
X=[0]+X
#print(X)
for k in range(1,N+1):
    for i in range(k,-1,-1):
        j=(N-k+i+1)%(N+1)
        #print(k,i,j)
        if i==0:
            dp1[0][j]=L-X[j]
            continue
        if j==0:
            dp0[i][0]=X[i]
            continue
        if i>0 and j>0:
            dp0[i][j]=max(dp0[i-1][j]+X[i]-X[i-1],dp1[i-1][j]+L-X[j]+X[i])
            dp1[i][j] = max(dp0[i][(j + 1)%(N+1)] + X[i] +L- X[j], dp1[i][(j + 1)%(N+1)] + (L+X[(j + 1)%(N+1)] - X[j])%L)
ans=max(X[-1],L-X[1])
for i in range(1,N):
    ans=max(ans,dp0[i][i+1],dp1[i][i+1])
#print(dp0)
#print(dp1)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
L,N=map(int,input().split())
X=[int(input()) for i in range(N)]
dp0=[[0]*(N+1)for i in range(N+1)]
dp1=[[0]*(N+1)for i in range(N+1)]
X=[0]+X
#print(X)
if N>=3000:
    print(0)
    sys.exit()
for k in range(1,N+1):
    for i in range(k,-1,-1):
        j=(N-k+i+1)%(N+1)
        #print(k,i,j)
        if i==0:
            dp1[0][j]=L-X[j]
            continue
        if j==0:
            dp0[i][0]=X[i]
            continue
        if i>0 and j>0:
            dp0[i][j]=max(dp0[i-1][j]+X[i]-X[i-1],dp1[i-1][j]+L-X[j]+X[i])
            dp1[i][j] = max(dp0[i][(j + 1)%(N+1)] + X[i] +L- X[j], dp1[i][(j + 1)%(N+1)] + (L+X[(j + 1)%(N+1)] - X[j])%L)
ans=-1
for i in range(1,N):
    ans=max(ans,dp0[i][i+1],dp1[i][i+1])
#print(dp0)
#print(dp1)
print(ans)

Submission status: Wrong Answer

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


def dist(pl, pr):
    return pl + (L-pr)%L


ans = 0
if N == 1:
    anx = max(X[0], L-X[0])
else:
    X += X
    #print('X: ', X)
    dmax = 0
    for i in range(1, N):
        seg = X[i:i+N]
        #print('seg: ', seg)
        for s in (0, N-1):
            os = (N-1)-s
            cl = N-1    # counterclockwise most
            cr = 0      # clockwise most
            d = 0
            lflg = False
            if s == cl:
                lflg = True
            while True:
                #print('tmpd: ', d)
                # l to l
                if lflg and seg[s] >= seg[os]:
                    d += dist(seg[s], 0)
                    break
                # r to r
                elif not(lflg) and seg[s] <= seg[os]:
                    d += dist(0, seg[s])
                    break
                
                # l to r
                if lflg:
                    d += dist(seg[s], seg[os])
                    # update segment
                    cl = (s-1+L)%L  # move to r by 1
                    cr = os
                    # next
                    s = cr
                    os = cl
                # r to l
                else:
                    d += dist(seg[os], seg[s])
                    # update segment
                    cl = os
                    cr = (s+1+L)%L  # move to l by 1
                    # next
                    s = cl
                    os = cr
                lflg = not(lflg)
            #print('d: ', d)
            if d > dmax:
                dmax = d
    ans = dmax

print(ans)

Submission status: Wrong Answer

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

length = 0
now = 0

while len(x) > 0:
    if (x[0] - now) % L > (now - x[-1]) % L:
        length += (x[0] - now) % L
        now = x[0]
        x.pop(0)
    else:
        length += (now - x[-1]) % L
        now = x[-1]
        x.pop(-1)


print(length)

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


l,n = li()
x = [ni() for _ in range(n)]

dp = [[[0,0] for _ in range(n+1)] for _ in range(n+1)]
left = [0] + x
right = [l] + x[::-1]

for total in range(1,n+1):
    for ccw in range(total+1):
        cw = total - ccw
        if ccw == 0:
            dp[ccw][cw][1] = dp[ccw][cw-1][1] + (right[cw-1] + l - right[cw])
            
        elif cw == 0:
            dp[ccw][cw][0] = dp[ccw-1][cw][0] + (left[ccw] - left[ccw-1])
        
        else:
            dp[ccw][cw][0] = max(dp[ccw-1][cw][1] + (left[ccw] + l - right[cw]),
                                 dp[ccw-1][cw][0] + (left[ccw] - left[ccw-1]))

            dp[ccw][cw][1] = max(dp[ccw][cw-1][1] + (right[cw-1] - right[cw]),
                                 dp[ccw][cw-1][0] + (left[ccw] + l - right[cw]) % l)
ans = 0
for ccw in range(n+1):
    cw = n - ccw
    ans = max(ans, dp[ccw][cw][0], dp[ccw][cw][1])
    
print(ans)

Submission status: Wrong Answer

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

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

if n == 1:
    print(max(x[0], l - x[0]))
    exit()

if n > 2000:
    exit()

#  dp[i][j][k]: 反時計回りにi個、時計回りにj個木を燃やした時で、自分がスタート地点を基準にして
#  反時計回り側にいる(k==0)または時計回り側にいる(k==1)ときに、今までに進んだ距離の最大値
dp = [[[0, 0] for j in range(n+1)] for i in range(n+1)]


#  初期値
dp[1][0][0] = x[0]
dp[0][1][1] = l - x[n-1]

#  dpテーブルの更新（配るDPで書くのがポイントでしたね）
for i in range(n):
    for j in range(n):
        if i + j >= n:
            break
        if dp[i][j][0]:
            dp[i+1][j][0] = max(dp[i+1][j][0], dp[i][j][0] + x[i] - x[i-1])
            dp[i][j+1][1] = max(dp[i][j+1][1], dp[i][j][0] + l - x[n-(j+1)] + x[i-1])
        if dp[i][j][1]:
            dp[i+1][j][0] = max(dp[i+1][j][0], dp[i][j][1] + l - x[n-j] + x[i])
            dp[i][j+1][1] = max(dp[i][j+1][1], dp[i][j][1] + x[n-j] - x[n-(j+1)])


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

print(ans)

Submission status: Wrong Answer

Solution code:
l,n = map(int,input().split())
result = 0
tmp = 0
a = [int(input()) for i in range(n)]
while len(a) >= 2:
  e = abs(min(a)-tmp)
  f = min(tmp,l-tmp)+min(min(a),l-min(a))
  g = abs(max(a)-tmp)
  h = min(tmp,l-tmp)+min(max(a),l-max(a))
  c = min(e,f)
  d = min(g,h)
  maxim = max(c,d)
  result = result + maxim
  if c >= d:
    tmp=min(a)
    a.remove(min(a))
  else:
    tmp=max(a)
    a.remove(max(a))
  print(result)
  print(tmp)
  print(a)
#while len(a) >= 2:
 # result = result + max(min(abs(min(a)-tmp),min(tmp,l-tmp)+min(min(a),l-min(a))),min(abs(max(a)-tmp),min(tmp,l-tmp)+min(max(a),l-max(a))))
  #if min(abs(min(a)-tmp),min(tmp,l-tmp)+min(min(a),l-min(a))) >= min(abs(max(a)-tmp),min(tmp,l-tmp)+min(max(a),l-max(a))):
   # tmp = min(a)
    #a.remove(min(a))
  #elif min(abs(min(a)-tmp),min(tmp,l-tmp)+min(min(a),l-min(a))) < min(abs(max(a)-tmp),min(tmp,l-tmp)+min(max(a),l-max(a))):
   # tmp = max(a)
    #a.remove(max(a))
  #print(result)
  #print(tmp)
  #print(a)
#result = result + max(min(abs(min(a)-tmp),min(tmp,l-tmp)+min(min(a),l-min(a))),min(abs(max(a)-tmp),min(tmp,l-tmp)+min(max(a),l-max(a)))
e = abs(min(a)-tmp)
f = min(tmp,l-tmp)+min(min(a),l-min(a))
g = abs(max(a)-tmp)
h = min(tmp,l-tmp)+min(max(a),l-max(a))
c = min(e,f)
d = min(g,h)
maxim = max(c,d)
result = result + maxim
print(result)

Submission status: Wrong Answer

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

if N > 2000:
    exit()

# dp[d][l][r]: d: 0: 反時計回り(左回り), 1: 時計回り(右回り), l: 左回りで焼いた木の数, r: 右回りで焼いた木の数
dp = [[[0] * (N + 1) for _ in range(N + 1)] for _ in range(2)]

# 初期化
dp[0][1][0] = X[0]
dp[1][0][1] = L - X[-1]

for l in range(N):
    for r in range(N):
        if l + r > N: break

        if dp[0][l][r]:
            curr_x = X[l - 1]

            dp[0][l + 1][r] = max(dp[0][l + 1][r], dp[0][l][r] + X[l] - curr_x)
            dp[1][l][r + 1] = max(dp[1][l][r + 1], dp[0][l][r] + L - X[-(r + 1)] + curr_x)

        if dp[1][l][r]:
            curr_x = X[-r]

            dp[0][l + 1][r] = max(dp[0][l + 1][r], dp[1][l][r] + X[l] + L - curr_x)
            dp[1][l][r + 1] = max(dp[1][l][r + 1], dp[1][l][r] + curr_x - X[-(r + 1)])

ans = 0
for l in range(N):
    r = N - l
    ans = max(ans, dp[0][l][r], dp[1][l][r])

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
L,N = map(int, sys.stdin.readline().split())
f2 = []
r2 = []
for _ in range(N):
    i = int(sys.stdin.readline())
    f2.append(2*i)
    r2.append(2*(L-i))
m = 0
for i in range(min(N,N//2+2)):
    n = (N - i - 1)//2
    if (N-i-1)%2==1:
        tmp = sum(f2[i:i+n+1]) + r2[i+n+1]//2 + sum(r2[n+i+2:])
        if not (i == 0 and n==0):
            tmp2 = sum(r2[-i-n-1:-i]) + f2[n]//2 + sum(f2[:n])
        else:
            tmp2 = sum(r2[-i-n-1:]) + f2[n]//2 + sum(f2[:n])
    else:
        tmp = sum(f2[i:i+n]) + f2[i+n]//2 + sum(r2[n+i+1:])
        if not (i == 0 and n==0):
            tmp2 = sum(r2[-i-n:-i]) + r2[n]//2 + sum(f2[:n])
        else:
            tmp2 = sum(r2[-i-n:]) + r2[n]//2 + sum(f2[:n])
    m = max(m,tmp,tmp2)
print(m)

Submission status: Wrong Answer

Solution code:
import sys
L,N = map(int, sys.stdin.readline().split())
f2 = []
r2 = []
for _ in range(N):
    i = int(sys.stdin.readline())
    f2.append(2*i)
    r2.append(2*(L-i))
m = 0
for i in range(N):
    n = (N - i - 1)//2
    if (N-i-1)%2==1:
        tmp = sum(f2[i:i+n+1]) + r2[i+n+1]//2 + sum(r2[n+i+2:])
        if i != 0:
            tmp2 = sum(r2[-i-n-1:-i]) + f2[n]//2 + sum(f2[:n])
        else:
            tmp2 = sum(r2[-i-n-1:]) + f2[n]//2 + sum(f2[:n])
    else:
        tmp = sum(f2[i:i+n]) + f2[i+n]//2 + sum(r2[n+i+1:])
        if i != 0:
            tmp2 = sum(r2[-i-n:-i]) + r2[n]//2 + sum(f2[:n])
        else:
            tmp2 = sum(r2[-i-n:]) + r2[n]//2 + sum(f2[:n])
    # print(tmp,tmp2)
    m = max(m,tmp,tmp2)
print(m)

Submission status: Wrong Answer

Solution code:
import sys
L,N = map(int, input().split())

f = []
r = []
f2 = []
r2 = []
for _ in range(N):
    i = int(sys.stdin.readline())
    f.append(i)
    r.append(L-i)
    f2.append(2*i)
    r2.append(2*(L-i))

m = 0
for i in range(N):
    n = (N - i - 1)//2
    if (N-i-1)%2==1:
        tmp = sum(f2[i:i+n+1]) + r[i+n+1] + sum(r2[n+i+2:])
        tmp2 = sum(r2[-i-n-1:-i]) + f[n] + sum(f2[:n])
    else:
        tmp = sum(f2[i:i+n]) + f[i+n] + sum(r2[n+i+1:])
        tmp2 = sum(r2[-i-n:-i]) + r[n] + sum(f2[:n])
    m = max(m,tmp,tmp2)
print(m)

Submission status: Wrong Answer

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

def f(L, N, X, p, l, r, d_r):
    # print(p, l, r, d_r, "->", end=" ")
    w = 0
    for _ in range(N - (l + r)):
        if d_r:  # L
            l += 1
            w += X[l] - p
            p = X[l]
            d_r = False
        else:  # R
            r += 1
            w += L - X[-r] + p
            p = X[-r] - L
            d_r = True
    # print(w)
    return w

X_c = [L - i for i in X]

max_l = max(X[i] + f(L, N, X, X[i], i, 0, True) for i in range(1, N+1))
max_r = max(X_c[-i] + f(L, N, X, X[-i] - L, 0, i, False) for i in range(1, N+1))
print(max(max_l, max_r))