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:
#!/usr/bin/env python3
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right

def main():
    N, *A = map(int, open(0))
    A.sort()
    ans = 0
    if N % 2 == 1:
        ans += sum(A[N//2:])*2 - sum(A[:N//2])*2
        ans -= A[N//2]+A[N//2+1]
    else:
        ans += sum(A[N//2:])*2 - sum(A[:N//2])*2
        ans -= A[N//2]-A[N//2-1]
    

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

    print(max(ans,ans2))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n, *A = map(int, open(0).read().split())
a=sorted(A)
if n%2:
    print(sum(a[-n//2+1:])*2 - sum(a[:n//2])*2 - min(a[n//2+1]-a[n//2],a[n//2]-a[n//2-1]))
else:
    print(sum(a[n//2+1:])*2 -sum(a[:n//2-1])*2 +a[n//2] -a[n//2-1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
n, *A = map(int, open(0).read().split())
a=sorted(A)
if n%2:
    print(sum(a[-n//2+1:])*2 - sum(a[:n//2])*2 - min(a[n//2+1]-a[n//2],a[n//2]-a[n//2-1]))
else:
    print(sum(a[n//2+1:])*2 -sum(a[:n//2-1])*2 +a[n//2] -a[n//2-1])

Submission status: Accepted

Solution code:
import sys
from collections import deque
import copy

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


def calc(N, A, max_min):

    if max_min:
        al = deque([A.popleft()])
        f = True
    else:
        al = deque([A.pop()])
        f = False

    while A:
        if len(A) >= 2:
            if f:
                al.append(A.pop())
                al.appendleft(A.pop())
                f = False
            else:
                al.appendleft(A.popleft())
                al.append(A.popleft())
                f = True

        elif len(A) == 1:
            al.append(A.pop())

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

    return ans


def main():
    N = in_n()
    A = deque(sorted(list(in_na())))

    ans1 = calc(N, copy.copy(A), True)
    ans2 = calc(N, copy.copy(A), False)
    print(max(ans1, ans2))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
n = int(input())
a = [int(input()) for _ in range(n)]
a.sort()
if n % 2 == 0:
    print(2 * (sum(a[n // 2 :]) - sum(a[: n // 2])) - a[n // 2] + a[n // 2 - 1])
else:
    daishou = 2 * (sum(a[n // 2 :]) - sum(a[: n // 2])) - a[n // 2] - a[n // 2 + 1]
    shoudai = (
        2 * (sum(a[1 + n // 2 :]) - sum(a[: 1 + n // 2])) + a[n // 2] + a[n // 2 - 1]
    )
    print(max(daishou, shoudai))

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = [None]*n
for i in range(n):
    a[i] = int(input())
    
a.sort()
b = [None]*n
if n%2==0:
    b[0] = a[n//2-1]
    b[-1] = a[n//2]
    l1 = a[:n//2-1]
    l2 = a[n//2+1:][::-1]
    for i in range(len(l1)):
        b[2*i+1] = l2[i]
        b[2*i+2] = l1[i]
    ans = sum(abs(b[i]-b[i+1]) for i in range(n-1))
else:
    ind = n//2+1
    b[0] = a[ind]
    b[-1] = a[n//2]
    l1 = a[:n//2]
    l2 = a[ind:][::-1]
    b[1] = l1[0]
    for i in range(len(l1)-1):
        b[2*i+2] = l2[i]
        b[2*i+3] = l1[i+1]
    ans1 = sum(abs(b[i]-b[i+1]) for i in range(n-1))
    
    ind = n//2-1
    b[0] = a[n//2]
    b[-1] = a[ind]
    l1 = a[:ind]
    l2 = a[n//2+1:]
    b[1] = l2[0]
    for i in range(len(l2)-1):
        b[2*i+2] = l1[i]
        b[2*i+3] = l2[i+1]
    ans2 = sum(abs(b[i]-b[i+1]) for i in range(n-1))
    ans = max(ans1, ans2)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = sorted(list(int(input()) for _ in range(n)))

if n%2==0:
    ans = 2 * (sum(a[n//2:]) - sum(a[:n//2]))
    ans += a[n//2-1] - a[n//2]
    print(ans)
elif n%2!=0:
    ans = 2 * (sum(a[n//2+1:]) - sum(a[:n//2]))
    print(ans - min(a[n//2+1] - a[n//2], a[n//2] - a[n//2-1]))

Submission status: Accepted

Solution code:
n=int(input())
ans=[]
for i in range(n):
  ans.append(int(input()))
ans.sort()
counter=0
re=[]
for i in range(n):
  re.append(ans[i])
re.reverse()
pointer1=0
pointer2=0
thing=0
a=[]
while counter<n-2:
  if thing==0:
    a.append(ans[pointer1])
    pointer1+=1
    thing=1
  else:
    a.append(re[pointer2])
    pointer2+=1
    thing=0
  counter+=1
final=[]
final.append(re[pointer2])
for i in a:
  final.append(i)
final.append(ans[pointer1])
maxans=0
for i in range(n-1):
  maxans+=abs(final[i]-final[i+1])
pointer1=0
pointer2=0
thing=1
a=[]
counter=0
while counter<n-2:
  if thing==0:
    a.append(ans[pointer1])
    pointer1+=1
    thing=1
  else:
    a.append(re[pointer2])
    pointer2+=1
    thing=0
  counter+=1
final=[]
final.append(re[pointer2])
for i in a:
  final.append(i)
final.append(ans[pointer1])
maxans1=0
for i in range(n-1):
  maxans1+=abs(final[i]-final[i+1])
print(max(maxans1,maxans))

Submission status: Accepted

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

if N%2 == 0:
  c = N//2
  small = A[:c]
  large = A[c:]
  ans = 2*sum(large)-min(large)-(2*sum(small)-max(small))
else:
  c = N//2
  small = A[:c+1]
  small.sort()
  large = A[c+1:] #largeの数のほうが少ない
  ans = 2*sum(large)-(2*sum(small)-small[-1]-small[-2])
  #print(large,small)
  small = A[:c]
  large = A[c:]
  large.sort()
  anst = 2*sum(large)-large[0]-large[1]-2*sum(small)
  ans = max(ans,anst)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
from copy import deepcopy

n,*a = map(int,open(0).read().split())
acopy = deepcopy(a)
a.sort()
acopy.sort(reverse = True)

L = deque([])
a = deque(a)
acopy = deque(acopy)
Lcopy = deepcopy(L)

max_ = a.pop()
L.append(max_)
min_ = acopy.pop()
Lcopy.append(min_)

while a:
    if a:
        b = a.popleft()
        L.append(b)
    if a:
        c = a.popleft()
        L.appendleft(c)
    if a:
        d = a.pop()
        L.append(d)
    if a:
        e = a.pop()
        L.appendleft(e)

while acopy:
    if acopy:
        b = acopy.popleft()
        Lcopy.append(b)
    if acopy:
        c = acopy.popleft()
        Lcopy.appendleft(c)
    if acopy:
        d = acopy.pop()
        Lcopy.append(d)
    if acopy:
        e = acopy.pop()
        Lcopy.appendleft(e)
ans1,ans2 = 0,0
#print(L,Lcopy)
for i in range(len(L)-1):
    ans1 +=abs(L[i+1] - L[i])
for i in range(len(Lcopy)-1):
    ans2 +=abs(Lcopy[i+1] - Lcopy[i])
print(max(ans1,ans2))

Submission status: Accepted

Solution code:
n = int(input())
dat = []
for _ in range(n):
    dat.append(int(input()))
dat.sort()
# 1 2 3 4 5
# 1 2 3 4

if n & 1 == 0:
    x1 = n // 2
    x2 = x1 - 1
    res = 0
    for i in range(n):
        if i < x2:
            res += (dat[i]) * -2
            continue
        if i == x2:
            res += (dat[i]) * -1
            continue
        if i == x1:
            res += (dat[i])
            continue
        if i > x1:
            res += (dat[i]) * 2
            continue
    print(res)
else:
    xc = n // 2
    xl = xc - 1
    xr = xc + 1

    res = 0
    for i in range(n):
        if i < xl:
            res += (dat[i]) * -2
            continue
        if i == xl:
            res += (dat[i]) * -1
            continue
        if i == xc:
            res += (dat[i]) * -1
            continue
        if i > xc:
            res += (dat[i]) * 2
            continue

    res2 = 0
    for i in range(n):
        if i < xc:
            res2 += (dat[i]) * -2
            continue
        if i == xc:
            res2 += (dat[i]) * 1
            continue
        if i == xr:
            res2 += (dat[i]) * 1
            continue
        if i > xr:
            res2 += (dat[i]) * 2
            continue

    print(max(res, res2))

Submission status: Accepted

Solution code:
n = int(input())
a = [0]*n
for i in range(n):
    a[i] = int(input())
a = sorted(a)
from collections import deque
q = deque([])
q.extend(a)
p = deque([])
i = 0
while len(q) > 1:
    if i%2 == 0:
        p.appendleft(q.popleft())
        p.append(q.pop())
    else:
        p.append(q.popleft())
        p.appendleft(q.pop())
    i += 1
p1 = list(p) + list(q)
p2 = list(q) + list(p)
ans1 = 0
ans2 = 0
for i in range(n-1):
    ans1 += abs(p1[i+1]-p1[i])
    ans2 += abs(p2[i+1]-p2[i])
print(max(ans1,ans2))

Submission status: Accepted

Solution code:
n = int(input())
a = [0]*n
for i in range(n):
    a[i] = int(input())
a = sorted(a)
from collections import deque
q = deque([])
q.extend(a)
p = deque([])
i = 0
while len(q) > 1:
    if i%2 == 0:
        y = q.popleft()
        p.appendleft(y)
        
        x = q.pop()
        p.append(x)
            
    else:
        y = q.popleft()
        p.append(y)
        
        x = q.pop()
        p.appendleft(x)
    i += 1
p1 = list(p) + list(q)
p2 = list(q) + list(p)
ans1 = 0
ans2 = 0
for i in range(n-1):
    ans1 += abs(p1[i+1]-p1[i])
    ans2 += abs(p2[i+1]-p2[i])
print(max(ans1,ans2))

Submission status: Accepted

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
def gcd(*numbers): reduce(math.gcd, numbers)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
count = 0
ans = 0

N = i()
A = []
for j in range(N):
    a = i()
    A.append(a)

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

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
from typing import Any, Callable, Deque, Dict, List, Mapping, Optional, Sequence, Set, Tuple, TypeVar, Union
# import time
# import math
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import Fraction               # Fraction(a, b) => a / b ∈ Q. note: Fraction(0.1) do not returns Fraciton(1, 10). Fraction('0.1') returns Fraction(1, 10)



def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79e+308
    # inf = 2 ** 63 - 1             # (for fast JIT compile in PyPy) 9.22e+18
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def isp():   return input().split()
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    

    def calc_max_diff(seq):
        n = len(seq)
        total = 0
        min_diff = inf
        for i in range(1, n):
            diff = abs(seq[i] - seq[i-1])
            total += diff
            min_diff = min(min_diff, diff)
        diff = abs(seq[0] - seq[-1])
        total += diff
        min_diff = min(min_diff, diff)
        return total - min_diff

    
    n = ii()
    L = [ii() for _ in range(n)]
    
    L.sort()
    dq = deque(L)
    large_small = []
    while dq:
        # print(dq)
        large_small.append(dq.pop())
        if dq:
            large_small.append(dq.popleft())

    dq = deque(L)
    small_large = []
    while dq:
        small_large.append(dq.popleft())
        if dq:
            small_large.append(dq.pop())


    a = calc_max_diff(large_small)
    b = calc_max_diff(small_large)
    # print(a, b)
    print(max(a, b))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log,gcd
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')

#Pythonを用いる場合
#numpy 1.18.0, scipy 1.4.1, scikit-learn 0.22, numba 0.47.0, networkx 2.4
 
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

n=ii()
arr=deque(list(sorted([ii() for _ in range(n)])))
cop=deque(deepcopy(list(arr)))
mat=deque([])

for i in range(n):
    if i%4==0:
        p=arr.popleft()
        mat.append(p)
    elif i%4==1:
        p=arr.pop()
        mat.appendleft(p)
    elif i%4==2:
        p=arr.pop()
        mat.append(p)
    else:
        p=arr.popleft()
        mat.appendleft(p)

mat2=deque([])
for i in range(n):
    if i%4==0:
        p=cop.pop()
        mat2.append(p)
    elif i%4==1:
        p=cop.popleft()
        mat2.appendleft(p)
    elif i%4==2:
        p=cop.popleft()
        mat2.append(p)
    else:
        p=cop.pop()
        mat2.appendleft(p)

ans=0
ans1=0
chk=list(mat)
chk1=list(mat2)
for i in range(n-1):
    ans+=abs(chk[i]-chk[i+1])
    ans1+=abs(chk1[i]-chk1[i+1])
print(max(ans,ans1))

Submission status: Accepted

Solution code:
from collections import deque

def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    A.sort()
    D = deque(A)
    d = D.popleft()
    tmp = deque([d])
    cnt = 0
    while D:
        if cnt % 2 == 0:
            i = D.pop()
            tmp.appendleft(i)
            if D:
                j = D.pop()
                tmp.append(j)
        else:
            i = D.popleft()
            tmp.appendleft(i)
            if D:
                j = D.popleft()
                tmp.append(j)
        cnt += 1

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

    D = deque(A)
    d = D.pop()
    tmp = deque([d])
    cnt = 0
    while D:
        if cnt % 2 == 0:
            i = D.popleft()
            tmp.appendleft(i)
            if D:
                j = D.popleft()
                tmp.append(j)

        else:
            i = D.pop()
            tmp.appendleft(i)
            if D:
                j = D.pop()
                tmp.append(j)
        cnt += 1

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

    print(max(a,ans))

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

a.sort()

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

Submission status: Accepted

Solution code:
n=int(input())
a=sorted([int(input()) for _ in range(n)])
f=0
ans=0
while a:
  f^=1
  if len(a)==3 and n%2==1:
    ans+=max(3*max(a)-sum(a),sum(a)-3*min(a))
    break
  ans+=([-1,1][f])*(2 if len(a)>2 else 1)*a.pop(-f)
print(ans)

Submission status: Accepted

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

A.sort()
B=[]
C=[]
if N%2==1:
    m=A[N//2]
    ans=0
    for i in range(N//2):
        B.append(A[i])
        C.append(A[-1-i])
        B.append(A[-1-i])
        C.append(A[i])
    dB=abs(m-B[0])
    dC=abs(m-C[0])
    for j in range(1,len(B)):
        dB+=abs(B[j]-B[j-1])
        dC+=abs(C[j]-C[j-1])
    ans=max(dB,dC)
else:
    for i in range(N//2):
        B.append(A[i])
        C.append(A[-1-i])
        B.append(A[-1-i])
        C.append(A[i])
    dB=abs(B[-1]-B[0])
    dC=abs(C[-1]-C[0])
    for j in range(1,len(B)-1):
        dB+=abs(B[j]-B[j-1])
        dC+=abs(C[j]-C[j-1])
    ans=max(dB,dC)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
if n == 1:
    print(0)
    exit()
a = [int(input()) for _ in range(n)]
a.sort()
na = [0]*n
c = n//2
if n%2 == 1:
    if a[c]-a[c-1] < a[c+1]-a[c]:
        lst1 = a[:c+1]
        lst2 = a[c+1:]
    else:
        lst1 = a[c:][::-1]
        lst2 = a[:c]
    na[0] = lst1[-1]
    na[-1] = lst1[-2]
else:
    lst1 = a[:c]
    lst2 = a[c:][::-1]
    na[0] = lst1[-1]
    na[-1] = lst2[-1]
i1 = i2 = 0
for i in range(1,n-1):
    if i%2 == 0:
        na[i] = lst1[i1]
        i1 += 1
    else:
        na[i] = lst2[i2]
        i2 += 1
# print(na)
ans = 0
for i in range(1,n): ans += abs(na[i]-na[i-1])
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
if n ==1:
    print(0)
    exit()
a = [int(input()) for _ in range(n)]
a.sort()
na = [0]*n
c = n//2
if n%2 == 1:
    if a[c]-a[c-1] < a[c+1]-a[c]:
        lst1 = a[:c+1]
        lst2 = a[c+1:]
        na[0] = lst1[-1]
        na[-1] = lst1[-2]
    else:
        lst1 = a[c:][::-1]
        lst2 = a[:c]
        na[0] = lst1[-1]
        na[-1] = lst1[-2]
else:
    lst1 = a[:c]
    lst2 = a[c:][::-1]
    na[0] = lst1[-1]
    na[-1] = lst2[-1]
i1 = i2 = 0
for i in range(1,n-1):
    if i%2 == 0:
        na[i] = lst1[i1]
        i1 += 1
    else:
        na[i] = lst2[i2]
        i2 += 1
# print(na)
ans = 0
for i in range(1,n): ans += abs(na[i]-na[i-1])
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

from collections import deque

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

    lnow = A.pop()
    rnow = lnow
    ret = 0
    while len(A)>0:
        lnxt = A[0]
        rnxt = A[-1]
        ll = abs(lnow - lnxt)
        rl = abs(rnow - lnxt)
        lr = abs(lnow - rnxt)
        rr = abs(rnow - rnxt)
        mx = max(ll, rl, lr, rr)
        ret += mx
        if mx == ll:
            lnow = lnxt
            x = A.popleft()
        elif  mx == rl:
            rnow = lnxt
            x = A.popleft()
        elif  mx == lr:
            lnow = rnxt
            x = A.pop()
        elif  mx == rr:
            rnow = rnxt
            x = A.pop()

    print(ret)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
#from decimal import *

N = INT()
A = [INT() for _ in range(N)]

A.sort()

if N%2 == 0:
	a = A[:N//2]
	b = A[N//2:]

	print((2*sum(b)-b[0]) - (2*sum(a)-a[-1]))

else:
	a1 = A[:N//2]
	b1 = A[N//2:]

	ans1 = (2*sum(b1)-b1[0]-b1[1]) - 2*sum(a1)

	a2 = A[:-(-N//2)]
	b2 = A[-(-N//2):]

	ans2 = (2*sum(b2)) - (2*sum(a2)-a2[-1]-a2[-2])

	print(max(ans1, ans2))

Submission status: Accepted

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

p = [0]*n
m = [0]*n

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

print(max(ans,ans2))

Submission status: Accepted

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
n = int(input())
As = sorted([int(input()) for i in range(n)])
q = deque(As[1:])
# 初期化
ans = 0
cnt = 1
p1 = As[0]
p2 = As[0]
flg = False
while True:
    if len(q) == 0: break
    if flg:
        n1 = q.popleft()
    else:
        n1 = q.pop()
    ans += abs(p1-n1)
    p1 = n1

    if len(q) == 0: break
    if flg:
        n2 = q.popleft()
    else:
        n2 = q.pop()
    ans += abs(p2-n2)
    p2 = n2

    flg = not flg

# 初期化(小さい順)
As = As[::-1]
ans2 = 0
p1 = As[0]
p2 = As[0]
q = deque(As[1:])
flg = False
while True:
    if len(q) == 0: break
    if flg:
        n1 = q.popleft()
    else:
        n1 = q.pop()
    ans2 += abs(p1-n1)
    p1 = n1

    if len(q) == 0: break
    if flg:
        n2 = q.popleft()
    else:
        n2 = q.pop()
    ans2 += abs(p2-n2)
    p2 = n2

    flg = not flg


print(max(ans,ans2))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AtoZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  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

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  divisors.sort()
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
N = I()
A = ILs(N)
A.sort()

if N == 3:
  a,b,c = A
  print(max(abs(a-c)+abs(a-b),abs(a-c)+abs(c-b)))
  exit()

if N%2:
  U1 = A[-(-N//2):]
  D1 = A[:-(-N//2)]
  ans1= (sum(U1)-sum(D1))*2+D1[-1]+D1[-2]
  
  U2 = A[N//2:]
  D2 = A[:N//2]
  ans2= (sum(U2)-sum(D2))*2-U2[0]-U2[1]
  
  print(max(ans1,ans2))
else:
  U = A[N//2:]
  D = A[:N//2]
  print((sum(U)-sum(D))*2-U[0]+D[-1])

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
a = []
for i in range(N):
    a.append(int(input()))
a.sort()
d = deque(a)
ans = deque([d.popleft()])
cur = 0
while d:
    if cur%2 == 0:
        ans.appendleft(d.pop())
        if len(d) != 0:
            ans.append(d.pop())
        cur += 1
    else:
        ans.appendleft(d.popleft())
        if len(d) != 0:
            ans.append(d.popleft())
        cur += 1
p = 0
for x, y in zip(list(ans), list(ans)[1:]):
    p += abs(x-y)

d = deque(a)
ans = deque([d.pop()])
cur = 1
while d:
    if cur%2 == 0:
        ans.appendleft(d.pop())
        if len(d) != 0:
            ans.append(d.pop())
        cur += 1
    else:
        ans.appendleft(d.popleft())
        if len(d) != 0:
            ans.append(d.popleft())
        cur += 1
q = 0
for x, y in zip(list(ans), list(ans)[1:]):
    q += abs(x-y)
print(max(p, q))