Problem:


Score : 400 points

Problem Statement

You are given N integers; the i-th of them is A_i.
Find the maximum possible sum of the absolute differences between the adjacent elements after arranging these integers in a row in any order you like.

Constraints

2 \leq N \leq 10^5

1 \leq A_i \leq 10^9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1
:
A_N

Output

Print the maximum possible sum of the absolute differences between the adjacent elements after arranging the given integers in a row in any order you like.

Sample Input 1

5
6
8
1
2
3

Sample Output 1

21

When the integers are arranged as 3,8,1,6,2, the sum of the absolute differences between the adjacent elements is |3 - 8| + |8 - 1| + |1 - 6| + |6 - 2| = 21. This is the maximum possible sum.

Sample Input 2

6
3
1
4
1
5
9

Sample Output 2

25

Sample Input 3

3
5
5
1

Sample Output 3

8



Sample input:
5
6
8
1
2
3


Sample output:
21

Submission status: Time Limit Exceeded

Solution code:
#### import ####
import sys
sys.setrecursionlimit(10**7)
import math
from collections import defaultdict

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

N = I()
A = [0]*N
for i in range(N):
  A[i] = I()
  
A.sort()
A2 = A[:]

temp = A.pop(0)
B = [temp]
for i in range(math.ceil((N-1)/2)):
  if i%2==0:
    temp = A.pop(len(A)-1)
    B.insert(0,temp)
    if len(A)>0:
      temp = A.pop(0)
      B.insert(0,temp)
  else:
    temp = A.pop(len(A)-1)
    B.append(temp)
    if len(A)>0:
      temp = A.pop(0)
      B.append(temp)

temp = A2.pop(N-1)
B2 = [temp]
for i in range(math.ceil((N-1)/2)):
  if i%2==0:
    temp = A2.pop(0)
    B2.insert(0,temp)
    if len(A2)>0:
      temp = A2.pop(len(A2)-1)
      B2.insert(0,temp)
  else:
    temp = A2.pop(0)
    B2.append(temp)
    if len(A2)>0:
      temp = A2.pop(len(A2)-1)
      B2.append(temp)

val1 = 0
val2 = 0
for i in range(N-1):
  val1 += abs(B[i]-B[i+1])
  val2 += abs(B2[i]-B2[i+1])
  
print(max(val1,val2))

Submission status: Time Limit Exceeded

Solution code:
def solve(n, a):
    a = sorted(a)
    return max(f(n, a), f(n, a[::-1]))

def f(n, a):
    a = a.copy()
    b = []
    for i in range(n):
        if (i-1) % 4 < 2:
            v = a.pop(0)
        else:
            v = a.pop()
        if i % 2 == 0:
            b = [v] + b
        else:
            b = b + [v]
    return sum([abs(b[i+1]-b[i]) for i in range(n-1)])

n = int(input())
a = [int(input()) for i in range(n)]
print(solve(n, a))

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    A.sort()
    ans = 0
    edge = [A.pop()] * 2
    while len(A):
        a = abs(edge[0] - A[0])
        b = abs(edge[0] - A[len(A) - 1])
        c = abs(edge[1] - A[0])
        d = abs(edge[1] - A[len(A) - 1])
        if max(a, b, c, d) == a:
            edge[0] = A.pop(0)
            ans += a
        elif max(a, b, c, d) == b:
            edge[0] = A.pop()
            ans += b
        elif max(a, b, c, d) == c:
            edge[1] = A.pop(0)
            ans += c
        else:
            edge[1] = A.pop()
            ans += d
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(input()) for _ in range(N)]

A.sort()

ans = A[len(A) - 1] - A[0]
small = 0
large = len(A) - 1
while (A != []):

    if len(A) == 2:
        break
    elif len(A) == 3:
        ans += max(A[1] - A[0], A[2] - A[1])
        break
    ans += A[len(A) - 2] - A[0] + A[len(A) - 1] - A[1]
    A = A[1:-1]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=[int(input()) for _ in range(N)]

A.sort()

B=[]
while A!=[]:
  B.append(A.pop())
  A=A[::-1]
  
if B[0]>B[-1]:
  B.insert(0,B[-1])
  B=B[:-1]
  
ans=0
for i in range(N-1):
  ans+=abs(B[i]-B[i+1])
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

A = []
for _ in range(n):
    a = int(input())
    A.append(a)
A_ = []

l = 0
r = len(A)-1

A = sorted(A)

for _ in range(n):
    if len(A_) == 0:
        A_.append(A[r])
        r-=1
        continue

    todo = "ll"
    bestVal = abs(A[l]-A_[0])
    if(abs(A[l]-A_[-1]) > bestVal):
        bestVal = abs(A[l]-A_[-1])
        todo = "lr"
    if(abs(A[r]-A_[-1]) > bestVal):
        bestVal = abs(A[r]-A_[-1])
        todo = "rr"
    if(abs(A[r]-A_[0]) > bestVal):
        bestVal = abs(A[r]-A_[0])
        todo = "rl"

    if todo == "ll":
        A_.insert(0, A[l])
        l+=1
    if todo == "lr":
        A_.append(A[l])
        l+=1
    if todo == "rr":
        A_.append(A[r])
        r-=1
    if todo == "rl":
        A_.insert(0, A[r])
        r-=1
ans = 0
for i in range(len(A_)-1):
    ans += abs(A_[i+1]-A_[i])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def getNext(tv, ta):
    maxv = abs(max(ta)-tv)
    minv = abs(tv-min(ta))
    if (maxv > minv):
        return max(ta)
    else:
        return min(ta)

n = int(input())

a = []
for i in range(n):
    a.append(int(input()))

ms = 0 
for i in range(len(a)):
    s = 0 
    top = a[i]
    fv = top 
    c = list(a)
    c.remove(fv)
    next = 0 
    while(c):
        if (next==0):
            v = getNext(fv, c)
            if (v > fv):
                next = -1
            else:
                next = 1 
        elif (next==1):
            v = max(c)
            next = -1
        elif (next==-1):
            v = min(c)
            next = 1 
        s = s + abs(fv-v)
        c.remove(v)
#        print(fv,v,next)
        fv = v 
#    print(s)
    if (s > ms):
        ms = s 
print(ms)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

N = int(input())

A = []
for i in range(N):
    A.append(int(input()))

diff = []
for _A in list(permutations(A, N)):
    _diff = 0
    for i in range(N - 1):
        _diff += abs(_A[i] - _A[i + 1])
    diff.append(int(_diff))

print(max(diff))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys
from itertools import permutations

def load():
    nums = []
    lines = iter(sys.stdin)
    line = next(lines)
    N = int(line.strip())
    for line in lines:
        nums.append(int(line.strip()))
    return nums

def calc(nums):
    it = iter(nums)
    next(it)
    return sum( abs(x - y) for x, y in zip(nums, it) )

def main():
    nums = load()
    #
    max = 0; ans = None
    for t in permutations(nums):
        n = calc(t)
        if n > max:
            max = n
            ans = t
    #
    print(max)
    #print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
import itertools

def getNext(tv, ta):
    maxv = abs(max(ta)-tv)
    minv = abs(tv-min(ta))
    if (maxv > minv):
        return max(ta)
    else:
        return min(ta)

n = int(input())

a = []
for i in range(n):
    a.append(int(input()))

ms = 0
for i in range(len(a)):
    s = 0
    top = a[i]
    fv = top
    c = list(a)
    c.remove(fv)
    while(c):
        v = getNext(fv, c)   
#        print(fv,v)
        s = s + abs(fv-v)
        c.remove(v)
        fv = v
    if (s > ms):
        ms = s
print(ms)

Submission status: Time Limit Exceeded

Solution code:
import itertools

def getNext(tv, ta):
    maxv = abs(max(ta)-tv)
    minv = abs(tv-min(ta))
    if (maxv > minv):
        return max(ta)
    else:
        return min(ta)

n = int(input())

a = []
for i in range(n):
    a.append(int(input()))

vs = []
for i in range(len(a)):
    s = 0
    top = a[i]
    fv = top
    c = list(a)
    c.remove(fv)
    while(c):
        v = getNext(fv, c)   
#        print(fv,v)
        s = s + abs(fv-v)
        c.remove(v)
        fv = v
#    print("s is" + str(s))
    vs.append(s)

print(max(vs))

Submission status: Time Limit Exceeded

Solution code:
import itertools

N = int(input())

A = []
for i in range(N):
    A.append(int(input()))

diff = []
for _A in list(itertools.permutations(A)):
    _diff = 0
    for i in range(N - 1):
        _diff += abs(_A[i] - _A[i + 1])
    diff.append(int(_diff))

print(max(diff))

Submission status: Time Limit Exceeded

Solution code:
import itertools

n = int(input())

a = []
for i in range(n):
    a.append(int(input()))

p = list(itertools.permutations(a))
vs = []
rv = 0
for i in range(len(p)):
    s = 0
    for ii in range(len(p[i])):
        if (ii>0):
            s += abs(p[i][ii]-p[i][ii-1])
    if s > rv:
        rv = s
print(rv)

Submission status: Time Limit Exceeded

Solution code:
import itertools

n = int(input())

a = []
for i in range(n):
    a.append(int(input()))

p = list(itertools.permutations(a))
vs = []
for i in range(len(p)):
    s = 0
    for ii in range(len(p[i])):
        if (ii>0):
            s += abs(p[i][ii]-p[i][ii-1])
    vs.append(s)
print(max(vs))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n = int(input())
listx = [int(input()) for i in range(n)]

listx.sort()
listx = deque(listx)
listy = deque([])
ans=0

x=listx.popleft()
listy.appendleft(x)
x=listx.pop()
listy.append(x)
ans+=int(listy[1])-int(listy[0])

for i in range(n-2):
    abs1=abs(listx[0]-listy[-1])
    abs2=abs(listx[-1]-listy[0])

    if abs1 < abs2:
        x=listx.pop()
        listy.appendleft(x)
        ans+=abs2

    else:
        x=listx.popleft()
        listy.append(x)
        ans+=abs1
        
    if listy[0] > listy[-1]:
        listy.reverse()

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n = int(input())
listx = [int(input()) for i in range(n)]
listx.sort()
listx = deque(listx)
listy = deque([])
ans=0

x=listx.popleft()
listy.appendleft(x)
x=listx.pop()
listy.append(x)
ans+=int(listy[1])-int(listy[0])

while n-2 >=1:
    abs1=abs(listx[0]-listy[-1])
    abs2=abs(listx[-1]-listy[0])

    if abs1 < abs2:
        x=listx.pop()
        listy.appendleft(x)
        ans+=abs2

    else:
        x=listx.popleft()
        listy.append(x)
        ans+=abs1
        
    if listy[0] > listy[-1]:
        listy.reverse()

    n += -1
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n = int(input())
listx = [int(input()) for i in range(n)]
listx.sort()
listx = deque(listx)
listy = deque([])
ans=0

x=listx.popleft()
listy.appendleft(x)
x=listx.pop()
listy.append(x)
ans+=int(listy[1])-int(listy[0])

while len(listx)>=1:
    abs1=abs(listx[0]-listy[-1])
    abs2=abs(listx[-1]-listy[0])

    if abs1 < abs2:
        x=listx.pop()
        listy.appendleft(x)
        ans+=abs2

    else:
        x=listx.popleft()
        listy.append(x)
        ans+=abs1
        
    if listy[0] > listy[-1]:
        listy.reverse()

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n = int(input())
listx = [int(input()) for i in range(n)]

listx.sort()
listy = deque([])
ans=0

x=listx.pop(0)
listy.appendleft(x)
x=listx.pop(-1)
listy.append(x)
ans+=int(listy[1])-int(listy[0])

while len(listx)>=1:
    abs1=abs(listx[0]-listy[-1])
    abs2=abs(listx[-1]-listy[0])

    if abs1 < abs2:
        x=listx.pop(-1)
        listy.appendleft(x)
        ans+=abs2
    else:
        x=listx.pop(0)
        listy.append(x)
        ans+=abs1
    
    if listy[0] > listy[-1]:
        listy.reverse()

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
listx = [int(input()) for i in range(n)]
listx.sort()
listy=[]
ans=0

x=listx.pop(0)
listy.append(x)
x=listx.pop(-1)
listy.append(x)
ans+=int(listy[1])-int(listy[0])

while len(listx)>=1:
    abs1=abs(listx[0]-listy[-1])
    abs2=abs(listx[-1]-listy[0])

    if abs1 < abs2:
        x=listx.pop(-1)
        listy.insert(0,x)
        ans+=abs2
    else:
        x=listx.pop(0)
        listy.append(x)
        ans+=abs1
    
    if listy[0] > listy[-1]:
        listy.reverse()

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
listx = [int(input()) for i in range(n)]

listx.sort()
listy=[]
ans=0

x=listx.pop(0)
listy.append(x)
x=listx.pop(-1)
listy.append(x)
ans=ans+int(listy[1])-int(listy[0])

while len(listx)>=1:
    abs1=abs(listx[0]-listy[-1])
    abs2=abs(listx[-1]-listy[0])

    if abs1 < abs2:
        x=listx.pop(-1)
        listy.insert(0,x)
        ans=ans+abs2
    else:
        x=listx.pop(0)
        listy.append(x)
        ans=ans+abs1
    
    if listy[0] > listy[-1]:
        listy.reverse()

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
listx = [int(input()) for i in range(n)]

listx.sort()
listy=[]

x=listx.pop(0)
listy.append(x)
x=listx.pop(-1)
listy.append(x)
listy.sort()

while len(listx)>=1:
    abs1=abs(listx[0]-listy[-1])
    abs2=abs(listx[-1]-listy[0])

    if abs1 < abs2:
        x=listx.pop(-1)
        listy.insert(0,x)
    else:
        x=listx.pop(0)
        listy.append(x)
    
    if listy[0] > listy[-1]:
        listy.reverse()
ans=0
for i in range(len(listy)-1):
    ans=ans+abs(listy[i]-listy[i+1])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
listx = [int(input()) for i in range(n)]

listx.sort()
listy=[]

x=listx.pop(0)
listy.append(x)
x=listx.pop(-1)
listy.append(x)
listy.sort()

while len(listx)>=1:
    abs1=abs(listx[0]-listy[-1])
    abs2=abs(listx[-1]-listy[0])

    if abs1 < abs2:
        x=listx.pop(-1)
        listy.insert(0,x)
    else:
        x=listx.pop(0)
        listy.append(x)
    
    if listy[0] > listy[-1]:
        listy.reverse()
ans=0

for i in range(len(listy)-1):
    ans=ans+abs(listy[i]-listy[i+1])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
nums = [int(input()) for i in range(n)]
nums_sorted = sorted(nums)
sortnums = []

maxf = nums_sorted[len(nums_sorted) - 1]
sortnums.append(maxf)
nums_sorted.pop(len(nums_sorted) - 1)

while True:
  mini = nums_sorted[0]
  l = len(sortnums) - 1
  if abs(sortnums[0] - mini) <= abs(sortnums[l] - mini):
    sortnums.append(mini)
    nums_sorted.pop(0)
  else:
    sortnums.insert(0, mini)
    nums_sorted.pop(0)
  if nums_sorted == []:
    break
  else:
    maxi = nums_sorted[len(nums_sorted) - 1]
    l = len(sortnums) - 1
    if abs(sortnums[0] - maxi) <= abs(sortnums[l] - maxi):
      sortnums.append(maxi)
      nums_sorted.pop(len(nums_sorted) - 1)
    else:
      sortnums.insert(0, maxi)
      nums_sorted.pop(len(nums_sorted) - 1)
    if nums_sorted == []:
      break
    else:
      pass

sum = 0
for j in range(len(sortnums) - 1):
  sum += abs(sortnums[j + 1] - sortnums[j])
  
print(sum)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
nums = [int(input()) for i in range(n)]
sortnums = []

maxf = max(nums)
sortnums.append(maxf)
nums.remove(maxf)

while True:
  mini = min(nums)
  l = len(sortnums) - 1
  if abs(sortnums[0] - mini) <= abs(sortnums[l] - mini):
    sortnums.append(mini)
    nums.remove(mini)
  else:
    sortnums.insert(0, mini)
    nums.remove(mini)
  if nums == []:
    break
  else:
    maxi = max(nums)
    l = len(sortnums) - 1
    if abs(sortnums[0] - maxi) <= abs(sortnums[l] - maxi):
      sortnums.append(maxi)
      nums.remove(maxi)
    else:
      sortnums.insert(0, maxi)
      nums.remove(maxi)
    if nums == []:
      break
    else:
      pass

sum = 0
for j in range(len(sortnums) - 1):
  sum += abs(sortnums[j + 1] - sortnums[j])
  
print(sum)

Submission status: Time Limit Exceeded

Solution code:
import itertools
n=int(input())
x=[int(input()) for i in range(n)]
listX = list(itertools.permutations(x, n))

listY = []
for j in range(len(listX)):
  y = 0
  for i in range(n-1):
    y = y + abs(listX[j][i]-listX[j][i+1])
  listY.append(y)

print(max(listY))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding:utf-8 -*-
import itertools

# 隣あう要素の差の絶対値を足し合わせる
def sum_diff(ary):
    re = 0
    pre_n = ary.pop(0)
    for n in ary:
        re += abs(n - pre_n)
        pre_n = n
    return re

n = int(input())
num = []
for i in range(n):
    m = int(input())
    num.append(m)

# num配列の順列生成
a = itertools.permutations(num)

# permutationオブジェクトをsetにしてtupleの重複排除、
# 更にmapで各要素をlist化
b = map(list, set(a))

c = map(sum_diff, b)
print(max(c))

Submission status: Time Limit Exceeded

Solution code:
N=input()
A=[ input() for i in range(N) ] 

A.sort()

K=[]
K2=[]

if N%2==0:
	n=(N-2)/2
	K=[ -2 for i in range(n) ]+[-1,1]+[ 2 for i in range(n) ]
else:
	n=(N-2)/2

	## Pattern 1
	K=[ -2 for i in range(n) ]+[-1,-1]+[ 2 for i in range(n+1) ]
	## End

	## Pattern 2
	K2=[ -2 for i in range(n+1) ]+[1,1]+[ 2 for i in range(n) ]
	## End

ans=0

t1=0
for x, y in zip(A,K):
	t1+=x*y

t2=0
for x, y in zip(A,K2):
	t2+=x*y


print max(t1,t2)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N=input()
A=[ input() for i in range(N) ] 

A.sort()

K=[]
K2=[]

if N%2==0:
	n=(N-2)/2
	for i in range(n):
		K.append(-2)
	K.append(-1)
	K.append(1)
	for i in range(n):
		K.append(2)
else:
	n=(N-2)/2

	## Pattern 1
	for i in range(n):
		K.append(-2)
	K.append(-1)
	K.append(-1)
	for i in range(n+1):
		K.append(2)
	## End

	## Pattern 2
	for i in range(n+1):
		K2.append(-2)
	K2.append(1)
	K2.append(1)
	for i in range(n):
		K2.append(2)
	## End

ans=0

t1=0
for x, y in zip(A,K):
	t1+=x*y

t2=0
for x, y in zip(A,K2):
	t2+=x*y


print max(t1,t2)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = []
for i in range(n):
    a.append(int(input()))
for i in range(n):
    for j in range(n-1):
        if a[j] > a[j+1]:
            k = a[j]
            a[j] = a[j+1]
            a[j+1] = k
b = [[],[]]
for j in range(2):
    for i in range(n):
        if i % 2 == j:
            b[j].append(a[i//2])
        else:
            b[j].append(a[n-i//2-1])
s1 = 0
s2 = 0
for i in range(n-1):
    s1 += abs(b[0][i]-b[0][i-1])
    s2 += abs(b[1][i]-b[1][i-1])
print(max(s1, s2))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = []
for i in range(n):
    A.append(int(input()))
    
A.sort()
B = []
for i in range(n):
    if(i==0):
        B.append(A.pop(0))
    elif(i==n-1):
        if(abs(B[0]-A[0])>abs(B[-1]-A[0])):
            B.insert(0, A.pop())
        else:
            B.append(A.pop())
    elif(not(i%4==0 or (i+1)%4==0)):
        if(i%2==0):
            B.insert(0, A.pop())
        else:
            B.append(A.pop())
    else:
        if(i%2==0):
            B.insert(0, A.pop(0))
        else:
            B.append(A.pop(0))

res = 0
for i in range(n-1):
    res += abs(B[i]-B[i+1])

print(res)

Submission status: Time Limit Exceeded

Solution code:
def diffarray(arr):
    sum = 0
    tmp = arr[0]
    for digit in arr[1:]:
        sum += abs(tmp - digit)
        tmp = digit
    return sum

def neighbor_diff(i, arr):
    if i == 0:
        return abs(arr[i] - arr[i+1])
    if i == len(arr) - 1:
        return abs(arr[i-1] - arr[i])
    else:
        return abs(arr[i-1] - arr[i]) + abs(arr[i] - arr[i+1])

def swap_arr(arr, i, j):
    tmp_i = arr[i]
    arr[i] = arr[j]
    arr[j] = tmp_i
    return


def search_diff(i,j,arr):
    '''
    数列arrのi番目とj番目をスワップさせた場合の差の総量の変化
    :return: 変化量
    '''
    tmp = - neighbor_diff(i, arr) - neighbor_diff(j, arr)

    swapped_arr = arr[:]
    swap_arr(swapped_arr, i, j)

    tmp += neighbor_diff(i, swapped_arr) + neighbor_diff(j, swapped_arr)
    return tmp

def change(arr):
    '''

    :param arr: 検証元の数列
    :return: 検証した結果見つかった最も差が大きい数列
    '''
    ret_arr = arr[:]

    for i in range(0, len(arr)):
        for j in range(i, len(arr)):
            henka = search_diff(i, j, arr)
            if henka > 0:
                swap_arr(arr,i,j)
            #print(i,j,henka,max,arr,swapped_arr)
    return True

def main():
    N = int(input())
    arr=[]
    for i in range(N):
        arr.append(int(input()))
    arr.sort()

    mid, mod = divmod(N, 2)

    start_arr = []
    for i in range(mid):
        start_arr.append(arr[i])
        start_arr.append(arr[-i-1])
    if mod == 1:
        start_arr.append(arr[mid])

    assert(len(arr) == len(start_arr))
    while True:
        nochange = change(start_arr)
        if nochange:
            break

    #print(start_arr,diffarray(start_arr[1:-1]))
    print(diffarray(start_arr))
    return


main()

Submission status: Time Limit Exceeded

Solution code:

def main():

    def diffarray(arr):
        sum = 0
        tmp = arr[0]
        for digit in arr[1:]:
            sum += abs(tmp - digit)
            tmp = digit
        return sum

    def neighbor_diff(i, arr):
        if i == 0:
            return abs(arr[i] - arr[i+1])
        if i == len(arr) - 1:
            return abs(arr[i-1] - arr[i])
        else:
            return abs(arr[i-1] - arr[i]) + abs(arr[i] - arr[i+1])

    def swap_arr(arr, i, j):
        tmp_i = arr[i]
        arr[i] = arr[j]
        arr[j] = tmp_i
        return


    def search_diff(i,j,arr):
        '''
        数列arrのi番目とj番目をスワップさせた場合の差の総量の変化
        :return: 変化量
        '''
        tmp = - neighbor_diff(i, arr) - neighbor_diff(j, arr)

        swapped_arr = arr[:]
        swap_arr(swapped_arr, i, j)

        tmp += neighbor_diff(i, swapped_arr) + neighbor_diff(j, swapped_arr)
        return tmp, swapped_arr

    def change(arr):
        '''

        :param arr: 検証元の数列
        :return: 検証した結果見つかった最も差が大きい数列
        '''
        ret_arr = arr[:]

        max = 0
        mem_i = -1
        mem_j = -1

        for i in range(0, len(arr)):
            for j in range(i, len(arr)):
                henka, swapped_arr = search_diff(i, j, arr)
                if henka > max:
                    ret_arr = swapped_arr
                    max = henka
                    mem_i = i
                    mem_j = j
                #print(i,j,henka,max,arr,swapped_arr)

        if max == 0:
            return False
        swap_arr(arr, mem_i, mem_j)
        return True



    N = int(input())
    arr=[]
    for i in range(N):
        arr.append(int(input()))
    arr.sort()

    mid, mod = divmod(N, 2)

    start_arr = []
    for i in range(mid):
        start_arr.append(arr[i])
        start_arr.append(arr[-i-1])
    if mod == 1:
        start_arr.append(arr[mid])

    assert(len(arr) == len(start_arr))
    while True:
        ret_arr = change(start_arr)
        if not ret_arr:
            break

    #print(start_arr,diffarray(start_arr[1:-1]))
    print(diffarray(start_arr))
    return


main()

Submission status: Time Limit Exceeded

Solution code:
n,*a=map(int,open(0).read().split())
if n<3:
    print(abs(a[0]-a[1]))
    exit()
l=[]
for i in range(n):
    for j in range(i+1,n):
        l.append([abs(a[i]-a[j]),i,j])
l.sort(key=lambda x:x[0],reverse=1)
m=k=0
c=[0]*n
for t,u,v in l:
    if c[u]>1or c[v]>1:continue
    if c[u]and c[v]and k>n-2:continue
    k+=(c[u]<1)+(c[v]<1)
    c[u]+=1;c[v]+=1
    m+=t
print(m)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
n=int(input())
a=[]
for i in range(0,n):
  a.append(int(input()))
a.sort()

b = [a[0]]
#a=a[1:]
li=1
ri=len(a)-1

while ri>=li:
  ln = abs(b[0]-a[li])
  lx = abs(b[0]-a[ri])
  rn = abs(b[len(b)-1]-a[li])
  rx = abs(b[len(b)-1]-a[ri])

  x = max(ln, max(lx, max(rn, rx)))
  
  if x == ln:
    b.insert(0,a[li])
    li=li+1
  elif x == lx:
    b.insert(0,a[ri])
    ri=ri-1
  elif x == rn:
    b.append(a[li])
    li=li+1
  else:
    b.append(a[ri])
    ri=ri-1

res=0
for i in range(0,len(b)-1):
  res=res+abs(b[i]-b[i+1])
print(res)

Submission status: Time Limit Exceeded

Solution code:
def calc(a) :
    sum = 0
    for i in range(len(a) - 1):
        sum += abs(a[i + 1] - a[i])
    return sum

def crossList(a,b):
    y = []
    if len(a) > len(b):
        for i in range(len(b)):
            y.append(a[i])
            y.append(b[i])
        y.append(a[i+1])
    elif len(a) < len(b): 
        for i in range(len(a)):
            y.append(b[i])
            y.append(a[i])
        y.append(b[i+1])
    else :
        for i in range(len(a)):
            y.append(b[i])
            y.append(a[i])
    return y

n = int(input())
a = []
for i in range(n):
    a.append(int(input()))
a.sort()
b = []
c = []
f = []
g = []
if len(a) % 2 == 1:
    b = a[0:int((len(a) - 1)/2) ]
    c = a[int((len(a) - 1)/2) : len(a)]
    f = a[0:int((len(a) - 1)/2) + 1]
    g = a[int((len(a) - 1)/2) + 1 : len(a)]
else :
    b = a[0:int((len(a) - 1)/2) + 1 ]
    c = a[int((len(a) - 1)/2) + 1: len(a)]
c.reverse()
g.reverse()
d = []
e = []
h = []
j = []
forward = True;
for i in range(len(b)):
    if forward:
        d.append(b[i])
    else :
        d.reverse()
        d.append(b[i])
        d.reverse()
    forward = not forward
forward = True
for i in range(len(c)):
    if forward:
        e.append(c[i])
    else :
        e.reverse()
        e.append(c[i])
        e.reverse()
    forward = not forward
forward = True
for i in range(len(f)):
    if forward:
        h.append(f[i])
    else :
        h.reverse()
        h.append(f[i])
        h.reverse()    
    forward = not forward
forward = True
for i in range(len(g)):
    if forward:
        j.append(g[i])
    else :
        j.reverse()
        j.append(g[i])
        j.reverse()
    forward = not forward
print(max(calc(crossList(d,e)),calc(crossList(d[::-1],e[::-1])),
          calc(crossList(d,e[::-1])),calc(crossList(d[::-1],e)),
          calc(crossList(h[::-1],j[::-1])),calc(crossList(h,j[::-1])),
          calc(crossList(h[::-1],j)),calc(crossList(h,j))))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(input()) for i in range(N)]
A.sort()

li = []
li.append(A.pop(0))
result = 0

while len(A) != 0:
    diffMax = 0
    diffMaxIndex = 0

    for i in range(len(A)):
        if diffMax < abs(li[-1] - A[i]):
            diffMax = abs(li[-1] - A[i])
            diffMaxIndex = i

        if diffMax < abs(li[0] - A[i]):
            diffMax = abs(li[0] - A[i])
            diffMaxIndex = i

    if abs(li[0] - A[diffMaxIndex]) <= abs(li[-1] - A[diffMaxIndex]):
        result += abs(li[-1] - A[diffMaxIndex])
        li.append(A.pop(diffMaxIndex))
    else:
        result += abs(li[0] - A[diffMaxIndex])
        li.insert(0, A.pop(diffMaxIndex))
print(result)

Submission status: Time Limit Exceeded

Solution code:
def calc(a) :
    sum = 0
    for i in range(len(a) - 1):
        sum += abs(a[i + 1] - a[i])
    return sum

def crossList(a,b):
    y = []
    if len(a) > len(b):
        for i in range(len(b)):
            y.append(a[i])
            y.append(b[i])
        y.append(a[i+1])
    elif len(a) < len(b): 
        for i in range(len(a)):
            y.append(b[i])
            y.append(a[i])
        y.append(b[i+1])
    else :
        for i in range(len(a)):
            y.append(b[i])
            y.append(a[i])
    return y

n = int(input())
a = []
for i in range(n):
    a.append(int(input()))
a.sort()
b = []
c = []
f = []
g = []
if len(a) % 2 == 1:
    b = a[0:int((len(a) - 1)/2) ]
    c = a[int((len(a) - 1)/2) : len(a)]
    f = a[0:int((len(a) - 1)/2) + 1]
    g = a[int((len(a) - 1)/2) + 1 : len(a)]
else :
    b = a[0:int((len(a) - 1)/2) + 1 ]
    c = a[int((len(a) - 1)/2) + 1: len(a)]
c.reverse()
g.reverse()
d = []
e = []
h = []
j = []
forward = False;
for i in range(len(b)):
    if forward:
        d.append(b[i])
    else :
        d.insert(0,b[i])
    forward = not forward
forward = False
for i in range(len(c)):
    if forward:
        e.append(c[i])
    else :
        e.insert(0,c[i])
    forward = not forward
for i in range(len(f)):
    if forward:
        h.append(f[i])
    else :
        h.insert(0,f[i])
    forward = not forward
forward = False
for i in range(len(g)):
    if forward:
        j.append(g[i])
    else :
        j.insert(0,g[i])
    forward = not forward
print(max(calc(crossList(d,e)),calc(crossList(d[::-1],e[::-1])),
          calc(crossList(d,e[::-1])),calc(crossList(d[::-1],e)),
          calc(crossList(h[::-1],j[::-1])),calc(crossList(h,j[::-1])),
          calc(crossList(h[::-1],j)),calc(crossList(h,j))))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, [input() for _ in range(N)]))

#N = 100000
#A = [1]*N

def sub_array(n, A):
    return [A[i] for i in range(len(A)) if i!=n]

memo = [-1]*(N-1)

def dp(a, A):
    if len(A)==1:
        return abs(a-A[0])

    #if memo[N-len(A)] != -1:
    #    return memo[N-len(A)]

    m = 0
    for i in range(len(A)):
        new = sub_array(i, A)
        r = abs(a-A[i]) + dp(A[i], new)
        m = max(m, r)

    #memo[N-len(A)] = m    
    return m

r = 0
for n in range(N):
    t = dp(A[n], sub_array(n, A))
    if r < t:
        r = t

print(r)

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
import itertools
n = int(input())
a = []
for i in range(n):
    a.append(input())
# [d1, d2, d3, ..., dN]
a = [int(m) for m in a]
sum = []

a.sort()

count = 0
s = 0

for a in itertools.permutations(a):
    #a = [int(m) for m in a]
    #print(a)
    a = list(a)
#print(np.diff(a, n=1, axis=-1))
    for j in range(n):
        if j != 0:
            if j == 1:
                sum.append(abs(a[j] - a[j - 1]))
            if j != 1:
                sum[count] += abs(a[j] - a[j - 1])
    if count == 0:
        s = sum[count]
    if sum[count] > s and count > 0:
        s = sum[count]
    count += 1

print(s)

Submission status: Time Limit Exceeded

Solution code:
import sys,itertools
import numpy as np
N = int(input())
numList = []
diffList = []
for line in sys.stdin:
    numList.append(int(line))
for elem in itertools.permutations(numList, N):
	diff = np.abs(np.array(elem[1:])-np.array(elem[:-1]))
	diffList.append(sum(diff))
print(max(diffList))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = sorted([int(input()) for i in range(N)])
ans1 = [A[N-1]]
ans2 = [A[0]]

f = 0
f2 = 1
b = N - 2
b2 = N - 1
s = True
while f <= b:
    if s:
        ans1.append(A[f])
        f += 1
        if f <= b:
            ans1.insert(0, A[f])
            f += 1

        ans2.append(A[b2])
        b2 -= 1
        if f2 <= b2:
            ans2.insert(0, A[b2])
            b2 -= 1
    else:
        ans1.append(A[b])
        b -= 1
        if f <= b:
            ans1.insert(0, A[b])
            b -= 1

        ans2.append(A[f2])
        f2 += 1
        if f2 <= b2:
            ans2.insert(0, A[f2])
            f2 += 1            
    s = not s


a1 = a2 = 0
for i in range(N-1):
    a1 += abs(ans1[i] - ans1[i+1])
    a2 += abs(ans2[i] - ans2[i+1])

print(max(a1,a2))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = sorted([int(input()) for i in range(N)])
ans1 = [A[N-1]]
ans2 = [A[0]]

f = 0
b = N - 2
s = True
while f <= b:
    if s:
        ans1.append(A[f])
        f += 1
        if f <= b:
            #ans1 = [A[f]] + ans1
            ans1.insert(0, A[f])
            f += 1
    else:
        ans1.append(A[b])
        b -= 1
        if f <= b:
            ans1.insert(0, A[b])
            #ans1 = [A[b]] + ans1
            b -= 1
    s = not s

f = 1
b = N - 1
s = True
while f <= b:
    if s:
        ans2.append(A[b])
        b -= 1
        if f <= b:
            ans2.insert(0, A[b])
            #ans2 = [A[b]] + ans2
            b -= 1
    else:
        ans2.append(A[f])
        f += 1
        if f <= b:
            ans2.insert(0, A[f])
            #ans2 = [A[f]] + ans2
            f += 1
    s = not s

a1 = a2 = 0
for i in range(N-1):
    a1 += abs(ans1[i] - ans1[i+1])

for i in range(N-1):
    a2 += abs(ans2[i] - ans2[i+1])

print(max(a1,a2))