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:
import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(1000000)


# Debug output
def chkprint(*args):
    names = {
        id(v): k
        for k, v in inspect.currentframe().f_back.f_locals.items()
    }
    print(', '.join(
        names.get(id(arg), '???') + ' = ' + repr(arg) for arg in args))


# Binary converter
def to_bin(x):
    return bin(x)[2:]


def li_input():
    return [int(_) for _ in input().split()]


def gcd(n, m):
    if n % m == 0:
        return m
    else:
        return gcd(m, n % m)


def gcd_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = gcd(v, L[i])

    return v


def lcm(n, m):
    return (n * m) // gcd(n, m)


def lcm_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = lcm(v, L[i])

    return v


# Width First Search (+ Distance)
def wfs_d(D, N, K):
    """
    D: 隣接行列(距離付き)
    N: ノード数
    K: 始点ノード
    """

    dfk = [-1] * (N + 1)
    dfk[K] = 0

    cps = [(K, 0)]
    r = [False] * (N + 1)
    r[K] = True
    while len(cps) != 0:
        n_cps = []
        for cp, cd in cps:
            for i, dfcp in enumerate(D[cp]):
                if dfcp != -1 and not r[i]:
                    dfk[i] = cd + dfcp
                    n_cps.append((i, cd + dfcp))
                    r[i] = True

        cps = n_cps[:]

    return dfk


# Depth First Search (+Distance)
def dfs_d(v, pre, dist):
    """
    v:  現在のノード
    pre: １つ前のノード
    dist: 現在の距離

    以下は別途用意する
    D: 隣接リスト(行列ではない)
    D_dfs_d: dfs_d関数で用いる，始点ノードから見た距離リスト
    """

    global D
    global D_dfs_d

    D_dfs_d[v] = dist

    for next_v, d in D[v]:
        if next_v != pre:
            dfs_d(next_v, v, dist + d)

    return


def sigma(N):
    ans = 0
    for i in range(1, N + 1):
        ans += i
    return ans


def comb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2, r + 1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p - 1, r, p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def bisearch(L, target):
    low = 0
    high = len(L) - 1
    
    while low <= high:
        mid = (low + high) // 2
        guess = L[mid]
        if guess == target:
            return True
        elif guess < target:
            low = mid + 1
        elif guess > target:
            high = mid - 1
    if guess != target:
        return False

# --------------------------------------------

dp = None


def main():
    L, N = li_input()
    X = [int(input()) for _ in range(N)]

    finalans = -1
    
    current = X[0]
    li = 1
    ri = len(X) - 1
    ans = X[0]
    N_ = N-1
    while N_:
        if current < X[li]:
            l_dist = X[li] - current
        else:
            l_dist = (L - current) + X[li]

        if current > X[ri]:
            r_dist = current - X[ri]
        else:
            r_dist = current + (L - X[ri])

        if l_dist > r_dist:
            ans += l_dist
            current = X[li]
            li += 1
        elif l_dist < r_dist:
            ans += r_dist
            current = X[ri]
            ri -= 1
        else:
            ans += l_dist
            current = X[li]
            li += 1

        N_ -= 1

    finalans = max(finalans, ans)

    current = X[0]
    li = 1
    ri = len(X) - 1
    ans = X[0]
    N_ = N-1
    while N_:
        if current < X[li]:
            l_dist = X[li] - current
        else:
            l_dist = (L - current) + X[li]

        if current > X[ri]:
            r_dist = current - X[ri]
        else:
            r_dist = current + (L - X[ri])

        if l_dist > r_dist:
            ans += l_dist
            current = X[li]
            li += 1
        elif l_dist < r_dist:
            ans += r_dist
            current = X[ri]
            ri -= 1
        else:
            ans += r_dist
            current = X[ri]
            ri -= 1

        N_ -= 1

    finalans = max(finalans, ans)

    current = X[-1]
    li = 0
    ri = len(X) - 2
    ans = L - X[-1]    
    N_ = N-1
    while N_:
        if current < X[li]:
            l_dist = X[li] - current
        else:
            l_dist = (L - current) + X[li]

        if current > X[ri]:
            r_dist = current - X[ri]
        else:
            r_dist = current + (L - X[ri])

        if l_dist > r_dist:
            ans += l_dist
            current = X[li]
            li += 1
        elif l_dist < r_dist:
            ans += r_dist
            current = X[ri]
            ri -= 1
        else:
            ans += l_dist
            current = X[li]
            li += 1

        N_ -= 1

    finalans = max(finalans, ans)

    current = X[-1]
    li = 0
    ri = len(X) - 2
    ans = L - X[-1]
    N_ = N-1
    while N_:
        if current < X[li]:
            l_dist = X[li] - current
        else:
            l_dist = (L - current) + X[li]

        if current > X[ri]:
            r_dist = current - X[ri]
        else:
            r_dist = current + (L - X[ri])

        if l_dist > r_dist:
            ans += l_dist
            current = X[li]
            li += 1
        elif l_dist < r_dist:
            ans += r_dist
            current = X[ri]
            ri -= 1
        else:
            ans += r_dist
            current = X[ri]
            ri -= 1

        N_ -= 1

    finalans = max(finalans, ans)

    print(finalans)

main()

Submission status: Wrong Answer

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

ans = 0
left = 0
right = N - 1
now = 0
while left <= right:
    if abs(X[left] - now) > abs(L - X[right] + now):
        ans += abs(X[left] - now)
        now = X[left]
        left += 1
    else:
        ans += abs(L - X[right] + now)
        now = -(L - X[right])
        right -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
l, n = map(int, input().split())
xs = [int(input()) for _ in range(n)]
ans, now, fin = 0, 0, False
i, j = 0, n - 1
while i <= j:
    root1 = xs[i] - now if now < xs[i] else xs[i] + (l - now)
    root2 = now - xs[j] if now > xs[j] else now + (l - xs[j])
    print(root1, root2)
    ans += max(root1, root2)
    if root1 > root2:
        now = xs[i]
        i += 1
    else:
        now = xs[j]
        j -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
li=list(map(int,input().split()))
l=li[0]
N=li[1]
xl=[]
for i in range(N):
    xl.append(int(input()))
s=0
n=N
for i in range(N):
    if xl[0]>l-xl[n-1]:
        dma=xl[0]
        s+=dma
        for i in range(n):
            xl[i]=(xl[i]-dma)%l
        xl.remove(0)
        #print(xl)
        n-=1
    else:
        dma=xl[n-1]
        s+=(l-dma)
        for i in range(n):
            xl[i]=(xl[i]-dma)%l
        xl.remove(0)
        n-=1
print(s)

Submission status: Wrong Answer

Solution code:
from collections import deque
L,N=map(int,input().split())
Y=[int(input()) for i in range(N)]
anss=[]
for k in range(2):
    X=deque([i for i in Y])
    ans=0
    p=0
    i=k
    while(len(X)>0):
        a=(X[0]-p)%L
        b=(-X[-1]+p)%L
        if i%2==0:
            ans+=a
            p=X.popleft()
        else:
            ans+=b
            p=X.pop()
        i+=1
    anss.append(ans)
X=deque([Y[i] for i in range(N-1)])
ans=0
p=0
i=1
while(len(X)>0):
    a=(X[0]-p)%L
    b=(-X[-1]+p)%L
    if i%2==0:
        ans+=a
        p=X.popleft()
    else:
        ans+=b
        p=X.pop()
    i+=1
anss.append(ans)
X=deque([Y[i] for i in range(1,N)])
ans=0
p=0
i=0
while(len(X)>0):
    a=(X[0]-p)%L
    b=(-X[-1]+p)%L
    if i%2==0:
        ans+=a
        p=X.popleft()
    else:
        ans+=b
        p=X.pop()
    i+=1
anss.append(ans)
print(max(anss))

Submission status: Wrong Answer

Solution code:
INF = float('inf')

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

dp = [[[-INF] * (2) for B in range(N+1)] for A in range(N+1)]
dp[1][N][0] = 0
dp[1][N][1] = 0
for A in range(1, N+1):
    for B in reversed(range(A, N+1)):
        # C=0 ccw
        C = 0
        if B > 1:  # ccw
            dp[A][B-1][0] = max(dp[A][B-1][0], dp[A][B][C] + Xs[B+1] - Xs[B])
        if A < N:  # cw
            dp[A+1][B][1] = max(dp[A+1][B][1], dp[A][B][C] + (L - Xs[B+1]) + Xs[A])
        # C=1 cw
        C = 1
        if B > 1:  # ccw
            dp[A][B-1][0] = max(dp[A][B-1][0], dp[A][B][C] + Xs[A-1] + (L - Xs[B]))
        if A < N:  # cw
            dp[A+1][B][1] = max(dp[A+1][B][1], dp[A][B][C] + Xs[A] - Xs[A-1])

ans = 0
for A in range(N+1):
    for B in range(N+1):
        for C in range(2):
            ans = max(ans, dp[A][B][C])
print(ans)

Submission status: Wrong Answer

Solution code:
s = input().split(" ")
s = [int(i) for i in s]
x = []
for i in range(s[1]) : 
    x.append(int(input()))

def getDistance(x , y , tokei , L) : 
    if not tokei : 
        dist = y[0] - x[0]
        if dist < 0 : return L + dist
        return dist
    else : 
        dist = y[1] - x[1]
        if dist < 0 : return L + dist
        return dist
    
def getDistanceFromList(startPoint , candidates , tokei , L) : 
    dists = []
    for cand in candidates : 
        dist = getDistance(startPoint , cand , tokei , L)
        dists.append(dist)
    return dists


L = s[0]

def getPosition(x , L) : 
    new_x = []
    for elem in x : 
        new_x.append((elem , L - elem))
    return new_x

new_x = getPosition(x , L)

start_position = (0 , 0)
all_dist = 0
while not len(new_x) == 0 :
    rights = getDistanceFromList(start_position , new_x , True , L)
    lefts = getDistanceFromList(start_position , new_x , False , L)
    
    rights_min = min(rights)
    lefts_min = min(lefts)
    if rights_min > lefts_min : 
        next_index = rights.index(rights_min)
        all_dist += rights_min
    else : 
        next_index = lefts.index(lefts_min)
        all_dist += lefts_min
    start_position = new_x.pop(next_index)

print(all_dist)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

def walklen(posN, posT,dir,L):
    if posN < posT:
        if dir == 0:
            return posT - posN
        else:
            return L - (posT - posN)
    else:
        if dir == 0:
            return L - (posN - posT)
        else:
            return posN -posT

cand_num = 2**(N-1)
ans = []
for i in range(cand_num):
    st = "{:>0"+str(N-1)+"}"
    dirs = list(map(int,st.format(bin(i)[2:])))
    dist = 0
    pos = 0
    tempX = X.copy()
    for j in range(N-1):
        dist+= walklen(pos,tempX[dirs[j]*-1],dirs[j],L)
        pos = tempX[dirs[j]*-1]
        _ = tempX.pop(dirs[j]*-1)
    dist+= max(walklen(pos,tempX[0],0,L),walklen(pos,tempX[0],1,L))
    ans.append(dist)

print("ans:",max(ans))

Submission status: Wrong Answer

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

now=0
dist=0
for i in range(n):
    right = x[0]  - now if now <= x[0]  else l - now + x[0]
    left  = now - x[-1] if now >= x[-1] else l - x[-1] + now
    if right >= left :
        now   = x[0]
        dist += right
        x.pop(0)
    else:
        now   = x[-1]
        dist += left
        x.pop(-1)
print(dist)

Submission status: Wrong Answer

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 > 2000:
        return -1
    r = 0
    for i in range(n):
        t = x[i]
        j = n - 1
        while i < j:
            t += x[i] + l - x[j]
            i += 1
            if i == j:
                break
            t += l - x[j] + x[i]
            j -= 1
        if r < t:
            r = t

    for j in range(n):
        t = l - x[j]
        i = 0
        while i < j:
            t += l - x[j] + x[i]
            j -= 1
            if i == j:
                break
            t += x[i] + l - x[j]
            i += 1
        if r < t:
            r = t

    return r


print(main())

Submission status: Wrong Answer

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

for i in range(N):
    arr.append(int(input()))
    
import copy 
tmp = copy.deepcopy(arr)
pos = 0
ans = 0

for i in range(N):
    # Clockwise
    if pos>tmp[-1]: # 裏側にあるケース
        clk = pos-tmp[-1] # 単に引けばよい
    else: # 先にあるケース
        clk = pos + L - tmp[-1] # グルっと回る
    # Counterclockwise
    if tmp[0]>pos: # 先にあるケース
        ctclk = tmp[0] - pos # 単に引けばよい
    else: # 裏側にあるケース
        ctclk = tmp[0] + L - pos # グルっと回る
#     print(tmp, clk, ctclk)
    if clk >= ctclk:
        ans += clk
        pos = tmp[-1]
        tmp = tmp[0:-1]
    else:
        ans += ctclk
        pos = tmp[0]
        tmp = tmp[1:]

print(ans)

Submission status: Wrong Answer

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

max_length = 0
for i in range(2):
    now_at = L*i
    y=[]
    length = 0
    for num in x:
        y.append(num)
    while len(y)>0:
        if y[0] > now_at:
            if y[0]-now_at >=now_at+L-y[-1]:
                length += y[0]-now_at
                now_at=y[0]
                y.pop(0)
            else:
                length += now_at+L-y[-1]
                now_at=y[-1]
                y.pop(-1)
        else:
            if now_at-y[-1] >= y[0]+L-now_at:
                length += now_at-y[-1]
                now_at=y[-1]
                y.pop(-1)
            else:
                length += y[0]+L-now_at
                now_at=y[0]
                y.pop(0)
    if max_length < length:
        max_length=length
print(max_length)

Submission status: Wrong Answer

Solution code:
l,n=map(int,input().split())
x1=[]
x2=[]
for i in range(n):
    t=int(input())
    x1.append(t)
    x2.append(l-t)
x2.reverse()
ans1=0
ans2=0
z=0
pm=0
u1=0
u2=0

ans1+=x1[0]
z=x1[0]
pm=1
u1+=1


while u1+u2<n:
    if pm==1:
        if x1[u1]-z>x2[u2]+z:
            ans1+=x1[u1]-z
            z=x1[u1]
            pm=1
            u1+=1
        else:
            ans1+=x2[u2]+z
            z=x2[u2]
            pm=-1
            u2+=1
    else:
        if x2[u2]-z>x1[u1]+z:
            ans1+=x2[u2]-z
            z=x2[u2]
            pm=-1
            u2+=1
        else:
            ans1+=x1[u1]+z
            z=x1[u1]
            pm=1
            u1+=1
   # print(ans1)

z=0
pm=0
u1=0
u2=0
ans2+=x2[0]
z=x2[0]
pm=-1
u2+=1
while u1+u2<n:
    if pm==1:
        if x1[u1]-z>x2[u2]+z:
            ans2+=x1[u1]-z
            z=x1[u1]
            pm=1
            u1+=1
        else:
            ans2+=x2[u2]+z
            z=x2[u2]
            pm=-1
            u2+=1
    else:
        if x2[u2]-z>x1[u1]+z:
            ans2+=x2[u2]-z
            z=x2[u2]
            pm=-1
            u2+=1
        else:
            ans2+=x1[u1]+z
            z=x1[u1]
            pm=1
            u1+=1
ans3=0
ans4=0
u1=0
u2=0
ans3+=x1[u1]
u1+=1
pm=1
while u1+u2<n:
    if pm==1:
        ans3+=x2[u2]
        u2+=1
        pm=-1
    else:
        ans3+=x1[u1]
        u1+=1
        pm=1
u1=0
u2=0
ans4+=x2[u2]
u2+=1
pm=-1
while u1+u2<n:
    if pm==1:
        ans4+=x2[u2]
        u2+=1
        pm=-1
    else:
        ans4+=x1[u1]
        u1+=1
        pm=1
print(max(ans1,ans2,ans3,ans4))

Submission status: Wrong Answer

Solution code:
import sys

def diff_dist_1(p1, p2, l):
    if p2-p1 < 0:
        return l+p2-p1
    else:
        return p2-p1

def diff_dist_2(p1, p2, l):
    if p1-p2 < 0:
        return l+p1-p2
    else:
        return p1-p2

if __name__ == '__main__':
    # a not yum, bc yum
    l, n = [int(i) for i in input().split()]
    tree_list = [int(input()) for i in range(n)]
    total_len = 0
    cur_pos = 0
    while len(tree_list) != 0:
        if len(tree_list) == 1:
            total_len += max(diff_dist_1(cur_pos, tree_list[0],l), diff_dist_2(cur_pos, tree_list[0],l))
            break
        if diff_dist_1(cur_pos, tree_list[0],l) > diff_dist_2(cur_pos, tree_list[-1],l):
            total_len += diff_dist_1(cur_pos, tree_list[0],l)
            cur_pos = tree_list[0]
            tree_list.pop(0)
        else:
            total_len += diff_dist_2(cur_pos, tree_list[-1],l)
            cur_pos = tree_list[-1]
            tree_list.pop(-1)

    print(total_len)

Submission status: Wrong Answer

Solution code:
x = input()
y = x.split(" ")
L = int(y[0])
N = int(y[1])
tree = []
index = 0
d_left = 0
d_right = 0
total = 0
cur = 0
flag = True #初手左周り　家の前を通るたびに切り替え
while(N > 0):
    tree.append(int(input()))
    N -= 1
N = int(y[1])
while(N > 0):
    if(flag):
        d_left = tree[index] - cur
        d_right = cur - tree[index - 1] + L
    else:
        d_left = tree[index] - cur + L
        d_right = cur - tree[index - 1]
    if(d_left > d_right):
        total += d_left
        cur = tree[0]
        tree.pop(0)
        flag = True
    else:
        total += d_right
        cur = tree[-1]
        tree.pop(-1)
        flag = False
    N -= 1
print(total)

Submission status: Wrong Answer

Solution code:
l,n=map(int,input().split())
m=[]
for i in range(n):
  x=int(input())
  m.append(x)
tem=0
sum=0
for i in range(n):
  if m[0]>tem:
    a=m[0]-tem
  else:
    a=m[0]+l-tem
  if m[n-i-1]<tem:
    b=tem-m[n-i-1]
  else:
    b=tem+l-m[n-i-1]
  if a>b:
    sum+=a
    tem=m[0]
    m.pop(0)
  else:
    sum+=b
    tem=m[n-i-1]
    m.pop(n-i-1)
print(sum)

Submission status: Wrong Answer

Solution code:
inp=raw_input().split()
l=int(inp[0])
n=int(inp[1])
x=[0]
for i in range(n):
	x.append(int(input()))
x.append(l)
ans = 0
left = [[0 for i in range(n+1)] for j in range(n+1)]
right = [[0 for i in range(n+1)] for j in range(n+1)]
for i in range(n+1):
	for j in range(0,n-i+1):
		if(i < n-1):
			left[i+1][j] = max(left[i][j]+(x[i+1] - x[i]), right[i][j]+(l - x[n+1-j] + x[i+1]))
		
		if(j < n-1):
			right[i][j+1] = max(left[i][j]+(l + x[i] - x[n-j]), right[i][j]+(x[n-j+1] - x[n-j]))
		
		ans=max(ans,left[i][j],right[i][j])

print(ans)

Submission status: Wrong Answer

Solution code:
L, N = map(int,input().split())
X = [0] * N
for i in range(N):
    X[i] = int(input())
T = 0
ans = 0
for j in range(N):
  if (X[0] - T) > (L - X[-1] + T):
    ans += (X[0] - T)
    T = X[0]
    del X[0]
  else:
    ans += (L - X[-1] + T)
    T = X[-1] - L
    del X[-1]
print(ans)

Submission status: Wrong Answer

Solution code:
L,N = map(int,input().split(" "))
zahyo = []
for i in range(N):
    zahyo.append(int(input()))
zahyo.sort()
ima = 0
n = 2**N
MAX = 0
for i in range(n):
    zaco = zahyo
    b = bin(i)
    b = b.lstrip("0b")
    length = len(b)
    for j in range(N-1-length):
        b = "0"+b
    blist = list(b)
    dist = 0
    for k in range(N-2):
        if len(zaco) == 0:
            break
        elif blist[k] == 0:
            cl = zaco.pop(0)
            dist+=(cl-ima)
            ima = cl
        else:
            ancl = zaco.pop()
            dist+=(L-ancl+ima)
            ima = ancl
    if dist > MAX:
        MAX = dist
print(MAX)

Submission status: Wrong Answer

Solution code:
l,n=map(int,input().split())
x1=[]
x2=[]
for i in range(n):
    t=int(input())
    x1.append(t)
    x2.append(l-t)
x2.reverse()
ans1=0
ans2=0
z=0
pm=0
u1=0
u2=0

ans1+=x1[0]
z=x1[0]
pm=1
u1+=1


while u1+u2<n:
    if pm==1:
        if x1[u1]-z>=x2[u2]+z:
            ans1+=x1[u1]-z
            z=x1[u1]
            pm=1
            u1+=1
        else:
            ans1+=x2[u2]+z
            z=x2[u2]
            pm=-1
            u2+=1
    else:
        if x2[u2]-z>=x1[u1]+z:
            ans1+=x2[u2]-z
            z=x2[u2]
            pm=-1
            u2+=1
        else:
            ans1+=x1[u1]+z
            z=x1[u1]
            pm=1
            u1+=1
   # print(ans1)

z=0
pm=0
u1=0
u2=0
ans2+=x2[0]
z=x2[0]
pm=-1
u2+=1
while u1+u2<n:
    if pm==1:
        if x1[u1]-z>=x2[u2]+z:
            ans2+=x1[u1]-z
            z=x1[u1]
            pm=1
            u1+=1
        else:
            ans2+=x2[u2]+z
            z=x2[u2]
            pm=-1
            u2+=1
    else:
        if x2[u2]-z>=x1[u1]+z:
            ans2+=x2[u2]-z
            z=x2[u2]
            pm=-1
            u2+=1
        else:
            ans2+=x1[u1]+z
            z=x1[u1]
            pm=1
            u1+=1
print(max(ans1,ans2))

Submission status: Wrong Answer

Solution code:
import numpy as np
L, N = list(map(int,input().split()))
xs = []
for k in range(N):
    xs.append(int(input()))
xs = np.array(xs)

xs_clock = np.copy(xs)
xs_reverse = L - np.copy(xs)

sum_dist = 0
# print(sum_dist, xs_clock, xs_reverse)
while True:
    clock_min, reverse_min = np.min(xs_clock),np.min(xs_reverse)
#     print(clock_min, reverse_min)

    if clock_min > reverse_min:
#         print('crock')
        ma = clock_min
        sum_dist += ma
        xs_clock -= ma
        xs_reverse += ma
        use_inds = xs_clock>0
        xs_clock = xs_clock[use_inds]
        xs_reverse = xs_reverse[use_inds]
    else:
#         print('reverse')
        ma = reverse_min
        sum_dist += ma
        xs_clock += ma
        xs_reverse -= ma
        use_inds = xs_reverse>0
        xs_clock = xs_clock[use_inds]
        xs_reverse = xs_reverse[use_inds]
#     print(sum_dist, xs_clock, xs_reverse)
    if len(xs_reverse) == 0:
        break
print(sum_dist)

Submission status: Wrong Answer

Solution code:
import math
l,n=map(int,input().split())
arr=[]
for i in range(n):
	x=int(input())
	arr.append(x)
ans=0
arr=sorted(arr)
d=0 #anticlockwise 1 clockwise
for i in range(n):
	if i==0:
		ans+=arr[i]
		d=0
	else:
		aa=arr[i]
		bb=arr[i-1]+abs(arr[i]-l)
		mm=min(aa,bb)
		# print("tis is mm",mm)
		# print(aa,bb)
		if d==0:
			if mm==bb:
				ans+=mm 
				d=1
			else:
				d=0
				ans+=mm
		else:
			if mm==aa:
				ans+=mm 
				d=0
			else:
				d=1
				ans+=mm
		# ans+=mm
print(ans)

Submission status: Wrong Answer

Solution code:
l,n = map(int,input().split())
x = set()
for i in range(n):
    x.add(int(input()))
cnt = 0
s = 0
while len(x): 
    if min(x)-s <= l-max(x)+s:
        cnt +=l-max(x)+s
        s = max(x)
        x.remove(max(x))
    else:
        cnt += min(x)-s
        s = min(x)
        x.remove(min(x))
print(cnt)

Submission status: Wrong Answer

Solution code:
ln = input().split()
l = int(ln[0])
n = int(ln[1])
x = [0]*n
for i in range(n):
    x[i] = int(input())
x.sort()
ans = 0
while x!=[]:
    a = x[0]
    b = l-x[-1]
    if a>b:
        ans += a
        x = x[1:]
    else:
        ans += b
        x = x[:-1]
    m = max(a,b)
    for i in range(len(x)):
        if x[i]>m:
            x[i] = x[i]-m
        else:
            x[i] = x[i]-m+l
            
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

def diff_dist(p1, p2):
    if p1 > p2:
        return max(p1-p2, 10-(p1-p2))
    else:
        return max(p2-p1, 10-(p2-p1))

if __name__ == '__main__':
    # a not yum, bc yum
    l, n = [int(i) for i in input().split()]
    tree_list = [int(input()) for i in range(n)]
    total_len = 0
    cur_pos = 0
    while len(tree_list) != 0:
        if len(tree_list) == 1:
            total_len += diff_dist(cur_pos, tree_list[0])
            break
        if diff_dist(cur_pos, tree_list[0]) > diff_dist(cur_pos, tree_list[-1]):
            total_len += diff_dist(cur_pos, tree_list[0])
            cur_pos = tree_list[0]
            tree_list.pop(0)
        else:
            total_len += diff_dist(cur_pos, tree_list[-1])
            cur_pos = tree_list[-1]
            tree_list.pop(-1)

    print(total_len)

Submission status: Wrong Answer

Solution code:
from collections import deque
import copy
l,n = map(int,input().split())
a = [int(input()) for i in range(n)]
b = deque(copy.deepcopy(a))
ima = b.popleft()
tmp = ima
for i in range(n-1):
    if b[0] < ima:
        migi = l+b[0] -ima
    else:
        migi = b[0] - ima
    if b[-1] < ima:
        hidari = ima - b[-1]
    else:
        hidari = ima+l-b[-1]
    if migi > hidari:
        x = b.popleft()
        tmp += migi
        ima = x
    else:
        x = b.pop()
        tmp += hidari
        ima = x
b = deque(copy.deepcopy(a))
ima = b.pop()
tmp2 = l-ima
for i in range(n-1):
    if b[0] < ima:
        migi = l+b[0] -ima
    else:
        migi = b[0] - ima
    if b[-1] < ima:
        hidari = ima - b[-1]
    else:
        hidari = ima+l-b[-1]
    if migi > hidari:
        x = b.popleft()
        tmp2 += migi
        ima = x
    else:
        x = b.pop()
        tmp2 += hidari
        ima = x
print(max(tmp,tmp2))

Submission status: Wrong Answer

Solution code:
l,n=[int(i) for i in input().split()]
tree=[]
p=0
ans=0
for i in range(n):
    tree.append(int(input()))
while(tree!=[]):
    if((tree[0]-p)%l>(p-tree[len(tree)-1])%l):
        ans+=(tree[0]-p)%l
        p=tree[0]
        tree.pop(0)
    else:
        ans+=(p-tree[len(tree)-1])%l
        p=tree[len(tree)-1]
        tree.pop(len(tree)-1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


l,n = list(map(int, input().split()))
x = [None]*n
for i in range(n):
    x[i] = int(input())

dpl = [[0]*(n+1) for _ in range(n+1)]
dpr = [[0]*(n+1) for _ in range(n+1)]
dpl[1][0] = x[0] # dpl: x[i-1]にいる
dpr[0][1] = l - x[-1] # dpr: x[n-j]にいる
for i in range(n+1):
    for j in range(n+1):
        if i+j>=n or i==j==0:
            continue
        if i>=1:
            dpl[i+1][j] = max(dpl[i+1][j], dpl[i][j] + x[i] - x[i-1])
            dpr[i][j+1] = max(dpr[i][j+1], dpl[i][j] + x[i-1] + (l - x[n-j-1]))
        if j>=1:
            dpl[i+1][j] = max(dpl[i+1][j], dpr[i][j] + (l - x[n-j]) + x[i])
            dpr[i][j+1] = max(dpr[i][j+1], dpr[i][j] + x[n-j] - x[n-j-1])
        
            
ansl = max(dpl[i][n-i] for i in range(n+1))
ansr = max(dpr[i][n-i] for i in range(n+1))
ans = max(ansl, ansr)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def dist_index(i,xlist):
  dist=xlist[i-1]
  x2list=deque(xlist[i:])
  oldpos=dist
  
  while(len(x2list)>0):
    newpos=x2list.pop()
    dist+=(oldpos-newpos)%L
    oldpos=newpos
    
    if len(x2list)==0:
      break
      
    newpos=x2list.popleft()
    dist+=(newpos-oldpos)%L
    oldpos=newpos
    
  return dist

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

maxdist=0
# start by counter-clockwise
for i in range(1,N+1):  
  dist=dist_index(i,xlist)
  maxdist=max(maxdist,dist)

# start by clockwise
xlist_rev=[]
for i in reversed(range(N)):
  xlist_rev.append(L-xlist[i])
#print(xlist_rev)

for i in range(1,N+1):
  dist=dist_index(i,xlist_rev)
  maxdist=max(maxdist,dist)

print(maxdist)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

# start by counter-clockwise
maxdist_ccw=0
for i in range(1,N+1):
  dist=pos=xlist[i-1]
  x2list=deque(xlist[i:])
  #print(dist,x2list)

  # repeat cw,ccw,cw...
  while(len(x2list)>0):
    dist+=(pos-x2list[-1])%L
    pos=x2list.pop()
    
    if len(x2list)==0:
      break
    
    dist+=(x2list[0]-pos)%L
    pos=x2list.popleft()
      
  maxdist_ccw=max(maxdist_ccw,dist)
#print(maxdist_ccw)

# start by clockwise
maxdist_cw=0
for i in range(1,N+1):
  pos=xlist[-i]
  dist=L-pos
  x2list=deque(xlist[:-i])
  #print(dist,x2list)

  # repeat ccw,cw,ccw...
  while(len(x2list)>0):
    dist+=(x2list[0]-pos)%L
    pos=x2list.popleft()
    
    if len(x2list)==0:
      break
    
    dist+=(pos-x2list[-1])%L
    pos=x2list.pop()
      
  maxdist_cw=max(maxdist_cw,dist)
#print(maxdist_cw)

print(max(maxdist_ccw,maxdist_cw))

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

# start by counter-clockwise
maxdist_ccw=0
for i in range(1,N+1):
  x2list=xlist[:]  
  dist=pos=x2list[i-1]
  x2list=x2list[i:]
  #print(dist,x2list)

  # repeat cw,ccw,cw...
  while(len(x2list)>0):
    dist+=(pos-x2list[-1])%L
    pos=x2list[-1]
    x2list.pop()
    
    if len(x2list)==0:
      break
    
    dist+=(x2list[0]-pos)%L
    pos=x2list[0]
    x2list=x2list[1:]
      
  maxdist_ccw=max(maxdist_ccw,dist)
#print(maxdist_ccw)

# start by clockwise
maxdist_cw=0
for i in range(1,N+1):
  x2list=xlist[:]  
  pos=x2list[-i]
  dist=L-pos
  x2list=x2list[:-i]
  #print(dist,x2list)

  # repeat ccw,cw,ccw...
  while(len(x2list)>0):
    dist+=(x2list[0]-pos)%L
    pos=x2list[0]
    x2list=x2list[1:]
    
    if len(x2list)==0:
      break
    
    dist+=(pos-x2list[-1])%L
    pos=x2list[-1]
    x2list.pop()
      
  maxdist_cw=max(maxdist_cw,dist)
#print(maxdist_cw)

print(max(maxdist_ccw,maxdist_cw))