Problem: 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.

Submission attempts (in order):
import numpy as np
import sys

L, N = map(int, input().split())
X = np.array([int(sys.stdin.readline()) for _ in range(N)])
Y1 = np.concatenate(([X[0]], X[1:] - X[:-1], [L - X[-1]]))
Y2 = Y1[::-1]


def func(n):
    return np.concatenate((np.full(n + 1, N - n, dtype=np.int), np.arange(N - n - 2, -1, -2), np.arange(N - n - 1, -1, -2)[::-1]))


ans = 0
for n in range(0, (N + 1) // 2):
    a = func(n)
    len1 = np.dot(a, Y1)
    len2 = np.dot(a, Y2)
    ans = max(ans, len1, len2)

print(ans)

import numpy as np
import sys

L, N = map(int, input().split())
X = np.array([int(sys.stdin.readline()) for _ in range(N)])
Y1 = np.concatenate(([X[0]], X[1:] - X[:-1], [L - X[-1]]))

X2 = X[::-1]
Y2 = Y1[::-1]


def func(n):
    return np.concatenate((np.full(n + 1, N - n, dtype=np.int), np.arange(N - n - 2, -1, -2), np.arange(N - n - 1, -1, -2)[::-1]))


if N < 10000:
    ans = 0
    for n in range((N + 1) // 2):
        a = func(n)
        len1 = np.dot(a, Y1)
        len2 = np.dot(a, Y2)
        ans = max(ans, len1, len2)

    print(ans)
else:
    ans = 0
    cn = (N + 1) // 200
    len1 = [0] * cn
    len2 = [0] * cn
    can1 = [0] * cn
    can2 = [0] * cn
    for n in range(0, (N + 1) // 2, 100):
        a = func(n)
        i = n // 100
        len1[i] = np.dot(a, Y1)
        len2[i] = np.dot(a, Y2)
        ans = max(ans, len1[i], len2[i])

    for n, len_ in enumerate(len1):
        if len_ + 50 * L > ans:
            for j in range(100 * n, 100 * n + 100):
                ans = max(np.dot(func(j), Y1), ans)

    for n, len_ in enumerate(len2):
        if len_ + 50 * L > ans:
            for j in range(100 * n, 100 * n + 100):
                ans = max(np.dot(func(j), Y2), ans)
    print(ans)

import numpy as np
import sys

L, N = map(int, input().split())
X = np.array([int(sys.stdin.readline()) for _ in range(N)])
Y1 = np.concatenate(([X[0]], X[1:] - X[:-1], [L - X[-1]]))

X2 = X[::-1]
Y2 = Y1[::-1]


def func(n):
    return np.concatenate((np.full(n + 1, N - n, dtype=np.int), np.arange(N - n - 2, -1, -2), np.arange(N - n - 1, -1, -2)[::-1]))


if N < 10000:
    ans = 0
    for n in range((N + 1) // 2):
        a = func(n)
        len1 = np.dot(a, Y1)
        len2 = np.dot(a, Y2)
        ans = max(ans, len1, len2)

    print(ans)
else:
    ans = 0
    cn = (N + 1) // 200
    len1 = [0] * cn
    len2 = [0] * cn
    can1 = [0] * cn
    can2 = [0] * cn
    for n in range(0, (N + 1) // 2, 100):
        a = func(n)
        i = n // 100
        len1[i] = np.dot(a, Y1)
        len2[i] = np.dot(a, Y2)
        can1[i] = (X[n + (N - n + 100)//2] - 2 * X[n] - (L - X[(N - n - 101)//2])) * 100
        can2[i] = (X2[n + (N - n + 100) // 2] - 2 * X2[n] - (L - X2[(N - n - 101) // 2])) * 100
        ans = max(ans, len1[i], len2[i])

    for n, (len_, can) in enumerate(zip(len1, can1)):
        if len_ + can > ans:
            for j in range(100 * n, 100 * n + 100):
                ans = max(np.dot(func(j), Y1), ans)

    for n, (len_, can) in enumerate(zip(len2, can2)):
        if len_ + can > ans:
            for j in range(100 * n, 100 * n + 100):
                ans = max(np.dot(func(j), Y2), ans)
    print(ans)

import numpy as np
import sys

L, N = map(int, input().split())
X = np.array([int(sys.stdin.readline()) for _ in range(N)])
Y1 = np.concatenate(([X[0]], X[1:] - X[:-1], [L - X[-1]]))

X2 = X[::-1]
Y2 = Y1[::-1]


def func(n):
    return np.concatenate((np.full(n + 1, N - n, dtype=np.int), np.arange(N - n - 2, -1, -2), np.arange(N - n - 1, -1, -2)[::-1]))


if N < 10000:
    ans = 0
    for n in range((N + 1) // 2):
        a = func(n)
        len1 = np.dot(a, Y1)
        len2 = np.dot(a, Y2)
        ans = max(ans, len1, len2)

    print(ans)
else:
    ans = 0
    cn = (N + 1) // 200
    len1 = [0] * cn
    len2 = [0] * cn
    can1 = [0] * cn
    can2 = [0] * cn
    for n in range(0, (N + 1) // 2, 100):
        a = func(n)
        i = n // 100
        len1[i] = np.dot(a, Y1)
        len2[i] = np.dot(a, Y2)
        can1[i] = X[n + (N - n + 100)//2] - 2 * X[n] - (L - X[(N - n - 101)//2])
        can2[i] = X2[n + (N - n + 100) // 2] - 2 * X2[n] - (L - X2[(N - n - 101) // 2])
        ans = max(ans, len1[i], len2[i])

    for n, (len_, can) in enumerate(zip(len1, can1)):
        if len_ + can > ans:
            for j in range(100 * n, 100 * n + 100):
                ans = max(np.dot(func(j), Y1), ans)

    for n, (len_, can) in enumerate(zip(len2, can2)):
        if len_ + can > ans:
            for j in range(100 * n, 100 * n + 100):
                ans = max(np.dot(func(j), Y2), ans)
    print(ans)


import numpy as np
import sys

L, N = map(int, input().split())
X = np.array([int(sys.stdin.readline()) for _ in range(N)])
Y1 = np.concatenate(([X[0]], X[1:] - X[:-1], [L - X[-1]]))
Y2 = Y1[::-1]


def func(n):
    return np.concatenate((np.full(n + 1, N - n, dtype=np.int), np.arange(N - n - 2, -1, -2), np.arange(N - n - 1, -1, -2)[::-1]))


ans = 0
flag1 = True
flag2 = True

for n in range(0, (N + 1) // 2):
    a = func(n)
    if flag1:
        len1 = np.dot(a, Y1)
        if ans - len1 > L:
            flag1 = False
            if flag2:
                break
    if flag2:
        len2 = np.dot(a, Y2)
        if ans - len2 > L:
            flag2 = False
            if flag1:
                break
    ans = max(ans, len1, len2)

print(ans)


import numpy as np
import sys

L, N = map(int, input().split())
X = np.array([int(sys.stdin.readline()) for _ in range(N)])
Y1 = np.concatenate(([X[0]], X[1:] - X[:-1], [L - X[-1]]))

X2 = X[::-1]
Y2 = Y1[::-1]


def func(n):
    return np.concatenate((np.full(n + 1, N - n, dtype=np.int), np.arange(N - n - 2, -1, -2), np.arange(N - n - 1, -1, -2)[::-1]))


if N < 10000:
    ans = 0
    for n in range((N + 1) // 2):
        a = func(n)
        len1 = np.dot(a, Y1)
        len2 = np.dot(a, Y2)
        ans = max(ans, len1, len2)

    print(ans)
else:
    ans = 0
    cn = (N + 1) // 200
    len1 = [0] * cn
    len2 = [0] * cn
    can1 = [0] * cn
    can2 = [0] * cn
    for n in range(0, (N + 1) // 2, 100):
        a = func(n)
        i = n // 100
        len1[i] = np.dot(a, Y1)
        len2[i] = np.dot(a, Y2)
        ans = max(ans, len1[i], len2[i])

    print(ans)

import numpy as np
import sys

L, N = map(int, input().split())
X = np.array([int(sys.stdin.readline()) for _ in range(N)])
Y1 = np.concatenate(([X[0]], X[1:] - X[:-1], [L - X[-1]]))
Y2 = Y1[::-1]


def func(n):
    return np.concatenate((np.full(n + 1, N - n, dtype=np.int), np.arange(N - n - 2, -1, -2), np.arange(N - n - 1, -1, -2)[::-1]))


if N < 10000:
    ans = 0
    for n in range((N + 1) // 2):
        a = func(n)
        len1 = np.dot(a, Y1)
        len2 = np.dot(a, Y2)
        ans = max(ans, len1, len2)

    print(ans)
else:
    ans = 0
    for n in range(0, (N + 1) // 2, 100):
        a = func(n)
        i = n // 100
        len1 = np.dot(a, Y1)
        len2 = np.dot(a, Y2)
        ans = max(ans, len1, len2)

    print(ans)

import numpy as np

L, N = map(int, input().split())
X = np.array([int(input()) for _ in range(N)])
Y = np.concatenate(([X[0]], X[1:] - X[:-1], [L - X[-1]]))


def func1(n):
    return np.concatenate((np.full(n + 1, N - n, dtype=np.int), np.arange(N - n - 2, -1, -2), np.arange(N - n - 1, -1, -2)[::-1]))


def func2(n):
    return np.concatenate((np.arange(N - n - 1, -1, -2), np.arange(N - n - 2, -1, -2)[::-1], np.full(n + 1, N - n, dtype=np.int)))


ans = 0
for n in range((N + 1) // 2):
    len_ = np.dot(func1(n), Y)
    ans = max(ans, len_)
    len_ = np.dot(func2(n), Y)
    ans = max(ans, len_)

print(ans)


import numpy as np
import sys

L, N = map(int, input().split())
X = np.array([int(sys.stdin.readline()) for _ in range(N)])
X2 = X[::-1]
Y1 = np.concatenate(([X[0]], X[1:] - X[:-1], [L - X[-1]]))
Y2 = Y1[::-1]


def func(n):
    return np.concatenate((np.full(n + 1, N - n, dtype=np.int), np.arange(N - n - 2, -1, -2), np.arange(N - n - 1, -1, -2)[::-1]))


if N < 10000:
    ans = 0
    for n in range((N + 1) // 2):
        a = func(n)
        len1 = np.dot(a, Y1)
        len2 = np.dot(a, Y2)
        ans = max(ans, len1, len2)
    
    print(ans)
else:
    ans = 0
    len1 = [0] * (N + 1) // 200
    len2 = [0] * (N + 1) // 200
    can1 = [0] * (N + 1) // 200
    can2 = [0] * (N + 1) // 200
    for n in range(0, (N + 1) // 2, 100):
        a = func(n)
        i = n // 100
        len1[i] = np.dot(a, Y1)
        len2[i] = np.dot(a, Y2)
        can1[i] = X[n + (N - n + 100)//2] - 2 * X[n] - (L - X[(N - n - 101)//2])
        can2[i] = X2[n + (N - n + 100) // 2] - 2 * X2[n] - (L - X2[(N - n - 101) // 2])
        ans = max(ans, len1[n], len2[n])
        
    for n, len_, can in enumerate(zip(len1, can1)):
        if len + can > ans:
            for j in range(100 * n, 100 * n + 100):
                ans = max(np.dot(func(j), Y1), ans)
                
    for n, len_, can in enumerate(zip(len2, can2)):
        if len + can > ans:
            for j in range(100 * n, 100 * n + 100):
                ans = max(np.dot(func(j), Y2), ans)
    print(ans)


import numpy as np
import sys

L, N = map(int, input().split())
X = np.array([int(sys.stdin.readline()) for _ in range(N)])
X2 = L - X[::-1]
Y1 = np.concatenate(([X[0]], X[1:] - X[:-1], [L - X[-1]]))
Y2 = Y1[::-1]
Z = np.concatenate((np.arange(N, -1, -2), np.arange(N - 1, -1, -2)[::-1]))


def myfunc(n, x):
    return x[n + (N - n + 1)//2 - 1] - 2 * x[n - 1] - (L - x[N - (N - n + 1)//2])


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

print(ans)

Verdicts: Time Limit Exceeded

Runtime Error

Runtime Error

Runtime Error

Wrong Answer

Runtime Error

Wrong Answer

Time Limit Exceeded

Runtime Error

Accepted