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:
import collections

N=int(input())

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

A.sort()

ans=[A[0],A[-1]]
ans=collections.deque(ans)
l=1
r=-2
n=[0]*4
ansn=abs(A[0]-A[-1])
for i in range(N-2):
    n[0]=abs(A[l]-ans[0])
    n[1]=abs(A[l]-ans[-1])
    n[2]=abs(A[r]-ans[0])
    n[3]=abs(A[r]-ans[-1])
    if n[0]==max(n):
        ansn+=n[0]
        ans.appendleft(A[l])
        l+=1
    elif n[1]==max(n):
        ansn+=n[1]
        ans.append(A[l])
        l+=1
    elif n[2]==max(n):
        ansn+=n[2]
        ans.appendleft(A[r])
        r-=1
    elif n[3]==max(n):
        ansn+=n[3]
        ans.append(A[r])
        r-=1

print(ansn)

Submission status: Accepted

Solution code:
N=int(input())

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

A.sort()

ansl=A[0]
ansr=A[-1]
l=1
r=-2
n=[0]*4
ansn=abs(A[0]-A[-1])
for i in range(N-2):
    n[0]=abs(A[l]-ansl)
    n[1]=abs(A[l]-ansr)
    n[2]=abs(A[r]-ansl)
    n[3]=abs(A[r]-ansr)
    if n[0]==max(n):
        ansn+=n[0]
        ansl=A[l]
        l+=1
    elif n[1]==max(n):
        ansn+=n[1]
        ansr=A[l]
        l+=1
    elif n[2]==max(n):
        ansn+=n[2]
        ansl=A[r]
        r-=1
    elif n[3]==max(n):
        ansn+=n[3]
        ansr=A[r]
        r-=1

print(ansn)

Submission status: Accepted

Solution code:
n=int(input())
l=[]
for i in range(n):
  l.append(int(input()))
l1=sorted(l)
if n%2==0:
  k=n//2
  sum=0
  for i in range(0,k):
    sum-=2*l1[i]
  for i in range(k,n):
    sum+=2*l1[i]
  sum-=l1[k]
  sum+=l1[k-1]
  print(sum)
else:
  k=n//2
  sum=0
  for i in range(k,n):
    sum+=2*l1[i]
  for i in range(k):
    sum-=2*l1[i]
  sum-=l1[k]
  sum-=l1[k+1]
  sum1=0
  for i in range(k+1,n):
    sum1+=2*l1[i]
  for i in range(k+1):
    sum1-=2*l1[i]
  sum1+=l1[k]
  sum1+=l1[k-1]
  print(max(sum,sum1))

Submission status: Accepted

Solution code:
#%%
n = int(input())
a = [0] * n
for i in range(n):
    a[i] = int(input())
a.sort(reverse=True)
ook = []
tii = []
for i in range(0, n//2):
    ook.append(a[i])
for i in range(n//2, n):
    tii.append(a[i])
if n % 2 == 0:
    ans = 2 * (sum(ook) - sum(tii)) - (ook[-1] - tii[0])
    print(ans)
else:
    tmp = tii.pop(0)
    tmp1 = 2 * (sum(ook) - sum(tii)) + (tii[0]) - tmp
    tmp2 = 2 * (sum(ook) - sum(tii)) + tmp - ook[-1]
    print(max(tmp1, tmp2))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)

def main():
    n = int(input().strip())
    a = [0] * n
    for i in range(n):
        a[i] = int(input().strip())
    a = sorted(a)
    ans = 0
    if n % 2 == 0:
        kei1 = sorted([1, -1] + [-2] * ((n-2)//2) + [2] * ((n-2)//2))
        for i in range(n):
            ans += a[i] * kei1[i]
    else:
        kei1 = sorted([-1] * 2 + [2] * (n//2) + [-2] * (n//2 - 1))
        kei2 = sorted([1] * 2 + [2] * (n//2-1) + [-2] * (n//2))
        ans2 = 0
        for i in range(n):
            ans += a[i] * kei1[i]
            ans2 += a[i] * kei2[i]
        ans = max(ans, ans2)

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import*
n,*a=map(int,open(0).read().split())
def f(a):
  a=deque(a)
  deq=deque([a.popleft()])
  for i in range(n-1):
    if i%4==0:
      deq.appendleft(a.pop())
    elif i%4==1:
      deq.append(a.pop())
    elif i%4==2:
      deq.appendleft(a.popleft())
    else:
      deq.append(a.popleft())
  l=list(deq)
  return sum(abs(i-j)for i,j in zip(l,l[1:]))
s=sorted(a)
print(max(f(s),f(s[::-1])))

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
A = []
B = []

for i in range(N):

    a = int(input())

    A.append(a)

A.sort()

now = A.pop(0)
L = now
R = now
ans = 0
Lind = 0
Rind = -1

for i in range(N-1):

    if abs(L-A[Lind]) == max(abs(L-A[Lind]),abs(L-A[Rind]),abs(R-A[Lind]),abs(R-A[Rind])):
        ans += abs(L-A[Lind])
        L = A[Lind]
        Lind += 1

    elif abs(L-A[Rind]) == max(abs(L-A[Lind]),abs(L-A[Rind]),abs(R-A[Lind]),abs(R-A[Rind])): 
        ans += abs(L-A[Rind])
        L = A[Rind]
        Rind -= 1

    elif abs(R-A[Lind]) == max(abs(L-A[Lind]),abs(L-A[Rind]),abs(R-A[Lind]),abs(R-A[Rind])):
        ans += abs(R-A[Lind])
        R = A[Lind]
        Lind += 1

    elif abs(R-A[Rind]) == max(abs(L-A[Lind]),abs(L-A[Rind]),abs(R-A[Lind]),abs(R-A[Rind])):
        ans += abs(R-A[Rind])
        R = A[Rind]
        Rind -= 1

    else:
        print ("eeror")

    #print (A,L,R,ans)

print (ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(int(input())for i in range(N))
A.sort()
L = []
R = []
for i in range(N):
    if i%2 == 0:
        L.append(A[i//2])
        R.append(A[-(i//2)-1])
    else:
        L.append(A[-(i//2)-1])
        R.append(A[i//2])
saL,saR = [],[]
for i in range(N):
    saL.append(abs(L[i]-L[i-1]))
    saR.append(abs(R[i]-R[i-1]))
print(max(sum(saL)-min(saL),sum(saR)-min(saR)))

Submission status: Accepted

Solution code:
from copy import copy
N = int(input())
A = [int(input()) for _ in range(N)]
A.sort()
A1 = copy(A)
A2 = copy(A)
B1 = []
B2 = []
i=0
while A1 and A2:
    if i%2 == 0:
        B1.append(A1.pop(0))
        B2.append(A2.pop(-1))
    else:
        B1.append(A1.pop(-1))
        B2.append(A2.pop(0))
    i += 1
B1.append(B1[0])
B2.append(B2[0])
C1 = [abs(B1[i+1]-B1[i]) for i in range(len(B1)-1)]
C2 = [abs(B2[i+1]-B2[i]) for i in range(len(B2)-1)]
print(max(sum(C1)-min(C1),sum(C2)-min(C2)))

Submission status: Accepted

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

A_sorted = sorted(A,reverse=True)

if N%2:
  a1=2*(sum(A_sorted[:N//2])-sum(A_sorted[N//2:]))+A_sorted[N//2]+A_sorted[N//2+1]
  a2=2*(sum(A_sorted[:N//2+1])-sum(A_sorted[N//2+1:]))-A_sorted[N//2]-A_sorted[N//2-1]
  print(max(a1,a2))
else:
  print(2*(sum(A_sorted[:N//2])-sum(A_sorted[N//2:]))-A_sorted[N//2-1]+A_sorted[N//2])

Submission status: Accepted

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

ans = -1

if n % 2 == 1:
    sum2 = 0
    sum1 = 0
    for i in range(n):
        if n // 2 - 1 <= i <= n // 2:
            sum1 -= a[i]
        elif i < n // 2:
            sum2 -= a[i]
        else:
            sum2 += a[i]
    ans = max(ans, sum2 * 2 + sum1)

    a.reverse()
    sum2 = 0
    sum1 = 0
    for i in range(n):
        if n // 2 - 1 <= i <= n // 2:
            sum1 += a[i]
        elif i < n // 2:
            sum2 += a[i]
        else:
            sum2 -= a[i]
    ans = max(ans, sum2 * 2 + sum1)
else:
    Sum = 0
    for i in range(n):
        if i == n // 2 - 1:
            Sum -= a[i]
        elif i == n // 2:
            Sum += a[i]
        elif i < n // 2:
            Sum -= a[i] * 2
        else:
            Sum += a[i] * 2
    ans = max(ans, Sum)
    
    
print(ans)

Submission status: Accepted

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

a = sorted(a)


s_a = a[0:n//2]
l_a = a[n//2:]

if len(s_a) == len(l_a):
    print(2*sum(l_a) - l_a[0] - 2*sum(s_a) + s_a[-1])

else:
    tmp_ans1 = 2*sum(l_a) - l_a[0] - l_a[1] - 2*sum(s_a)    
    s_a = a[0:n//2+1]
    l_a = a[n//2+1:]
    tmp_ans2 = 2*sum(l_a) - 2*sum(s_a) + s_a[-2] + s_a[-1]
    print(max(tmp_ans1, tmp_ans2))

Submission status: Accepted

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

lis=sorted(lists)
if n%2==0:
    sig=sum(lis)
    left=sum(lis[:n//2])
    print(2*sig-4*left+lis[n//2-1]-lis[n//2])
if n%2!=0:
    sig=sum(lis)
    print(max(2*sig-4*sum(lis[:(n-1)//2])-lis[(n-1)//2]-lis[(n+1)//2], 2*sig-4*sum(lis[:(n+1)//2])+lis[(n-1)//2]+lis[(n-3)//2]))

Submission status: Accepted

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

if N%2 == 0:
  S = A[:N//2]
  L = A[N//2:]
  ans = 2*sum(L)-L[0]-2*sum(S)+S[-1]
else:
  S1 = A[:N//2]
  L1 = A[N//2:]
  S2 = A[:N//2+1]
  L2 = A[N//2+1:]
  ans1 = 2*sum(L1)-L1[0]-L1[1]-2*sum(S1)
  ans2 = 2*sum(L2)-2*sum(S2)+S2[-1]+S2[-2]
  ans = max(ans1,ans2)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = [int(input()) for _ in range(n)]
a.sort()
if n % 2 == 0:
    half_n = n // 2
    pre = a[:half_n]
    post = a[half_n:]
    print((sum(post) * 2 - post[0]) - (sum(pre) * 2 - pre[-1]))
else:
    half_n = n // 2
    pre1 = a[:half_n]
    post1 = a[half_n:]
    pre2 = a[:half_n+1]
    post2 = a[half_n+1:]
    diff1 = (sum(post1) * 2 - post1[0] - post1[1]) - sum(pre1) * 2
    diff2 = sum(post2) * 2 - (sum(pre2) * 2 - pre2[-1] - pre2[-2])
    print(max(diff1, diff2))

Submission status: Accepted

Solution code:
import os
import os
import sys
from collections import deque

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N = int(sys.stdin.readline())
A = [int(sys.stdin.readline()) for _ in range(N)]


def solve(A):
    if N % 2 == 0:
        ans = [-1] * N
        for i, a in enumerate(A[:N // 2]):
            ans[i * 2 + 1] = a
        for i, a in enumerate(A[N // 2:]):
            ans[i * 2] = a
    else:
        ans = deque()
        que = deque(A)
        while len(que) > 1:
            ans.append(que.popleft())
            ans.append(que.pop())
        ans.appendleft(que.pop())
        ans = list(ans)
    return np.abs(np.diff(ans)).sum()


A.sort()
a = solve(A)
A.reverse()
b = solve(A)
print(max(a, b))

#
# def solve():
#     ans = []
#     for li in itertools.permutations(A):
#         ans.append((np.abs(np.diff(li)).sum(), li))
#     ans.sort()
#
#     print(*ans, sep='\n')
#
#
# solve()

Submission status: Accepted

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

A.sort()

if N % 2 == 0:  # Nが偶数ならそのままやる
    small = A[:N//2]
    big = A[N//2:]
    ans = sum(big)*2 - sum(small)*2 - big[0] + small[-1]
    print(ans)
else:  # Nが奇数なら中央値くんをsmallに加えるかbig加えるかで議論が起きる
    small = A[:N//2]
    big = A[N//2+1:]
    midian = A[N//2]

    # midianをbigに加えた時, midianを右端に置く
    ans_big = sum(big)*2 - sum(small)*2 - big[0] + midian  # midianを加える代わりにbig[0]とsmall[-1]を救うことができない
    # midianをsmallに加えた時, midianを左端に置く
    ans_small = sum(big)*2 - sum(small)*2 - midian + small[-1]  # midianが引かれる代わりにbig[0]とsmall[-1]を救うことができる
    print(max(ans_big, ans_small))

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
H = []
Q = deque()
for i in range(N):
  A = int(input())
  H.append(A)
H.sort()
#H = deque(H)

if N%2 == 0:
  groupA = H[:N//2]
  groupB = H[N//2:]
  ans = 2*sum(groupB)-2*sum(groupA)-groupB[0]+groupA[-1]
else:
  groupA1 = H[:N//2]
  groupB1 = H[N//2:]
  groupA2 = H[:N//2+1]
  groupB2 = H[N//2+1:]
  ans1 = 2*sum(groupB1)-2*sum(groupA1)-groupB1[0]-groupB1[1]
  ans2 = 2*sum(groupB2)-2*sum(groupA2)+groupA2[-1]+groupA2[-2]
  ans = max(ans1,ans2)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = sorted([int(input()) for i in range(n)])
l = n//2

if n % 2 == 0:
    small = a[:l]
    big = a[l:]
    ans = sum(big) * 2 - sum(small) * 2  - big[0] + small[-1]
    print(ans)

else:
    small = a[:l]
    big = a[l+1:]
    ans = sum(big) * 2 - sum(small) * 2 - min(a[l] - small[-1], big[0] - a[l])
    print(ans)

Submission status: Accepted

Solution code:
N=int(input())
l=[]

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

l=sorted(l)
i=0
sum=0
nr=0
nl=0
right=l.pop(0)
left=right

while len(l)>1:
    if i%4==0:
        nr=l.pop(-1)
        sum+=nr-right
        right=nr        
    elif i%4==1:
        nl=l.pop(-1)
        sum+=nl-left
        left=nl
    elif i%4==2:
        nr=l.pop(0)
        sum-=nr-right
        right=nr       
    elif i%4==3:
        nl=l.pop(0)
        sum-=nl-left
        left=nl
        
    i+=1

#終わりのはじっこの処理がヤバイ? ちゃんと差がおおきくなるように配置できてるか
#11678で25出せればおけ
        
print(sum+max(abs(right-l[0]),abs(left-l[0])))

Submission status: Accepted

Solution code:
n = int(input())
a = sorted([int(input()) for i in range(n)])
l = n//2

if n % 2 == 0:
    small = a[:l]
    big = a[l:]
    ans = sum(big) * 2 - sum(small) * 2  - big[0] + small[-1]
    print(ans)

else:
    small = a[:l]
    big = a[l+1:]
    ans = sum(big) * 2 - sum(small) * 2 - min(a[l] - small[-1], big[0] - a[l])
    print(ans)

Submission status: Accepted

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

if n % 2 == 0:
    small = a[:(n//2)]
    big = a[(n//2):]
    ans = sum(big) * 2 - sum(small) * 2  - big[0] + small[-1]
    print(ans)

else:
    small = a[:(n//2)]
    big = a[(n//2):]
    ans = sum(big) * 2 - sum(small) * 2  - big[0] -big[1]

    small = a[:(n//2)+1]
    big = a[(n//2)+1:]
    ans = max(ans, sum(big) * 2 - sum(small) * 2 + small[-1] + small[-2])
    print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = [int(input()) for _ in range(n)]
num = int(n/2)
a.sort(reverse = True)
x = []
y = []
if n%2 == 0:
    result = 0
    x = a[:num]
    y = a[num:]
    result += sum(x)*2 - x[-1]
    result -= sum(y)*2 - y[0]
    print(result)
else:
    x = a[:num]
    y = a[num+1:]
    mid = a[num]
    result_1 = int(sum(x)*2 + mid - x[-1] - sum(y)*2)
    result_2 = int(sum(x)*2 - sum(y)*2 -mid + y[0])
    print(max(result_1, result_2))

Submission status: Accepted

Solution code:
from collections import deque

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

a.sort()

d = deque()

lft = False
smll = False

d.append(a[0])
fst = 1
end = n-1

for i in range(n-1):
    if not(smll):
        if not(lft):
            d.appendleft(a[end])
            end -= 1
            lft = True
        else:
            d.append(a[end])
            end -= 1
            lft = False
            smll = True
    else:
        if not(lft):
            d.appendleft(a[fst])
            fst += 1
            lft = True
        else:
            d.append(a[fst])
            fst += 1
            lft = False
            smll = False

memo = d.pop()
ans = 0
for i in range(n-1):
    memo2 = d.pop()
    ans += abs(memo-memo2)
    memo = memo2
    


d.append(a[n-1])
fst = 0
end = n-2
lft = False
smll = True


for i in range(n-1):
    if not(smll):
        if not(lft):
            d.appendleft(a[end])
            end -= 1
            lft = True
        else:
            d.append(a[end])
            end -= 1
            lft = False
            smll = True
    else:
        if not(lft):
            d.appendleft(a[fst])
            fst += 1
            lft = True
        else:
            d.append(a[fst])
            fst += 1
            lft = False
            smll = False

memo3 = d.pop()
ans2 = 0
for i in range(n-1):
    memo4 = d.pop()
    ans2 += abs(memo3-memo4)
    memo3 = memo4
    
ans = max(ans,ans2)
    
print(ans)

Submission status: Accepted

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

ans = 0
if N % 2 == 0:
  for i in range(N//2-1):
    ans -= A[i]*2
  ans += -A[N//2-1] + A[N//2]
  for i in range(N//2+1,N):
    ans += A[i]*2
else:
  ans1 = 0
  for i in range(N//2-1):
    ans1 -= A[i]*2
  ans1 += -A[N//2-1]-A[N//2]
  for i in range(N//2+1,N):
    ans1 += A[i]*2
  ans2 = 0
  for i in range(N//2):
    ans2 -= A[i]*2
  ans2 += A[N//2] + A[N//2+1]
  for i in range(N//2+2,N):
    ans2 += A[i]*2
  #print(ans1,ans2)
  ans = max(ans1,ans2)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = sorted(int(input()) for _ in range(N))
if N % 2:
    B1 = A[:N // 2]
    C1 = A[N // 2:]
    c1 = 2 * sum(C1) - C1[0] - C1[1]
    b1 = 2 * sum(B1)
    B2 = A[:N // 2 + 1]
    C2 = A[N // 2 + 1:]
    c2 = 2 * sum(C2)
    b2 = 2 * sum(B2) - B2[-1] - B2[-2]
    print(max(c1 - b1, c2 - b2))
else:
    B = A[:N // 2]
    C = A[N // 2:]
    c = 2 * sum(C) - C[0]
    b = 2 * sum(B) - B[-1]
    print(c - b)

Submission status: Accepted

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

a.sort(reverse = True)


keisuu = [0]*n
for i in range(n-1):
    if i % 2 == 0:
        keisuu[i] += 1
        keisuu[i+1] -= 1
    else:
        keisuu[i] -= 1
        keisuu[i+1] += 1
ans = 0
keisuu.sort(reverse = True)
for i in range(n):
    ans += a[i] * keisuu[i]


keisuu = [0]*n
for i in range(n-1):
    if i % 2 == 1:
        keisuu[i] += 1
        keisuu[i+1] -= 1
    else:
        keisuu[i] -= 1
        keisuu[i+1] += 1
keisuu.sort(reverse = True)
ans1 = 0
for i in range(n):
    ans1 += a[i] * keisuu[i]

print(max(ans, ans1))

Submission status: Accepted

Solution code:
n = int(input())
a = [int(input()) for _ in range(n)]
a.sort()
m = n // 2 - 1
if n % 2 == 0:
    ans = sum(a[:m]) * -2 - a[m] + a[m+1] + sum(a[m+2:]) * 2
else:
    ans1 = sum(a[:m]) * -2 - (a[m] + a[m+1]) + sum(a[m+2:]) * 2
    ans2 = sum(a[:m+1]) * -2 + (a[m+1] + a[m+2]) + sum(a[m+3:]) * 2
    ans = max(ans1, ans2)
    
print(ans)

Submission status: Accepted

Solution code:
# tenka1-2018-beginnerC - Align
def main():
    N, *A = map(int, open(0).read().split())
    A.sort()
    if N & 1:
        low, high, mid = A[: N // 2], A[N // 2 + 1 :], A[N // 2]
        x = (sum(high) - sum(low)) * 2 - mid + low[-1]
        y = (sum(high) - sum(low)) * 2 + mid - high[0]
        ans = max(x, y)
    else:
        low, high = A[: N // 2], A[N // 2 :]
        ans = (sum(high) - sum(low)) * 2 - high[0] + low[-1]
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# tenka1-2018-beginnerC - Align
from collections import deque


def main():
    N, *A = map(int, open(0).read().split())
    A.sort()
    if N & 1:
        low, high, mid = A[: N // 2], A[N // 2 + 1 :], A[N // 2]
        x = (sum(high) - sum(low)) * 2 - mid + low[-1]
        y = (sum(high) - sum(low)) * 2 + mid - high[0]
        ans = max(x, y)
    else:
        low, high = A[: N // 2], A[N // 2 :]
        ans = (sum(high) - sum(low)) * 2 - high[0] + low[-1]
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/tenka1-2018-beginner/tasks/tenka1_2018_c

import math

n = int(input())
num = [int(input()) for _ in range(n)]
num.sort()


def dif():
    ans = 0
    for i in range(1, n):
        ans += abs(b[i] - b[i - 1])
    return ans


b = [0]*n
# print(num)
if (n % 2 == 0):
    for i in range(n // 2):
        b[i * 2 + 1] = num[i]
        b[i * 2] = num[i + n // 2]
    # print(b)
    print(dif())
    # 大小大小…と並べていけば最適
    # 先頭・末尾以外は、大同士、小同士を入れ替えても差の絶対値に変化がない→中央値より大きい数値を小さい方から、中央値より小さい数値を小さい方から使っていけばいい
    # 偶数の時は中央値は真ん中の左側として、末尾に配置
    # 先頭の値は中央値より大きい値の内一番小さい値
else:
    # 奇数の時は中央値はもちろん真ん中の値
    # 先頭におくか末尾におくかでパターンが分かれる
    for i in range(n // 2):
        b[i * 2 + 1] = num[i]
        b[i*2] = num[i+n//2+1]
    b[n - 1] = num[n // 2]
    temp = dif()
    # print(b)
    for i in range(n // 2):
        b[i * 2 + 2] = num[i]
        b[i*2+1] = num[i+n//2+1]
    b[0] = num[n // 2]
    # print(b)
    print(max(dif(), temp))

Submission status: Accepted

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

if N % 2 == 1:
    A11 = A[:N//2+1]
    A12 = A[N//2+1:]
    ans1 = sum(A12)*2-sum(A11)*2+A11[-1]+A11[-2]

    A21 = A[:N//2]
    A22 = A[N//2:]
    ans2 = sum(A22)*2-sum(A21)*2-A22[0]-A22[1]

    ans = max(ans1, ans2)
else:
    A1 = A[:N//2]
    A2 = A[N//2:]
    ans = sum(A2)*2-sum(A1)*2+A1[-1]-A2[0]


print(ans)

Submission status: Accepted

Solution code:
def main():

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

    if N % 2 == 0:
        A1 = A[:N//2]
        A2 = A[N//2:][::-1]
        B1 = []
        B2 = []
        k, l = 0, 0
        for i in range(N):
            if i % 2 == 0:
                B1.append(A1[k])
                B2.append(A2[k])
                k += 1
            else:
                B1.append(A2[l])
                B2.append(A1[l])
                l += 1
        B1 = [B1[-1]] + B1[:-1]
        B2 = [B2[-1]] + B2[:-1]

        cand1, cand2 = 0, 0
        for i in range(1, N):
            cand1 += abs(B1[i-1]-B1[i])
            cand2 += abs(B2[i-1]-B2[i])
        return max(cand1, cand2)
    else:
        A3 = A[:N//2]
        A4 = A[N//2:][::-1]
        A5 = A[:(N+1)//2]
        A6 = A[(N+1)//2:][::-1]
        B3 = []
        B4 = []
        k, l = 0, 0
        for i in range(N):
            if i % 2 == 0:
                B3.append(A4[k])
                B4.append(A5[k])
                k += 1
            else:
                B3.append(A3[l])
                B4.append(A6[l])
                l += 1
        B3 = [B3[-1]] + B3[:-1]
        B4 = [B4[-1]] + B4[:-1]

        cand3, cand4 = 0, 0
        for i in range(1, N):
            cand3 += abs(B3[i-1]-B3[i])
            cand4 += abs(B4[i-1]-B4[i])
        return max(cand3, cand4)


if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
N = int(input())
As = []
for i in range(N):
  A = int(input())
  As.append(A)
As.sort()
if N%2 == 0:
  r = 2*sum(As[N//2+1:])-2*sum(As[:N//2-1])+As[N//2]-As[N//2-1]
if N%2 == 1:
  r1 = 2*sum(As[N//2+1:])-2*sum(As[:N//2-1])-As[N//2]-As[N//2-1]
  As.reverse()
  r2 = -2*sum(As[N//2+1:])+2*sum(As[:N//2-1])+As[N//2]+As[N//2-1]
  r = max(r1, r2)
print(r)

Submission status: Accepted

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

A.sort()
ans = 0
if N%2==0:
    B1 = A[:N//2]
    B2 = A[N//2:]
    ans = 2*(sum(B2)-sum(B1)) + B1[-1] - B2[0]
else:
    B1 = A[:N//2]
    B2 = A[N//2:]
    p = 2*(sum(B2)-sum(B1)) - B2[0] - B2[1]

    C1 = A[:N//2+1]
    C2 = A[N//2+1:]
    q = 2*(sum(C2)-sum(C1)) + C1[-1] + C1[-2]
    ans = max(p, q)

print(ans)

Submission status: Accepted

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

A.sort()
q = deque(A)

#小さいの中心
B = [0] * N


center = N // 2
minimum = q.popleft()
B[center] = minimum
left = center - 1
right = center + 1
cnt = 0
while q:
    if cnt % 4 == 0:
        num = q.pop()
        B[left] = num
        left -= 1
    elif cnt % 4 == 1:
        num = q.pop()
        B[right] = num
        right += 1
    elif cnt % 4 == 2:
        num = q.popleft()
        B[left] = num
        left -= 1
    elif cnt % 4 == 3:
        num = q.popleft()
        B[right] = num
        right += 1
    
    cnt += 1

ans_b = 0
for a,b in zip(B, B[1:]):
    ans_b += abs(a-b)

# 大きいの中心
q = deque(A)

B = [0] * N

center = N // 2
maximum = q.pop()
B[center] = maximum

left = center - 1
right = center + 1
cnt = 0
while q:
    if cnt % 4 == 2:
        num = q.pop()
        B[left] = num
        left -= 1
    elif cnt % 4 == 3:
        num = q.pop()
        B[right] = num
        right += 1
    elif cnt % 4 == 0:
        num = q.popleft()
        B[left] = num
        left -= 1
    elif cnt % 4 == 1:
        num = q.popleft()
        B[right] = num
        right += 1
    
    cnt += 1
#print("--", B, center)

ans_c = 0
for a,b in zip(B, B[1:]):
    ans_c += abs(a-b)




print(max(ans_b, ans_c))

Submission status: Accepted

Solution code:
import sys,bisect as bs,collections as cl,heapq as hq
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

n = onem()
a = []
for i in range(n):
    a.append(onem())
a.sort()
bbb = a[n//2+(n%2):]
bbb.reverse()

bbbb = a[n//2:]

if len(bbb) >= 3:
    bbbb = [bbbb[0]] + bbbb[2:] + [bbbb[1]]


aaa = a[:n//2+(n%2)]
if len(aaa) >= 3:
    aaa = [aaa[-1]] + aaa[:-2] + [aaa[-2]]

aaaa = a[:n//2]

lll = []
llll = []

for i in range(n):
    if i % 2 == 0:
        lll.append(aaa[i//2])
        llll.append(bbbb[i//2])
    else:
        lll.append(bbb[i//2])
        llll.append(aaaa[i//2])
ans = 0
an = 0
for i in range(n):
    if i == 0:
        st = lll[0]
        stt = llll[0]
    else:
        ans += abs(lll[i] - st)
        st = lll[i]
        an += abs(llll[i] - stt)
        stt = llll[i]
print(max(ans,an))

Submission status: Accepted

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

A.sort()

if N % 2 == 0:
    small = A[:N // 2]
    big = A[N//2:]
    x = 2 * sum(small) - small[-1]
    y = 2 * sum(big) - big[0]
    ans = y - x
else:
    small = A[:N // 2]
    big = A[N // 2 + 1:]
    mid = A[N // 2]

    left = 2 * sum(big) - 2 * sum(small) - mid + small[-1]
    right = 2 * sum(big) - 2 * sum(small) + mid - big[0]

    ans = max(left, right)

print(ans)

Submission status: Accepted

Solution code:
def calc_diffsum(li):
    ans = 0
    for ind,i in enumerate(li[:-1]):
        ans += abs(i-li[ind+1])
    return ans
#%%
N = int(input())
A = [int(input())for _ in range(N)]
#%%
A.sort()
li = []
li2 = []
for ind,i in enumerate(A):
    if(ind%2==1):
        li.append(A[-ind//2])
        li2.append(A[ind//2])
    else:
        li.append(A[ind//2])
        li2.append(A[-ind//2-1])

if(abs(li[-1]-li[0])>abs(li[-1]-li[-2])):
    li.insert(0,li[-1])
    del li[-1]
if(abs(li2[-1]-li2[0])>abs(li2[-1]-li2[-2])):
    li2.insert(0,li2[-1])
    del li2[-1]
print(max(calc_diffsum(li),calc_diffsum(li2)))

Submission status: Accepted

Solution code:
N=int(input())
a=sorted([int(input()) for i in range(N)])
r=[0]*N
r[1:-1:2]=a[:(N-1)//2]
r[-1]=a[(N-1)//2]
r[:-1:2]=a[(N-1)//2+1:]
A=list(reversed(a))
R=[0]*N
R[1:-1:2]=A[:(N-1)//2]
R[-1]=A[(N-1)//2]
R[:-1:2]=A[(N-1)//2+1:]
print(max(sum([abs(r[i]-r[i+1]) for i in range(N-1)]),sum([abs(R[i]-R[i+1]) for i in range(N-1)])))

Submission status: Accepted

Solution code:
#C問題
N = int(input())
A = [int(input()) for i in range(N)]
A.sort(reverse=True)

p = 0
n = 0
if N%2 == 0:
    MAX = 0
    for i in range(N):
        if i < (N//2):
            if i == (N//2)-1:
                p+=A[i]
            else:
                p+=A[i]*2
        else:
            if i == (N//2):
                n+=A[i]
            else:
                n+=A[i]*2
    MAX = max(MAX,p-n)
else:
    MAX = 0
    for i in range(N):
        if i <= (N//2):
            if i == (N//2) or i == (N//2)-1:
                p+=A[i]
            else:
                p+=A[i]*2
        else:
            n+=A[i]*2
    MAX = max(MAX,p-n)
    p = 0
    n = 0
    for i in range(N):
        if i <= (N//2)-1:
            p+=A[i]*2
        else:
            if i == (N//2) or i == (N//2)+1:
                n+=A[i]
            else:
                n+=A[i]*2
    MAX = max(MAX,p-n)
        
print(MAX)

Submission status: Accepted

Solution code:
from collections import deque

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

stack = deque(sorted(a))
one = 0
right = stack.pop()
left = right
count = 0
while stack:
    if count % 2 == 0:
        if len(stack) >= 2:
            stack_right = stack.popleft()
            stack_left = stack.popleft()
            one += abs(stack_right - right) + abs(stack_left - left)
            right = stack_right
            left = stack_left
        else:
            stack_one = stack.pop()
            one += max(abs(stack_one - right), abs(stack_one - left))
    else:
        if len(stack) >= 2:
            stack_right = stack.pop()
            stack_left = stack.pop()
            one += abs(stack_right - right) + abs(stack_left - left)
            right = stack_right
            left = stack_left
        else:
            stack_one = stack.pop()
            one += max(abs(stack_one - right), abs(stack_one - left))
    count += 1
stack = deque(sorted(a))
two = 0
right = stack.popleft()
left = right
count = 0
while stack:
    if count % 2 == 1:
        if len(stack) >= 2:
            stack_right = stack.popleft()
            stack_left = stack.popleft()
            two += abs(stack_right - right) + abs(stack_left - left)
            right = stack_right
            left = stack_left
        else:
            stack_one = stack.pop()
            two += max(abs(stack_one - right), abs(stack_one - left))
    else:
        if len(stack) >= 2:
            stack_right = stack.pop()
            stack_left = stack.pop()
            two += abs(stack_right - right) + abs(stack_left - left)
            right = stack_right
            left = stack_left
        else:
            stack_one = stack.pop()
            two += max(abs(stack_one - right), abs(stack_one - left))
    count += 1
print(max(one, two))

Submission status: Accepted

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

sorted_A = sorted(A, reverse=True)

if N % 2 == 0:
    ans = sum(sorted_A[:(N - 2) // 2]) * 2 + sorted_A[(N - 2) // 2] - sorted_A[(N - 2) // 2 + 1] - sum(sorted_A[(N - 2) // 2 + 2:] * 2)
else:
    ans_a = sum(sorted_A[:(N - 2) // 2]) * 2 + sum(sorted_A[(N - 2) // 2: (N - 2) // 2 + 2]) - sum(sorted_A[(N - 2) // 2 + 2:]) * 2
    ans_b = sum(sorted_A[:(N - 1) // 2]) * 2 - sum(sorted_A[(N - 1) // 2: (N - 1) // 2 + 2]) - sum(sorted_A[(N - 1) // 2 + 2:]) * 2
    ans = max(ans_a, ans_b)
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=sorted([int(input())for i in range(n)])
def f(x):
    p,q=1,n-2
    l,r=[a[0]],[a[n-1]]
    c=a[n-1]-a[0]
    t=0
    while p<=q:
        if t==x:
            r.append(a[q])
            c+=a[q]-l[0]
            q-=1
            l.pop(0)
        else:
            l.append(a[p])
            c+=r[0]-a[p]
            p+=1
            r.pop(0)
        t=(t+1)%2
    return c
print(max(f(0),f(1)))

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
n=int(input())
a=[int(input()) for i in range(n)]
a.sort()
if n==2:
    print(a[1]-a[0])
    quit()

ans=0
for i in range((n-1)//2):
    ans-=a[i]
for i in range((n-2)//2):
    ans+=a[n-1-i]
ans*=2
if n%2!=0:
    ans+=a[n//2]+a[n//2+1]
else:
    ans+=a[n//2]-a[n//2-1]

ans2=0
for i in range((n-1)//2):
    ans2+=a[n-1-i]
for i in range((n-2)//2):
    ans2-=a[i]
ans2*=2
if n%2!=0:
    ans2-=a[n//2]+a[n//2-1]
else:
    ans2+=a[n//2]-a[n//2+1]

# print(ans)
# print(ans2)

print(max(ans,ans2))