Problem:


Score : 400 points

Problem Statement

You are given N integers; the i-th of them is A_i.
Find the maximum possible sum of the absolute differences between the adjacent elements after arranging these integers in a row in any order you like.

Constraints

2 \leq N \leq 10^5

1 \leq A_i \leq 10^9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1
:
A_N

Output

Print the maximum possible sum of the absolute differences between the adjacent elements after arranging the given integers in a row in any order you like.

Sample Input 1

5
6
8
1
2
3

Sample Output 1

21

When the integers are arranged as 3,8,1,6,2, the sum of the absolute differences between the adjacent elements is |3 - 8| + |8 - 1| + |1 - 6| + |6 - 2| = 21. This is the maximum possible sum.

Sample Input 2

6
3
1
4
1
5
9

Sample Output 2

25

Sample Input 3

3
5
5
1

Sample Output 3

8



Sample input:
5
6
8
1
2
3


Sample output:
21

Submission status: Accepted

Solution code:
import sys

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


def input():
    return sys.stdin.readline().strip()


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

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

        ans2 = A[N // 2] + A[N // 2 + 1]
        for i in range(N // 2):
            ans2 -= 2 * A[i]
        for i in range(N // 2 + 2, N):
            ans2 += 2 * A[i]

        ans = max(ans1, ans2)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

    mid = n//2
    aa = sum(a[:mid])
    if n%2 == 0:
        ad = sum(a[mid:])
        print(2*(ad-aa)-(a[mid]-a[mid-1]))
        return 0
    ad = sum(a[mid+1:])
    tmp = min(a[mid+1]-a[mid],a[mid]-a[mid-1])
    print(2*(ad-aa)-tmp)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n=int(input())
    A=[int(input())for _ in range(n)]
    A.sort()
    ans1=0
    if n%2==0:
        ans1=(2*sum(A[n//2:])-A[n//2])-(2*sum(A[:n//2])-A[n//2-1])
    else:
        ans1=(2*sum(A[n//2:])-A[n//2]-A[n//2+1])-2*sum(A[:n//2])
    ans2=0
    if n%2==0:
        ans2=(2*sum(A[n//2:])-A[n//2])-(2*sum(A[:n//2])-A[n//2-1])
    else:
        ans2=2*sum(A[n//2+1:])-(2*sum(A[:n//2+1])-A[n//2-1]-A[n//2])      
    print(max(ans1,ans2))

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
def resolve():
    '''
    code here
    '''
    import collections
    N = int(input())
    A_list = [int(input()) for _ in range(N)]
    A_odered = collections.deque(sorted(A_list))
    res_list = collections.deque([A_odered.popleft()])
    res_list.appendleft(A_odered.pop())
    res = abs(res_list[0] - res_list[1])

    while len(A_odered) >= 1:
        temp_def1 = abs(res_list[0] - A_odered[-1])
        temp_def2 = abs(res_list[-1] - A_odered[-1])
        temp_def3 = abs(res_list[0] - A_odered[0])
        temp_def4 = abs(res_list[-1] - A_odered[0])

        max_deff = max(temp_def1, temp_def2, temp_def3, temp_def4)
        if temp_def1 == max_deff:
            res += temp_def1
            res_list.appendleft(A_odered.pop())
        elif temp_def2 == max_deff:

            res += temp_def2
            res_list.append(A_odered.pop())
        elif temp_def3 == max_deff:
            res += temp_def3
            res_list.appendleft(A_odered.popleft())
        else:
            res += temp_def4
            res_list.append(A_odered.popleft())
    # print(res_list)
    print(res)
if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
n = int(input())
a = [int(input()) for _ in range(n)]
a.sort(reverse = True)
b = [0] * n
l = n // 2 - 1
for i in range(l):
    b[i] = 2
b[l] = 1
if n % 2 == 1:
    b[l + 1] = 1
else:
    b[l + 1] = -1
for i in range(l + 2, n):
    b[i] = -2
ans1, ans2 = 0, 0
for i in range(n):
    ans1 += (a[i] * b[i])
    ans2 += (-1 * a[i] * b[n - i - 1])
print(max(ans1, ans2))

Submission status: Accepted

Solution code:
n=int(input())
a=[]
for _ in range(n):
    a.append(int(input()))
     
if n==2:
    print(abs(a[0]-a[1]))
    exit()

a=sorted(a)
turn=(n-1)//2
pre=a[0]*2
ans=0
for i in range(turn):
    if i%2==0:
        p=a[n-i-1]
        q=a[n-i-2]
        new=p+q
        ans += new-pre
        m=p-a[n-i-3]
    else:
        p=a[i]
        q=a[i+1]
        new=p+q
        ans += pre-new
        m=a[i+2]-p
    pre=new

if n%2==0:
    ans += m

a=sorted(a,reverse=True)
pre=a[0]*2
ans1=0
for i in range(turn):
    if i%2==0:
        p=a[n-i-1]
        q=a[n-i-2]
        new=p+q
        ans1 += pre-new
        m=a[n-i-3]-p
    else:
        p=a[i]
        q=a[i+1]
        new=p+q
        ans1 += new-pre
        m=p-a[i+2]
    pre=new

if n%2==0:
    ans1 += m

las=max(ans,ans1)
print(las)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_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

N = INT()
A = [INT() for _ in range(N)]
A.sort()
T = deepcopy(A)
T = deque(T)

l = deque([])
l.append(T.popleft())

while T:
	l.appendleft(T.pop())
	if not T:
		break
	l.append(T.pop())
	if not T:
		break
	l.appendleft(T.popleft())
	if not T:
		break
	l.append(T.popleft())

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

T = deepcopy(A)
T = deque(T)
l = deque([])
l.append(T.pop())
while T:
	l.appendleft(T.popleft())
	if not T:
		break
	l.append(T.popleft())
	if not T:
		break
	l.appendleft(T.pop())
	if not T:
		break
	l.append(T.pop())

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

ans = max(ans, tmp)
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:
  print(sum(a[:n//2])-sum(a[n//2:])+sum(a[:n//2-1])-sum(a[n//2+1:]))
else:
  c=sum(a[:n//2+1])+sum(a[:n//2-1])-2*sum(a[n//2+1:])
  d=2*sum(a[:n//2])-sum(a[n//2:])-sum(a[n//2+2:])
  print(max(c,d))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

n = int(input())
a = list(int(input()) for i in range(n))

a.sort()
if n%2==0:
    start = n//2-1
    left = 0
    right = n-1
    ans0 = abs(a[right]- a[start])
    while start != left:
        ans0+=abs(a[left]-a[right])
        right -= 1
        ans0+=abs(a[right]-a[left])
        left += 1

    start = n//2
    left = 0
    right = n-1
    ans1 = abs(a[left]- a[start])
    while start != right:
        ans1+=abs(a[right]-a[left])
        left += 1
        ans1+=abs(a[left]-a[right])
        right -= 1

    ans = max(ans0,ans1)
    print(ans)

if n%2==1:
    start = n//2
    left = 0
    right = n-1
    ans0 = abs(a[right]- a[start])
    while True:
        ans0+=abs(a[left]-a[right])
        right -= 1
        if start == right: break
        ans0+=abs(a[right]-a[left])
        left += 1


    left = 0
    right = n-1
    ans1 = abs(a[left]- a[start])
    while True:
        ans1+=abs(a[right]-a[left])
        left += 1
        if start == left: break
        ans1+=abs(a[left]-a[right])
        right -= 1

    ans = max(ans0,ans1)
    print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    A = sorted(list(int(input()) for _ in range(n)))
    B = deque([])
    for i in range(n // 2):
        if i % 2 == 0:
            B.appendleft(A[i])
            B.append(A[-(i + 1)])
        else:
            B.append(A[i])
            B.appendleft(A[-(i + 1)])

    if n % 2 != 0:
        if abs(B[0] - A[n // 2]) < abs(B[-1] - A[n // 2]):
            B.append(A[n // 2])
        else:
            B.appendleft(A[n // 2])

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

    print(res)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    N = int(input())
    A = sorted([int(input()) for i in range(N)], reverse=True)
    c = 1
    cnt = 0
    if N % 2 == 0:
        print(sum(A[:N // 2 - 1]) * 2 + A[N // 2 - 1] - A[N // 2] - sum(A[N // 2 - 1 + 2:] * 2))
    else:
        ans1 = sum(A[:N // 2]) * 2 - sum(A[N // 2:N // 2 + 2]) - sum(A[N // 2 + 2:] * 2)
        ans2 = sum(A[:N // 2 - 1]) * 2 + sum(A[N // 2 - 1:N // 2 + 1]) - sum(A[N // 2 + 1:] * 2)
        print(max(ans1, ans2))


resolve()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
chk = []
for i in range(n):
  a = int(input())
  chk.append(a)
chk.sort()
if n%2 == 0:
  l = [i*2 for i in chk[:n//2]]
  r = [i*2 for i in chk[n//2:]]
  print(sum(r)-sum(l)+chk[n//2-1]-chk[n//2])
else:
  l = [i*2 for i in chk[:(n-1)//2]]
  r = [i*2 for i in chk[(n-1)//2+1:]]
  p = sum(r)-sum(l)+chk[(n-1)//2-1]-chk[(n-1)//2]
  q = sum(r)-sum(l)+chk[(n-1)//2]-chk[(n-1)//2+1]
  print(max(p,q))

Submission status: Accepted

Solution code:
from collections import deque

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

A.sort()

X = deque(A.copy())

B = deque([X.pop()])
flg = True
while X:
    if flg:
        B.append(X.popleft())
        if X:
            B.appendleft(X.popleft())
    else:
        B.append(X.pop())
        if X:
            B.appendleft(X.pop())
    flg = not flg

X = deque(A.copy())
C = deque([X.popleft()])
flg = True
while X:
    if flg:
        C.append(X.pop())
        if X:
            C.appendleft(X.pop())
    else:
        C.append(X.popleft())
        if X:
            C.appendleft(X.popleft())
    flg = not flg

print(max(sum([abs(B[i]-B[i-1]) for i in range(1,N)]), sum([abs(C[i]-C[i-1]) for i in range(1,N)])))

Submission status: Accepted

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

if n % 2 == 0:
    low = A[:n//2]
    high = A[n//2:]
    ans = abs(2*sum(high)-high[0]-(2*sum(low)-low[-1]))
else:
    low = A[:n//2]
    high = A[n//2+1:]
    mid = A[n//2]
    ans = abs(2*sum(high)-high[0]-(2*sum(low)-low[-1]))
    ans += max(high[0]-mid, mid-low[-1])
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
A = sorted(int(input())for _ in range(n))
L = 1
R = n-1
B = deque([A[0]])
prev_L = A[0]
prev_R = A[0]
while L <= R:
    x, y = A[L], A[R]
    if abs(min(prev_L, prev_R)-y) < abs(max(prev_L, prev_R)-x):
        if prev_L < prev_R:
            B.append(x)
            prev_R = x
        else:
            B.appendleft(x)
            prev_L = x
        L += 1
    else:
        if prev_L < prev_R:
            B.appendleft(y)
            prev_L = y
        else:
            B.append(y)
            prev_R = y
        R -= 1

B = list(B)
ans = 0
for x, y in zip(B, B[1:]):
    ans += abs(x-y)
print(ans)

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n, *a = map(int, read().split())
a.sort()
a1 = 2 * (sum(a[(n + 1) // 2:]) - sum(a[:(n + 1) // 2]))
a2 = 2 * (sum(a[n // 2:]) - sum(a[:n // 2]))
if n % 2 == 0:
    v = a[n // 2] - a[n // 2 - 1]
    a1 -= v
    a2 -= v
else:
    a1 += a[n // 2 - 1] + a[n // 2]
    a2 -= a[n // 2 + 1] + a[n // 2]
print(max(a1, a2))

Submission status: Accepted

Solution code:
from collections import deque
n=int(input())
a=[0]*n
for i in range(n):
    a[i]=int(input())
a.sort()
ans1=0
d1=deque([a[0]])
l1=1
r1=n-1
while l1<=r1:
    d1.appendleft(a[r1])
    r1-=1
    if l1<=r1:
        d1.append(a[r1])
        r1-=1
    if l1<=r1:
        d1.appendleft(a[l1])
        l1+=1
    if l1<=r1:
        d1.append(a[l1])
        l1+=1
d1_l=list(d1)
ans2=0
d2=deque([a[n-1]])
l2=0
r2=n-2
while l2<=r2:
    d2.appendleft(a[l2])
    l2+=1
    if l2<=r2:
        d2.append(a[l2])
        l2+=1
    if l2<=r2:
        d2.appendleft(a[r2])
        r2-=1
    if l2<=r2:
        d2.append(a[r2])
        r2-=1
d2_l=list(d2)
for i in range(n-1):
    ans1+=abs(d1_l[i]-d1_l[i+1])
for i in range(n-1):
    ans2+=abs(d2_l[i]-d2_l[i+1])
print(max(ans1,ans2))

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
ai = [int(input()) for i in range(n)]

ai.sort()

deq = deque()
deq.appendleft(ai[0])

#print(ai)
#print()

for i in range(n-1):
    if i % 4 == 0:
        deq.appendleft(ai[n-i//2-1])
        #print(n-i//2-1)
    elif i % 4 == 1:
        deq.append(ai[n-i//2-2])
        #print(n-i//2-2)
    elif i % 4 == 2:
        deq.appendleft(ai[i//2])
        #print(i//2)
    elif i % 4 == 3:
        deq.append(ai[i//2+1])
        #print(i//2+1)
        #print(n-i//3-2)
    #print(deq)
    
ans = 0

#print(deq)

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


ai.sort(reverse=True)

deq = deque()
deq.appendleft(ai[0])

#print(ai)
#print()

for i in range(n-1):
    if i % 4 == 0:
        deq.appendleft(ai[n-i//2-1])
        #print(n-i//2-1)
    elif i % 4 == 1:
        deq.append(ai[n-i//2-2])
        #print(n-i//2-2)
    elif i % 4 == 2:
        deq.appendleft(ai[i//2])
        #print(i//2)
    elif i % 4 == 3:
        deq.append(ai[i//2+1])
        #print(i//2+1)
        #print(n-i//3-2)
    #print(deq)
    
ans2 = 0

#print(deq)

for i in range(n-1):
    ans2 += abs(deq[i+1] - deq[i])
#print(ans2)
print(max(ans,ans2))

Submission status: Accepted

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

if n%2==0:
    a=sorted(a)
    if n==2:
        print(a[1]-a[0])
        exit()
    else:
        ans=0
        for i in range(n):
            if i<n//2-1:
                ans-=a[i]*2
            elif i==n//2-1:
                ans-=a[i]
            elif i==n//2:
                ans+=a[i]
            else:
                ans+=a[i]*2
        print(ans)
else:
    a=sorted(a,reverse=True)
    ans=0
    tmp=0
    for i in range(n):
        if i<n//2-1:
            tmp+=a[i]*2
        elif i==n//2-1 or i==n//2:
            tmp+=a[i]
        else:
            tmp-=a[i]*2
    ans=tmp
    tmp=0
    for i in range(n):
        if i<n//2:
            tmp+=a[i]*2
        elif i==n//2 or i==n//2+1:
            tmp-=a[i]
        else:
            tmp-=a[i]*2
    ans=max(ans,tmp)
    print(ans)

Submission status: Accepted

Solution code:
import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

N = ii()
A = sorted([ii() for _ in range(N)])

if N % 2:
    ans_1 = sum(A[N//2+1:])*2 - sum(A[:N//2+1])*2
    ans_1 += A[N//2-1] + A[N//2]
    ans_2 = sum(A[N//2:])*2 - sum(A[:N//2])*2
    ans_2 -= A[N//2] + A[N//2+1]
    print(max(ans_1, ans_2))
else:
    ans = sum(A[N//2:])*2 - sum(A[:N//2])*2
    ans -= A[N//2] - A[N//2-1]
    print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = sorted([int(input()) for _ in range(N)], reverse=True)
result = 0
if N % 2 == 0:
    k = [2]*((N-2)//2)
    k += [1]
    k += [-1]
    a = [-2]*((N-2)//2)
    k = k+a
    for a, keisu in zip(A, k):
        result += a*keisu
else:
    k = [2]*(N//2-1)
    k += [1]
    k += [1]
    a = [-2]*(N//2)
    k = k+a
    result1 = 0
    for a, keisu in zip(A, k):
        result1 += a*keisu
    k = [2]*(N//2)
    k += [-1]
    k += [-1]
    a = [-2]*(N//2-1)
    k = k+a
    result2 = 0
    for a, keisu in zip(A, k):
        result2 += a*keisu
    result = max(result1, result2)
print(result)

Submission status: Accepted

Solution code:
import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

N = ii()
A = sorted([ii() for _ in range(N)])
'''
if N > 2:
    ans += A[-1] * 2 - A[0] - A[1]
    l_ind = 2
    r_ind = N-2
    while True:
        if r_ind - 2 >= l_ind:
'''
if N==2:
    print(A[1]-A[0])
#elif N%2:
else:
    '''
    ans_1 = A[N-1]*2 - A[0] - A[1]
    ans_1 += sum(A[N//2:N-1])*2 - sum(A[:N//2])*2 - A[N//2] - A[N//2-1]
    ans_2 = A[N-1] + A[N-2] - A[0]*2
    ans_2 += sum(A[N//2+1:])*2 - sum(A[1:N//2+1])*2 - A[N//2] - A[N//2+1]
    print(ans_1, ans_2)
    '''
    ans_1 = A[N-1]*2 - A[0] - A[1]
    tmp = A[0] + A[1]
    l_ind = 1
    r_ind = N-1
    while True:
        r_ind -= 2
        if N%2 and l_ind > r_ind:
            break
        if (not N%2) and r_ind == l_ind:
            ans_1 += A[r_ind+1] - A[r_ind-1]
            break
        ans_1 += A[r_ind] + A[r_ind+1] - tmp
        tmp = A[r_ind] + A[r_ind+1]
        l_ind += 2
        if N%2 and l_ind > r_ind:
            break
        if (not N%2) and r_ind == l_ind:
            ans_1 += A[r_ind+1] - A[r_ind-1]
            break
        ans_1 += tmp - (A[l_ind] + A[l_ind-1])
        tmp = A[l_ind] + A[l_ind-1]

    ans_2 = A[N-1] + A[N-2] - A[0]*2
    tmp = A[N-1] + A[N-2]
    l_ind = 0
    r_ind = N-2
    while True:
        l_ind += 2
        if N%2 and l_ind > r_ind:
            break
        if (not N%2) and r_ind == l_ind:
            ans_2 += A[r_ind+1] - A[r_ind-1]
            break
        ans_2 += tmp - (A[l_ind] + A[l_ind-1])
        tmp = A[l_ind] + A[l_ind-1]
        r_ind -= 2
        if N%2 and l_ind > r_ind:
            break
        if (not N%2) and r_ind == l_ind:
            ans_2 += A[r_ind+1] - A[r_ind-1]
            break
        ans_2 += A[r_ind] + A[r_ind+1] - tmp
        tmp = A[r_ind] + A[r_ind+1]

    print(max(ans_1, ans_2))

Submission status: Accepted

Solution code:
import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

N = ii()
A = sorted([ii() for _ in range(N)])
'''
if N > 2:
    ans += A[-1] * 2 - A[0] - A[1]
    l_ind = 2
    r_ind = N-2
    while True:
        if r_ind - 2 >= l_ind:
'''
if N==2:
    print(A[1]-A[0])
elif N%2:
    '''
    ans_1 = A[N-1]*2 - A[0] - A[1]
    ans_1 += sum(A[N//2:N-1])*2 - sum(A[:N//2])*2 - A[N//2] - A[N//2-1]
    ans_2 = A[N-1] + A[N-2] - A[0]*2
    ans_2 += sum(A[N//2+1:])*2 - sum(A[1:N//2+1])*2 - A[N//2] - A[N//2+1]
    print(ans_1, ans_2)
    '''
    ans_1 = A[N-1]*2 - A[0] - A[1]
    tmp = A[0] + A[1]
    l_ind = 1
    r_ind = N-1
    while True:
        r_ind -= 2
        if r_ind < l_ind:
            break
        ans_1 += A[r_ind] + A[r_ind+1] - tmp
        tmp = A[r_ind] + A[r_ind+1]
        l_ind += 2
        if l_ind > r_ind:
            break
        ans_1 += tmp - (A[l_ind] + A[l_ind-1])
        tmp = A[l_ind] + A[l_ind-1]
    #print(ans_1)

    ans_2 = A[N-1] + A[N-2] - A[0]*2
    tmp = A[N-1] + A[N-2]
    l_ind = 0
    r_ind = N-2
    while True:
        l_ind += 2
        if l_ind > r_ind:
            break
        ans_2 += tmp - (A[l_ind] + A[l_ind-1])
        tmp = A[l_ind] + A[l_ind-1]
        r_ind -= 2
        if r_ind < l_ind:
            break
        ans_2 += A[r_ind] + A[r_ind+1] - tmp
        tmp = A[r_ind] + A[r_ind+1]

    print(max(ans_1, ans_2))

else:
    ans_1 = A[N-1]*2 - A[0] - A[1]
    tmp = A[0] + A[1]
    l_ind = 1
    r_ind = N-1
    while True:
        r_ind -= 2
        if r_ind == l_ind:
            ans_1 += A[r_ind+1] - A[r_ind-1]
            break
        ans_1 += A[r_ind] + A[r_ind+1] - tmp
        tmp = A[r_ind] + A[r_ind+1]
        l_ind += 2
        if l_ind == r_ind:
            ans_1 += A[r_ind+1] - A[r_ind-1]
            break
        ans_1 += tmp - (A[l_ind] + A[l_ind-1])
        tmp = A[l_ind] + A[l_ind-1]

    ans_2 = A[N-1] + A[N-2] - A[0]*2
    tmp = A[N-1] + A[N-2]
    l_ind = 0
    r_ind = N-2
    while True:
        l_ind += 2
        if l_ind == r_ind:
            ans_2 += A[r_ind+1] - A[r_ind-1]
            break
        ans_2 += tmp - (A[l_ind] + A[l_ind-1])
        tmp = A[l_ind] + A[l_ind-1]
        r_ind -= 2
        if r_ind == l_ind:
            ans_2 += A[r_ind+1] - A[r_ind-1]
            break
        ans_2 += A[r_ind] + A[r_ind+1] - tmp
        tmp = A[r_ind] + A[r_ind+1]

    print(max(ans_1, ans_2))

Submission status: Accepted

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

from collections import deque

n = int(input())
A = [int(input()) for _ in range(n)]
A.sort(reverse=True)

# edit ans
# n=9のとき
# (1) a1 > a2 < a3 > a4 < a5 > a6 < a7 > a8 < a9
# (2) a1 < a2 > a3 < a4 > a6 < a6 > a7 < a8 > a9

# (1)のとき
# (a1 - a2) + (a3 - a2) + (a3 - a4) + ...
# -> a1 1, a2 -2, a3 2, a4 -2, ..., a8 -2, a9 1
# => 2, 2, 2, 1, 1, -2, -2, -2, -2 が係数
# 
# (2)のとき
# -> a1 -1, a2 2, a3 -2, ... a8 2, a9 -1
# => 2, 2, 2, 2, -1, -1, -2, -2, -2 が係数
#
# (N)偶数のとき (N=10)
# => 2, 2, 2, 2, 1, -1, -2, -2, -2, -2

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:
    # pattern 1
    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

    # pattern 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:
from collections import deque

d = deque()
N=int(input())
A=[]
for i in range(N):
    a=int(input())
    A.append(a)
A=sorted(A)
A2=A.copy()
#61823
#351914
#419153
B=deque()
#最初に大きい方
B.append(A.pop(-1))
while len(A)>0:
    if len(A)>0:
        B.appendleft(A.pop(0))
    if len(A)>0:
        B.append(A.pop(0))
    if len(A)>0:
        B.appendleft(A.pop(-1))
    if len(A)>0:
        B.append(A.pop(-1))
B=list(B)
C=deque()
#最初に小さい方
C.append(A2.pop(0))
while len(A2)>0:
    if len(A2)>0:
        C.appendleft(A2.pop(-1))
    if len(A2)>0:
        C.append(A2.pop(-1))
    if len(A2)>0:
        C.appendleft(A2.pop(0))
    if len(A2)>0:
        C.append(A2.pop(0))
C=list(C)
countb=0
countc=0
for i in range(1,N):
    countb+=abs(B[i]-B[i-1])
    countc+=abs(C[i]-C[i-1])
print(max(countb, countc))

Submission status: Accepted

Solution code:
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n = inn()
a = []
for i in range(n):
    a.append(inn())
a.sort()
if n%2==0:
    m = n//2
    sa = sum(a[:m])
    sb = sum(a[m:])
    print(2*sb-2*sa-a[m]+a[m-1])
else:
    m = n//2
    sa = sum(a[:m])
    sb = sum(a[m+1:])
    if a[m+1]-a[m]>a[m]-a[m-1]:
        print(2*sb-2*sa-a[m]+a[m-1])
    else:
        print(2*sb-2*sa-a[m+1]+a[m])

Submission status: Accepted

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

lis.sort()

mid = lis[n-1]
front, back = [], []
flag = 1
for i in range((n-1)//2):
    if flag:
        front.append(lis[i])
        back.append(lis[i + 1])
        flag = 0
    else:
        front.append(lis[n - i - 1])
        back.append(lis[n - i - 2])
        flag = 1
if (n-1) % 2 == 1:
    front.append(lis[n//2-1])

if n == 2:
    ans_M = mid - front[0]
else:
    ans_M = mid - front[0] + mid - back[0]

for i in range(1, len(front)):
    ans_M += abs(front[i] - front[i-1])
for i in range(1, len(back)):
    ans_M += abs(back[i] - back[i-1])

mid = lis[0]
front, back = [], []
flag = 1
for i in range((n-1)//2):
    if flag:
        front.append(lis[n - i - 1])
        back.append(lis[n - i - 2])
        flag = 0
    else:
        front.append(lis[i])
        back.append(lis[i + 1])
        flag = 1
if (n-1) % 2 == 1:
    front.append(lis[n//2-1])

if n == 2:
    ans_m = front[0] - mid
else:
    ans_m = front[0] - mid + back[0] - mid

for i in range(1, len(front)):
    ans_m += abs(front[i] - front[i-1])
for i in range(1, len(back)):
    ans_m += abs(back[i] - back[i-1])

print(max(ans_M, ans_m))

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = ni()
a = []

for i in range(n):
    a.append(ni())

a.sort()
t = n//2

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

Submission status: Accepted

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

A.sort()
if n&1:
    a = -sum(A[:n//2+1])*2 + sum(A[n//2+1:])*2 + A[n//2] + A[n//2-1]
    b = -sum(A[:n//2])*2 + sum(A[n//2:])*2 - A[n//2] - A[n//2+1]
    print(max(a,b))
else:
    ans = sum(A[n//2:])*2 - sum(A[:n//2])*2 - A[n//2] + A[n//2 - 1]
    print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = []
for i in range(n):
    a.append(int(input()))
a.sort()
b = []
d = []
for i in range(n):
    c = i // 2
    if i%2 == 0:
        b.append(a[c])
    else:
        b.append(a[n-1-c])
        
for i in range(n):
    c = i // 2
    if i%2 == 1:
        d.append(a[c])
    else:
        d.append(a[n-1-c])
        
b.append(a[0])
d.append(a[n-1])
sa = []
sa2 = []
for i in range(n):
    sa.append(abs(b[i+1] - b[i]))
    sa2.append(abs(d[i+1] - d[i]))
    
print(max(sum(sa) - min(sa) , sum(sa2) - min(sa2)))

Submission status: Accepted

Solution code:
import sys
import math  # noqa
import bisect  # noqa
import queue  # noqa
from collections import deque


def input():
    return sys.stdin.readline().rstrip()


def main():
    N = int(input())

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

    left_idx = 0
    right_idx = N - 1
    left = A[left_idx]
    right = A[right_idx]
    res = abs(right - left)
    left_idx += 1
    right_idx -= 1
    while left_idx <= right_idx:
        al = A[left_idx]
        ar = A[right_idx]
        dl = max(abs(al - left), abs(al - right))
        dr = max(abs(ar - left), abs(ar - right))
        if dl < dr:
            if abs(ar - left) < abs(ar - right):
                res += abs(ar - right)
                right = ar
            else:
                res += abs(ar - left)
                left = ar
            right_idx -= 1
        else:
            if abs(al - left) < abs(al - right):
                res += abs(al - right)
                right = al
            else:
                res += abs(al - left)
                left = al
            left_idx += 1

    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
signs = [1, -1]
coefs = [[-1],[1]]
i = 0
while i < N-2:
  j = 0
  while j < 2:
    coefs[j].append(2*signs[j])
    signs[j] *= -1
    j += 1
  i += 1
coefs[0].append(signs[0])
coefs[1].append(signs[1])
coefs[0].sort()
coefs[1].sort()
A = sorted([int(input()) for _ in range(N)])
print(max([sum([A[i]*coef[i]  for i in range(N)]) for coef in coefs]))

Submission status: Accepted

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

Submission status: Accepted

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

s = collections.deque([A[0]])
i = 1
j = N-1
while i <= j:
    xl = max(abs(s[0]-A[j]), abs(s[-1]-A[j]))
    xs = max(abs(s[0]-A[i]), abs(s[-1]-A[i]))
    if xl > xs:
        x = A[j]
        j -= 1
    else:
        x = A[i]
        i += 1
    if abs(s[0]-x) > abs(s[-1]-x):
        s.appendleft(x)
    else:
        s.append(x)
assert len(s) == N
ans = 0
for i in range(1, N):
    ans += abs(s[i] - s[i-1])
print(ans)

Submission status: Accepted

Solution code:
N,*L = map(int, open(0).read().split())
L.sort()
if N%2==0:
  A = L[:N//2]
  B = L[N//2:]
  a = 0
  b = -1
  m = 0
  n = 0
  p = B[0]
  for i in range(N-1):
    if i%2==0:
      m += p-A[a]
      p = A[a]
      a += 1
    else:
      m += B[b]-p
      p = B[b]
      b -= 1
  p = A[-1]
  a = 0
  b = -1
  for i in range(N-1):
    if i%2==0:
      n += B[b]-p
      p = B[b]
      b -= 1
    else:
      n += p-A[a]
      p = A[a]
      a += 1
  print(max(m,n))
else:
  A = L[:N//2]
  B = L[N//2:]
  a = 0
  b = -1
  m = 0
  n = 0
  p = B[0]
  for i in range(N-1):
    if i%2==0:
      m += p-A[a]
      p = A[a]
      a += 1
    else:
      m += B[b]-p
      p = B[b]
      b -= 1
  A = L[:N//2+1]
  B = L[N//2+1:]
  p = A[-1]
  a = 0
  b = -1
  for i in range(N-1):
    if i%2==0:
      n += B[b]-p
      p = B[b]
      b -= 1
    else:
      n += p-A[a]
      p = A[a]
      a += 1
  print(max(m,n))