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:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import fractions
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import Counter
from collections import deque
import pprint

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""
def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# a^n
def power(a,n,mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod

# n*(n-1)*...*(l+1)*l
def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n-1
    while(tmp >= l):
        a = a*tmp%mod
        tmp -= 1
    return a

inf = 10**18
mod = 10**9+7

n = ir()
a = [ir() for i in range(n)]
a.sort()
ans = [0,0]

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

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

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

    for i in range(n//2-1):
        ans[1]-=2*a[i]
    ans[1]-=a[n//2-1]
    ans[1]-=a[n//2]
    for i in range(n//2+1,n):
        ans[1]+=2*a[i]
print(max(ans))

Submission status: Accepted

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

m = n//2
a1 = a[:m]
a2 = a[:m-1:-1]
if n%2==1:a1.append(a[m])

from collections import deque
l = deque([])

for i in range(m):
    if i%2==0:
        l.append(a1[i])
        l.appendleft(a2[i])
    else:
        l.append(a2[i])
        l.appendleft(a1[i])

if n%2==1:
    if abs(l[0]-a1[-1])>abs(l[-1]-a1[-1]):
        l.appendleft(a1[-1])
    else:
        l.append(a1[-1])

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

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

if N == 2:
    print(abs(A_list[0] - A_list[1]))
    exit()

if N == 3:
    a0,a1,a2 = A_list
    print(max(abs(a0-a1) + abs(a1-a2),abs(a1-a2) + abs(a2-a0) ,abs(a0-a2) + abs(a0-a1)))
    exit()
    
q = deque(A_list)
res_q = deque([q.popleft(), q.pop()])
l = res_q[0]
r = res_q[-1]

v1 = v2 =0

v1 = q.popleft()
v2 = q.pop()
res = abs(l-r)
for _ in range(2,N-2):
    diff_l1 = abs(l-v1)
    diff_l2 = abs(l-v2)
    diff_r1 = abs(r-v1)
    diff_r2 = abs(r-v2)
    max_diff = max(diff_l1,diff_l2, diff_r1, diff_r2)
    
    res += max_diff
    if diff_l1 == max_diff:
        l = v1
        v1 = q.popleft()
    elif diff_l2 == max_diff:
        l = v2
        v2 = q.pop()
    elif diff_r1 == max_diff:
        r = v1
        v1 = q.popleft()
    else:
        r = v2
        v2 = q.pop()

# あまった2つの処理
diff_list = [abs(l-v1) + abs(v1-v2),
            abs(l-v1) + abs(r-v2),
            abs(l-v2) + abs(v1-v2),
            abs(l-v2) + abs(r-v1),
            abs(r-v1) + abs(l-v2),
            abs(r-v1) + abs(v1-v2),
            abs(r-v2) + abs(l-v1),
            abs(r-v2) + abs(v1-v2)]
res += max(diff_list)

print(res)

Submission status: Accepted

Solution code:
n = int(input())
a = [int(input()) for i in range(n)]
a.sort()
if n % 2 == 0:
    lower = a[:n//2]
    upper = a[n//2:]
    x = 2 * sum(upper) - upper[0]
    y = 2 * sum(lower) - lower[-1]
    ans = x - y
else:
    lower = a[:n//2]
    upper = a[n//2+1:]
    mid = a[n//2]
    x = 2 * sum(upper) - 2 * sum(lower) - mid + lower[-1]
    y = 2 * sum(upper) - 2 * sum(lower) + mid - upper[0]
    ans = max(x, y)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
arr = [int(input()) for x in range(n)]

arr.sort()

med = n // 2

# 偶奇で場合分け
if n % 2 == 0:
    ans = 2 * sum(arr[med + 1:]) - 2 * sum(arr[:med - 1]) + arr[med] - arr[med - 1]
# 初項と末項の組み合わせ方で場合分け
else:
    ans1 = 2 * sum(arr[med + 1:]) - 2 * sum(arr[:med - 1]) - arr[med - 1] - arr[med]
    ans2 = 2 * sum(arr[med + 2:]) - 2 * sum(arr[:med]) + arr[med + 1] + arr[med]
    ans = max(ans1, ans2)

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

n=int(input())
a = []

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

a.sort()

a=deque(a)

mid = a[(n-1)//2]
midi = abs(a[(n-1)//2-1] - mid)
mida = abs(a[(n-1)//2+1] - mid)

rev = False
omi = a[0]
oma = a[-1]

ans = abs(oma - omi)
for i in range(len(a)//2):
    mi = a.popleft()
    ma = a.pop()

    if rev:
        q = mi
        mi = ma
        ma = q

    ans+=abs(mi - omi)+abs(ma - oma)

    omi = mi
    oma = ma
    rev = not rev

if len(a)==1:
    ans+=max(midi,mida)

print(ans)

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    from collections import deque
    
    N=I()
    A2=[0]*N
    for i in range(N):
        A2[i]=I()
        
    A2.sort(reverse=True)
    
    A=deque()
    B=deque()
    for i in range(N):
        A.append(A2[i])
        B.appendleft(A2[i])
    
    
    ans=0
    L=[0]*(2*N+1)
    L[N]=A.pop()
    l=N-1
    r=N+1
    
    for i in range(N-1):
        if i%4==0:
            a=A.popleft()
            L[l]=a
            ans+=abs(L[l]-L[l+1])
            l-=1
        elif i%4==1:
            a=A.popleft()
            L[r]=a
            ans+=abs(L[r]-L[r-1])
            r+=1
        elif i%4==2:
            a=A.pop()
            L[l]=a
            ans+=abs(L[l]-L[l+1])
            l-=1
        else:
            a=A.pop()
            L[r]=a
            ans+=abs(L[r]-L[r-1])
            r+=1
            
    ###
    ans2=0
    L=[0]*(2*N+1)
    L[N]=B.pop()
    l=N-1
    r=N+1
    
    for i in range(N-1):
        if i%4==0:
            a=B.popleft()
            L[l]=a
            ans2+=abs(L[l]-L[l+1])
            l-=1
        elif i%4==1:
            a=B.popleft()
            L[r]=a
            ans2+=abs(L[r]-L[r-1])
            r+=1
        elif i%4==2:
            a=B.pop()
            L[l]=a
            ans2+=abs(L[l]-L[l+1])
            l-=1
        else:
            a=B.pop()
            L[r]=a
            ans2+=abs(L[r]-L[r-1])
            r+=1
    ###        
    
    print(max(ans,ans2))
            
            
            
        
    
    
    

main()

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import permutations
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

N = getN()
A = sorted(getArray(N))
A = deque(A)
ans_list = deque([])

cnt = 0
for i in range(N // 2):

    m = A.popleft()
    if cnt % 2 == 0:
        ans_list.append(m)
    else:
        ans_list.appendleft(m)

    m = A.pop()
    if cnt % 2 == 0:
        ans_list.appendleft(m)
    else:
        ans_list.append(m)
    cnt += 1

if N % 2 == 1:
    m = A.pop()
    opt1 = abs(ans_list[0] - m)
    opt2 = abs(ans_list[-1] - m)

    if opt1 >= opt2:
        ans_list.appendleft(m)
    else:
        ans_list.append(m)

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
a=[]
for i in range(n):
    a.append(int(input()))
a=sorted(a)
from collections import deque

if n%2==0:
    front=a[:n//2]
    rear=a[n//2:]
    f1=deque(front)
    f2=deque(front)
    r1=deque(rear)
    r2=deque(rear)
    ans1=0
    ans2=0
    for i in range(n):
        #print(f1,f2,r1,r2)
        if i==0:
            last1=f1.pop()
            last2=r2.popleft()
        elif i%2==1:
            now1=r1.pop()
            now2=f2.popleft()
            ans1+=abs(last1-now1)
            ans2+=abs(last2-now2)
            last1=now1
            last2=now2
        elif i%2==0:
            now1=f1.popleft()
            now2=r2.pop()
            ans1+=abs(last1-now1)
            ans2+=abs(last2-now2)
            last1=now1
            last2=now2
    print(max(ans1,ans2))
else:
    med=a[n//2]
    front=a[:n//2]
    rear=a[n//2+1:]
    f1=deque(front)
    f2=deque(front)
    r1=deque(rear)
    r2=deque(rear)
    ans1=0
    ans2=0
    for i in range(n):
        #print(f1,f2,r1,r2)
        if i==0:
            last1=med
            last2=med
        elif i%2==1:
            now1=r1.pop()
            now2=f2.popleft()
            ans1+=abs(last1-now1)
            ans2+=abs(last2-now2)
            last1=now1
            last2=now2
        elif i%2==0:
            now1=f1.popleft()
            now2=r2.pop()
            ans1+=abs(last1-now1)
            ans2+=abs(last2-now2)
            last1=now1
            last2=now2
    print(max(ans1,ans2))

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
A = []
for _ in range(n):
    A.append(int(input()))
if n == 2:
    print(abs(A[1]-A[0]))
    exit()
A.sort()
s = sum(A)
if n % 2 == 1:
    small = 0
    for i in range(n//2):
        small += A[i]
    big = s - small
    ans1 = 2*big-2*small-A[n//2]-A[n//2+1]
    small += A[n//2]
    big = s-small
    ans2 = 2*big -2*small+A[n//2]+A[n//2-1]
    print(max(ans1,ans2))
else:
    small = 0
    for i in range(n//2):
        small += A[i]
    big = s -small
    ans1 = 2*big -2*small + A[n//2-1]-A[n//2]
    small += A[n//2]
    big = s -small
    ans2 = 2*big-2*small+A[n//2]-A[n//2+1]
    print(max(ans1,ans2))

Submission status: Accepted

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

A.sort()

arr = []
arr.append(A[0])
arr.append(A[-1])
Atop = 1
Abtm = len(A) - 2
ans = arr[-1]-arr[0]
for i in range(len(A)-2):
    (Ai, ai) = (Atop, 0)
    if abs(A[Atop]-arr[-1]) > abs(A[Ai]-arr[ai]):
        (Ai, ai) = (Atop, -1)
    if abs(A[Abtm]-arr[0]) > abs(A[Ai]-arr[ai]):
        (Ai, ai) = (Abtm, 0)
    if abs(A[Abtm]-arr[-1]) > abs(A[Ai]-arr[ai]):
        (Ai, ai) = (Abtm, -1)

    #print('A[Ai]: ', A[Ai])
    #print(arr)
    ans += abs(A[Ai]-arr[ai])
    if ai == -1:
        arr[-1] = A[Ai]
    else:
        arr[0] = A[Ai]

    if Ai == Atop:
        Atop += 1
    else:
        Abtm -= 1


print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N = int(input())
    A = [0] * N
    for n in range(N):
        A[n] = int(input())
    
    A.sort()
    ans1 = sum([-2*a for a in A[:N//2+N%2]]) + sum([2*a for a in A[N//2+N%2:]])
    if N % 2:
        ans1 += A[N//2-1]
        ans1 += A[N//2]
    else:
        ans1 += A[N//2-1]
        ans1 -= A[N//2]

    ans2 = sum([-2*a for a in A[:N//2]]) + sum([2*a for a in A[N//2:]])
    if N % 2:
        ans2 -= A[N//2]
        ans2 -= A[N//2+1]
    else:
        ans2 -= A[N//2]
        ans2 += A[N//2-1]

    print(max(ans1, ans2))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
import copy
N = int(input())
A = deque(sorted([int(input()) for i in range(N)]))
B = copy.copy(A)
ans = deque([A.popleft()])
while A:
    if A:
        ans.appendleft(A.pop())
    if A:
        ans.append(A.pop())
    if A:
        ans.appendleft(A.popleft())
    if A:
        ans.append(A.popleft())
res_1 = 0
ans = list(ans)
for i in range(N - 1):
    res_1 += abs(ans[i] - ans[i + 1])
ans = deque([B.pop()])
while B:
    if B:
        ans.appendleft(B.popleft())
    if B:
        ans.append(B.popleft())
    if B:
        ans.appendleft(B.pop())
    if B:
        ans.append(B.pop())
res_2 = 0
ans = list(ans)
for i in range(N - 1):
    res_2 += abs(ans[i] - ans[i + 1])
print(max(res_1, res_2))

Submission status: Accepted

Solution code:
N = int(input())
# n, a, b = [int(i) for i in input().split()]
r = []
for i in range(N):
    A = int(input())
    r.append(A)

r_asc = sorted(r)
r_desc = sorted(r, reverse=True)
row = []
row2 = []

for i in range(N):
    if i % 2 == 0:
        row.append(r_asc[i//2])
        row2.append(r_desc[i//2])
    else:
        row.append(r_desc[i//2])
        row2.append(r_asc[i//2])
row3 = [row[-1]] + row[:-1]
row4 = [row2[-1]] + row2[:-1]
row_diff = [abs(row[i] - row[i-1]) for i in range(1, N)]
row2_diff = [abs(row2[i] - row2[i-1]) for i in range(1, N)]
row3_diff = [abs(row3[i] - row3[i-1]) for i in range(1, N)]
row4_diff = [abs(row4[i] - row4[i-1]) for i in range(1, N)]
print(max(sum(row_diff), sum(row2_diff), sum(row3_diff), sum(row4_diff)))

Submission status: Accepted

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


n = int(input())
L = [int(input()) for _ in range(n)]
L.sort()
n_2 =n // 2

ans = 0
if n % 2 == 1:
    ans = 2*sum(L[n_2+1:])-2*sum(L[:n_2-1])-L[n_2-1]-L[n_2]
    ans_2 = 2*sum(L[n_2+2:])-2*sum(L[:n_2])+L[n_2+1]+L[n_2]
    ans = max(ans,ans_2)
else:
    ans = 2*sum(L[n_2+1:])-2*sum(L[:n_2-1])+L[n_2]-L[n_2-1]
    

print(ans)

Submission status: Accepted

Solution code:
N = int(input())

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

rlt = 0

if len(As) % 2 == 1:
  tmp1 = 0
  tmp2 = 0
  b = len(As)//2
  for i in As[:b]:
    tmp1 -= 2*i
  for i in As[b:]:
    tmp1 += 2*i
  tmp1 -= As[b]
  tmp1 -= As[b+1]
  
  for i in As[:b+1]:
    tmp2 -= 2*i
  for i in As[b+1:]:
    tmp2 += 2*i
  tmp2 += As[b]
  tmp2 += As[b-1]
  if tmp1 > tmp2:
    rlt = tmp1
  else:
    rlt = tmp2

else:
  b = len(As)//2
  for i in As[:b]:
    rlt -= 2*i
  for i in As[b:]:
    rlt += 2*i
  rlt += As[b-1]
  rlt -= As[b]
  
print(rlt)

Submission status: Accepted

Solution code:
n=int(input())
l=sorted([int(input())for i in range(n)],reverse=1)
if n%2:
    print(max(2*sum(l[:n//2-1])+l[n//2-1]+l[n//2]-2*sum(l[n//2+1:]),2*sum(l[:n//2])-sum(l[n//2:n//2+2])-2*sum(l[n//2+2:])))
else:
    o=-1
    print(2*sum(l[:n//2-1])+l[n//2+o]-l[n//2+1+o]-2*sum(l[o+n//2+2:]))

Submission status: Accepted

Solution code:
n=int(input())

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

A.sort(reverse=True)

s=0
if n%2==0:#P1-2P2+...+2Pn-1-Pn
    s=2*sum(A[0:(n//2-1)])+A[n//2-1]-A[n//2]-2*sum(A[n//2+1:n])
else:#P1-2P2+...-2Pn-1+Pn
    s1=2*sum(A[0:n//2-1])+A[n//2-1]+A[n//2]-2*sum(A[n//2+1:n])
    s2=2*sum(A[0:n//2])-A[n//2]-A[n//2+1]-2*sum(A[n//2+2:n])
    s=max(s1,s2)

print(s)

Submission status: Accepted

Solution code:
import sys

def input(): return sys.stdin.readline().strip()
def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    N = Z()
    A = sorted([Z() for _ in range(N)])
    used = [0] * (N)
    output1 = output2 = 0

    i1 = i2 = 0
    j1, j2 = N-1, N-2
    f1 = f2 = True
    used[i1], used[i2], used[j1], used[j2] = 1, 1, 1, 1

    while f1 or f2:
        if f1: output1 += (A[j1]-A[i1])
        if f2: output1 += (A[j2]-A[i2])

        while used[i1]:
            if i1 == N-1:
                f1 = False
                break
            i1 += 1
        used[i1] = 1

        while used[i2]:
            if i2 == N-1:
                f2 = False
                break
            i2 += 1
        used[i2] = 1

        if f1: output1 += (A[j1]-A[i1])
        if f2: output1 += (A[j2]-A[i2])

        while used[j1]:
            if j1 == 0:
                f1 = False
                break
            j1 -= 1
        used[j1] = 1
        while used[j2]:
            if j2 == 0:
                f2 = False
                break
            j2 -= 1
        used[j2] = 1

    i1, i2 = 0, 1
    j1 = j2 = N-1
    f1 = f2 = True
    used = [0] * (N)
    used[i1], used[i2], used[j1], used[j2] = 1, 1, 1, 1

    while f1 or f2:
        if f1: output2 += (A[j1]-A[i1])
        if f2: output2 += (A[j2]-A[i2])

        while used[j1]:
            if j1 == 0:
                f1 = False
                break
            j1 -= 1
        used[j1] = 1
        while used[j2]:
            if j2 == 0:
                f2 = False
                break
            j2 -= 1
        used[j2] = 1

        if f1: output2 += (A[j1]-A[i1])
        if f2: output2 += (A[j2]-A[i2])

        while used[i1]:
            if i1 == N-1:
                f1 = False
                break
            i1 += 1
        used[i1] = 1

        while used[i2]:
            if i2 == N-1:
                f2 = False
                break
            i2 += 1
        used[i2] = 1


    print(max(output1, output2))

    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def point(arr):
    res=0
    for i in range(1,N):
        res+=abs(arr[i]-arr[i-1])
    return res
def merge(li_1,li_2):
    arr=[]
    for i in range(N):
        if not i%2:
            arr.append(li_2[i//2])
        else:
            arr.append(li_1[i//2])
    return arr

N=int(input())
A=[int(input()) for i in range(N)]
A.sort()
if not N%2:
    ans=0
    l,r=A[:N//2],A[N//2:]
    print(point(merge(l,r)))
else:
    ans=-1
    li=[]
    l,r=A[:N//2],A[N//2:]
    r[1],r[-1]=r[-1],r[1]
    ans=max(ans,point(merge(l,r)))
    li=[]
    l,r=A[:N//2+1],A[N//2+1:]
    l[0],l[-2]=l[-2],l[0]
    ans=max(ans,point(merge(r,l)))
    print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

a.sort()
def calc(m):
    if m == 1:
        dqa = deque(a[1:])
        dq = deque([a[0]])
        cnt = 0
    else: 
        dqa = deque(a[:N-1])
        dq = deque([a[-1]])
        cnt = 2

    while len(dq) < N:
        if cnt == 0:
            q = dqa.pop()
            dq.append(q)
        elif cnt == 1:
            q = dqa.pop()
            dq.appendleft(q)
        elif cnt == 2:
            q = dqa.popleft()
            dq.append(q)
        else:
            q = dqa.popleft()
            dq.appendleft(q)
            cnt = -1
        cnt += 1

    ans = 0
    for i in range(1, N):
        ans += abs(dq[i] - dq[i-1])
    return ans
        
print(max(calc(0), calc(1)))

Submission status: Accepted

Solution code:
N=int(input())
a = [int(input()) for _ in range(N)]
b = [0]*N

if N%2==1:
  #最大値を中央に置くケース
  a.sort()
  m = N//2
  L,R = m,m
  b[m]=a[-1]
  for i in range(m):
    L -= 1
    R += 1
    if i%2==0:
      b[L]=a[i]
      b[R]=a[i+1]
    else:
      b[L]=a[-2-(i-1)]
      b[R]=a[-3-(i-1)]
  ans1=0
  for i in range(1,N):
    ans1 += abs(b[i]-b[i-1])
  #print(b)
  
  #最小値を中央に置くケース
  a.sort()
  m = N//2
  L,R = m,m
  b[m]=a[0]
  for i in range(m):
    L -= 1
    R += 1
    if i%2==0:
      b[L]=a[-1-i]
      b[R]=a[-2-i]
    else:
      b[L]=a[(i-1)+1]
      b[R]=a[(i-1)+2]
  ans2=0
  for i in range(1,N):
    ans2 += abs(b[i]-b[i-1])
  ans=max(ans1,ans2)
  #print(b)
  print(ans)

else:
  a.sort()
  m = N//2
  L,R = m-1,m
  b[L]=a[0]
  b[R]=a[-1]
  
  for i in range(m-1):
    L -= 1
    R += 1
    if i%2==0:
      b[L]=a[-2-i]
      b[R]=a[i+1]
    else:
      b[L]=a[i+1]
      b[R]=a[-2-i]
  ans=0
  for i in range(1,N):
    ans += abs(b[i]-b[i-1])
  #print(b)
  print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
a=[0]*n
for i in range(n):
    a[i]=int(input())
a.sort()
k=n//2
if n%2==1:
    ans_1 = 2*sum(a[k+1:]) - 2*sum(a[:k+1]) + a[k-1]+a[k]
    ans_2 = 2*sum(a[k:])   - 2*sum(a[:k])   -(a[k]+a[k+1])
    print(max(ans_1,ans_2))
else:
    ans = 2*sum(a[k:])   - 2*sum(a[:k]) -a[k]+a[k-1]
    print(ans)

Submission status: Accepted

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

if n % 2 == 0:
    res = 0
    for i in range(n // 2 - 1):
        res += a[i] * 2
    res += a[n // 2 - 1]
    res -= a[n // 2]
    for i in range(n // 2 + 1, n):
        res -= a[i] * 2
    print(res)
else:
    res1 = 0
    for i in range(n // 2 - 1):
        res1 += a[i] * 2
    res1 += a[n // 2 - 1] + a[n // 2]
    for i in range(n // 2 + 1, n):
        res1 -= a[i] * 2

    res2 = 0
    for i in range(n // 2):
        res2 += a[i] * 2
    res2 -= a[n // 2] + a[n // 2 + 1]
    for i in range(n // 2 + 2, n):
        res2 -= a[i] * 2
    print(max(res1, res2))

Submission status: Accepted

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

if n % 2 == 0:
    res = 0
    for i in range(n//2-1):
        res += a[i] * 2
    res += a[n//2-1]
    res -= a[n//2]
    for i in range(n//2+1, n):
        res -= a[i] * 2
    print(res)
else:
    res1 = 0
    for i in range(n//2-1):
        res1 += a[i] * 2
    res1 += a[n//2-1] + a[n//2]
    for i in range(n//2+1, n):
        res1 -= a[i] * 2
    
    res2 = 0
    for i in range(n//2):
        res2 += a[i] * 2
    res2 -= a[n//2] + a[n//2+1]
    for i in range(n//2+2, n):
        res2 -= a[i] * 2
    print(max(res1, res2))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
import heapq
import decimal
# import statistics
import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n = ni()
    a = [ni() for _ in range(n)]

    a.sort()

    ans1 = []
    ans2 = []
    if not n % 2:
        small = a[:n // 2]
        large = a[n // 2:]
        for i in range(n // 2):
            ans2.append(large[i])
            ans2.append(small[i])

        tmp_ans = 0
        for i in range(1, n):
            tmp_ans += abs(ans2[i - 1] - ans2[i])

        print(tmp_ans)

    else:
        small1 = a[:n // 2 + 1]
        large1 = a[n // 2 + 1:]
        small1.insert(0, small1[-1])
        del small1[-1]
        for i in range(n // 2):
            ans1.append(small1[i])
            ans1.append(large1[i])
        ans1.append(small1[n // 2])

        small2 = a[:n // 2]
        large2 = a[n // 2:]
        large2.append(large2[0])
        del large2[0]
        for i in range(n // 2):
            ans2.append(large2[i])
            ans2.append(small2[i])
        ans2.append(large2[n // 2])

        tmp_ans1 = 0
        tmp_ans2 = 0
        for i in range(1, n):
            tmp_ans1 += abs(ans1[i - 1] - ans1[i])
            tmp_ans2 += abs(ans2[i - 1] - ans2[i])

        print(max(tmp_ans1, tmp_ans2))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def tenka18beg_c():
    # https://atcoder.jp/contests/tenka1-2018-beginner/submissions/6799465
    inp = list(map(int, read().split()))
    N = inp[0]
    A = inp[1:]
    A.sort()

    if N % 2 == 0:
        lower = A[:N//2]
        upper = A[N//2:]
        ans = (2 * sum(upper) - upper[0]) - (2 * sum(lower) - lower[-1])
    else:
        lower = A[:N//2]
        upper = A[N//2 + 1:]
        mid = A[N//2]
        x = 2 * sum(upper) - 2 * sum(lower) - mid + lower[-1]  # 中央が +2* -1* -1* のパターン
        y = 2 * sum(upper) - 2 * sum(lower) + mid - upper[0]  # 中央が +1* +1* -2* のパターン
        ans = max(x, y)
    print(ans)

tenka18beg_c()

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/tenka1-2018-beginner/submissions/6799465
def tenka18beg_c():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    A.sort()

    if N % 2 == 0:
        lower = A[:N//2]
        upper = A[N//2:]
        ans = (2 * sum(upper) - upper[0]) - (2 * sum(lower) - lower[-1])
    else:
        lower = A[:N//2]
        upper = A[N//2 + 1:]
        mid = A[N//2]
        x = 2 * sum(upper) - 2 * sum(lower) - mid + lower[-1]  # 中央が +2* -1* -1* のパターン
        y = 2 * sum(upper) - 2 * sum(lower) + mid - upper[0]  # 中央が +1* +1* -2* のパターン
        ans = max(x, y)
    print(ans)

tenka18beg_c()

Submission status: Accepted

Solution code:
def tenka18beg_c():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    A_desc = sorted(A, reverse=True)

    if N % 2 == 1:
        tot1, tot2 = 0, 0
        for i, a in enumerate(A_desc):
            if i < N//2 - 1:
                tot1 += 2*a
                tot2 += 2*a
            elif i == N//2 - 1:
                tot1 += a
                tot2 += 2*a
            elif i == N//2:
                tot1 += a
                tot2 -= a
            elif i == N//2 + 1:
                tot1 -= 2*a
                tot2 -= a
            elif N//2 + 1 < i:
                tot1 -= 2*a
                tot2 -= 2*a
        ans = max(tot1, tot2)
    else:
        tot = 0
        for i, a in enumerate(A_desc):
            if i < N//2 - 1:
                tot += 2*a
            elif i == N//2 - 1:
                tot += a
            elif i == N//2:
                tot -= a
            elif N//2 < i:
                tot -= 2*a
        ans = tot
    print(ans)

tenka18beg_c()

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/tenka1-2018-beginner/tasks/tenka1_2018_c
from collections import deque
n = int(input())
nums = []
for _ in range(n):
    nums.append(int(input()))
nums.sort()
ans = 0
l = 0
r = n - 1
q = deque()
while l <= r:
    left = nums[l]
    right = nums[r]
    if not q:
        ans += abs(right - left)
        q.append(left)
        q.append(right)
        l += 1
        r -= 1
    else:
        s = max(abs(q[-1] - right), abs(q[0] - right))
        t = max(abs(q[-1] - left), abs(q[0] - left))
        if s >= t:
            if abs(q[-1] - right) > abs(q[0] - right):
                ans += abs(q[-1] - right)
                q.append(right)
            else:
                ans += abs(q[0] - right)
                q.appendleft(right)
            r -= 1
        else:
            if abs(q[-1] - left) > abs(q[0] - left):
                ans += abs(q[-1] - left)
                q.append(left)
            else:
                ans += abs(q[0] - left)
                q.appendleft(left)
            l += 1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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


print(ans)

Submission status: Accepted

Solution code:
import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))
## libs ##
from collections import deque
#======================================================#
def main():
    n = II()
    aa = [II() for _ in range(n)]
    aa.sort()
    maxv = 0
    if n%2==0:
        sumv = 0
        l = aa[:n//2]
        r = aa[n//2:]
        sumv += sum(2*ri for ri in r)
        sumv -= r[0]
        sumv -= sum(2*li for li in l)
        sumv += l[-1]
        maxv = max(maxv, sumv)
    else:
        sumv = 0
        l = aa[:n//2]
        r = aa[n//2:]
        sumv += sum(2*ri for ri in r)
        sumv -= r[0]+r[1]
        sumv -= sum(2*li for li in l)
        maxv = max(maxv, sumv)

        sumv = 0
        l = aa[:n//2+1]
        r = aa[n//2+1:]
        sumv += sum(2*ri for ri in r)
        sumv -= sum(2*li for li in l)
        sumv += l[-1]+l[-2]
        maxv = max(maxv, sumv)
    print(maxv)

if __name__ == '__main__':
    main()