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 _collections import deque


def parser():
    while 1:
        data = list(input().split(' '))
        for number in data:
            if len(number) > 0:
                yield (number)


input_parser = parser()


def gw():
    global input_parser
    return next(input_parser)


def gi():
    data = gw()
    return int(data)


MOD = int(1e9 + 7)

import numpy
import scipy
from collections import deque
from math import sqrt
from math import floor
#https://atcoder.jp/contests/tenka1-2018-beginner/tasks/tenka1_2018_c
#C - Align
"""
need to consider the case that ticket is not enough to lower everything
"""

N = gi()
A = [0] * N
ais = [0] * N

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

A.sort()
base = 0
half_i = N // 2

for i in range(half_i):
    base -= 2 * A[i]

for i in range(half_i, N):
    base += 2 * A[i]

el = 0
ol_l = 0
ol_h = 0

if N % 2 == 0:
    el = base - A[half_i] + A[half_i - 1]

if (N >= 3 and N % 2):
    ol_l = base - 3 * A[half_i] + A[half_i - 1]
    ol_h = base - A[half_i] - A[half_i + 1]

print(max(el, ol_l, ol_h))

#HLHL

Submission status: Accepted

Solution code:
# coding: utf-8
N = int(input())
A = []
for _ in range(N):
    A.append(int(input()))
A.sort()
L1, L2 = [0] * N, [0] * N
L1[0] = A[N//2]
L2[0] = A[N//2]
for i in range(1, N):
    if i % 2 == 0:
        L1[i] = A[i//2-1]
        L2[i] = A[-i//2]
    else:
        L1[i] = A[-i//2]
        L2[i] = A[i//2]
a1, a2 = 0, 0
for i in range(N-1):
    a1 += abs(L1[i] - L1[i+1])
    a2 += abs(L2[i] - L2[i+1])
print(max(a1, a2))

Submission status: Accepted

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

A.sort()
A = A[::-1]

if N % 2:
  a = sum(A[:(N - 1) // 2])
  b = sum(A[(N - 1) // 2:(N - 1) // 2 + 2])
  c = sum(A[(N - 1) // 2 + 2:])
  answer = a * 2 + b * (-1) + c * (-2)
  a = sum(A[:(N - 3) // 2])
  b = sum(A[(N - 3) // 2:(N - 3) // 2 + 2])
  c = sum(A[(N - 3) // 2 + 2:])
  answer = max(answer, a * 2 + b + c * (-2))
else:
  a = sum(A[:(N - 2) // 2])
  b = A[(N - 2) // 2:(N - 2) // 2 + 2]
  c = sum(A[(N - 2) // 2 + 2:])
  answer = a * 2 + b[0] - b[1] + c * (-2)
print(answer)

Submission status: Accepted

Solution code:
n=int(input())
a=[int(input())for _ in range(n)]
if n==2:print(abs(a[0]-a[1]));exit()
f=[-1]
for i in range(1,n-1-(n%2==0)):
  if i%2:f.append(2)
  else:f.append(-2)
if n%2:f+=[-1]
else:f+=[-2,1]
b=[]
c=[]
for i in f:
  b.append(i)
  c.append(-i)
b.sort()
c.sort()
sb=sc=0
a.sort()
for i in range(n):
  sb+=a[i]*b[i]
  sc+=a[i]*c[i]
print(max(sb,sc))

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n = inp()
a = inpln(n)
a.sort()
if n%2 == 0:
    res = 0
    for i in range(n//2-1):
        res -= a[i] * 2
        res += a[n-i-1] * 2
    res += a[n//2] - a[n//2-1]
    print(res)
else:
    res_1 = 0
    res_2 = 0
    l = a[:n//2]
    r = a[n//2:]
    res_1 = sum(r)*2 - (r[0] + r[1]) - sum(l)*2 
    
    l = a[:n//2+1]
    r = a[n//2+1:]
    res_2 = sum(r)*2 - sum(l)*2 + l[-1]+l[-2]
    print(max(res_1, res_2))

Submission status: Accepted

Solution code:
from collections import deque
from copy import copy
N = int(input())
A = deque(sorted([int(input()) for _ in range(N)]))
A2 = copy(A)
d = deque()
d.append(A.popleft())
while True:
    try:
        d.append(A.pop())
        d.appendleft(A.pop())
        d.append(A.popleft())
        d.appendleft(A.popleft())
    except IndexError:
        break
ans = 0
for i in range(N-1):
    ans += abs(d[i]-d[i+1])
A = A2
d = deque()
d.append(A.pop())
while True:
    try:
        d.append(A.popleft())
        d.appendleft(A.popleft())
        d.append(A.pop())
        d.appendleft(A.pop())
    except IndexError:
        break
n = 0
for i in range(N-1):
    n += abs(d[i]-d[i+1])
print(max(ans, n))

Submission status: Accepted

Solution code:
#N=5
#A=[ 32, 1, 87, 25, 36]
N=int(input())
A=[0]*N
for i in range(N):
    A[i]=int(input())

A=sorted(A)

mf=0
ms=0
sf=0
ss=0
d=0
c=0
n=0


ml=N-1
mr=N-1
sl=0
sr=1
n=1
while(True):
    if(n==N):break
    d+=(A[ml]-A[sl])
    ml=mr-1
    n+=1
    if(n==N):break
    d+=(A[mr]-A[sr])
    mr=ml-1
    n+=1
    if(n==N):break
    d+=(A[ml]-A[sl])
    sl=sr+1
    n+=1
    if(n==N):break
    d+=(A[mr]-A[sr])
    sr=sl+1
    n+=1

ml=N-1
mr=N-2
sl=0
sr=0
n=1
while(True):
    if(n==N):break
    c+=(A[ml]-A[sl])
    sl=sr+1
    n+=1
    if(n==N):break
    c+=(A[mr]-A[sr])
    sr=sl+1
    n+=1
    if(n==N):break
    c+=(A[ml]-A[sl])
    ml=mr-1
    n+=1
    if(n==N):break
    c+=(A[mr]-A[sr])
    mr=ml-1
    n+=1

print(max(d,c))

Submission status: Accepted

Solution code:
def examA():
    S = SI()
    if len(S)==3:
        ans = S[::-1]
    else:
        ans = S
    print(ans)
    return

def examB():
    A, B, K = LI()
    for i in range(K):
        if i%2==0:
            B +=A//2
            A //=2
        else:
            A +=B//2
            B //=2
    print(A,B)
    return

def examC():
    N = I()
    A = [I() for _ in range(N)]
    A.sort()
    A1 = A[:N//2]; A2 = A[N//2:]
    ans = 0; cur = 0
    for i in range(len(A2)):
        if i<len(A1):
            cur +=(A2[i]-A1[i])
        if i-1>=0:
            cur +=(A2[i]-A1[i-1])
    if N%2==1:
        cur += (A2[-1] - A2[1])
    ans = max(ans,cur)
#    print(A1,A2)
#    print(ans)
    if N%2==1:
        A1 = A[:1+(N//2)]; A2 = A[1+(N//2):]
        cur = 0
        for i in range(len(A1)):
            if i < len(A2):
                cur += (A2[i] - A1[i])
            if i - 1 >= 0:
                cur += (A2[i-1] - A1[i])
        cur +=(A1[-2]-A1[0])
        ans = max(ans, cur)
#    print(A1,A2)
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examC()

Submission status: Accepted

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

ans1 = 0
l = 0
r = N-1
for i in range(N-2):
    if i%2 == 0:
        ans1 += 2 * A[r]
        r -= 1
    else:
        ans1 += -2 * A[l]
        l += 1
if N%2 == 0:
    ans1 -= min(A[l], A[r])
    ans1 += max(A[l], A[r])
else:
    ans1 -= (A[l] + A[r])

ans2 = 0
l = 0
r = N-1
for i in range(N-2):
    if i%2 == 1:
        ans2 += 2 * A[r]
        r -= 1
    else:
        ans2 += -2 * A[l]
        l += 1
if N%2 == 0:
    ans2 -= min(A[l], A[r])
    ans2 += max(A[l], A[r])
else:
    ans2 += (A[l] + A[r])

print(max(ans1,ans2))

Submission status: Accepted

Solution code:
import sys
from collections import deque as dq
input = sys.stdin.readline
N = int(input())
a = []
for _ in range(N):
  a.append(int(input()))
sa = dq(sorted(a))
res = 0
x = [0] * N
x[0] = sa[N // 2]
for i in range(1, N):
  if i % 2 == 0:
    x[i] = sa.popleft()
  else:
    x[i] = sa.pop()

for i in range(N - 1): res += abs(x[i + 1] - x[i])
res2 = 0
sa = dq(sorted(a))
x = [0] * N
x[0] = sa[-N // 2]
for i in range(1, N):
  if i % 2:
    x[i] = sa.popleft()
  else:
    x[i] = sa.pop()
for i in range(N - 1): res2 += abs(x[i + 1] - x[i])
print(max(res, res2))

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
import sys
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
    
def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])

def warshall_floyd(): # 全点対最短路問題O(N^3)
    n,w = inpm() #n:頂点数　w:辺の数
    d = [[10**10 for i in range(n)] for i in range(n)] 
    #d[u][v] : 辺uvのコスト(存在しないときはinf)
    xyz=[]
    for i in range(w):
        x,y,z = inpm()
        x -= 1
        y -= 1
        xyz.append((x,y,z))
        d[x][y] = z
        d[y][x] = z
    for i in range(n):
        d[i][i] = 0 #自身のところに行くコストは0
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return n,w,d,xyz

def main():
    n=inp()
    a=inplm(n)
    a.sort()
    n1 = 0
    n2 = 0
    minus = n//2

    for i in range(n):
        if i<minus-1:
            n1-=2*a[i]
        elif i==minus-1:
            n1-=(1+n%2)*a[i]
        elif i==minus:
            n1+=a[i]
        elif i==minus+1 and n%2==1:
            n1+=a[i]
        else:
            n1+=2*a[i]

    a.reverse()
    plus = n//2
    for i in range(n):
        if i<plus-1:
            n2+=2*a[i]
        elif i==plus-1:
            n2+=(1+n%2)*a[i]
        elif i==plus:
            n2-=a[i]
        elif i==plus+1 and n%2==1:
            n2-=a[i]
        else:
            n2-=2*a[i]

    print(max(n1,n2))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
A = []
for _ in range(N):
    A.append(int(input()))
    
A.sort()
D = deque()
for i in range(N):
    if i%4==0:
        D.append(A[i//2])
    elif i%4==1:
        D.appendleft(A[-1-(i-1)//2])
    elif i%4==2:
        D.appendleft(A[i//2])
    else:
        D.append(A[-1-(i-1)//2])
ans1 = 0
for i in range(N-1):
    ans1 += abs(D[i+1]-D[i])

A.sort(reverse=True)
D = deque()
for i in range(N):
    if i%4==0:
        D.append(A[i//2])
    elif i%4==1:
        D.appendleft(A[-1-(i-1)//2])
    elif i%4==2:
        D.appendleft(A[i//2])
    else:
        D.append(A[-1-(i-1)//2])
ans2 = 0
for i in range(N-1):
    ans2 += abs(D[i+1]-D[i])
    
print(max(ans1,ans2))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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


A.sort()

def calc(A):
    ans = 0
    tmp1 = A[0]
    tmp2 = A[0]

    count = 1
    flag = True
    i = 1
    j = 1
    while True:
        if flag:
            if tmp1 > tmp2:
                tmp1, tmp2 = tmp2, tmp1
        else:
            if tmp1 < tmp2:
                tmp1, tmp2 = tmp2, tmp1


        if count == N:
            break
        if flag:
            ans += abs(tmp1 - A[-i])
            tmp1 = A[-i]
            i += 1
        else:
            ans += abs(tmp1 - A[j])
            tmp1 = A[j]
            j += 1

        count += 1

        if count == N:
            break
        if flag:
            ans += abs(tmp2 - A[-i])
            tmp2 = A[-i]
            i += 1
        else:
            ans += abs(tmp2 - A[j])
            tmp2 = A[j]
            j += 1
        
        count += 1

        flag = not flag
        # print ('A', ans)
    return ans

# print (i, j)
print (max(calc(A[::-1]), calc(A)))

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
a=[int(input())for _ in range(n)]
a.sort()
ans1=0
ans2=0
if n%2:
    for i in range(n):
        if i<n//2:
            ans1-=a[i]*2
        elif i<n//2+2:
            ans1+=a[i]
        else:
            ans1+=a[i]*2
    for i in range(n):
        if i<(n-2)//2:
            ans2-=a[i]*2
        elif i<(n-2)//2+2:
            ans2-=a[i]
        else:
            ans2+=a[i]*2
    print(max(ans1,ans2))

else:
    for i in range(n):
        if i<(n-2)//2:
            ans1-=a[i]*2
        elif i<(n-2)//2+1:
            ans1-=a[i]
        elif i<(n-2)//2+2:
            ans1+=a[i]
        else:
            ans1+=a[i]*2
    print(ans1)

Submission status: Accepted

Solution code:
import sys
from collections import deque
read = sys.stdin.read

N, *A = map(int, read().split())

A.sort()
A = deque(A)
a = deque()
side = True
a.append(A.popleft())

while A:
    if side:
        a.append(A.pop())
        if A:
            a.appendleft(A.pop())
        side = False
    else:
        a.append(A.popleft())
        if A:
            a.appendleft(A.popleft())
        side = True

if side:
    tmp = a.popleft()
else:
    tmp = a.pop()

if abs(tmp - a[0]) <= abs(tmp - a[-1]):
    a.append(tmp)
else:
    a.appendleft(tmp)

if not side:
    tmp = a.popleft()
else:
    tmp = a.pop()

if abs(tmp - a[0]) <= abs(tmp - a[-1]):
    a.append(tmp)
else:
    a.appendleft(tmp)

answer = 0
a = list(a)
for i, j in zip(a, a[1:]):
    answer += abs(i - j)

print(answer)

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
A = deque(sorted([int(input()) for _ in range(N)]))
B = deque([])
B.append(A.popleft())
cnt = 0
while A:
    a0 = A[0]
    a1 = A[-1]
    b0 = B[0]
    b1 = B[-1]
    c00 = abs(a0-b0)
    c01 = abs(a0-b1)
    c10 = abs(a1-b0)
    c11 = abs(a1-b1)
    cmax = max(c00,c01,c10,c11)
    if cmax == c00:
        B.appendleft(A.popleft())
    elif cmax == c01:
        B.append(A.popleft())
    elif cmax == c10:
        B.appendleft(A.pop())
    else:
        B.append(A.pop())
    cnt += cmax
print(cnt)

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
a = [int(input()) for _ in range(n)]
a.sort()
x = deque(a)
y = deque(a)


def align(a, fromLeft=1):
    if fromLeft:
        p = a.popleft()
    else:
        p = a.pop()
    q = p

    res = 0
    fromLeft = 1 - fromLeft
    while a:
        p1 = a.popleft() if fromLeft else a.pop()
        if a:
            q1 = a.popleft() if fromLeft else a.pop()
            res += abs(p - p1) + abs(q - q1)
            p = p1
            q = q1
        else:
            res += max(abs(p - p1), abs(q - p1))
        fromLeft = 1 - fromLeft
    return res


ans = max(align(x, 1), align(y, 0))
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


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

    import collections
    q = collections.deque(A)

    p = collections.deque()
    p.append(q.pop())
    ans = 0
    while q:
        q1, q2 = q[0], q[-1]
        p1, p2 = p[0], p[-1]
        a = abs(q1 - p1)
        b = abs(q1 - p2)
        c = abs(q2 - p1)
        d = abs(q2 - p2)
        ma = max(a, b, c, d)
        ans += ma
        if ma == a:
            p.appendleft(q.popleft())
        elif ma == b:
            p.append(q.popleft())
        elif ma == c:
            p.appendleft(q.pop())
        elif ma == d:
            p.append(q.pop())
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


# 解説ACのつもり。場合分けがバヤで完全に無理
def main():
    N = int(input())
    A = []
    for _ in range(N):
        A.append(int(input()))
    A.sort()
    ans = 0
    m = N//2
    if N % 2 == 0:
        for i in range(m - 1):
            ans -= 2 * A[i]
        for i in range(m + 1, N):
            ans += 2 * A[i]
        ans -= A[m-1]
        ans += A[m]
    else:
        for i in range(m - 1):
            ans -= 2 * A[i]
        for i in range(m + 2, N):
            ans += 2 * A[i]
        a1 = ans - 2*A[m-1] + A[m] + A[m+1]
        a2 = ans - A[m-1] - A[m] + 2*A[m+1]
        ans = max(a1, a2)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools

n=int(input())
a=list(int(input()) for i in range(n))
b=[]
a.sort()
ans=0

if n%2==1:
    x=2*sum(a[n//2+1:])-2*sum(a[:n//2+1])+sum(a[n//2-1:n//2+1])
    y=2*sum(a[n//2:])-sum(a[n//2:n//2+2])-2*sum(a[:n//2])
    print(max(x,y))

else:
    x=2*sum(a[n//2:])-(a[n//2]) -2*sum(a[:n//2])+a[n//2-1]
    print(x)

Submission status: Accepted

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

A.sort()

ret1 = 0
i, j = 1, len(A) - 1
e1, e2 = A[0], A[0]
mode = 0

while i <= j :
    if i == j :
        ret1 += max(abs(e1-A[i]), abs(e2-A[i]))
        i += 1
    else :
        if mode == 0 :
            ret1 += abs(e1-A[j]) + abs(e2-A[j-1])
            e1, e2 = A[j], A[j-1]
            j -= 2
        else :
            ret1 += abs(e1-A[i]) + abs(e2-A[i+1])
            e1, e2 = A[i], A[i+1]
            i += 2
            
        mode ^= 1
        
ret2 = 0
i, j = 0, len(A) - 2
e1, e2 = A[-1], A[-1]
mode = 1

while i <= j :
    if i == j :
        ret2 += max(abs(e1-A[i]), abs(e2-A[i]))
        i += 1
    else :
        if mode == 0 :
            ret2 += abs(e1-A[j]) + abs(e2-A[j-1])
            e1, e2 = A[j], A[j-1]
            j -= 2
        else :
            ret2 += abs(e1-A[i]) + abs(e2-A[i+1])
            e1, e2 = A[i], A[i+1]
            i += 2
            
        mode ^= 1
        
print(max(ret1, ret2))

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    b = IR(n)
    b.sort()
    a = deque(b)
    q = deque([a.pop()])
    n -= 1
    for i in range(n):
        if i&2:
            ai = a.pop()
        else:
            ai = a.popleft()
        x = q[0]
        y = q[-1]
        if i&1:
            q.append(ai)
        else:
            q.appendleft(ai)
    ans = 0
    for i in range(n):
        ans += abs(q[i+1]-q[i])
    a = deque(b)
    q = deque([a.popleft()])
    for i in range(n):
        if i&2:
            ai = a.popleft()
        else:
            ai = a.pop()
        if i&1:
            q.append(ai)
        else:
            q.appendleft(ai)
    ans2 = 0
    for i in range(n):
        ans2 += abs(q[i+1]-q[i])
    print(max(ans,ans2))
    return


#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    b = IR(n)
    b.sort()
    a = deque(b)
    q = deque([a.pop()])
    n -= 1
    for i in range(n):
        if i&1:
            ai = a.pop()
        else:
            ai = a.popleft()
        x = q[0]
        y = q[-1]
        if abs(x-ai) < abs(y-ai):
            q.append(ai)
        else:
            q.appendleft(ai)
    ans = 0
    for i in range(n):
        ans += abs(q[i+1]-q[i])
    a = deque(b)
    q = deque([a.popleft()])
    for i in range(n):
        if i&1:
            ai = a.popleft()
        else:
            ai = a.pop()
        x = q[0]
        y = q[-1]
        if abs(x-ai) < abs(y-ai):
            q.append(ai)
        else:
            q.appendleft(ai)
    ans2 = 0
    for i in range(n):
        ans2 += abs(q[i+1]-q[i])
    a = deque(b)
    q = deque([a.pop()])
    for i in range(n):
        if i&2:
            ai = a.pop()
        else:
            ai = a.popleft()
        x = q[0]
        y = q[-1]
        if abs(x-ai) < abs(y-ai):
            q.append(ai)
        else:
            q.appendleft(ai)
    ans3 = 0
    for i in range(n):
        ans3 += abs(q[i+1]-q[i])
    a = deque(b)
    q = deque([a.popleft()])
    for i in range(n):
        if i&2:
            ai = a.popleft()
        else:
            ai = a.pop()
        x = q[0]
        y = q[-1]
        if abs(x-ai) < abs(y-ai):
            q.append(ai)
        else:
            q.appendleft(ai)
    ans4 = 0
    for i in range(n):
        ans4 += abs(q[i+1]-q[i])
    print(max(ans,ans2,ans3,ans4))
    return


#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
A = [int(input()) for _ in range(N)]
A.sort()
if N % 2 == 0:
  up = [-1,1]
  down = [-1,1]
else:
  up = [-1,-1]
  down = [1,1]
for i in range(1,N-1):
  if i % 2 == 0:
    up.append(-2)
    down.append(2)
  else:
    up.append(2)
    down.append(-2)
up.sort()
down.sort()
up = np.array(up)
down = np.array(down)
print(max(np.sum(up * A),np.sum(down * A)))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, heapq, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
sys.setrecursionlimit(10**8)
inf = float('inf')
ans = 0
count = 0
n=int(input())
A=[int(input()) for i in range(n)]
A.sort()
if n%2==1:
    if A[n//2]-A[n//2-1]<=A[n//2+1]-A[n//2]:
        A.insert(0,A[n//2+1])
    else:
        A.append(A[n//2])
    n+=1
tmp=A[n//2]
for i in range(n//2):
    ans+=abs(tmp-A[i+n//2])
    tmp = A[i+n//2]
    # print(tmp)
    ans+=abs(tmp-A[i])
    tmp=A[i]
    # print(tmp)
print(ans)

# print(A)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):
    b = deque()
    A.sort()
    for i in range(N//2):
        if i % 2 == 0:
            b.appendleft(A[i])
            b.append(A[N-i-1])
        else:
            b.append(A[i])
            b.appendleft(A[N-i-1])
    if N % 2 !=  0:
        a = A[N//2]
        l = b[0]
        r = b[-1]
        if abs(a-l) > abs(a-r):
            b.appendleft(a)
        else:
            b.append(a)
    
    ans = 0
    for i in range(N-1):
        ans += abs(b[i]-b[i+1])
        
    return ans


def main():
    N = read_int()
    A = [read_int() for _ in range(N)]
    print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
a=[]
for i in range(n):
	a.append(int(input()))
a.sort()
ans1=ans2=0
p=q=a[n//2]
if n%2==0:
	for i in range(n//2-1):
		ans1+=abs(p-a[i])
		p=a[i]
		ans1+=abs(p-a[-i-1])
		p=a[-i-1]
	ans1+=abs(p-a[n//2-1])
	print(ans1)
else:
	for i in range(n//2):
		ans1+=abs(p-a[i])
		p=a[i]
		ans1+=abs(p-a[-i-1])
		p=a[-i-1]
		ans2+=abs(q-a[-i-1])
		q=a[-i-1]
		ans2+=abs(q-a[i])
		q=a[i]
	print(max(ans1,ans2))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N=int(input())
A=[int(input()) for i in range(N)]
from collections import deque
A.sort()
q=deque(A)
q2=deque()
q2.append(q.popleft())
k=N-1
while(k>0):
  if len(q)>0:
    q2.appendleft(q.pop())
    k-=1
  if len(q)>0:
    q2.append(q.pop())
    k-=1
  if len(q)>0:
    q2.appendleft(q.popleft())
    k-=1
  if len(q)>0:
    q2.append(q.popleft())
    k-=1
  if len(q)==0:
    break
prev=q2.popleft()
ans=0
for i in range(N-1):
  now=q2.popleft()
  ans+=abs(now-prev)
  prev=now

q=deque(A)
q2=deque()
q2.append(q.pop())
k=N-1
while(k>0):
  if len(q)>0:
    q2.appendleft(q.popleft())
    k-=1
  if len(q)>0:
    q2.append(q.popleft())
    k-=1
  if len(q)>0:
    q2.append(q.pop())
    k-=1
  if len(q)>0:
    q2.appendleft(q.pop())
    k-=1
  if len(q)==0:
    break
prev=q2.popleft()
tmp=0
for i in range(N-1):
  now=q2.popleft()
  tmp+=abs(now-prev)
  prev=now  
  
print(max(ans,tmp))

Submission status: Accepted

Solution code:
N=int(input())
A=sorted([int(input()) for i in range(N)])
#A=[i for i in range(50)]
#N=len(A)
value=0
B,C=A[0],A[0]
i=1
z=0

while N-1>z:

    if z%4==0:
        value+=A[-i]-B
        B=A[-i]
    if z%4==1:
        value+=A[-i-1]-C
        C=A[-i-1]
    if z%4==2:
        value+=B-A[i]
        B=A[i]
    if z%4==3:
        value+=C-A[i+1]
        C=A[i+1]
        i+=2
    #print(B,C,i,z)
    z+=1
value1=value
value=0
B,C=A[-1],A[-1]
i=0
z=0
while N-1>z:

    if z%4==0:
        value+=B-A[i]
        B=A[i]

    if z%4==1:
        value+=C-A[i+1]
        C=A[i+1]

    if z%4==2:
        value+=A[-i-2]-B
        B=A[-i-2]
    if z%4==3:
        value+=A[-i-3]-C
        C=A[-i-3]
        i+=2
    #print(B,C,i,z,value)
    z+=1
value2=value
print(max(value1,value2))

Submission status: Accepted

Solution code:
n=int(input())
l=[]
for i in range(n):
    l.append(int(input()))
l.sort()
if n%2==0:
    s=l[:n//2]
    b=l[n//2:]
    ans=0
    for i in range(n-1):
        if i%2==0:
            ans+=b[i//2]-s[i//2]
        else:
            ans+=b[(i+1)//2]-s[i//2]
    print(ans)
else:
    s=l[:n//2]
    b=l[n//2+1:]+[l[n//2]]
    ans1=0
    for i in range(n-1):
        if i%2==0:
            ans1+=b[i//2]-s[i//2]
        else:
            ans1+=b[(i+1)//2]-s[i//2]
    t=[l[(n//2)]]+l[:n//2]
    c=l[n//2+1:]
    ans2=0
    for i in range(n-1):
        if i%2==0:
            ans2+=c[i//2]-t[i//2]
        else:
            ans2+=c[i//2]-t[(i+1)//2]
    print(max(ans1,ans2))

Submission status: Accepted

Solution code:
n = int(input())
a_ls = []
for i in range(n):
    a_ls.append(int(input()))
a_ls.sort()
flg = n % 2 == 1
if flg:
    first = a_ls[:n//2]
    center = a_ls[n//2]
    second = a_ls[n//2 + 1:] + [center]
    best = 0
    for ind in range(n//2):
        best += abs(second[ind] - first[ind]) + abs(second[ind + 1] - first[ind])
    center = a_ls[n // 2]
    first = [center] + a_ls[:n // 2]
    second = a_ls[n // 2 + 1:]
    score = 0
    for ind in range(n // 2):
        score += abs(second[ind] - first[ind]) + abs(second[ind] - first[ind+1])
    if best < score:
        best = score
else:
    first = a_ls[:n // 2]
    second = a_ls[n // 2:]
    best = 0
    for ind, (i, j) in enumerate(zip(first, second)):
        if ind > 0:
            best += abs(j - last_i)
        best += abs(j - i)
        last_i = i
print(best)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(input()) for _ in range(N)]
A.sort()
ans = 0
if N % 2 == 0:
  l = A[:N//2]
  h = A[N//2:]
  for i,j in zip(l, h):
    ans += (j - i) * 2 
  ans = ans - h[0] + l[-1]
else:
  l = A[:N//2]
  h = A[N//2+1:]
  m = A[N//2]
  for i,j in zip(l, h):
    ans += (j - i) * 2 
  ans = max(ans - h[0] + m, ans + l[-1] - m)
print(ans)

Submission status: Accepted

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



def f(A):
    l = r = A.pop(0)

    ans = 0

    for i in range(len(A)//2):
        if i % 2 == 0:
            ans += abs(l - A[-1]); l = A.pop(-1);
            ans += abs(r - A[-1]); r = A.pop(-1);
        else:
            ans += abs(l - A[0]); l = A.pop(0);
            ans += abs(r - A[0]); r = A.pop(0);
    if (A):
        ans += abs(l - A[0])

    return ans


print(max(f(a), f(b)))

Submission status: Accepted

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

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

A = sorted(A)

B = [0] * N
m = int(N/2)
B[m] = A[0]

si = 1
bi = 0
ci = 1

for i in range(1, N):
    si *= -1
    ii = int(i/2 + 0.5)

    if i % 4 == 1 or i % 4 == 2:
        B[m+si*ii] = A[N-bi-1]
        bi += 1
    if i % 4 == 3 or i % 4 == 0:
        B[m+si*ii] = A[ci]
        ci += 1

C = [0] * N
m = int(N/2)
C[m] = A[N-1]

si = 1
bi = 1
ci = 0

for i in range(1, N):
    si *= -1
    ii = int(i/2 + 0.5)

    if i % 4 == 1 or i % 4 == 2:
        C[m+si*ii] = A[ci]
        ci += 1
    if i % 4 == 3 or i % 4 == 0:
        C[m+si*ii] = A[N-bi-1]
        bi += 1

cntB = 0
cntC = 0
for i in range(N-1):
    cntB += abs(B[i] - B[i+1])
    cntC += abs(C[i] - C[i+1])


print(max(cntB, cntC))

Submission status: Accepted

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

A.sort()

k1=[]
if N%2==1:
    k1.extend([1,1])
    k1.extend([-2]*(N//2))
    k1.extend([2]*(N-N//2-2))
    k1.sort()
    sum1=0
    sum2=0
    for i in range(N):
        sum1+=A[i]*k1[i]
        sum2+=(-1)*A[i]*k1[-1-i]
    print(max(sum1,sum2))
else:
    k1.extend([-1,1])
    k1.extend([-2]*((N-2)//2))
    k1.extend([2]*((N-2)//2))
    k1.sort()
    sum1=0
    sum2=0
    for i in range(N):
        sum1+=A[i]*k1[i]
        sum2+=(-1)*A[i]*k1[-1-i]
    print(max(sum1,sum2))