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:
#!/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:]

f=True
#while len(a)>0:
for i in range(0,n-1):
  la=len(a)-1
  lb=len(b)-1
  ln = abs(b[0]-a[0])
  lx = abs(b[0]-a[la])
  rn = abs(b[lb]-a[0])
  rx = abs(b[lb]-a[la])

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

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:
import numpy as np
import copy
#import time

N = int(raw_input().replace("\n", ""))

a_array = np.asarray(sorted([int(raw_input().replace("\n", "")) for i in xrange(N)]))
len_array = a_array.shape[0]

if len_array % 2 == 0:
    elm_is = [len_array/2 -1, len_array/2]
else:
    elm_is = [(len_array-1)/2]
aa_array = a_array[elm_is]

#s_time = time.time()


sum_diffs = []
#for elm_i, start_elm in enumerate(a_array):
for elm_i, start_elm in zip(elm_is, aa_array):
    mask = np.ones(len_array, dtype=bool)
    target_elm = start_elm

    sum_diff = 0
    for count in xrange(len_array - 1):
        #c_time = time.time()
        mask[elm_i] = False
        masked_a_array = a_array[mask]
        relative_a_array = np.abs(masked_a_array[[0, -1]] - target_elm)
        #relative_a_array = np.abs(masked_a_array - target_elm)
        target_elm_index1 = np.argmax(relative_a_array)
        target_elm_index = 0 if target_elm_index1 == 0 else len(masked_a_array) - 1
        target_elm = masked_a_array[target_elm_index]
        sum_diff += relative_a_array[target_elm_index1]
        
        #print("mae:", time.time() - c_time)
        #c_time = time.time()
        count_ = -1
        for mask_i, elm in enumerate(mask):
            if elm:
                count_ += 1
                if count_ == target_elm_index:
                    elm_i = mask_i
                    break
        #print("ato:", time.time() - c_time)
    
    sum_diffs.append(sum_diff)

print max(sum_diffs)
#print(time.time() - s_time)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(input()) for _ in range(N)] 
 
A = sorted(A)
res = 0
A2 = []
for i in range(len(A)):
    if len(A) == 1:
        if abs(A[0] - A2[0]) < abs(A[0] - A2[-1]):
            A2.append(A[0])
        else:
            A2.insert(0,A[0])
        break
    if i % 2 == 0:
        if i == 0:
            A2.append(A.pop(-1))
        else:
            if abs(A[-1] - A2[0]) < abs(A[-1] - A2[-1]):
                A2.append(A.pop(-1))
            else:
                A2.insert(0,A.pop(-1))
    else:
        #A2.append(A.pop(0))
        if abs(A[0] - A2[0]) < abs(A[0] - A2[-1]):
            A2.append(A.pop(0))
        else:
            A2.insert(0,A.pop(0))
for i in range(len(A2)-1):
    res += abs(A2[i] - A2[i+1])

print(res)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
 
num = []
for i in range(N):
  num.append(int(input()))
  
num = sorted(num)
ans = [num[0]]
num.pop(0)
 
for i in range(len(num)-1):
  if i % 4 == 0:
    ans.append(num[-1])
    num.pop(-1)
  elif i % 4 == 1:
    ans.insert(0,num[-1])
    num.pop(-1)
  elif i % 4 == 2:
    ans.append(num[0])
    num.pop(0)
  else:
    ans.insert(0,num[0])
    num.pop(0)
 
answer = max(abs(num[0]-ans[0]), abs(num[0]-ans[-1]))
for i in range(len(ans)-1):
  answer += abs(ans[i] - ans[i+1])
  
print(answer)

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 = ans1 + [A[f]]
        f += 1
        if f <= b:
            ans1 = [A[f]] + ans1
            f += 1
    else:
        ans1 = ans1 + [A[b]]
        b -= 1
        if f <= b:
            ans1 = [A[b]] + ans1
            b -= 1
    s = not s

f = 1
b = N - 1
s = True
while f <= b:
    if s:
        ans2 = ans2 + [A[b]]
        b -= 1
        if f <= b:
            ans2 = [A[b]] + ans2
            b -= 1
    else:
        ans2 = ans2 + [A[f]]
        f += 1
        if f <= b:
            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))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
number = []
for index in range(N):
    number.append(int(input()))
answer = []
length = len(number)
count =0
while count < length - 1:
    if count % 2 == 0: 
        answer.insert(0,number.pop(number.index(max(number))))
    else:
        answer.insert(0,number.pop(number.index(min(number))))
    count += 1

answer.append(number[0])

sum1 = 0
for index in range(len(answer)-1):
    sum1 += abs(answer[index] - answer[index+1])

answer.insert(0, answer.pop(-1))
sum2 = 0
for index in range(len(answer)-1):
    sum2 += abs(answer[index] - answer[index+1])

if sum1 > sum2:
    print(sum1)
else:
    print(sum2)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import copy
#import time

N = int(raw_input().replace("\n", ""))

a_array = np.asarray(sorted([int(raw_input().replace("\n", "")) for i in xrange(N)]))
len_array = a_array.shape[0]

if len_array % 2 == 0:
    elm_is = [len_array/2 -1, len_array/2]
else:
    elm_is = [(len_array-1)/2]
aa_array = a_array[elm_is]

#s_time = time.time()


sum_diffs = []
#for elm_i, start_elm in enumerate(a_array):
for elm_i, start_elm in zip(elm_is, aa_array):
    mask = np.ones(len_array, dtype=bool)
    target_elm = start_elm

    sum_diff = 0
    for count in xrange(len_array - 1):
        #c_time = time.time()
        mask[elm_i] = False
        masked_a_array = a_array[mask]
        relative_a_array = np.abs(masked_a_array - target_elm)
        target_elm_index = np.argmax(relative_a_array)
        target_elm = masked_a_array[target_elm_index]
        sum_diff += relative_a_array[target_elm_index]
        
        #print("mae:", time.time() - c_time)
        #c_time = time.time()
        count_ = -1
        for mask_i, elm in enumerate(mask):
            if elm:
                count_ += 1
                if count_ == target_elm_index:
                    elm_i = mask_i
                    break
        #print("ato:", time.time() - c_time)
    
    sum_diffs.append(sum_diff)

print max(sum_diffs)
#print(time.time() - s_time)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import itertools
n=int(input())
s=[int(input()) for i in range(n)]
iter=list(itertools.permutations(s,n))
print(max(np.sum(np.abs(np.diff(iter)),axis=1)))

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

MAX =0
sum=0

for i in itertools.permutations(A):
    sum=0
    for j in range(N-1):
        sum =sum +abs(int(i[j+1]) - int(i[j]))
    if sum >MAX:
        MAX= sum

print(MAX)

Submission status: Time Limit Exceeded

Solution code:
N = int(input().strip('\n'))
lis = []
for i in range(N):
    lis.append(int(input().strip('\n')))
lis.sort()
mx_n = lis[-1]
ms_n = lis[0]
lis = lis[1:-1]
point = mx_n-ms_n
while len(lis)>=2:
    mx = lis[-1]
    ms = lis[0]
    point += (mx_n-ms+mx-ms_n)
    mx_n = mx
    ms_n = ms
    lis = lis[1:-1]
if len(lis)==1:
    point += max(abs(mx_n-lis[0]),abs(ms_n-lis[0]))
print(point)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
c = 1
A = []
while c <= N:
    a = int(input())
    A = A + [a]
    c += 1


b = []
while len(A) >= 4:
    b = b + [max(A)] + [min(A)]
    A.remove(max(A))
    A.remove(min(A))

c = []
d = []
b = b + [max(A)]
A.remove(max(A))
b = [min(A)] + b
A.remove(min(A))
#print(A)
c = b
d = b
if len(A) == 1:
    c = c + [A[0]]
    d = [A[0]] + d
#print(c)
6
8
1
2
3

i = 0
s_c = 0
while i <= len(c)-2:
    x = c[i] - c[i+1]
    if x < 0:
        x *= -1

    s_c += x
    i += 1

i = 0
s_d = 0
while i <= len(d)-2:
    x = d[i] - d[i+1]
    if x < 0:
        x *= -1

    s_d += x
    i += 1

print(max(s_c,s_d))

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 = ans1 + [A[f]]

        f += 1
        if f <= b:
            ans1 = [A[f]] + ans1
            f += 1
    else:
        ans1 = ans1 + [A[b]]
        b -= 1
        if f <= b:
            ans1 = [A[b]] + ans1
            b -= 1
    s = not s

f = 1
b = N - 1
s = True
while f <= b:
    if s:
        
        ans2 = ans2 + [A[b]]
        b -= 1
        if f <= b:
            ans2 = [A[b]] + ans2
            b -= 1
    else:
        ans2 = ans2 + [A[f]]
        f += 1
        if f <= b:
            ans2 = [A[f]] + ans2
            f += 1

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

Submission status: Time Limit Exceeded

Solution code:
import itertools

def main():
    n = int(input())

    lst = [0 for i in range(n)]
    for i in range(n):
        lst[i] = int(input())

    lst = sorted(lst)


    # -(-n//2) => 切り上げ
    if n %2 == 0:
        lst1 = lst[0:-(-n//2)]
        lst2 = lst[-(-n//2):n]

        lst1 = list(itertools.permutations(lst1))
        #lst2 = list(itertools.permutations(lst2))

        ans = 0
        l2 = lst2
        for l1 in lst1:
            #for l2 in lst2:
            ans = max(ans,calc(n,l1, l2))

        print(ans)

    else:
        lst2A = list(itertools.permutations(lst[n//2:n]))
        lst1B = list(itertools.permutations(lst[0:-(-n//2)]))

        ans = 0

        l1 = lst[0:n//2]
        for l2 in lst2A:
            ans = max(ans,calcA(l1, l2))

        l2 = lst[-(-n//2):n]
        for l1 in lst1B:
            ans = max(ans,calc(n, l1, l2))

        print(ans)

def calc(n,lst1,lst2):
    ret = 0
    if n %2 == 1:
        for i in range(len(lst2)):
            ret += lst2[i] - lst1[i]
            ret += lst2[i] - lst1[i+1]
    else:
        for i in range(n//2):
            ret += lst2[i] - lst1[i]
            if not i == len(lst2)-1:
                ret += lst2[i+1] - lst1[i]
    return ret

def calcA(lst1,lst2):
    ret=0
    for i in range(len(lst1)):
        ret += lst2[i] - lst1[i]
        ret += lst2[i+1] - lst1[i]

    return ret



if __name__ == "__main__":
        main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

A.sort()

q=deque(A)
q2=deque()

cnt=0
while q:
	cnt+=1

	if cnt==1:
		v=q.popleft()
		q2.append(v)
	else:
		if cnt%2==0:
			v=q.pop()
		else:
			v=q.popleft()			

		begin=q2[0]
		end=q2[-1]

		if abs(begin-v)>=abs(end-v):
			q2.appendleft(v)
		else:
			q2.append(v)

l=list(q2)

ans=0
for i in range(N-1):
	ans+=abs(l[i+1]-l[i])

print ans

Submission status: Time Limit Exceeded

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

import itertools

stock = []

for element in itertools.permutations(list):
    stock_temp = []
    pre = 0
    cnt = 0
    for i in element:
        if cnt == 0:
            pre = i
            cnt += 1
        else:
            stock_temp.append(abs(pre - i))
            pre = i
            cnt += 1
    stock.append(sum(stock_temp))

print(max(stock))

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

N = int(input())
As = [int(input()) for _ in range(N)]

def slow_solve(As):
   
    nmax = 0
    N = len(As)
    for Ns in permutations(As, len(As)):
        m = sum([abs(Ns[i + 1] - Ns[i]) for i in range(N - 1)])
        nmax = max(m, nmax)
    return nmax

print(slow_solve(As))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
inp=[]
for _ in range(N):
    inp.append(int(input()))
inp.sort(reverse=True)
    
data=[inp[0]]

for t in range(1,N):
    
    if t%2:
        a=inp[-(t//2+1)]
    else:
        a=inp[t//2]
    
    max_num=abs(data[0]-a)
    max_ind=0
     
    if max_num<abs(data[-1]-a):
        max_num=abs(data[-1]-a)
        max_ind=len(data)
         
    for i in range(1,len(data)):
        temp=abs(data[i]-a)+abs(data[i-1]-a)-abs(data[i]-data[i-1])
        if temp > max_num:
            max_num=temp
            max_ind=i
            
    data.insert(max_ind,a)
    
ans=0

for i in range(N-1):
    ans += abs(data[i+1]-data[i])
    
print(ans)

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

f=True
while len(a)>0:
  la=len(a)-1
  lb=len(b)-1
  ln = abs(b[0]-a[0])
  lx = abs(b[0]-a[la])
  rn = abs(b[lb]-a[0])
  rx = abs(b[lb]-a[la])

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

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:
N = int(input())

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

A.sort()
difference = 0
cnt = 0
flag = 0
while A:
    cnt += 1
    if N % 2 == 1:
        if cnt % 2 == 1 and flag == 0:
            A_min = min(A)
            A.remove(A_min)
            A_max1 = A[-1]
            A_max2 = A[-2]
            difference += A_max1 - A_min
            difference += A_max2 - A_min
        else:
            A_max = max(A)
            A.remove(A_max)
            A_min = min(A)
            A.remove(A_min)
            difference += A_max - A_min
            flag += 1
            if flag == 2:
                flag = 0
    else:
        if cnt % 2 == 1 and flag == 0:
            A_min = min(A)
            A_max = max(A)
            difference += A_max - A_min
        else:
            A_min2 = A[1]
            difference += A_max - A_min2
            A.remove(A_max)
            A_max2 = max(A)
            difference += A_max2 - A_min
            A.remove(A_min)
            flag += 1
            A_max = A_max2
            A_min = A_min2
            if flag == 2:
                flag = 0
                
print(difference)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())

a=[]

for i in range(n):
    b=int(input())
    a.append(b)
    
a.sort()

ans=["" for i in range(n)]

ans[n//2]=a[-1]
a.remove(a[-1])
l=(n//2)-1
r=(n//2)+1
num=0
for i in range(n-1):
    if i%4==0:
        ans[l]=a[0]
        a.remove(a[0])
        num+=abs(ans[l+1]-ans[l])
        l-=1
    elif i%4==1:
        ans[r]=a[0]
        a.remove(a[0])
        num+=abs(ans[r]-ans[r-1])
        r+=1
    elif i%4==2:
        ans[l]=a[-1]
        a.remove(a[-1])
        num+=abs(ans[l+1]-ans[l])
        l-=1
    elif i%4==3:
        ans[r]=a[-1]
        a.remove(a[-1])
        num+=abs(ans[r]-ans[r-1])
        r-=1

ans.append(ans[0]) 
num+=abs(ans[-1]-ans[-2])    

num-=min(abs(ans[0]-ans[1]),abs(ans[-1]-ans[-2]),abs(ans[-2]-ans[-3]))
        
print(num)

Submission status: Time Limit Exceeded

Solution code:
def solve(pos):
    start = pos
    ans = 0
    a = 0
    b = N - 1
    for i in range(N-1):
        if a==start:
            a += 1
        elif b==start:
            b -= 1
        if abs(A[a]-A[pos])>=abs(A[b]-A[pos]):
            ans += abs(A[a]-A[pos])
            pos = a
            a += 1
        else:
            ans += abs(A[b]-A[pos])
            pos = b
            b -= 1
        #print(ans, a, b)
    #print(ans)
    return ans

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

if N<=10000:
    pos_list = list(range(N))
else:
    M = (A[0] + A[-1])/2
    for i in range(N-1):
        if A[i]<=M and M<A[i+1]:
            break
    a = max(0, i - 50)
    b = min(N - 1, i + 50)
    pos_list = list(range(a, b+1))
    if pos_list[0]!=0:
        pos_list = [0] + pos_list
    if pos_list[-1]!= N - 1:
        pos_list.append(N-1)
#print(pos_list)

ans = 0
for pos in pos_list:
    tmp = solve(pos)
    ans = max(ans, tmp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
n = int(input())
a1 = list()
for i in range(n):
    a_i = int(input())
    a1.append(a_i)
a1.sort()
a2 = copy.deepcopy(a1)
al1 = list()
al2 = list()
k = 0
ans1 = 0
ans2 = 0
if n % 2 != 0:
    al1.append(a1[0])
    a1.pop(0)
    al2.append(a2[-1])
    a2.pop(-1)
    for i in range(n//2):
        if k % 2 == 0:
            al1.insert(0, a1[-1])
            al1.append(a1[-2])
            a1.pop(-1)
            a1.pop(-1)
            al2.insert(0, a2[0])
            al2.append(a2[1])
            a2.pop(0)
            a2.pop(0)
        else:
            al2.insert(0, a2[-1])
            al2.append(a2[-2])
            a2.pop(-1)
            a2.pop(-1)
            al1.insert(0, a1[0])
            al1.append(a1[1])
            a1.pop(0)
            a1.pop(0)
        k += 1
    for i in range(n - 1):
        ans1 += abs(al1[i] - al1[i + 1])
        ans2 += abs(al2[i] - al2[i + 1])
else:
    al1.append(a1[0])
    a1.pop(0)
    al2.append(a2[-1])
    a2.pop(-1)
    for i in range(n // 2 - 1):
        if k % 2 == 0:
            al1.insert(0, a1[-1])
            al1.append(a1[-2])
            a1.pop(-1)
            a1.pop(-1)
            al2.insert(0, a2[0])
            al2.append(a2[1])
            a2.pop(0)
            a2.pop(0)
        else:
            al2.insert(0, a2[-1])
            al2.append(a2[-2])
            a2.pop(-1)
            a2.pop(-1)
            al1.insert(0, a1[0])
            al1.append(a1[1])
            a1.pop(0)
            a1.pop(0)
        k += 1
    for i in range(n - 2):
        ans1 += abs(al1[i] - al1[i + 1])
        ans2 += abs(al2[i] - al2[i + 1])
    ans1 += max(abs(a1[0] - al1[0]), abs(a1[0] - al1[-1]))
    ans2 += max(abs(a2[0] - al2[0]), abs(a2[0] - al2[-1]))
print(max(ans1, ans2))

Submission status: Time Limit Exceeded

Solution code:
number = []
num = []
goukei = []
t = int(0)
n = int(input())
for i in range(n):
    t = int(input())
    number.insert(n+1,t)

import numpy as np

import itertools
for i in itertools.permutations(number):
    k = len(i)
    for j in range(k-1):
        num.append(abs(i[j]-i[j+1]))

    goukei.append(sum(num))
    num.clear()

print(max(goukei))

Submission status: Time Limit Exceeded

Solution code:
def solve(pos):
    start = pos
    ans = 0
    a = 0
    b = N - 1
    for i in range(N-1):
        if a==start:
            a += 1
        elif b==start:
            b -= 1
        if abs(A[a]-A[pos])>=abs(A[b]-A[pos]):
            ans += abs(A[a]-A[pos])
            pos = a
            a += 1
        else:
            ans += abs(A[b]-A[pos])
            pos = b
            b -= 1
        #print(ans, a, b)
    #print(ans)
    return ans

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

if N<=10000:
    pos_list = list(range(N))
else:
    M = (A[0] + A[-1])/2
    for i in range(N-1):
        if A[i]<=M and M<A[i+1]:
            break
    a = max(0, i - 500)
    b = min(N - 1, i + 500)
    pos_list = list(range(a, b+1))
    if pos_list[0]!=0:
        pos_list = [0] + pos_list
    if pos_list[-1]!= N - 1:
        pos_list.append(N-1)
#print(pos_list)

ans = 0
for pos in pos_list:
    tmp = solve(pos)
    ans = max(ans, tmp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input().strip('\n'))
lis = []
for i in range(N):
    lis.append(int(input().strip('\n')))
mx_n = max(lis)
ms_n = min(lis)
lis.remove(mx_n)
lis.remove(ms_n)
point = mx_n-ms_n
while len(lis)>=2:
    mx = max(lis)
    ms = min(lis)
    point += mx_n-ms
    point += mx-ms_n
    mx_n = mx
    ms_n = ms
    lis.remove(mx)
    lis.remove(ms)
if len(lis)==1:
    point += max(abs(mx_n-lis[0]),abs(ms_n-lis[0]))
print(point)

Submission status: Time Limit Exceeded

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


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

left = min(A)
right = max(A)
li = 0
A.pop(A.index(min(A)))
ri = 1
A.pop(A.index(max(A)))
sum = abs(left-right)

while len(A) != 0:
    if li + ri  == 0:
        ma = max(A)
        A.pop(A.index(max(A)))
        if abs(left-ma) > abs(right-ma):
            sum = sum + abs(left - ma)
            left = ma
            li = 1

        else:
            sum = sum + abs(right - ma)
            right = ma
            ri = 1

    elif li + ri == 2:
        mi = min(A)
        A.pop(A.index(min(A)))
        if abs(left - mi) > abs(right - mi):
            sum = sum + abs(left - mi)
            left = mi
            li = 0

        else:
            sum = sum + abs(right - mi)
            right = mi
            ri = 0

    else:
        mi = min(A)
        A.pop(A.index(min(A)))
        if abs(left - mi) > abs(right - mi):
            sum = sum + abs(left - mi)
            left = mi
            li = 0

        else:
            sum = sum + abs(right - mi)
            right = mi
            ri = 0


print(sum)

Submission status: Time Limit Exceeded

Solution code:
import itertools

def main():
    n = int(input())

    lst = [0 for i in range(n)]
    for i in range(n):
        lst[i] = int(input())

    lst = sorted(lst)


    # -(-n//2) => 切り上げ
    if n %2 == 0:
        lst1 = lst[0:-(-n//2)]
        lst2 = lst[-(-n//2):n]

        lst1 = list(itertools.permutations(lst1))
        lst2 = list(itertools.permutations(lst2))

        ans = 0
        for l1 in lst1:
            for l2 in lst2:
                ans = max(ans,calc(n,l1, l2))

        print(ans)

    else:
        lst2A = list(itertools.permutations(lst[n//2:n]))
        lst1B = list(itertools.permutations(lst[0:-(-n//2)]))

        ans = 0

        for l2 in lst2A:
            l1 = lst[0:n//2]
            ans = max(ans,calcA(l1, l2))

        for l1 in lst1B:
            l2 = lst[-(-n//2):n]
            ans = max(ans,calc(n, l1, l2))

        print(ans)

def calc(n,lst1,lst2):
    ret = 0
    if n %2 == 1:
        for i in range(len(lst2)):
            ret += lst2[i] - lst1[i]
            ret += lst2[i] - lst1[i+1]
    else:
        for i in range(n//2):
            ret += lst2[i] - lst1[i]
            if not i == len(lst2)-1:
                ret += lst2[i+1] - lst1[i]
    return ret

def calcA(lst1,lst2):
    ret=0
    for i in range(len(lst1)):
        ret += lst2[i] - lst1[i]
        ret += lst2[i+1] - lst1[i]

    return ret



if __name__ == "__main__":
        main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
number = []
for index in range(N):
    number.append(int(input()))
number = sorted(number)
answer = []
count =0
while True:
    if len(number) == 1:
        answer.append(number[0])
        break
    if count % 2 == 0: 
        answer.insert(0,number.pop(number.index(max(number))))
    else:
        answer.insert(0,number.pop(number.index(min(number))))
    count += 1

sum1 = 0
for index in range(len(answer)-1):
    sum1 += abs(answer[index] - answer[index+1])

answer.insert(0, answer.pop(-1))
sum2 = 0
for index in range(len(answer)-1):
    sum2 += abs(answer[index] - answer[index+1])

if sum1 > sum2:
    print(sum1)
else:
    print(sum2)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
num=[int(input()) for i in range(N)]
num.sort()
jun=[]
sig=[i for i in range(1,N+1)]
if N%2!=0: #kisu
  manaka=int(N/2)
  if abs(num[manaka]-num[0])<abs(num[manaka]-num[N-1]):
    jun.append(manaka)
    for i in range(int((N-1)/2)):
      jun.append(max(sig)-1)
      sig.remove(max(sig))
      jun.append(min(sig)-1)
      sig.remove(min(sig))
  else:
    jun.append(manaka)
    for i in range(int((N-1)/2)):
      jun.append(min(sig)-1)
      sig.remove(min(sig))
      jun.append(max(sig)-1)
      sig.remove(max(sig))
else:
  manaka=int(N/2)
  jun.append(manaka)
  for i in range(manaka-1):
    jun.append(min(sig)-1)
    sig.remove(min(sig))
    jun.append(max(sig)-1)
    sig.remove(max(sig))
  jun.append(sig[0]-1)
delta=[abs(num[jun[i]]-num[jun[i+1]]) for i in range(N-1)]
print(sum(delta))

Submission status: Time Limit Exceeded

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

A = sorted(A)
res = []
begin = 0
end = len(A) - 1
res = deque()
res.append(A[begin])
res.append(A[end])
begin += 1
end -= 1
for i in range(N - 2):
	l = [abs(res[0] - A[begin]), abs(res[0] - A[end]), abs(res[-1] - A[begin]), abs(res[-1] - A[end])]
	cand = l.index(max(l))
	if cand == 0:
		res.appendleft(A[begin])
		begin += 1
	elif cand == 1:
		res.appendleft(A[end])
		end -= 1
	elif cand == 2:
		res.append(A[begin])
		begin += 1
	elif cand == 3:
		res.append(A[end])
		end -= 1
sum_diff = 0
for i in range(N - 1):
	 sum_diff += abs(res[i] - res[i + 1])
print sum_diff

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
nums =[]

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

nums.sort()
a = [nums.pop()]

while not len(nums) == 0:
  try:
    a.insert(0,nums.pop(0))
    a.append(nums.pop(0))
    a.insert(0,nums.pop())
    a.append(nums.pop())
  except IndexError:
    pass

tmp_1 = abs(a[-1] - a[-2])
tmp_2 = abs(a[-1] - a[0])

if tmp_1 < tmp_2:
  a.insert(0,a.pop())

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

array = [int(input()) for i in range(N)]

array.sort()
array2 = []
array3 = []

for i in range(N):
    if ((i + 1) // 2) % 2 == 0:
        if i % 2 == 0:
            array2.append(array[i // 2])
            array3.append((array[N - 1 - (i // 2)]))
        else:
            array2.insert(0, array[i // 2])
            array3.insert(0, (array[N - 1 - (i // 2)]))
    else:
        if i % 2 == 0:
            array3.append(array[i // 2])
            array2.append((array[N - 1 - (i // 2)]))
        else:
            array3.insert(0, array[i // 2])
            array2.insert(0, (array[N - 1 - (i // 2)]))
ans1 = 0
ans2 = 0

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

if ans1 > ans2:
    print(ans1)
    exit()
print(ans2)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
n = int(input())
A = [int(input()) for _ in range(n)]
def f(x):
    cnt = 0
    for i in range(len(x) - 1):
        cnt += abs(x[i] - x[i + 1])
    return cnt
ans = []
for B in permutations(A):
    ans.append((f(B), B))
ans.sort(reverse=True)
print(ans[0][0])

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
a=[]
b=[]
c=[]
for i in range(N):
    t=int(input())
    a.append(t)
for i in range(N//2):
    ma=max(a)
    mi=min(a)
    b.append(ma)
    c.append(mi)
    a.remove(ma)
    a.remove(mi)
if N==3:
    i=max(b)
    y=min(c)
    e=max(a)
    q=2*i-y-e
    w=i+e-2*y
    ans=max(q,w)

elif N%2==1:
    k=max(a)
    c.append(k)
    sma=sum(b)
    smi=sum(c)
    ans0=2*sma-2*smi
    h=max(c)
    ans1=h+ans0 
    c.remove(h)
    j=max(c)
    ans1+=j
    v=min(b)
    ans2=ans0-v
    b.remove(v)
    if len(b)==0:
        z=k
    else:
        z=min(b)
    ans2-=z
    d=[ans1,ans2]
    ans=max(d)
elif N%2==0:
    sma=sum(b)
    smi=sum(c)
    ans=2*sma-2*smi
    h=max(c)
    ans +=h 
    j=min(b)
    ans -=j
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    li = [int(input()) for i in range(N)]
    li = sorted(li)
    # print(li)# 1 1 3 4 5 9
    result = [li[-1], li[0]]#9 1 
    diff_total = abs(li[-1] - li[0])
    del li[-1]
    del li[0]# 1 3 4 5
    index_l = None
    diff_l = -1
    while len(li) > 0:
        for ind, n in enumerate(li):
            diff = max(abs(n - result[0]), abs(n - result[-1]))
            # print(diff)
            if diff > diff_l:
                index_l = ind
                diff_l = diff
                # print("!")
        val = li[index_l]
        del li[index_l]
        a = abs(val - result[0])
        b = abs(val - result[-1])
        if a > b:
            result.insert(0, val)
            diff_total += a
        else:
            result.append(val)
            diff_total += b
        

        index_l = None
        diff_l = -1
        
        # print(result)
    print(diff_total)
    # print(" ".join([str(j) for  j in result]))
main()

Submission status: Time Limit Exceeded

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


def distance(p, Array):
    
    m = 0
    index = 0
    for i in range(len(Array)):
        if m < abs(p - Array[i]):
            m = abs(p - Array[i])
            index = i
    return index


A.sort()
S = 0
for f in range(N):
    B = A[:]
    bi = B.pop(f)
    s = 0 
    #print(bi, "----")
    while B:
        j = distance(bi, B)

        # b[j] が bi から一番遠い
        bj = B.pop(j)
        s += abs(bi - bj)
       # print(s, bi, bj)

        bi = bj
        
    
    if S < s:
        S = s

print(S)

Submission status: Time Limit Exceeded

Solution code:
import itertools

def main():
    n = int(input())

    lst = [0 for i in range(n)]
    for i in range(n):
        lst[i] = int(input())

    lst = sorted(lst)


    # -(-n//2) => 切り上げ
    if n %2 == 0:
        lst1 = lst[0:-(-n//2)]
        lst2 = lst[-(-n//2):n]

        lst1 = list(itertools.permutations(lst1))
        lst2 = list(itertools.permutations(lst2))

        ans = 0
        for l1 in lst1:
            for l2 in lst2:
                ans = max(ans,calc(n,l1, l2))

        print(ans)

    else:
        lst1A = list(itertools.permutations(lst[0:n//2]))
        lst2A = list(itertools.permutations(lst[n//2:n]))
        lst1B = list(itertools.permutations(lst[0:-(-n//2)]))
        lst2B = list(itertools.permutations(lst[-(-n//2):n]))

        ans = 0

        for l1 in lst1A:
            for l2 in lst2A:
                ans = max(ans,calcA(l1, l2))

        for l1 in lst1B:
            for l2 in lst2B:
                ans = max(ans,calc(n, l1, l2))

        print(ans)

def calc(n,lst1,lst2):
    ret = 0
    if n %2 == 1:
        for i in range(len(lst2)):
            ret += abs(lst1[i] - lst2[i])
            ret += abs(lst1[i+1] - lst2[i])
    else:
        for i in range(len(lst2)):
            ret += abs(lst1[i] - lst2[i])
            if not i == len(lst2)-1:
                ret += abs(lst1[i+1] - lst2[i])
    return ret

def calcA(lst1,lst2):
    ret=0
    for i in range(len(lst1)):
        ret += abs(lst1[i] - lst2[i])
        ret += abs(lst1[i] - lst2[i+1])

    return ret



if __name__ == "__main__":
        main()