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:
a = list(map(int,input().split()))

b = []
bbb = []
su =0 
s = 0
po = 0
for i in range(a[1]):
	k = int(input())
	b.append(k)
for i in range(a[1]):
	bbb.append(b[-(i+1)])
k = 0
ppp = 0
for i in range(1,a[1]):
	s = b[i-1]
	k = i
	po = b[i-1]
	s = b[i-1]
	for j in range(a[1]-i):
		if j % 2 == 0:
			s += a[0] - bbb[ppp] + po
			po = bbb[ppp]
			ppp += 1
		else:
			s += a[0] - po + b[k]
			po = b[k]
			k += 1
	su = max(su,s)
	ppp = 0

for i in range(1,a[1]):
	s = bbb[i-1]
	k = i
	po = bbb[i-1]
	s = a[0]-bbb[i-1]
	for j in range(a[1]-i):
		if j % 2 != 0:
			s += a[0] - bbb[k] + po
			po = bbb[k]
			k += 1
		else:
			s += a[0] - po + b[ppp]
			po = b[ppp]
			ppp += 1
	su = max(su,s)
	ppp = 0

print(su)

Submission status: Wrong Answer

Solution code:
a = list(map(int,input().split()))

b = []
bbb = []
su =0 
s = 0
po = 0
for i in range(a[1]):
	b.append(int(input()))
	bbb.append(b[-(i+1)])
k = 0
ppp = 0
for i in range(1,a[1]):
	s = b[i-1]
	k = i
	po = b[i-1]
	s = b[i-1]
	for j in range(a[1]-i):
		if j % 2 == 0:
			s += a[0] - bbb[ppp] + po
			po = bbb[ppp]
			ppp += 1
		else:
			s += a[0] - po + b[k]
			po = b[k]
			k += 1
	su = max(su,s)
	ppp = 0

for i in range(1,a[1]):
	s = bbb[i-1]
	k = i
	po = bbb[i-1]
	s = a[0]-bbb[i-1]
	for j in range(a[1]-i):
		if j % 2 != 0:
			s += a[0] - bbb[k] + po
			po = bbb[k]
			k += 1
		else:
			s += a[0] - po + b[ppp]
			po = b[ppp]
			ppp += 1
	su = max(su,s)
	ppp = 0

print(su)

Submission status: Wrong Answer

Solution code:
a = list(map(int,input().split()))

b = []
bbb = []
su =0 
s = 0
po = 0
for i in range(a[1]):
	b.append(int(input()))
	bbb.append(b[-(i+1)])
k = 0
ppp = 0
for i in range(1,a[1]):
	s = b[i-1]
	k = i
	po = b[i-1]
	s = b[i-1]
	for j in range(a[1]-i):
		if j % 2 == 0:
			s += a[0] - bbb[ppp] + po
			po = bbb[ppp]
			ppp += 1
		else:
			s += a[0] - po + b[k]
			po = b[k]
			k += 1
	su = max(su,s)
	ppp = 0
	s = bbb[i-1]
	k = i
	po = bbb[i-1]
	s = a[0]-bbb[i-1]
	for j in range(a[1]-i):
		if j % 2 != 0:
			s += a[0] - bbb[k] + po
			po = bbb[k]
			k += 1
		else:
			s += a[0] - po + b[ppp]
			po = b[ppp]
			ppp += 1
	su = max(su,s)
	ppp = 0

print(su)

Submission status: Wrong Answer

Solution code:
a = list(map(int,input().split()))

b = []
bbb = []
su =0 
s = 0
po = 0
for i in range(a[1]):
	k = int(input())
	b.append(k)
for i in range(a[1]):
	bbb.append(b[-(i+1)])
k = 0
ppp = 0
for i in range(1,a[1]):
	s = b[i-1]
	k = i
	po = b[i-1]
	s = b[i-1]
	for j in range(a[1]-i):
		if j % 2 == 0:
			s += a[0] - bbb[ppp] + po
			po = bbb[ppp]
			ppp += 1
		else:
			s += a[0] - po + b[k]
			po = b[k]
			k += 1
	su = max(su,s)
	ppp = 0

for i in range(1,a[1]):
	s = bbb[i-1]
	k = i
	po = bbb[i-1]
	s = a[0]-bbb[i-1]
	for j in range(a[1]-i):
		if j % 2 != 0:
			s += a[0] - bbb[k] + po
			po = bbb[k]
			k += 1
		else:
			s += a[0] - po + b[ppp]
			po = b[ppp]
			ppp += 1
	su = max(su,s)
	ppp = 0

print(su)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000000)
ln=list(map(int,input().split()))
l=ln[0]
n=ln[1]
x=[int(input()) for i in range(n)]

def far(x):
    f = len(x)
    if f <3:
        return False
    else:
        s = 0
        while (x[s+1]-x[s]) == (x[f-s-1]-x[f-s-2]) and s < f//2:
            s += 1
        return (x[s+1]-x[s]) >= (x[f-s-1]-x[f-s-2])
    
def burn(x,p,w):
    if len(x) == 1:
        return w + max(abs(x[0]-p),abs(l-abs(x[0]-p)))
    elif p != 0:
        y = [] + x
        for i in range(len(x)):
            if x[i] > p:
                y[i] = x[i] -p
            else:
                y[i] = x[i] -p+l
        return burn(y,0,w)

    else:
        if x[0] > (l-x[len(x)-1]) or far(x):
            p = x[0]
            del x[0]
            w2 = w+p
            return burn(x,p,w2)
        else:
            p = x[len(x)-1]
            del x[len(x)-1]
            w2 = w+l-p
            return burn(x,p,w2)  

print(burn(x,0,0))

Submission status: Wrong Answer

Solution code:
L,N=input().split()
L,N=int(L),int(N)
X=list()
X.append(0)
for i in range(N):
    X.append(int(input()))

dp = [[[0,0] for i in range(N+1)] for j in range(N+1)]
dp[1][0][0]=X[0]
dp[0][1][1]=L-X[-1]
ans=0
for i in range(0,N+1):
    for j in range(max(0,2-i),N+1):
        #print("i,j=",i,j)
        if i+j > N:
            break
        if i>0:
            fromi=0
            fromj=0
            if i>1:
                fromi=X[i]-X[i-1]+dp[i-1][j][0]
            if j>0:
                fromj=dp[i-1][j][1]+X[i]+L-X[N+1-j]
            #print(fromi,fromj)
            dp[i][j][0]=max(fromi,fromj)

        if j>0:
            fromi=0
            fromj=0
            if i>0:
                fromi=X[i]+L-X[N+1-j]+dp[i][j-1][0]
            if j>1:
                fromj=dp[i][j-1][1]+(X[N-j+2]-X[N-j+1])
            #print(fromi,fromj)
            dp[i][j][1]=max(fromi,fromj)

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

Submission status: Wrong Answer

Solution code:
def solve(L, N, X):
  maxLength = 0

  scSum = [0 for i in range(N)]
  for i in range(N):
    sumLength = X[i]
    currentPos = X[i]
    s = i + 1
    e = N - 1
    for j in range(N - i - 1):
      if j & 1 == 1:
        sumLength += X[s] - currentPos + L
        currentPos = X[s]
        s += 1
      else:
        sumLength += currentPos - X[e] + L
        currentPos = X[e]
        e -= 1

    if maxLength < sumLength:
      maxLength = sumLength

  ccSum = [0 for i in range(N)]
  for i in range(N):
    sumLength = L - X[N - i - 1]
    currentPos = L - X[N - i - 1]
    s = i + 1
    e = N - 1
    for j in range(N - i - 1):
      if j & 1 == 1:
        sumLength += L - X[N - s - 1] - currentPos + L
        currentPos = L - X[N - s - 1]
        s += 1
      else:
        sumLength += currentPos - L - X[N - e - 1] + L
        currentPos = L - X[N - e - 1]
        e -= 1

    if maxLength < sumLength:
      maxLength = sumLength

  return maxLength


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

print(solve(L, N, X))

Submission status: Wrong Answer

Solution code:
def solve(L, N, X):
  scSum = [0 for i in range(N)]
  for i in range(N):
    sumLength = X[i]
    currentPos = X[i]
    s = i + 1
    e = N - 1
    for j in range(N - i - 1):
      if j & 1 == 1:
        sumLength += X[s] - currentPos + L
        currentPos = X[s]
        s += 1
      else:
        sumLength += currentPos - X[e] + L
        currentPos = X[e]
        e -= 1

    scSum[i] = sumLength

  X = [L - X[N - i - 1] for i in range(N)]
  ccSum = [0 for i in range(N)]
  for i in range(N):
    sumLength = X[i]
    currentPos = X[i]
    s = i + 1
    e = N - 1
    for j in range(N - i - 1):
      if j & 1 == 1:
        sumLength += X[s] - currentPos + L
        currentPos = X[s]
        s += 1
      else:
        sumLength += currentPos - X[e] + L
        currentPos = X[e]
        e -= 1

    ccSum[i] = sumLength

  print(scSum)
  print(ccSum)

  return max([max(scSum), max(ccSum)])


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

print(solve(L, N, X))

Submission status: Wrong Answer

Solution code:
from sys import stdin
import numpy as np
L,N=[int(x) for x in stdin.readline().rstrip().split()]
a=[]
for i in range(N):
    a.append(int(input()))
a=list(a)
a.insert(0,0)
a.append(L)
b=list(reversed(a))

a=np.array(a)

b=np.array(b)

a=a[1:]-a[:-1]

b=abs(b[1:]-b[:-1])

resa = np.cumsum(a)
resb = np.cumsum(b)


ans=0
for i in range(N):
    if resa[0] > resb[0]:
        ans+=resa[0]
        resb=resb+resa[0]
        resa=resa-resa[0]
        resa=resa[resa!=0]
    else :
        ans+=resb[0]
        resa=resa+resb[0]
        resb=resb-resb[0]
        resb=resb[resb!=0]
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

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

if n > 2000:
	sys.exit()

dp = [[[-(10 ** 20), -(10 ** 20)] for _ in range(n)] for _ in range(n)]
dp[0][n-1][0] = x[0]
dp[0][n-1][1] = l - x[n-1]

for g in range(n-2, -1, -1):
	for i in range(0, n-g):
		j = i+g
		if i > 0 and j < n-1:
			dp[i][j][0] = max(dp[i-1][j][0] + (x[i]-x[i-1]), dp[i][j+1][1] + l - (x[j+1]-x[i]))
			dp[i][j][1] = max(dp[i-1][j][0] + l - (x[j]-x[i-1]), dp[i][j+1][1] + (x[j+1]-x[j]))
		elif i == 0:
			dp[i][j][0] = dp[i][j+1][1] + l - (x[j+1]-x[i])
			dp[i][j][1] = dp[i][j+1][1] + (x[j+1]-x[j])
		else:
			dp[i][j][0] = dp[i-1][j][0] + (x[i]-x[i-1])
			dp[i][j][1] = dp[i-1][j][0] + l - (x[j]-x[i-1])

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

print(ans)

Submission status: Wrong Answer

Solution code:
import sys

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

if n > 2000:
	sys.exit()

dp = [[[-(10 ** 20), -(10 ** 20)] for _ in range(n)] for _ in range(n)]
dp[0][n-1][0] = x[0]
dp[0][n-1][1] = l - x[n-1]

for g in range(n-2, -1, -1):
	for i in range(0, n-g):
		j = i+g
		if i > 0 and j < n-1:
			dp[i][j][0] = max(dp[i-1][j][0] + (x[i]-x[i-1]), dp[i][j+1][1] + l - (x[j+1]-x[i]))
			dp[i][j][1] = max(dp[i-1][j][0] + l - (x[j]-x[i-1]), dp[i][j+1][1] + (x[j+1]-x[j]))
		elif i == 0:
			dp[i][j][0] = dp[i][j+1][1] + l - (x[j+1]-x[i])
			dp[i][j][1] = dp[i][j+1][1] + (x[j+1]-x[j])
		else:
			dp[i][j][0] = dp[i-1][j][0] + (x[i]-x[i-1])
			dp[i][j][1] = dp[i-1][j][0] + l - (x[j]-x[i-1])

ans = 0
for i in range(n):
	for j in range(2):
		ans = max(ans, dp[i][i][j])

print(ans)

Submission status: Wrong Answer

Solution code:
def left(distances):
    assert len(distances) >= 2
    d = distances.pop(0)
    distances[-1] += d
    return d


def right(distances):
    assert len(distances) >= 2
    d = distances.pop(-1)
    distances[0] += d
    return d


def last_left(distances):
    n = (len(distances) - 1) // 2
    d = 0
    for _ in range(n):
        d += left(distances)
        d += right(distances)
    if len(distances) == 2:
        d += left(distances)
    assert len(distances) == 1
    return d


def last_right(distances):
    n = (len(distances) - 1) // 2
    d = 0
    for _ in range(n):
        d += right(distances)
        d += left(distances)
    if len(distances) == 2:
        d += right(distances)
    assert len(distances) == 1
    return d


def main():
    L, N = map(int, input().strip().split())
    X = [0] * N
    for i in range(N):
        X[i] = int(input().strip())

    distances = []
    p = 0
    for x in X:
        distances.append(x - p)
        p = x
    distances.append(L - p)

    dl = last_left(distances[:])
    dr = last_right(distances[:])

    dsl = distances[:]
    for i in range(1, N+1):
        left(dsl)
        tdl = sum(distances[:i]) + last_left(dsl[:])
        if tdl < dl:
            break
        dl = tdl

    dsr = distances[:]
    for i in range(N):
        right(dsr)
        tdr = sum(distances[N-i:]) + last_right(dsr[:])
        if tdr < dr:
            break
        dr = tdr

    print(max(dl, dr))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

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

if n > 2000:
	sys.exit()

dp = [[[-(10 ** 20) for _ in range(2)] for _ in range(n)] for _ in range(n)]
dp[0][n-1][0] = x[0]
dp[0][n-1][1] = l - x[n-1]

for g in range(n-2, -1, -1):
	for i in range(0, n-g):
		j = i+g
		if i > 0 and j < n-1:
			dp[i][j][0] = max(dp[i-1][j][0] + (x[i]-x[i-1]), dp[i][j+1][1] + l - (x[j+1]-x[i]))
			dp[i][j][1] = max(dp[i-1][j][0] + l - (x[j]-x[i-1]), dp[i][j+1][1] + (x[j+1]-x[j]))
		elif i == 0:
			dp[i][j][0] = dp[i][j+1][1] + l - (x[j+1]-x[i])
			dp[i][j][1] = dp[i][j+1][1] + (x[j+1]-x[j])
		else:
			dp[i][j][0] = dp[i-1][j][0] + (x[i]-x[i-1])
			dp[i][j][1] = dp[i-1][j][0] + l - (x[j]-x[i-1])

ans = 0
for i in range(n):
	for j in range(2):
		ans = max(ans, dp[i][i][j])

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import copy
args = input().split()
L = int(args[0])
N = int(args[1])
X = list()
for i in range(N):
    X.append(int(input()))

def burn(X, start):
    now = 0
    total = 0
    if start == "left":
        left = X[0] - now
        now = X[0]
        X.pop(0)
        total += left
    else:
        right = L - X[-1] + now
        now = X[-1]
        X.pop(-1)
        total += right
    for i in range(N-1):
        if now < X[0]:
            left = X[0] - now
        else:
            left = L - now + X[0]

        if now > X[-1]:
            right = now - X[-1]
        else:
            right = L - X[-1] + now

        if left <= right:
            now = X[-1]
            X.pop(-1)
            total += right
        else:
            now = X[0]
            X.pop(0)
            total += left
    return total

X1 = copy.deepcopy(X)
X2 = copy.deepcopy(X)

total1 = burn(X1, "left")
total2 = burn(X2, "right")
print(str(max(total1,total2)))

Submission status: Wrong Answer

Solution code:
import sys

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

if n > 2000:
	sys.exit()

dp = [[[-(10 ** 20) for _ in range(2)] for _ in range(n)] for _ in range(n)]
dp[0][n-1][0] = x[0]
dp[0][n-1][1] = l - x[n-1]

for g in range(n-2, -1, -1):
	for i in range(0, n-g):
		j = i+g
		if i > 0 and j < n-1:
			dp[i][j][0] = max(dp[i-1][j][0] + (x[i]-x[i-1]), dp[i][j+1][1] + l - (x[j+1]-x[i]))
			dp[i][j][1] = max(dp[i-1][j][0] + l - (x[j]-x[i-1]), dp[i][j+1][1] + (x[j+1]-x[j]))
		elif i == 0:
			dp[i][j][0] = dp[i][j+1][1] + l - (x[j+1]-x[i])
			dp[i][j][1] = dp[i][j+1][1] + (x[j+1]-x[j])
		else:
			dp[i][j][0] = dp[i-1][j][0] + (x[i]-x[i-1])
			dp[i][j][1] = dp[i-1][j][0] + l - (x[j]-x[i-1])


ans = 0
for i in range(n):
	for j in range(2):
		ans = max(ans, dp[i][i][j])

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
l,n=list(map(int, input().split()))
s=[]
c=0
x=0

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

while(len(s)>0):
    
    if s[0]-x>l-s[-1]+x:
        c=c+s[0]-x
        x=s[0]
        #print(c,s[0])
        s.pop(0)
    else:
        c=c+l-s[-1]+x
        x=s[-1]-l
        #print(c,s[-1])
        s.pop(len(s)-1)


print(c)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys

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

if n > 2000:
	sys.exit()

dp = [[[-float("inf") for _ in range(2)] for _ in range(n)] for _ in range(n)]
dp[0][n-1][0] = x[0]
dp[0][n-1][1] = l - x[n-1]

for g in range(n-2, -1, -1):
	for i in range(0, n-g):
		j = i+g
		if i > 0 and j < n-1:
			dp[i][j][0] = max(dp[i-1][j][0] + (x[i]-x[i-1]), dp[i][j+1][1] + l - (x[j+1]-x[i]))
			dp[i][j][1] = max(dp[i-1][j][0] + l - (x[j]-x[i-1]), dp[i][j+1][1] + (x[j+1]-x[j]))
		elif i == 0:
			dp[i][j][0] = dp[i][j+1][1] + l - (x[j+1]-x[i])
			dp[i][j][1] = dp[i][j+1][1] + (x[j+1]-x[j])
		else:
			dp[i][j][0] = dp[i-1][j][0] + (x[i]-x[i-1])
			dp[i][j][1] = dp[i-1][j][0] + l - (x[j]-x[i-1])


ans = 0
for i in range(n):
	for j in range(2):
		ans = max(ans, dp[i][i][j])

print(ans)

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
if N%2==0:
    n = N//2
    print([sum(f2[:n])+r[-n]+sum(r2[-n+1:]),sum(f2[:n-1])+f[n-1]+sum(r2[-n:]),sum(f2[:n])-f2[0] +r[n]+sum(r2[-n+1:]),sum(f2[:n-1])+r[n-1]+sum(r2[-n:])-r2[-1]])
    m = max([sum(f2[:n])+r[-n]+sum(r2[-n+1:]),sum(f2[:n-1])+f[n-1]+sum(r2[-n:]),sum(f2[:n])-f2[0] +r[n]+sum(r2[-n+1:]),sum(f2[:n-1])+r[n-1]+sum(r2[-n:])-r2[-1]])
    print(m)

if N%2==1:
    n = N//2
    print([sum(f2[:n])+max(r[n],f[n])+sum(r2[-n:]),sum(f2[:n+1])-f2[0] +r[-n]+sum(r2[-n+1:]),sum(f2[:n-1])+r[n-1]+sum(r2[-n:])-r2[-1]])
    m = max([sum(f2[:n])+max(r[n],f[n])+sum(r2[-n:]),sum(f2[:n+1])-f2[0] +r[-n]+sum(r2[-n+1:]),sum(f2[:n-1])+r[n-1]+sum(r2[-n:])-r2[-1]])
    print(m)

Submission status: Wrong Answer

Solution code:
l,n=map(int,input().split())
x_lst=[int(input())for i in range(n)]
ans=0
a=0
while len(x_lst):
    if x_lst[0]>l-x_lst[-1]:
        a=x_lst.pop(0)
        ans+=a
        x_lst=list(map(lambda x:x-a,x_lst))
    else:
        a=x_lst.pop(-1)
        ans+=l-a
        x_lst=list(map(lambda x:[x+l-a,x-a][x>=a],x_lst))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000000)
ln=list(map(int,input().split()))
l=ln[0]
n=ln[1]
x=[int(input()) for i in range(n)]

def far(x):
    f = len(x)
    if f <3:
        return False
    else:
        s = 0
        while (x[s+1]-x[s]) == (x[f-s-1]-x[f-s-2]) and s < f//2:
            s += 1
        return (x[s+1]-x[s]) >= (x[f-s-1]-x[f-s-2])
    
def burn(x,p,w):
    if len(x) == 1:
        return w + max(abs(x[0]-p),abs(l-abs(x[0]-p)))
    elif p != 0 and p <= l/2:
        y = list(map(lambda t:t-p,x))
        return burn(y,0,w)
    elif p != 0 and p > l/2:
        y = list(map(lambda t:t+l-p,x))
        return burn(y,0,w)
    else:
        if x[0] > (l-x[len(x)-1]) or far(x):
            p = x[0]
            del x[0]
            w2 = w+p
            return burn(x,p,w2)
        else:# x[0] < (l-x[len(x)-1]):
            p = x[len(x)-1]
            del x[len(x)-1]
            w2 = w+l-p
            return burn(x,p,w2)  

print(burn(x,0,0))

Submission status: Wrong Answer

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

x = []
y = 0
z = 0
j = 0
for i in range(N):
  x.append(int(input()))
  
while x != []:
  if min(x) - y >= L - max(x) + y:
    z += min(x) - y
    y = min(x)
    x.remove(min(x))
  else:
    z += L - max(x) + y
    y = max(x) - L
    x.remove(max(x))

      
print(z)

Submission status: Wrong Answer

Solution code:
def solve(L, N, X):
  dp = [0 for i in range(2 ** N)]
  for i in range(2 ** N):
    sumLength = 0
    currentPos = 0
    s = 0
    e = len(X) - 1
    for j in range(N):
      if i >> j & 1 == 0:
        sumLength += X[s] - currentPos + (L if currentPos > X[s] else 0)
        currentPos = X[s]
        s += 1
      else:
        sumLength += currentPos - X[e] + (L if currentPos < X[-1] else 0)
        currentPos = X[e]
        e -= 1

    dp[i] = sumLength

  return max(dp)


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

print(solve(L, N, X))

Submission status: Wrong Answer

Solution code:
l,n=map(int,input().split())
x_lst=[int(input())for i in range(n)]
ans=0
a=0
while len(x_lst)!=1:
    if x_lst[0]>l-x_lst[-1]:
        a=x_lst.pop(0)
        ans+=a
        x_lst=list(map(lambda x:x-a,x_lst))
    else:
        a=x_lst.pop(-1)
        ans+=l-a
        x_lst=list(map(lambda x:[x+l-a,x-a][x>=a],x_lst))
print(ans)

Submission status: Wrong Answer

Solution code:
import copy


"""
l, n = [10, 6]
x = [1, 2, 3, 6, 7, 9]
"""
l, n = [int(i) for i in input().split()]
x = [0 for _ in range(n)]
for i in range(n):
    x[i] = int(input())
x.sort()
"""
x = queue.Queue
for i in range(n):
    x.get(_x[i])
"""
"""
count = 0
prev = 0
while len(x) > 0:
    if prev <= x[0] <= x[-1]:
        if x[0] - prev > prev + l - x[-1]:
            count += x[0] - prev
            prev = x[0]
            x = x[1:]
        else:
            count += prev + l - x[-1]
            prev = x[-1]
            x = x[:-1]
    elif x[0] <= prev <= x[-1]:
        if prev - x[0] >= x[-1] - prev:
            count += prev - x[0]
            prev = x[0]
            x = x[1:]
        else:
            count += x[-1] - prev
            prev = x[-1]
            x = x[:-1]
    else:
        if prev - x[-1] > x[0] + l - prev:
            count += prev - x[-1]
            prev = x[-1]
            x = x[:-1]
        else:
            count += x[0] + l - prev
            prev = x[0]
            x = x[1:]
    print("x:{} prev:{} count:{}".format(x, prev, count))
"""

def right(i, j):
    # iからjまでの時計回りの距離
    if i < j:
        return i + l - j
    else:
        return i - j

def left(i, j):
    # iからjまでの反時計回りの距離
    if i < j:
        return j - i
    else:
        return j + l - i

_max = 0
for i in range(1, n-1):
    # x[i],x[i+1]は通らない
    # x[i+1]->x[i-1]->x[i+2]->x[i-2]
    _x = copy.deepcopy(x)
    _x = _x[i+2:n]+_x[0:i+1]
    # print(_x)
    count = 0
    prev = x[i+1]
    while len(_x) > 0:
        #print("i:{} count:{} prev:{}".format(i, count, prev))
        count += left(prev, _x[-1])
        prev = _x[-1]
        _x = _x[:-1]
        if len(_x) > 0:
            # print("i:{} count:{} prev:{}".format(i, count, prev))
            count += right(prev, _x[0])
            prev = _x[0]
            _x = _x[1:]
    # print("i:{} count:{}".format(i, count + min(abs(l - prev), prev)))
    _max = max(_max, count + min(abs(l - prev), prev))

    """
    _x = copy.deepcopy(x)
    _x = _x[i+3:n]+_x[0:i+2]
    count = 0
    prev = x[i]
    while len(_x) > 0:
        # print("i:{} count:{} prev:{}".format(i, count, prev))
        count += right(prev, _x[0])
        prev = _x[0]
        _x = _x[1:]
        if len(_x) > 0:
            # print("i:{} count:{} prev:{}".format(i, count, prev))
            count += left(prev, _x[-1])
            prev = _x[-1]
            _x = _x[:-1]
    print("i:{} count:{}".format(i, count + min(abs(l - prev), prev)))
    _max = max(_max, count + min(abs(l - prev), prev))
    """
print(_max)

Submission status: Wrong Answer

Solution code:
l, n = map(int, input().split())

tree_point = [ int(input()) for i in range(n)]	
tmp_sum = 0
tmp_point = 0

while tree_point:
	# print(tree_point, tmp_sum, tmp_point)
	if (tree_point[0] - tmp_point) % l > ( tmp_point - tree_point[-1]) % l:
		tmp_sum += (tree_point[0] - tmp_point) % l
		tmp_point = tree_point.pop(0)
	else:
		tmp_sum += ( tmp_point - tree_point[-1]) % l
		tmp_point = tree_point.pop()

print(tmp_sum)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000000)

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

c = [True for _ in range(l)]

for i in range(n):
    c[x[i]-1] = False

#print(c)

def burn(ki, check, s, a):
#    print('start = ' + str(s) + ' now = ' + str(a))

    if len(set(check)) == 1 and check[0] == True:
        print(a)
        exit(0)
    
    mi = -1
    ma = 0
    for i in range(l):
        if check[(s + i) % l] == False:
            if mi == -1:
                mi = i
            ma = i
    
#    print('mi = ' + str(mi), 'ma = ' + str(ma))

    j = abs(mi)
    g = abs((l - ma + s) % l)

#    print('j = ' + str(j), 'g = ' + str(g))
            
    nxt = 0

    if j >= g:
        a += j
        nxt = mi
        check[(s + j) % l] = True

    else:
        a += g
        nxt = ma
        check[(s + g) % l] = True

#    print(check)
        
    burn(ki, check, nxt, a)

burn(x, c, 0, 0)

Submission status: Wrong Answer

Solution code:
L,N = map(int,input().split(" "))
zahyo = []
for i in range(N):
    zahyo.append(int(input()))
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)%L)
            ima = cl
        else:
            ancl = zaco.pop()
            dist += ((L-ancl+ima)%L)
            ima = ancl
    if dist > MAX:
        MAX = dist
print(MAX)

Submission status: Wrong Answer

Solution code:
l,n = map(int, input().split())
k = n-1
a = []
b = []
c = []
for i in range(n):
    t = int(input())
    a.append(t)
    b.append(l-t)
    c.append(1)
p = 0
q=0
res = 0
f = 0
x=0
for i in range(n):
    if i == n-1:
        res+=max(a[p] ,abs(b[k-q]))
    else:
        if a[p] >=abs(b[k-q]):
            res += a[p]
            f += a[p]
            if  i==0: x = 0
            else:x= a[p-1]
            p +=1
            if c[p] == 1:
                a[p] -=f
                c[p]+=1
            if c[k-p]==1:
                b[k-q] +=f
                c[k-p]+=1
            #b[k-q] -=x
        else:
            res += b[k-q]
            f -= b[k-q]
            if  i==0: x = 0
            else:x= b[k-q-1]
            q +=1
            if c[p] == 1:
                a[p] +=f
                c[p]+=1
            if c[k-p]==1:
                b[k-q] -=f
                c[k-p]+=1
            #a[p] -=x
print(res)

Submission status: Wrong Answer

Solution code:
def func(i, j, p):

    global X, dp, used, L, N

    if used[i][j][p]:
        return dp[i][j][p]
    else:
        used[i][j][p] = True
        if i == j:
            return 0
        else:
            if p == 0:
                temp1 = X[i + 1] - X[i] + func(i + 1, j, 0)
                temp2 = X[i] + L - X[j] + func(i + 1, j, 1)
                temp = max(temp1, temp2)
            else:
                temp1 = X[j] - X[j - 1] + func(i, j - 1, 1)
                temp2 = L - X[j] + X[i] + func(i, j - 1, 0)
                temp = max(temp1, temp2)
            dp[i][j][p] = temp
            return temp

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

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

dp = [[[0] * 2 for _ in range(N)] for _ in range(N)]
used = [[[False] * 2 for _ in range(N)] for _ in range(N)]

ans = max(X[0] + func(0, N - 1, 0), L - X[-1] + func(0, N - 1, 1))
print(dp)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000000)

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

c = [True for _ in range(l)]

for i in range(n):
    c[x[i]-1] = False

print(c)

def burn(ki, check, s, a):
#    print('start = ' + str(s) + ' now = ' + str(a))

    if len(set(check)) == 1 and check[0] == True:
        print(a)
        exit(0)
    
    mi = -1
    ma = 0
    for i in range(l):
        if check[(s + i) % l] == False:
            if mi == -1:
                mi = i
            ma = i
    
#    print('mi = ' + str(mi), 'ma = ' + str(ma))

    j = abs(mi)
    g = abs((l - ma + s) % l)

#    print('j = ' + str(j), 'g = ' + str(g))
            
    nxt = 0

    if j >= g:
        a += j
        nxt = mi
        check[(s + j) % l] = True

    else:
        a += g
        nxt = ma
        check[(s + g) % l] = True

#    print(check)
        
    burn(ki, check, nxt, a)

burn(x, c, 0, 0)

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


dp = [[0] * (n) for i in range(n)]

for i in range(n):
    for j in range(n):
        if j > i:
            if i != 0:
                if j != n-1:
                    dp[i][j] = max(dp[i][j], max(dp[i-1][j] + x[i] - x[i-1], dp[j + 1][i] + l - x[j + 1] + x[i]))
                else:
                    dp[i][j] = max(dp[i][j], max(dp[i - 1][j] + x[i] - x[i - 1], dp[i-1][j] + x[i] - x[i-1]))
            elif i == 0 and j != n-1:
                dp[i][j] = max(dp[i][j], x[0] + l - x[j+1])
            else:
                dp[i][j] = max(dp[i][j], x[0])
        elif j < i:
            if i != n-1:
                dp[i][j] = max(dp[i][j], dp[i + 1][j] + x[i + 1] - x[i])
            elif i == n-1 and j-1 >= 0:
                dp[i][j] = max(dp[i][j], x[j-1] + x[j-1] + l - x[n-1])
            else:
                dp[i][j] = l - x[n-1]

ans = 0
for i in range(n):
    if i > 0:
        ans = max(ans, dp[i][i - 1] + max(x[i] - x[i - 1], l - (x[i] - x[i - 1])))
    if i < n-1:
        ans = max(ans, dp[i][i+1] + max(x[i+1] - x[i], l - (x[i+1] - x[i])))

print(ans)

Submission status: Wrong Answer

Solution code:
l, n = map(int, input().split())
Xi = []
idx = [0] + [i+1 for i in range(n)]
Xi.append(0)
for i in range(n):
    Xi.append(int(input()))
ans = 0

def Dfwd(next, now):
    # print('in Dfwd, next, now', next, now)
    if next < now:
        return l-(Xi[now]-Xi[next])
    else:
        return Xi[next] - Xi[now]

def Dback(next, now):
    # print('in Dback, next, now', next, now)
    if next > now:
        return l-(Xi[next] -Xi[now])
    else:
        return Xi[now] - Xi[next]

while len(idx)>1:
    dfwd = Dfwd(idx[1], idx[0])
    dback = Dback(idx[-1], idx[0])
    # print('dfwd dback is ',dfwd, dback)
    if dfwd > dback:
        ans += dfwd
        idx.pop(0)
        # print('前に進んだよ')
    else:
        ans += dback
        tmp = idx[-1]
        idx.pop(0)
        idx.pop(len(idx)-1)
        idx = [tmp] + idx[:]
        # print('後に進んだよ')
    # print(ans)
    # print("残っているのは", idx )
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
l,n=list(map(int, input().split()))
s=[]
c=0
x=0

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

while(len(s)>0):
    
    if s[0]-x>l-s[-1]+x:
        c=c+s[0]
        x=s[0]
        #print(c,s[0])
        s.pop(0)
    else:
        c=c+l-s[-1]
        x=-s[-1]
        #print(c,s[-1])
        s.pop(len(s)-1)


print(c)