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
#Tenka1 C

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = [I() for _ in range(n)]
a.sort()
if n % 2:
    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]
    print(max(x,y))
else:
    lower = a[:n//2]
    upper = a[n//2:]
    x = 2*sum(upper) - upper[0]
    y = 2*sum(lower) - lower[-1]
    print(x-y)

Submission status: Accepted

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

if n%2==0:
    print(2*sum(a[n//2+1:])-2*sum(a[:n//2-1])+a[n//2]-a[n//2-1])
else:
    b=abs(sum(a[n//2-1:n//2+1])+2*sum(a[:n//2-1])-2*sum(a[n//2+1:]))
    a.sort(reverse=True)
    c=abs(sum(a[n//2-1:n//2+1])+2*sum(a[:n//2-1])-2*sum(a[n//2+1:]))
    print(max(b,c))

Submission status: Accepted

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

N = int(input())
A = [int(input()) for _ 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]
    answer = 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]
    answer = max(x,y)
print(answer)

Submission status: Accepted

Solution code:
#### import ####
import sys
sys.setrecursionlimit(10**7)
import math
from collections import defaultdict

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

from collections import deque

N = I()
tempA = [0]*N
for i in range(N):
  tempA[i] = I()
  
tempA.sort()
A = deque(maxlen=N)
for i in range(N):
  A.append(tempA[i])
A2 = tempA[:]


temp = A.popleft()
B = deque(maxlen=N)
B.append(temp)
for i in range(math.ceil((N-1)/2)):
  if i%2==0:
    temp = A.pop()
    B.appendleft(temp)
    if len(A)>0:
      temp = A.popleft()
      B.appendleft(temp)
  else:
    temp = A.pop()
    B.append(temp)
    if len(A)>0:
      temp = A.popleft()
      B.append(temp)

val1 = 0
val2 = val1
for i in range(N-1):
  val1 += abs(B[i]-B[i+1])

if N%2==1:
  val2 = val1-abs(A2[(N-1)//2]-A2[(N-1)//2+1])+abs(A2[(N-1)//2]-A2[(N-1)//2-1])
print(max(val1,val2))

Submission status: Accepted

Solution code:
from collections import deque

def solve(n, a):
    a = sorted(a)
    return max(f(n, a), f(n, a[::-1]))

def f(n, a):
    a = deque(a)
    b = deque([])
    for i in range(n):
        if (i-1) % 4 < 2:
            v = a.popleft()
        else:
            v = a.pop()
        if i % 2 == 0:
            b.appendleft(v)
        else:
            b.append(v)
    return sum([abs(b[i+1]-b[i]) for i in range(n-1)])

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input().strip())
an = [int(input().strip()) for i in range(n)]
an.sort()

ans = an[-1] - an[0]
high = an[-1]
low = an[0]
c = n//2

if n % 2:
  for i in range(1,c):
    ans += high - an[i] + an[-i-1] - low
    high = an[-i-1]
    low = an[i]
  ans += max(high-an[c],an[c]-low)
  print(ans)
else:
  for i in range(1,c):
    ans += high - an[i] + an[-i-1] - low
    high = an[-i-1]
    low = an[i]
  print(ans)

Submission status: Accepted

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

if N%2:
    a = A[:N//2]
    b = A[N//2+1:][::-1]
    m = A[N//2]
    if abs(m-a[-1])>abs(m-b[-1]):
        a,b = b,a
    B = [m]*N
    for i in range(N//2):
        B[2*i+1] = b[i]
        B[2*i+2] = a[i]
else:
    a = A[:N//2][::-1]
    b = A[N//2:][::-1]
    B = [0]*N
    for i in range(N//2):
        B[i*2] = a[i]
        B[i*2+1] = b[i]
ans = sum(abs(B[i]-B[i+1]) for i in range(N-1))
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
l=[]
for i in range(n):
    l.append(int(input()))
l.sort()
if n%2==0:
    ln=l[:n//2]
    lx=l[n//2:]
    print(2*(sum(lx)-sum(ln))-lx[0]+ln[-1])
else:
    ln=l[:n//2]
    lm=l[n//2]
    lx=l[n//2+1:]
    p=sum(lx)
    q=sum(ln)
    print(max(2*(p-q)+ln[-1]-lm,2*(p-q)-lx[0]+lm))

Submission status: Accepted

Solution code:
import collections

n=int(input())
arr=[int(input()) for _ in range(n)]
arr=sorted(arr)
if n%2==1:
  q=collections.deque()
  q.append(arr[0])
  l=1
  r=n-1
  move=1
  while 1:
    q.appendleft(arr[r])
    r-=1
    q.append(arr[r])
    r-=1
    move+=2
    if move==n:
      break
    q.appendleft(arr[l])
    l+=1
    q.append(arr[l])
    l+=1
    move+=2
    if move==n:
      break
  q=list(q)
  ans1=0
  for i in range(n-1):
    ans1+=abs(q[i+1]-q[i])
  q=collections.deque()
  q.append(arr[-1])
  l=0
  r=n-2
  move=1
  while 1:
    q.appendleft(arr[l])
    l+=1
    q.append(arr[l])
    l+=1
    move+=2
    if move==n:
      break
    q.appendleft(arr[r])
    r-=1
    q.append(arr[r])
    r-=1
    move+=2
    if move==n:
      break
  q=list(q)
  ans2=0
  for i in range(n-1):
    ans2+=abs(q[i+1]-q[i])
  ans=max(ans1,ans2)
  print(ans)
else:
  q=collections.deque()
  q.append(arr[0])
  l=1
  r=n-1
  move=1
  while 1:
    if n-move==1:
      break
    q.appendleft(arr[r])
    r-=1
    q.append(arr[r])
    r-=1
    move+=2
    if n-move==1:
      break
    q.appendleft(arr[l])
    l+=1
    q.append(arr[l])
    l+=1
    move+=2
  q=list(q)
  ans1=0
  for i in range(n-2):
    ans1+=abs(q[i+1]-q[i])
  ans1+=max(abs(arr[l]-q[0]),abs(arr[l]-q[-1]))
  q=collections.deque()
  q.append(arr[-1])
  l=0
  r=n-2
  move=1
  while 1:
    if n-move==1:
      break
    q.appendleft(arr[l])
    l+=1
    q.append(arr[l])
    l+=1
    move+=2
    if n-move==1:
      break
    q.appendleft(arr[r])
    r-=1
    q.append(arr[r])
    r-=1
    move+=2
  q=list(q)
  ans2=0
  for i in range(n-2):
    ans2+=abs(q[i+1]-q[i])
  ans2+=max(abs(arr[r]-q[0]),abs(arr[r]-q[-1]))
  ans=max(ans1,ans2)
  print(ans)

Submission status: Accepted

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

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

ans = 0
middles = [n // 2 - 1, n // 2, n // 2 + 1]
if middles.count(0):
    middles.remove(0)
if middles.count(n-1):
    middles.remove(n-1)
for mid in middles:
    l = 0; r = n-1
    val = abs(a[mid] - a[l])
    state = True 
    while l != r:
        val += abs(a[r] - a[l])
        if state:
            l += 1
            if l == mid:
                l += 1
            state = False
        else:
            r -= 1
            if r == mid:
                r -= 1
            state = True
    ans = max(ans, val)
for mid in middles:
    l = 0; r = n-1
    val = abs(a[mid] - a[r])
    state = True 
    while l != r:
        val += abs(a[r] - a[l])
        if state:
            r -= 1
            if r == mid:
                r -= 1
            state = False
        else:
            l += 1
            if l == mid:
                l += 1
            state = True
    ans = max(ans, val)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
C - Align
https://atcoder.jp/contests/tenka1-2018-beginner/tasks/tenka1_2018_c

"""
import sys


from collections import deque

def solve(N, numbers):
    res = deque([numbers[0]])
    numbers = deque(numbers[1:])
    while numbers:
        bb = abs(numbers[-1] - res[-1])
        bf = abs(numbers[-1] - res[0])
        ff = abs(numbers[0] - res[0])
        fb = abs(numbers[0] - res[-1])
        t = sorted([[bb, 'bb'], [bf, 'bf'], [ff, 'ff'], [fb, 'fb']])
        if t[-1][1] == 'bb':
            res.append(numbers.pop())
        elif t[-1][1] == 'bf':
            res.appendleft(numbers.pop())
        elif t[-1][1] == 'ff':
            res.appendleft((numbers.popleft()))
        elif t[-1][1] == 'fb':
            res.append(numbers.popleft())

    res = list(res)
    return sum([abs(a-b) for a, b in zip(res, res[1:])])



def main(args):
    N = int(input())
    numbers = sorted([int(input()) for _ in range(N)])
    ans = solve(N, numbers)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
N = int(input())
 
num_list = []
for _ in range(N):
    num_list.append(int(input()))
    
num_sorted = sorted(num_list)
 
def calc_diff(add, add2, diff, diff2, num_sorted):
    total = 0
    
    for _ in range(add2):
        tmp = num_sorted.pop()
        total += tmp * 2
        
    for _ in range(add):
        tmp = num_sorted.pop()
        total += tmp * 1
        
    for _ in range(diff):
        tmp = num_sorted.pop()
        total -= tmp * 1
            
    for _ in range(diff2):
        tmp = num_sorted.pop()
        total -= tmp * 2
        
    return total
  
import copy
 
def calc(N, num_sorted):
    
    diff2 = 0
    add2 = 0
    diff = 0
    add = 0
    
    if N % 2 == 0:
        add = 1
        diff = 1
        add2 = N // 2 - 1
        diff2 = N // 2 - 1
        
        total = calc_diff(add, add2, diff, diff2, copy.deepcopy(num_sorted))
 
        return total
            
    if N % 2 == 1:        
        add = 0
        diff = 2
        add2 =(N - 1) // 2
        diff2 = (N - 1) // 2 - 1
        
        totalB = calc_diff(add, add2, diff, diff2, copy.deepcopy(num_sorted))
        
        add = 2
        diff = 0
        add2 =(N - 1) // 2 - 1
        diff2 = (N - 1) // 2
        
        totalC = calc_diff(add, add2, diff, diff2, copy.deepcopy(num_sorted))
        
        return max(totalB, totalC)
      
print(calc(N, num_sorted))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import collections
import copy
N = int(input())
As = [int(input()) for _ in range(N)]
As.sort()
As = collections.deque(As)
small1 = collections.deque()
small2 = collections.deque()
big1 = collections.deque()
big2 = collections.deque()
A1 = copy.copy(As)
A2 = copy.copy(As)
s = A1.popleft()
b = A2.pop()
small1.append(s)
small2.append(s)
big1.append(b)
big2.append(b)
cnt1 = 0
cnt2 = 0
while A1:
    if cnt1%4 == 0:
        b = A1.pop()
        small1.append(b)
        small2.appendleft(b)
        cnt1 += 1
    elif  cnt1%4 == 1:
        b = A1.pop()
        small2.append(b)
        small1.appendleft(b)
        cnt1 += 1
    elif cnt1%4 == 2:
        s = A1.popleft()
        small1.append(s)
        small2.appendleft(s)
        cnt1 += 1
    else:
        s = A1.popleft()
        small2.append(s)
        small1.appendleft(s)
        cnt1 += 1
while A2:
    if cnt2%4 == 0:
        s = A2.popleft()
        big1.append(s)
        big2.appendleft(s)
        cnt2 += 1
    elif  cnt2%4 == 1:
        s = A2.popleft()
        big2.append(s)
        big1.appendleft(s)
        cnt2 += 1
    elif cnt2%4 == 2:
        b = A2.pop()
        big1.append(b)
        big2.appendleft(b)
        cnt2 += 1
    else:
        b = A2.pop()
        big2.append(b)
        big1.appendleft(b)
        cnt2 += 1
anss1 = 0
anss2 = 0
ansb1 = 0
ansb2 = 0
for i in range(N-1):
    anss1 += abs(small1[i+1]-small1[i])
    anss2 += abs(small2[i+1]-small2[i])
    ansb1 += abs(big1[i+1]-big1[i])
    ansb2 += abs(big2[i+1]-big2[i])
print(max(anss1, anss2, ansb1, ansb2))

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 = 2*(sum(a[n//2:])-sum(a[:n//2]))-a[n//2]+a[n//2-1]
else:
    ans = (sum(a[n//2:])-sum(a[:n//2]))*2 - a[n//2] - a[n//2+1]
    ans = max(ans,(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:
n,*a=map(int,open(0).read().split())
a.sort()
d=len(a)//2
flag=0
if len(a)%2==1:
    b=a[:d+1]
    c=a[d+1:]
    flag=1
else:
    b=a[:d]
    c=a[d:]
l=[]
for i in range(d):
    l.append(c[i])
    l.append(b[i])
if flag:
    if abs(l[-1]-b[-1])>abs(l[0]-b[-1]):
        l.append(b[-1])
    else:
        l.insert(0,b[-1])
print(sum(abs(l[i+1]-l[i])for i in range(n-1)))

Submission status: Accepted

Solution code:
from collections import*
n,*a=map(int,open(0).read().split())
a.sort()
d=len(a)//2
flag=0
if len(a)%2==1:
    b=a[:d+1]
    c=a[d+1:]
    flag=1
else:
    b=a[:d]
    c=a[d:]
l=[]
for i in range(d):
    l.append(c[i])
    l.append(b[i])
if flag:
    if abs(l[-1]-b[-1])>abs(l[0]-b[-1]):
        l.append(b[-1])
    else:
        l.insert(0,b[-1])
print(sum(abs(l[i+1]-l[i])for i in range(n-1)))

Submission status: Accepted

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

A.sort(reverse=True)

def p1(l):
    if N%2 == 1:
        ans = 0
        ans += sum(l[:(N-3)//2])*2
        ans += sum(l[(N-3)//2:(N-3)//2+2])
        ans += sum(l[(N-3)//2+2:])*(-2)
        return ans
    else:
        ans = 0
        ans += sum(l[:(N-2)//2])*2
        ans += sum(l[(N-2)//2:(N-2)//2+1])
        ans += sum(l[(N-2)//2+1:(N-2)//2+2])*(-1)
        ans += sum(l[(N-2)//2+2:])*(-2)
        return ans

def p2(l):
    if N%2 == 1:
        ans = 0
        ans += sum(l[:(N-1)//2])*2
        ans += sum(l[(N-1)//2:(N-1)//2+2])*(-1)
        ans += sum(l[(N-1)//2+2:])*(-2)
        return ans
    else:
        ans = 0
        ans += sum(l[:(N-2)//2])*2
        ans += sum(l[(N-2)//2:(N-2)//2+1])
        ans += sum(l[(N-2)//2+1:(N-2)//2+2])*(-1)
        ans += sum(l[(N-2)//2+2:])*(-2)
        return ans
print(max(p1(A),p2(A)))

Submission status: Accepted

Solution code:
n = int(input())
A = sorted(int(input()) for i in range(n))
a = [0]*(n)
b = [0]*(n)
c = 1

for i in range(n-1):
    a[i] += -c
    a[i+1] += c
    b[i] += c
    b[i+1] += -c
    c *= -1
a.sort()
b.sort()
sum1,sum2 = 0,0
for i in range(n):
    sum1 += a[i] *A[i]
    sum2 += b[i] * A[i]
print(max(sum1,sum2))

Submission status: Accepted

Solution code:
from collections import deque


def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    A.sort()
    ans = 0
    B = deque(A)
    edge = [B.popleft()] * 2
    while len(B):
        a = abs(edge[0] - B[0])
        b = abs(edge[0] - B[len(B) - 1])
        c = abs(edge[1] - B[0])
        d = abs(edge[1] - B[len(B) - 1])
        if max(a, b, c, d) == a:
            edge[0] = B.popleft()
            ans += a
        elif max(a, b, c, d) == b:
            edge[0] = B.pop()
            ans += b
        elif max(a, b, c, d) == c:
            edge[1] = B.popleft()
            ans += c
        else:
            edge[1] = B.pop()
            ans += d
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
a=[]
n=int(input())
for i in range(n):a.append(int(input()))
a.sort()
if len(a)%2==0:
    b=[a.pop(len(a)//2-1)]
    while len(a)!=1:
        b.append(a.pop(-1))
        b.append(a.pop(0))
    b.append(a.pop(-1))
else:
    b=[a.pop(len(a)//2)]
    if abs(b[0]-a[len(a)//2])>abs(b[0]-a[len(a)//2-1]):
        while len(a)!=0:
            b.append(a.pop(-1))
            b.append(a.pop(0))
    else:
        while len(a)!=0:
            b.append(a.pop(0))
            b.append(a.pop(-1))
ans=0
for i in range(n-1):ans+=abs(b[i]-b[i+1])
print(ans)

Submission status: Accepted

Solution code:
from itertools import chain

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

A.sort()

m = N // 2
L, R = A[:m], A[m:]

def sumOfDiff(A):
    """隣の要素との差の合計"""
    return sum(abs(a - b) for a, b in zip(A, A[1:]))

def merge(L, R):
    """[L[0], R[0], L[1], R[1], ...]"""
    return list(chain.from_iterable(zip(L, R)))

if N % 2 == 0:
    # Rの最小値とLの最大値を端に
    s = sumOfDiff(merge(R, L))
else:
    L.reverse()
    B1 = merge(L, R[1:]) + [R[0]]  # Lの最大値が端
    B2 = merge(R[1:], L) + [R[0]]  # Rの最小値が端
    s = max(sumOfDiff(B1), sumOfDiff(B2))

print(s)

Submission status: Accepted

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

p1 = []
p2 = []
for i in range(n):
    x = 2
    if i == 0 or i == n-1:
        x = 1
    if i % 2 == 0:
        p1.append(x)
        p2.append(-x)
    else:
        p1.append(-x)
        p2.append(x)
p1.sort()
p2.sort()
# print(p1)
# print(p2)
ans1 = 0
ans2 = 0
for i in range(n):
    ans1 += l[i] * p1[i]
    ans2 += l[i] * p2[i]
    # print(ans1, ans2)

print(max(ans1, ans2))

Submission status: Accepted

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

sort_values = []
med = int(N/2) if N % 2 == 1 else int(N/2)-1
prev = values[med]
A = values[:med]
B = list(reversed(values[med+1:]))
BAsum = 0
for i in range(med+1):
  if i >= len(B):
    break
  now = B[i]
  BAsum += abs(now-prev)
  prev = now
  if i >= len(A):
    break
  now = A[i]
  BAsum += abs(now-prev)
  prev = now

med = int(N/2)
prev = values[med]
A = values[:med]
B = list(reversed(values[med+1:]))
ABsum = 0
for i in range(med+1):
  if i >= len(A):
    break
  now = A[i]
  ABsum += abs(now-prev)
  prev = now
  if i >= len(B):
    break
  now = B[i]
  ABsum += abs(now-prev)
  prev = now  

#print(A, B)
print(max([BAsum, ABsum]))

Submission status: Accepted

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

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
n = int(input())
a = [int(input()) for _ in range(n)]
a.sort()
p1 = []
p2 = []
for i in range(n):
    x = 2
    if i == 0 or i == n-1:
        x = 1
    if i % 2 == 0:
        p1.append(x)
        p2.append(-x)
    else:
        p1.append(-x)
        p2.append(x)
p1.sort()
p2.sort()

ans1 = 0
ans2 = 0
for i in range(n):
    ans1 += a[i]*p1[i]
    ans2 += a[i]*p2[i]

print(max(ans1, ans2))

Submission status: Accepted

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

A.sort()

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

Submission status: Accepted

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

A.sort()
temp = 0

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

Submission status: Accepted

Solution code:
n = int(input())
a = [int(input()) for i in range(n)]
a.sort()
ress = []
for i in range(2):
    if i == 0:
        res = 0
        b = a[n//2:]
        c = a[:n//2]
        res += 2*sum(b)
        res -= 2*sum(c)
        res -= b[0]
        if n%2 == 1:
            res -= b[1]
        else:
            res += c[-1]
        ress.append(res)
    if i==1 and n%2==1:
        res = 0
        b = a[n//2+1:]
        c = a[:n//2+1]
        res += 2*sum(b)
        res -= 2*sum(c)
        res += c[-1]+c[-2]
        ress.append(res)
print(max(ress))

Submission status: Accepted

Solution code:


def main():
    num = int(input())
    data_list = [int(input()) for i in range(num)]
    data_list.sort()


    if num % 2 == 1:
        hikukazu = 0
        for i in range(num // 2 + 1):
            hikukazu += 2 * data_list[i]
        hikukazu -= data_list[num // 2] + data_list[num // 2 - 1]

        tasukazu = 0
        for i in range(num // 2 + 1, num):
            tasukazu += 2 * data_list[i]
    else:
        hikukazu = 0
        for i in range(num // 2):
            hikukazu += 2 * data_list[i]
        hikukazu -= data_list[num // 2 - 1]

        tasukazu = 0
        for i in range(num // 2, num):
            tasukazu += 2 * data_list[i]
        tasukazu -= data_list[num // 2]

    a = tasukazu - hikukazu

    if num % 2 == 1:
        hikukazu = 0
        for i in range(num // 2):
            hikukazu += 2 * data_list[i]

        tasukazu = 0
        for i in range(num // 2, num):
            tasukazu += 2 * data_list[i]
        tasukazu -= data_list[num // 2] + data_list[num // 2 + 1]
    else:
        hikukazu = 0
        for i in range(num // 2):
            hikukazu += 2 * data_list[i]
        hikukazu -= data_list[num // 2 - 1]

        tasukazu = 0
        for i in range(num // 2, num):
            tasukazu += 2 * data_list[i]
        tasukazu -= data_list[num // 2]

    b = tasukazu - hikukazu

    # print(a, b)
    print(max(a, b))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

A.sort()

ans = A[len(A) - 1] - A[0]
small = 0
large = len(A) - 1
while (True):

    if large - small == 1:
        break
    elif large - small == 2:
        ans += max(A[large] - A[large - 1], A[small + 1] - A[small])
        break
    ans += A[large - 1] - A[small] + A[large] - A[small + 1]
    small += 1
    large -= 1

print(ans)

Submission status: Accepted

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

if n % 2:
    ans1 = (sum(a[n2 + 1:]) - sum(a[:n2 + 1])) * 2 + a[n2] + a[n2 - 1]
    ans2 = (sum(a[n2:]) - sum(a[:n2])) * 2 - a[n2] - a[n2 + 1]
    ans = max(ans1, ans2)
else:
    ans = (sum(a[n2:]) - sum(a[:n2])) * 2 - a[n2] + a[n2 - 1]

print(ans)

Submission status: Accepted

Solution code:
import bisect
from collections import deque
from collections import defaultdict
from fractions import gcd
#from math import factorial
from math import sqrt
from math import ceil
from itertools import permutations
from heapq import *

N=int(input())
A=[]
B=[]
for _ in range(N):
    a=int(input())
    A.append(a)
    B.append(a)
A.sort()
B.sort()
A=deque(A)
B=deque(B)
L=deque()
L.append(A.popleft())
num=0
while(A):
    if num==0:
        L.appendleft(A.pop())
        num+=1
    elif num==1:
        L.append(A.pop())
        num+=1
    elif num==2:
        L.appendleft(A.popleft())
        num+=1
    elif num==3:
        L.append(A.popleft())
        num=0
sum1=0
for i in range(N-1):
    sum1+=abs(L[i]-L[i+1])
R=deque()
R.append(B.pop())
num=2
while(B):
    if num==0:
        R.appendleft(B.pop())
        num+=1
    elif num==1:
        R.append(B.pop())
        num+=1
    elif num==2:
        R.appendleft(B.popleft())
        num+=1
    elif num==3:
        R.append(B.popleft())
        num=0
sum2=0
for i in range(N-1):
    sum2+=abs(R[i]-R[i+1])

print(max(sum1,sum2))

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime,random
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())

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

if N%2 == 0:
    ans = (sum(aa[N//2:]) - sum(aa[:N//2]))*2 - (aa[N//2]-aa[N//2-1])
    print(ans)
else:
    ans1 = (sum(aa[N//2:]) - sum(aa[:N//2]))*2 - (aa[N//2]+aa[N//2+1])
    ans2 = (sum(aa[(N//2+1):]) - sum(aa[:(N//2+1)]))*2 + (aa[N//2]+aa[N//2-1])
    print(max(ans1,ans2))

Submission status: Accepted

Solution code:
a = int(input())
k =[int(input()) for i in range(a)]
k.sort()
if a%2!=0:
  s1= 2*sum(k[a//2:]) - 2*sum(k[:a//2]) -k[a//2]-k[a//2+1]
  s2= 2*sum(k[a//2+1:]) - 2*sum(k[:a//2+1]) +k[a//2]+k[a//2-1]
  s = max(s1,s2)
else:
  s= 2*sum(k[a//2:]) - 2*sum(k[:a//2]) -k[a//2]+k[a//2-1]
print(s)
#print(2*sum(k[a//2+1:]) , 2*sum(k[:a//2]))

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = [int(input()) for i in range(N)]
    A.sort()
    BIG, SMALL = -1, 0
    big_index = N-1
    small_index = 0

    left = A[big_index]
    left_sign = BIG
    right = A[big_index]
    right_sign = BIG
    big_index-=1
    result = 0
    for i in range(1, N):
        val1, val2 = 0, 0
        s = A[small_index]
        b = A[big_index]
        against1, against2 = 0, 0
        if left_sign == BIG:
            val1 = abs(left - s)
            against1 = SMALL
        else:
            val1 = abs(left - b)
            against1 = BIG
        if right_sign == BIG:
            val2 = abs(right - s)
            against2 = SMALL
        else:
            val2 = abs(right - b)
            against2 = BIG
        if val1 > val2:
            result += val1
            if against1 == BIG:
                left = b
                left_sign = against1
                # print(b)
                big_index -= 1
            else:
                left = s
                left_sign = against1
                # print(s)
                small_index += 1
        else:
            result += val2
            if against2 == BIG:
                right = b
                right_sign = against2
                # print(b)
                big_index -= 1
            else:
                right = s
                right_sign = against2
                # print(s)
                small_index += 1
    print(result)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
L = []
S = 0
K = 0
for i in range(N):
  L.append(int(input()))
L.sort()
if N == 2:
  print(abs(L[0]-L[1]))
elif N == 3:
  print(max(abs(L[2]+L[1]-2*L[0]),abs(2*L[2]-L[1]-L[0])))
elif N == 4:
  print(abs(2*L[3]+L[2]-L[1]-2*L[0]))
elif N%2 == 0:
  for i in range((N-2)//2):
    S += 2*(L[N-i-1]-L[i])
  S += L[N//2]-L[(N-2)//2]
  print(S)
else:
  for i in range((N-3)//2):
    S += 2*L[N-i-1]
  for j in range(N//2):
    S -= 2*L[j]
  S += L[N//2]+L[N//2+1]
  for k in range(N//2):
    K += L[N-k-1]*2
  for m in range((N-3)//2):
    K -= 2*L[m]
  K -= (L[N//2]+L[N//2-1])
  print(max(S,K))