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

Solution code:
from statistics import median
N=int(input())
A=[]
for i in range(N):
    A.append(int(input()))
med=median(A)
A=[abs(int(i)-med) for i in A]
A=sorted(A)
ans=0
ans+=sum(A[:2]+2*A[2:])
print(int(ans))

Submission status: Accepted

Solution code:
x =input()
x = int(x)
y = []
for i in range(x):
    z = input()
    z = int(z)
    y.append(z)
y = sorted(y)
sum = 0
left =[]
right = []
center = y[0]
for i in range(int(x/2)):
    left.append(y[2*i+1])
    if x <= 2*i+2: break
    right.append(y[2*i+2])
b = len(left)
prev = y[0]
for i in range(b):
    if not left: break
    a =left.pop()
    sum += abs(prev - a)
    prev = a
    if not left : break
    a= left.pop(0)
    sum += abs(prev - a)
    prev = a
b = len(right)
prev = y[0]
for i in range(b):
    if not right: break
    a =right.pop()
    sum+= abs(prev-a)
    prev = a
    if not right : break
    a= right.pop(0)
    sum+= abs(prev-a)
    prev = a
suma = sum
y.reverse()
sum = 0
left =[]
right = []
center = y[0]
for i in range(int(x/2)):
    left.append(y[2*i+1])
    if x <= 2*i+2: break
    right.append(y[2*i+2])
b = len(left)
prev = y[0]
for i in range(b):
    if not left: break
    a =left.pop()
    sum += abs(prev - a)
    prev = a
    if not left : break
    a= left.pop(0)
    sum += abs(prev - a)
    prev = a
b = len(right)
prev = y[0]
for i in range(b):
    if not right: break
    a =right.pop()
    sum+= abs(prev-a)
    prev = a
    if not right : break
    a= right.pop(0)
    sum+= abs(prev-a)
    prev = a

if sum < suma : sum = suma
print(sum)

Submission status: Accepted

Solution code:
n=int(input())
a=[]
for i in range(n):
    a.append(int(input()))
a.sort()
ans = 0
l=0
r=0

if(n%2==1):
    tmp1=-1*a[int(n/2)-1]-a[int(n/2)]
    tmp2=a[int(n/2)]+a[int(n/2)+1]
    for i in range(int(n/2)):
        tmp1 += 2*a[-i-1]
        tmp2 += -2*a[i]
    for i in range(int(n/2)-1):
        tmp1 += -2*a[i]
        tmp2 += 2*a[-i-1]
    if(tmp1>tmp2):
        print(tmp1)
    else:
        print(tmp2)
    
else:
    tmp1=a[int(n/2)]-a[int(n/2)-1]
    for i in range(int(n/2)-1):
        tmp1+=-2*a[i]+2*a[int(n/2)+i+1]
    print(tmp1)

Submission status: Accepted

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

a = sorted(a)

if n == 2:
    print(a[1] - a[0])
    exit()

res1 = a[n - 1] + a[n - 2] - (a[0] * 2)
p = n - 3
q = 1
mode = 0
while 1:
    #print(p, q, res1)
    if p < q:
        break
    elif p == q:
        if mode == 0:
            res1 += a[p + 2] - a[p]
        else:
            res1 += a[p] - a[p - 2]
        break
    else:
        if mode == 0:
            res1 += a[p + 1] + a[p + 2] - a[q] - a[q + 1]
            mode = 1
            q += 2
        else:
            res1 += a[p] + a[p - 1] - a[q - 1] - a[q - 2]
            mode = 0
            p -= 2

res2 = a[n - 1] * 2 - a[0] - a[1]
p = n - 2
q = 2
mode = 1
while 1:
    #print(p, q, res2)
    if p < q:
        break
    elif p == q:
        if mode == 0:
            res2 += a[p + 2] - a[p]
        else:
            res2 += a[p] - a[p - 2]
        break
    else:
        if mode == 0:
            res2 += a[p + 1] + a[p + 2] - a[q] - a[q + 1]
            mode = 1
            q += 2
        else:
            res2 += a[p] + a[p - 1] - a[q - 1] - a[q - 2]
            mode = 0
            p -= 2

print(max(res1, res2))

Submission status: Accepted

Solution code:
N = int(input())
A = [int(input()) for i in range(N)]
A.sort()
As, Al = A[:N//2], A[N//2:]
Sum = 0
if N%2 == 0:
    for i in range(N//2 - 1):
        Sum += (Al[i+1] - As[i])*2
    Sum += Al[0] - As[-1]
else:
    S, L = 0, 0
    for i in range(N//2):
        S += (Al[i+1]-As[i])*2
        L += (Al[i+1]-As[i])*2
    L += Al[0]-Al[1]
    S += As[-1] - Al[0]
    Sum = max(L, S)
print(Sum)

Submission status: Accepted

Solution code:
n = int(input())
a = []
for _ in range(n):
    a.append(int(input()))
a.sort(reverse=True)

cand1 = 2 * sum(a[:n//2-1]) + a[n//2-1] \
        + (1 if n%2 else -1) * a[n//2] - 2 * sum(a[n//2+1:])
cand2 = 2 * sum(a[:(n-1)//2]) + (-1 if n%2 else 1) * a[(n-1)//2] \
        - a[(n-1)//2+1] - 2 * sum(a[(n-1)//2+2:])
print(max(cand1, cand2))

Submission status: Accepted

Solution code:
n = int(input())
a = [int(input()) for _ in range(n)]
a = sorted(a)
la = len(a)

if n % 2 == 0:
    p = la // 2
    ans = (sum(a[p:]) - sum(a[:p])) * 2 + a[p - 1] - a[p]
else:
    p = la // 2
    ans = (sum(a[p:]) - sum(a[:p])) * 2 - a[p] - a[p + 1]

    p = la // 2 + 1
    t = (sum(a[p:]) - sum(a[:p])) * 2 + a[p - 2] + a[p - 1]

    ans = max(ans, t)

print(ans)

Submission status: Accepted

Solution code:
import copy

N = int(input())
A = []
for i in range(N):
    x = int(input())
    A.append(x)
A.sort()
B = copy.copy(A)
ans1 = 0
ans2 = 0

for i in range(1,len(A)-1):
    if i%2 == 0:
        ans1 -= 2 * A.pop(0)
    else:
        ans1 += 2 * A.pop()

if N%2 == 1:
    ans1 = ans1 - A[0] - A[1]
else:
    ans1 = ans1 - min(A[0], A[1]) + max(A[0], A[1])
A = B

for i in range(1,len(A)-1):
    if i%2 == 0:
        ans2 += 2 * A.pop()
    else:
        ans2 -= 2 * A.pop(0)

if N%2  ==1:
    ans2 = ans2 + A[0] + A[1]
else:
    ans2 = ans2 + max(A[0], A[1]) - min(A[0], A[1])
    
print(max(ans1, ans2))

Submission status: Accepted

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

A_sorted = sorted(A)
coefficient_yama = [1 for i in range(N)]#上から
coefficient_tani = [-1 for i in range(N)]#下から

for i in range(1,N):
    if i  % 2 == 0:#even
        if N-i >= 2:
            coefficient_yama[i] = +2
            coefficient_tani[i] = -2
        else:
            coefficient_yama[i] = +1
            coefficient_tani[i] = -1
    else:#odd
        if N-i >= 2:
            coefficient_yama[i] = -2
            coefficient_tani[i] = +2
        else:
            coefficient_yama[i] = -1
            coefficient_tani[i] = +1

import numpy as np

ans_tani = np.sum(np.array(A_sorted) * np.array(sorted(coefficient_tani)))
ans_yama = np.sum(np.array(A_sorted) * np.array(sorted(coefficient_yama)))
#print(coefficient_tani)
#print(coefficient_yama)

if ans_tani >= ans_yama:
    print(ans_tani)
else:
    print(ans_yama)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(input()) for _ in range(N)]
A.sort()
ans=0
if N % 2 == 0:
    ans = 2 * (sum(A[N // 2 + 1:]) - sum(A[:N // 2 - 1])) + A[N // 2] - A[N // 2 - 1]
else:
    x = 2 * (sum(A[N // 2 + 1:]) - sum(A[:N // 2 - 1])) - A[N // 2] - A[N // 2 - 1]
    y = 2 * (sum(A[N // 2 + 2:]) - sum(A[:N // 2])) + A[N // 2] + A[N // 2 + 1]
    ans = max(x, y)
print(ans)

Submission status: Accepted

Solution code:
def c_align(N, A):
    """
    作る数列を p_1, ..., p_N としたとき、 p_{i-1} < p_i < p_{i+1} または
    p_{i-1} > p_i > p_{i+1} となるようなiは存在しないとしてよい。なぜなら、
    その他の要素の相対的順序を保ったままp_iを列の末尾に移しても、隣り合う項の
    差の絶対値の和は不変なため(末尾に移してそのようなiができたときは、
    末尾から2番めの要素を末尾に移せばよい)。

    このとき、ありうるパターンは (1) p_1>=p_2<=p_3>= ... または
    (2) p_1<=p_2>=p_3<= ... のいずれかなので、両方試して小さくない方の値を
    解とすればよい。求めたい値は
    (p_1-p_2)+(p_3-p_2)+(p_3-p_4)+(p_5-p_4)+... = \sum_{i=1}^N c_ip_i
    となる。

    Nが偶数のとき、 (1) のパターンでは c_1=1, c_N=-1, c_{2k}=-2, c_{2k+1}=2、
    (2) のパターンでは c_1=-1, c_N=1, c_{2k}=2, c_{2k+1}=-2 となる。
    (1) のパターンに基づくと、 N-1, N-3, ..., 5, 3, 1, N, N-2, ..., 4, 2 番目に
    元の数列の値が大きなものから入れていけばよい。
    (2) のパターンに基づくと、 2, 4, ..., N-2, N, 1, 3, 5, ..., N-3, N-1 番目に
    元の数列の値が大きなものから入れていけばよい。
    が、これは(1) のパターンに基づいて作った数列を逆順にしたものである。
    なので、どちらを出力してもよい。

    Nが奇数のとき、 (1) のパターンでは c_1=1, c_N=1, c_{2k}=-2, c_{2k+1}=2、
    (2) のパターンでは c_1=-1, c_N=-1, c_{2k}=2, c_{2k+1}=-2 となる。
    (1) のパターンに基づくと、 N-2, N-4, ..., 3, 1, N, N-1, N-3, ..., 4, 2 番目に
    元の数列の値が大きなものから入れていけばよい。
    (2) のパターンに基づくと、 2, 4, ..., N-3, N-1, N, 1, 3, ..., N-4, N-2 番目に
    元の数列の値が大きなものから入れていけばよい。
    この2つの数列は互いに逆順の関係というわけではないので、両方試して
    値が小さくない方を出力しなければならない。
    """
    A.sort()
    seq = [0] * N
    # コメントでは1-indexedだが、ここでは0-indexedである
    if N % 2 == 0:
        for k in range(N - 2, -1, -2):
            seq[k] = A.pop()
        for k in range(N - 1, 0, -2):
            seq[k] = A.pop()
        ans = 0
        for k in range(N - 1):
            ans += abs(seq[k] - seq[k + 1])
    else:
        tmp = A[:]
        for k in range(N - 3, -1, -2):
            seq[k] = tmp.pop()
        seq[N - 1] = tmp.pop()
        for k in range(N - 2, 0, -2):
            seq[k] = tmp.pop()

        seq2 = [0] * N
        tmp = A[:]
        for k in range(1, N - 1, 2):
            seq2[k] = tmp.pop()
        seq2[N - 1] = tmp.pop()
        for k in range(0, N - 2, 2):
            seq2[k] = tmp.pop()

        ans1, ans2 = 0, 0
        for k in range(N - 1):
            ans1 += abs(seq[k] - seq[k + 1])
        for k in range(N - 1):
            ans2 += abs(seq2[k] - seq2[k + 1])
        ans = max(ans1, ans2)
    return ans

N = int(input())
A = [int(input()) for _ in range(N)]
print(c_align(N, A))

Submission status: Accepted

Solution code:
def c_align(N, A):
    A.sort()
    seq = [0] * N
    if N % 2 == 0:
        for k in range(N - 2, -1, -2):
            seq[k] = A.pop()
        for k in range(N - 1, 0, -2):
            seq[k] = A.pop()
        ans = 0
        for k in range(N - 1):
            ans += abs(seq[k] - seq[k + 1])
    else:
        tmp = A[:]
        for k in range(N - 3, -1, -2):
            seq[k] = tmp.pop()
        seq[N - 1] = tmp.pop()
        for k in range(N - 2, 0, -2):
            seq[k] = tmp.pop()

        seq2 = [0] * N
        tmp = A[:]
        for k in range(1, N - 1, 2):
            seq2[k] = tmp.pop()
        seq2[N - 1] = tmp.pop()
        for k in range(0, N - 2, 2):
            seq2[k] = tmp.pop()

        ans1, ans2 = 0, 0
        for k in range(N - 1):
            ans1 += abs(seq[k] - seq[k + 1])
        for k in range(N - 1):
            ans2 += abs(seq2[k] - seq2[k + 1])
        ans = max(ans1, ans2)
    return ans

N = int(input())
A = [int(input()) for _ in range(N)]
print(c_align(N, A))

Submission status: Accepted

Solution code:
def create_sum(N):
    list_align = [2 for _ in range(N)]
    for i in range(N):
        if i % 2 == 0:
            list_align[i] *= -1
    list_align[0] //= 2
    list_align[N-1] //= 2
    list_align.sort()
    return list_align

def solve(N, Array):
    sum1 = 0
    sum2 = 0
    arr = create_sum(N)
    for i in range(N):
        sum1 += arr[i] * Array[i]
        sum2 += arr[i] * Array[N-1-i]
    print(max(abs(sum1), abs(sum2)))
    
if __name__ == "__main__":
    N = int(input())
    A = [int(input()) for _ in range(N)]
    A.sort()
    solve(N, A)

Submission status: Accepted

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

A.sort()

x1 = x2 = A[0]

i = 1
j = len(A) - 1

result = 0

while i <= j:
    a1 = A[i]
    a2 = A[j]
    d1 = abs(x1 - a1)
    d2 = abs(x1 - a2)
    d3 = abs(x2 - a1)
    d4 = abs(x2 - a2)
    ds = [d1, d2, d3, d4]
    dmax = max(ds)
    if dmax == d1:
        i += 1
        x1 = a1
        result += d1
    elif dmax == d2:
        j -= 1
        x1 = a2
        result += d2
    elif dmax == d3:
        i += 1
        x2 = a1
        result += d3
    else:
        j -= 1
        x2 = a2
        result += d4

print(result)

Submission status: Accepted

Solution code:
import itertools
n=int(input())
int_list=[int(input()) for i in range(n)]

# max min

int_list.sort()

if n%2 == 0:
    big = int_list[int(n)//2+1:]
    mid = int_list[int(n)//2-1:int(n)//2+1]
    min = int_list[:int(n)//2-1]
    result = 0
    a = mid[1]
    b = mid[0]

    for i, (plus, minus) in enumerate(zip(big, min)):
        if i%2 == 0:
            result += abs(b-plus)
            result += abs(a-minus)
            a = minus
            b = plus
        else:
            result += abs(b-minus)
            result += abs(a-plus)
            a = plus
            b = minus

    result += abs(a-b)
    print(result)
else:
    result_1 = 0
    result_2 = 0
    big = int_list[int(n)//2+2:]
    mid = int_list[int(n)//2:int(n)//2+2]
    min = int_list[:int(n)//2]
    left = mid[1]
    right = mid[0]

    for plus, minus in itertools.zip_longest(big, min):
        result_1 += abs(left - minus)
        if plus != None:
            result_1 += abs(minus - plus)
            left = plus
        else:
            left = minus

    result_1 += abs(left - right)

    big = int_list[int(n)//2+1:]
    mid = int_list[int(n)//2-1:int(n)//2+1]
    min = int_list[:int(n)//2-1]
    left = mid[0]
    right = mid[1]
    for plus, minus in itertools.zip_longest(big, min):
        result_2 += abs(left - plus)
        if minus != None:
            result_2 += abs(minus - plus)
            left = minus
        else:
            left = plus

    result_2 += abs(left - right)

    print(max(result_1, result_2))

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
 
num = []
for i in range(N):
  num.append(int(input()))
  
num = deque(sorted(num))
ans = deque([num.popleft()])
 
for i in range(N-2):
  if i % 4 == 0:
    ans.append(num.pop())
  elif i % 4 == 1:
    ans.appendleft(num.pop())
  elif i % 4 == 2:
    ans.append(num.popleft())
  else:
    ans.appendleft(num.popleft())

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

Solution code:
import sys


N=input()
A=[  int(sys.stdin.readline()) 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: Accepted

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

PLUS = A[int((N+1)//2):]
MINUS = A[:int((N+1)//2)]
#print(PLUS, MINUS)
ans = sum(PLUS)*2 - sum(MINUS)*2
if N%2==0:
    ans += MINUS[-1] - PLUS[0]
else:
    ans += sum(MINUS[-2:])

PLUS = A[int(N//2):]
MINUS = A[:int(N//2)]
#print(PLUS, MINUS)
ans2 = sum(PLUS)*2 - sum(MINUS)*2
if N%2==0:
    ans2 += MINUS[-1] - PLUS[0]
else:
    ans2 -= sum(PLUS[:2])

print(max(ans, ans2))

Submission status: Accepted

Solution code:
N = int(input())
A = [int(input()) for _ in range(N)]
A.sort()
ans = 0
if N % 2 == 0:
    ans = 2 * (sum(A[N // 2 + 1:]) - sum(A[:N // 2 - 1])) + A[N // 2] - A[N // 2 - 1]
else:
    x = 2 * (sum(A[N // 2 + 1:]) - sum(A[:N // 2 - 1])) - A[N // 2] - A[N // 2 - 1]
    y = 2 * (sum(A[N // 2 + 2:]) - sum(A[:N // 2])) + A[N // 2] + A[N // 2 + 1]
    ans = max(x, y)
print(ans)

Submission status: Accepted

Solution code:
import sys
N=int(input())
a=[]

for i in range(N):
    a.append(int(input()))

a.sort()
ans=0
ans2=0
if N%2==0:
    ans=2*sum(a[N//2:N])-a[N//2]-2*sum(a[0:N//2])+a[N//2-1]
    print(ans)
else:
    ans=2*sum(a[N//2+1:N])-2*sum(a[0:N//2+1])+a[N//2]+a[N//2-1]
    ans2=2*sum(a[N//2:N])-a[N//2]-a[N//2+1]-2*sum(a[0:N//2])
    print(max(ans,ans2))

Submission status: Accepted

Solution code:
from collections import deque
N = input()
A = [int(input()) for i in range(N)]
coef = [2] * N
coef[0] = 1
coef[-1] = 1
coef1 = [coef[i] if i % 2 == 0 else coef[i] * -1 for i in range(N)]
coef2 = [coef[i] if i % 2 != 0 else coef[i] * -1 for i in range(N)]

A = sorted(A)
coef1 = sorted(coef1)
coef2 = sorted(coef2)
res1 = 0
for i in range(N):
	res1 += A[i] * coef1[i]
res2 = 0
for i in range(N):
	res2 += A[i] * coef2[i]
print max(res1, res2)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(input()) for i in range(N)]
A.sort()
l,l_1,l_2 = [],[],[]
if len(A) % 2 == 0:  
  for i in range(len(A)):
    if i <= len(A)/2 - 2:
      l.append(-2)
    elif i == len(A)/2 -1:
      l.append(-1)
    elif i == len(A)/2:
      l.append(1)
    else:
      l.append(2)
  ans_d = [A[i]*l[i] for i in range(len(A))]
  print(sum(ans_d))
if len(A) % 2 == 1:
  for i in range(len(A)):
    if i <= int(len(A)/2) -2:
      l_1.append(2)
      l_2.append(-2)
    elif int(len(A)/2) -1 <= i <= int(len(A)/2):
      l_1.append(1)
      l_2.append(-1)
    else:
      l_1.append(-2)
      l_2.append(2)
  l_1.sort()
  l_2.sort()
  ans_d1 = [A[i]*l_1[i] for i in range(len(A))]
  ans_d2 = [A[i]*l_2[i] for i in range(len(A))]
  print(max(sum(ans_d1),sum(ans_d2)))

Submission status: Accepted

Solution code:
n = int(input())
a = list([int(input()) for i in range(n)])
a.sort()
import copy
b = copy.deepcopy(a)
a.reverse()

ans = 0

if(n%2==0):
    cnt = 0
    while(cnt!=n):
        if(cnt==0):
            initn = a[cnt]
            pre = a[cnt]
            cnt += 1

        elif(cnt == n-1):
            if(cnt%2 == 0):
                ans += abs(initn - a[cnt//2])
                pre = a[cnt//2]
            else:
                ans += abs(initn - b[cnt//2])
                pre = b[cnt//2]
            cnt += 1
            
        else:
            if(cnt%2 == 0):
                ans += abs(pre - a[cnt//2])
                pre = a[cnt//2]
            else:
                ans += abs(pre - b[cnt//2])
                pre = b[cnt//2]
            cnt += 1
    print(ans)
else:
    cnt = 0
    while(cnt!=n):
        if(cnt==0):
            initn = a[cnt]
            pre = a[cnt]
            cnt += 1

        elif(cnt == n-1):
            if(cnt%2 == 0):
                ans += abs(initn - a[cnt//2])
                pre = a[cnt//2]
            else:
                ans += abs(initn - b[cnt//2])
                pre = b[cnt//2]
            cnt += 1
            
        else:
            if(cnt%2 == 0):
                ans += abs(pre - a[cnt//2])
                pre = a[cnt//2]
            else:
                ans += abs(pre - b[cnt//2])
                pre = b[cnt//2]
            cnt += 1
    ans1 = ans
    ans = 0
    cnt = 0
    while(cnt!=n):
        if(cnt==0):
            initn = b[cnt]
            pre = b[cnt]
            cnt += 1

        elif(cnt == n-1):
            if(cnt%2 == 0):
                ans += abs(initn - b[cnt//2])
                pre = b[cnt//2]
            else:
                ans += abs(initn - a[cnt//2])
                pre = a[cnt//2]
            cnt += 1
            
        else:
            if(cnt%2 == 0):
                ans += abs(pre - b[cnt//2])
                pre = b[cnt//2]
            else:
                ans += abs(pre - a[cnt//2])
                pre = a[cnt//2]
            cnt += 1
    
    print(max(ans1,ans))

Submission status: Accepted

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

B = list(reversed(A))
result = abs(A[0] - B[0])

for _, (a, b) in enumerate(zip(A[1:N//2], B[1:N//2])):
    value = abs(A[0]-b) + abs(B[0]-a)
    result += value
    A[0], B[0] = a, b

if N % 2 != 0:
    x = A[N//2]
    result += max(abs(A[0]-x), abs(B[0]-x))

print(result)

Submission status: Accepted

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

if len(A) % 2:
    print(
        max(
            2 * (sum(A[len(A) // 2:]) - sum(A[:len(A) // 2])) - A[len(A) // 2] - A[len(A) // 2 + 1],
            2 * (sum(A[len(A) // 2 + 1:]) - sum(A[:len(A) // 2 + 1])) + A[len(A) // 2 - 1] + A[len(A) // 2]
        )
    )
else:
    print(2 * (sum(A[len(A) // 2:]) - sum(A[:len(A) // 2])) + A[len(A) // 2 - 1] - A[len(A) // 2])

Submission status: Accepted

Solution code:
from sys import stdin

def main():
    N = int(input())
    A = list(map(int, stdin.read().splitlines()))

    if N == 2:
        print(abs(A[1] - A[0]))
        return

    k = [2] * N; k[0] = 1; k[-1] = 1
    i = -1
    for j in range(N):
        k[j] *= i
        i *= -1
    k.sort()

    A.sort()
    ans1 = 0
    for i, j in zip(A, k):
        ans1 += i * j

    ans2 = 0
    for i, j in zip(A[::-1], k):
        ans2 += i * (j * -1)

    print(max(ans1, ans2))

input = lambda: stdin.readline()
main()

Submission status: Accepted

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

l = a[n-1]
r = a[0]
o = abs(l - r)
for i in range(n//2):
    o += abs(r - a[i])
    o += abs(l - a[n-i-1])
    l = a[i]
    r = a[n-i-1]
if n%2 != 0:
    i = n//2
    o += max(abs(l-a[i]) , abs(r-a[i]))


print(o)

Submission status: Accepted

Solution code:
def c_align(N, A):
    from collections import deque
    if N == 2:
        return abs(A[0] - A[1])
    tmp = sorted(A)

    seq = tmp[:]
    old_check = seq.pop(-1 + N // 2) if N % 2 == 0 else seq.pop(N // 2)
    current_check = -1
    seq = deque(seq)
    ans1 = 0
    turn = 0
    while seq:
        current_check = seq.pop() if turn % 2 == 0 else seq.popleft()
        ans1 += abs(current_check - old_check)
        old_check = current_check
        turn += 1

    seq = tmp[:]
    old_check = seq.pop(1 + N // 2) if N % 2 == 0 else seq.pop(N // 2)
    current_check = -1
    seq = deque(seq)
    ans2 = 0
    turn = 0
    while seq:
        current_check = seq.popleft() if turn % 2 == 0 else seq.pop()
        ans2 += abs(current_check - old_check)
        old_check = current_check
        turn += 1

    ans = max(ans1, ans2)
    return ans

N = int(input())
A = [int(input()) for _ in range(N)]
print(c_align(N, A))

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    array = [int(input()) for _ in range(N)]
    array.sort()

    div, mod = divmod(N, 2)
    if mod == 0:
        fore, last_in_fore, first_in_rear, rear = array[:div-1], array[div-1], array[div], array[div+1:]
        a = 2 * sum(rear) + first_in_rear - last_in_fore - 2 * sum(fore)
        print(a)
        return
    else:
        #mode1 (mfrfm):(1,-2,2,-2,1)
        fore1, mid1, rear1 = array[:div], array[div:div+2], array[div+2:]
        a1 = -2 * sum(fore1) + sum(mid1) + 2 * sum(rear1)
        #mode2 (mrfrm):(1,2,-2,2,1)
        fore2, mid2, rear2 = array[:div-1], array[div-1:div+1], array[div+1:]
        a2 = -2 * sum(fore2) - sum(mid2) + 2 * sum(rear2)

        print(max(a1, a2))
        return
    return


main()

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    array = [int(input()) for _ in range(N)]
    array.sort()

    div, mod = divmod(N, 2)
    if mod == 0:
        fore, last_in_fore, first_in_rear, rear = array[:div-1], array[div-1], array[div], array[div+1:]

        a = 2 * sum(rear) + first_in_rear - last_in_fore - 2 * sum(fore)
        print(a)
        return
    else:
        #mode1 (mrfrm):(1,2,-2,2,1)
        array1=array[:]
        fore1=[]
        rear1=[]
        while True:
            fore1.append(array1.pop(0))
            if len(array1) <= 2:
                break
            rear1.append(array1.pop(-1))
        mid1 = array1
        a1 = 2 * sum(rear1) + sum(mid1) - 2 * sum(fore1)

        #mode2 (mfrfm):(1,-2,2,-2,1)
        array2 = array[:]
        fore2=[]
        rear2=[]
        while True:
            rear2.append(array2.pop(-1))
            if len(array2) <= 2:
                break
            fore2.append(array2.pop(0))
        mid2 = array2
        a2 = 2 * sum(rear2) - sum(mid2) - 2 * sum(fore2)

        print(max(a1, a2))
        return
    return


main()

Submission status: Accepted

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

if N % 2 == 0:
    c = N // 2
    S = -2 * sum(A[:c]) + 2 * sum(A[c:]) + A[c-1] - A[c]
else:
    c = (N-1) // 2
    tmp1 = -2 * sum(A[:c]) + 2 * sum(A[c+2:]) + A[c] + A[c+1]
    tmp2 = -2 * sum(A[:c-1]) + 2 * sum(A[c+1:]) - A[c-1] - A[c]
    S = max(tmp1, tmp2)

print(S)

Submission status: Accepted

Solution code:
n = int(input())
nums = []
for _ in range(n):
    nums.append(int(input()))

nums.sort()
# 奇数は2通り
# w型とm型
if n % 2 == 1:
    w = -2*sum(nums[:n//2])+nums[n//2]+nums[n//2+1]+2*sum(nums[n//2+2:])
    m = -2*sum(nums[:n//2-1])-nums[n//2-1]-nums[n//2]+2*sum(nums[n//2+1:])
    print(max(w,m))
# 偶数は1通り
else:
    print(-2*sum(nums[:n//2-1])-nums[n//2-1]+nums[n//2]+2*sum(nums[n//2+1:]))

Submission status: Accepted

Solution code:
N=int(input())
A=sorted(int(input())for _ in[0]*N)
n=N//2-1
b=A[n+1]
print(2*sum(A[n+2:])-2*sum(A[:n])+b-A[n]-(min(A[n]+A[n+2],2*b)if N%2>0 else 0))

Submission status: Accepted

Solution code:
N=int(input())
A=sorted(int(input())for _ in[0]*N)
n=N//2-1
print(2*sum(A[n+2:])-2*sum(A[:n])+A[n+1]-A[n]-(min(A[n]+A[n+2],2*A[n+1])if N%2>0 else 0))

Submission status: Accepted

Solution code:
import numpy as np
import copy

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

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

len_array = len(a_array)

coffs = np.ones(len(a_array), dtype=bool) * 2

if len_array % 2 == 0:
    coffs = [-2] * ((len_array - 1) / 2) + [-1] + [1] + [2] * ((len_array -1) / 2)
    out = np.dot(a_array, coffs)
else:
    coffs1 = [-2] * ((len_array-3) / 2) + [-1] * 2 + [2] * ((len_array-1) / 2)
    coffs2 = [-2] * ((len_array-1) / 2) + [1] * 2 + [2] * ((len_array-3) / 2)
    out1 = np.dot(a_array, coffs1)
    out2 = np.dot(a_array, coffs2)
    out = max(out1, out2)

print out

Submission status: Accepted

Solution code:
N=int(input())
A=sorted(int(input())for _ in [0]*N)
n=N//2;m=n+1
print(2*sum(A[n+1:])-2*sum(A[:n-1])+A[n]-A[n-1]-(min(A[n-1]+A[n+1],2*A[n])if N%2>0 else 0))

Submission status: Accepted

Solution code:
N = int(input().strip())

A = []
for _ in range(N):
  A.append(int(input().strip()))
  
A = list(sorted(A))

if N % 2 == 1:
  coef = [-2] * ((N - 2) // 2) + [-1, -1] + [2] * ((N - 2) // 2 + 1)
  s1 = sum(c * a for c, a in zip(coef, A))
  coef = [-2] * ((N - 2) // 2 + 1) + [1, 1] + [2] * ((N - 2) // 2)
  s2 = sum(c * a for c, a in zip(coef, A))
  print(max(s1, s2))
else:
  coef = [-2] * ((N - 2) // 2) + [-1, 1] + [2] * ((N - 2) // 2)
  print(sum(c * a for c, a in zip(coef, A)))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

S = int(input())
lis = []
for item in range(0,int(S)):
    tmp = input()
    lis.append(int(tmp))
ls = sorted(lis)
lsb = sorted(lis)

center = ls[int(S/2-0.5)]
ans1 = ls[-1] - center
ls.remove(center)
for k in range(0,int(S/2)):
    try:
        
        ans1 = ans1 + ls.pop(-1) - ls[0]
        ans1 = ans1 + ls[-1] -ls.pop(0)
    except:
        break
    
if S % 2 ==0:
    print(ans1)
    exit()

center = lsb[int(S/2)]
ans2 = center - lsb[0] 

lsb.remove(center)

for k in range(0,int(S/2)):
    try:
        ans2 = ans2 + lsb[-1] - lsb.pop(0) 
        ans2 = ans2 + lsb.pop(-1) - lsb[0] 

    except:
        break
print(max(ans1,ans2))

Submission status: Accepted

Solution code:
# vim: set fileencoding=utf-8:
import collections


def main():
    # すべての数に対して、すべての数との差を計算する(10^5)か？TLEだ
    # 最大にするには、配列の中央の差が最大となるようにジグザグにしてけばいい
    N = input()
    A = sorted([input() for _ in xrange(N)])

    a = uzuamuki_sort(A, start="max", lr="right")
    b = uzuamuki_sort(A, start="max", lr="left")
    c = uzuamuki_sort(A, start="min", lr="right")
    d = uzuamuki_sort(A, start="min", lr="left")
    anss = [cal_ans(ele, N) for ele in [a, b, c, d]]
    print(max(anss))


def cal_ans(arr, N):
    ans = 0
    for i in xrange(N - 1):
        ans += abs(arr[i] - arr[i + 1])

    return ans


def uzuamuki_sort(A, start, lr):
    deq = collections.deque(A)
    uzu = collections.deque()

    def max_lr():
        uzu.appendleft(deq.popleft())
        uzu.append(deq.popleft())

    def max_rl():
        uzu.append(deq.popleft())
        uzu.appendleft(deq.popleft())

    def min_lr():
        uzu.appendleft(deq.pop())
        uzu.append(deq.pop())

    def min_rl():
        uzu.append(deq.pop())
        uzu.appendleft(deq.pop())

    if start == "max":
        uzu.append(deq.popleft())
        if lr == "right":
            while True:
                try:
                    min_rl()
                    max_rl()
                except IndexError:
                    break
        elif lr == "left":
            while True:
                try:
                    min_lr()
                    max_lr()
                except IndexError:
                    break

    elif start == "min":
        uzu.append(deq.pop())
        if lr == "right":
            while True:
                try:
                    max_rl()
                    min_rl()
                except IndexError:
                    break
        elif lr == "left":
            while True:
                try:
                    max_lr()
                    min_lr()
                except IndexError:
                    break

    return list(uzu)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Oct 27 19:18:58 2018
tenka1C
@author: maezawa
"""

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

a.sort()
b = [2*(-1)**i for i in range(n)]
b[0] = b[0]//2
b[-1] = b[-1]//2
b.sort()
ans1 = sum([a[i]*b[i] for i in range(n)])
c = [-b[i] for i in range(n)]
c.sort()
ans2 = sum([a[i]*c[i] for i in range(n)])
                    
print(max([ans1,ans2]))

Submission status: Accepted

Solution code:
import time
import random
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 = []
if len(a) % 2 == 1:
    b = a[0:int((len(a) - 1)/2) ]
    c = a[int((len(a) - 1)/2) : len(a)]
else :
    b = a[0:int((len(a) )/2)  ]
    c = a[int((len(a) )/2) : len(a)]
c.reverse()
d = []
e = []
forward = True;
for i in range(len(b)):
    if forward:
        d.append(b[i])
    else :
        d.insert(0,b[i])
    forward = not forward
forward = True

for i in range(len(c)):
    if forward:
        e.append(c[i])
    else :
        e.insert(0,c[i])
    forward = not forward

h = d[:]
j = e[:]
if len(a) % 2 == 1:
    if (len(h) % 2 == 0) :
        h.append(j.pop(-1))
    else:
        h.insert(0,j.pop(0))

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

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

a = [0] * N
b = [0] * N
j = 1

for i in range(N-1):    
    a[i] += -j
    a[i+1] += j
    b[i] += j
    b[i+1] += -j    
    j = -j

a.sort()
b.sort()
s1 = sum([i*j for i,j in zip(a, A)])
s2 = sum([i*j for i,j in zip(b, A)])
print(max(s1,s2))