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:
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 + 1:]) - sum(A[:N//2]) - sum(A[:N//2-1])
else:

    ans = sum(A[N//2:]) + sum(A[N//2+2:]) - 2 * sum(A[:N//2])
    
    ans = max(ans, 2 * sum(A[N//2+1:]) - sum(A[:N//2+1]) - sum(A[:N//2-1]))
    
print(ans)

Submission status: Accepted

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

a.sort(reverse = True)

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

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n = int(input())
a = []
for _ in range(n):
    a.append(int(input()))
a.sort()
from collections import deque
def getsm(q):
    last=q.popleft()
    sm=0
    for num in q:
        sm+=abs(last-num)
        last=num
    return sm

q = deque()
q.append(a[0])
l=0
r=n
while True:
    r-=1
    if r==l:
        break
    q.appendleft(a[r])
    r-=1
    if r==l:
        break
    q.append(a[r])
    l+=1
    if r==l:
        break
    q.appendleft(a[l])
    l+=1
    if r==l:
        break
    q.append(a[l])
ans1=getsm(q)


q = deque()
q.append(a[-1])
l=-1
r=n-1
while True:
    l+=1
    if r==l:
        break
    q.appendleft(a[l])
    l+=1
    if r==l:
        break
    q.append(a[l])
    r-=1
    if r==l:
        break
    q.appendleft(a[r])
    r-=1
    if r==l:
        break
    q.append(a[r])
ans2=getsm(q)
print(max(ans1,ans2))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
a=[0]*n
for  i in range(n):
    a[i]=int(input())
a.sort(reverse=True)
ans=0
aupper=a[:n//2]
adowner=a[n//2:]
if len(a)==2:print(a[0]-a[1])
elif len(a)==3:
    print(max(sum(a[:n-1])-a[n-1]*2,a[0]*2-sum(a[1:])))
elif n%2==1:
    ans1=0;ans2=0
    for i in range(n//2):
        ans1+=aupper[i]*2-(adowner[i]+adowner[i+1])
    ans1+=(adowner[1]-adowner[-1])
    a=a[::-1]
    adowner=a[:n//2]
    aupper=a[n//2:]
    for i in range(n//2):
        ans2+=aupper[i]+aupper[i+1]-adowner[i]*2
    ans2+=aupper[-1]-aupper[1]
    print(max(ans1,ans2))
else:
    ans=0
    for i in range(n//2):
        if i!=n//2-1:
            ans+=aupper[i]*2-(adowner[i]+adowner[i+1])
        else:
            ans+=aupper[i]-adowner[i]
    print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys,collections

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  # a1>a2<a3>a4...
  # a1-a2+a3-a2+a3-a4...
  # a1+2a3-2a2-2a4+...+an? -an?

  # 偶数なら例えば4: a1-2a2+2a3-a4
  # 奇数なら例えば3: a1-2a2+a3

  # 割り当て：2の係数がついて正の数は大きいやつを優先して
  # 2の係数がついて負の数は小さいやつを優先

  # 逆の場合は
  # a4-2a3+2a2-a1
  # -a3+2a2-a1

  n=I()
  l=[I() for _ in range(n)]

  l.sort()

  i1=0
  i2=n-1

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

    ans+=l[i2]
    ans-=l[i1]

  else:
    for i in range((n-2)//2):
      ans+=l[i2]*2
      i2-=1
      ans-=l[i1]*2
      i1+=1

    ans-=l[i1]*2
    i1+=1

    ans+=l[i2]
    ans+=l[i1]

  ans1=ans
  ans=0
  i1=0
  i2=n-1
  if n%2==0:
    for i in range((n-2)//2):
      ans+=l[i2]*2
      i2-=1
      ans-=l[i1]*2
      i1+=1

    ans+=l[i2]
    ans-=l[i1]

  else:
    # print(i1,i2,l)
    for i in range((n-2)//2):
      ans+=l[i2]*2
      i2-=1
      ans-=l[i1]*2
      i1+=1

    ans+=l[i2]*2
    i2-=1

    ans-=l[i2]
    ans-=l[i1]

  ans2=ans
  return max(ans1,ans2)

# main()
print(main())

Submission status: Accepted

Solution code:
def main():
    from itertools import cycle

    n = int(input())
    *a, = sorted(int(input()) for _ in range(n))

    half = n // 2
    h = reversed(a[:half])
    t = reversed(a[-half:])

    if n % 2 == 0:
        lis = []
        for e, o in zip(h, t):
            lis.append(e)
            lis.append(o)

        it = iter(lis)
        p = next(it)

        ret = 0
        for x in it:
            ret += abs(p - x)
            p = x

        print(ret)

    else:
        # 昇順ソートされたaを2つの山に分ける
        # xxx yy : 小を多く取る -> xyxyx
        # yは順序を気にしない
        # yとの差が小さくなるようなx（大きい方から2つ）を両端に置く
        # zz www : 大を多く取る -> wzwzw
        # zは順序を気にしない
        # zとの差が小さくなるようなw（小さい方から2つ）を両端に置く

        xs, ys = a[:-half], a[-half:]

        x = xs.pop()
        xs = [x] + xs

        cycl = cycle((xs, ys))

        p = next(cycl).pop()

        ret = 0
        for _ in range(n - 1):
            e = next(cycl).pop()
            ret += abs(p - e)
            p = e

        zs, ws = a[:half], a[half:]

        w, *ws = ws
        ws.append(w)

        cycl = cycle((ws, zs))

        p = next(cycl).pop()

        buf = 0
        for _ in range(n - 1):
            e = next(cycl).pop()
            buf += abs(p - e)
            p = e

        ret = max(ret, buf)

        print(ret)


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = [0] * 2 ;count = 0 ;pro = 1

n=int(input())
A=[int(input()) for i in range(n)]
A.sort()
# if n % 2 == 0:
# 1の処理
tmp = 0;k=0
k+=n//2-1; tmp += -2*sum(A[:k])
tmp += -1*A[k]; k += 1
tmp += (-1)**n*A[k]; k += 1
tmp += 2 * sum(A[k:])
ans[0] = tmp

# 2の処理
tmp = 0;k=0
k+=n//2-1+(n%2); tmp += -2*sum(A[:k])
# print(tmp,A[:k])
tmp += (-1)**(n+1)*A[k]; k += 1
tmp += A[k]; k += 1
tmp += 2 * sum(A[k:])
ans[1] = tmp

# print(A);print(ans)
print(max(ans))

Submission status: Accepted

Solution code:
# C - Align
from collections import deque
n=int(input())
a=[int(input()) for i in range(n)]
a.sort(reverse=True)
b=deque()
for i in range(n):
    t=0
    if i==n-1:
        t=a.pop(0)
        if abs(t-b[0])>=abs(t-b[-1]):
            b.appendleft(t)
        elif abs(t-b[0])<abs(t-b[-1]):
            b.append(t)
        break
    if i%2==0:
        if i==0:
            t=a.pop(0)
            b.append(t)
            continue
        if b[0]>=b[-1]:
            t=a.pop(0)
            b.append(t)
        elif b[0]<b[-1]:
            t=a.pop(0)
            b.appendleft(t)
    else:
        if i==1:
            t=a.pop(-1)
            b.append(t)
            continue
        if b[0]>=b[-1]:
            t=a.pop(-1)
            b.appendleft(t)
        elif b[0]<b[-1]:
            t=a.pop(-1)
            b.append(t)
ans=0
for i in range(n-1):
    ans+=abs(b[i+1]-b[i])
print(ans)

Submission status: Accepted

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

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

    tmp = N // 2
    if N % 2 == 1:
        L, M, R = A[:tmp], A[tmp], A[tmp+1:]
        # max(R[0]の隣にMを配置, L[-1]の隣にMを配置)
        print((sum(R) - sum(L)) * 2 + max(L[-1] - M, M - R[0]))
    else:
        L, R = A[:tmp], A[tmp:]
        """
        L[-1], R[0]は、第1項で
        それぞれ1回多く計算されているため、
        (L[-1] - R[0])としている
        """
        print((sum(R) - sum(L)) * 2 + (L[-1] - R[0]))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N, *A = map(int, open(0))
 
A.sort()
 
if N % 2 == 1:
    L, M, R = A[: N//2], A[N//2], A[N//2+1:]
    print((sum(R) - sum(L)) * 2 + max(- M + L[-1], M - R[0]))
else:
    L, R = A[:N // 2], A[N // 2:]
    print((sum(R) - sum(L)) * 2 - R[0] + L[-1])

Submission status: Accepted

Solution code:
from collections import deque
import sys
input = sys.stdin.readline


def solve(N, A, fromR=True):
    res = 0
    L, R = None, None

    while A:
        fromR = 1 - fromR

        if L is None:
            L = A.pop() if fromR else A.popleft()
            R = L
            continue

        if len(A) > 1:
            if fromR:
                x = A.pop()
                y = A.pop()
            else:
                x = A.popleft()
                y = A.popleft()
            res += abs((R + L) - (x + y))
            R, L = x, y
            continue

        if len(A) == 1:
            x = A.pop()
            res += max(abs(R - x), abs(L - x))
            continue

    return res


if __name__ == "__main__":
    N = int(input())
    A = sorted([int(input()) for _ in range(N)])
    B = deque(A[::])
    A = deque(A)
    

    ans1 = solve(N, A, 0)
    ans2 = solve(N, B, 1)
    ans = max(ans1, ans2)
    print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = [int(input()) for _ in range(n)]
a.sort()
front = a[n - 1]
back = a[n - 1]
i = 0
j = n - 2
ans = 0
while i <= j:
    diff1 = abs(front - a[i])
    diff2 = abs(back - a[i])
    diff3 = abs(front - a[j])
    diff4 = abs(back - a[j])
    mx = max(diff1, diff2, diff3, diff4)
    ans += mx
    if mx == diff1:
        front = a[i]
        i += 1
    elif mx == diff2:
        back = a[i]
        i += 1
    elif mx == diff3:
        front = a[j]
        j -= 1
    else:
        back = a[j]
        j -= 1
print(ans)

Submission status: Accepted

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

A = sorted(A)

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

print(ans)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = [int(input()) for i in range(N)]
    A.sort()
    le, ri = A[-1], A[-1]
    # print(le, ri)
    from collections import deque
    A = deque(A[:N-1])
    ans = 0
    for i in range(N-1):
        cur = [abs(A[0] - le), abs(A[-1] - ri),
               abs(A[-1] - le), abs(A[0] - ri)]
        #print(le, ri, cur)
        if max(cur) == cur[0]:
            c = A.popleft()
            ans += abs(c - le)
            le = c
        elif max(cur) == cur[1]:
            c = A.pop()
            ans += abs(c - ri)
            ri = c
        elif max(cur) == cur[2]:
            c = A.pop()
            ans += abs(c - le)
            le = c
        else:
            c = A.popleft()
            ans += abs(c - ri)
            ri = c
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

A.sort()
q = deque([A[0]])
i = 1
j = N-1
while i <= j:
    temp = max(abs(A[i]-q[0]), abs(A[j]-q[0]), abs(A[i]-q[-1]), abs(A[j]-q[-1]))
    if temp == abs(A[i]-q[0]):
        q.appendleft(A[i])
        i += 1
    elif temp == abs(A[j]-q[0]):
        q.appendleft(A[j])
        j -= 1
    elif temp == abs(A[i]-q[-1]):
        q.append(A[i])
        i += 1
    else:
        q.append(A[j])
        j -= 1
L = list(q)
ans = 0
for i in range(N-1):
    ans += abs(L[i+1]-L[i])
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = sorted([int(input()) for i in range(N)])
Ami = A[:N//2]
Ama = A[N//2:][::-1]
Ami2 = A[:(N+1)//2]
Ama2 = A[(N+1)//2:][::-1]

if N%2 == 1:
    ans = -2*sum(Ami)
    ans += 2*sum(Ama[:-2]) + Ama[-1]+Ama[-2]
    ans2 = -2*sum(Ami2[:-2]) - Ami2[-1]-Ami2[-2]
    ans2 += 2*sum(Ama2)
    print(max(ans2,ans))
else:
    ans = -2*sum(Ami[:-1]) - Ami[-1]
    ans += 2*sum(Ama[:-1]) + Ama[-1]
    print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

A.sort()
a1, b1 = A[:N//2], sorted(A[N//2:], reverse=True)
a2, b2 = A[:N//2+1], sorted(A[N//2+1:], reverse=True)

cand1 = 2 * sum(b1[:len(a1) - 1]) + sum(b1[len(a1) - 1:]) - (2 * sum(a1[:len(b1) - 1]) + sum(a1[len(b1) - 1:]))
cand2 = 2 * sum(b2[:len(a2) - 1]) + sum(b2[len(a2) - 1:]) - (2 * sum(a2[:len(b2) - 1]) + sum(a2[len(b2) - 1:]))
print(max(cand1, cand2))

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline

    N = int(input())
    A = [0] * N
    for i in range(N):
        A[i] = int(input())

    A.sort()
    i = 0
    j = N-1
    ans = A[j] - A[i]
    while j - i > 2:
        ans += A[j] - A[i+1] + A[j-1] - A[i]
        i += 1
        j -= 1
    if j - i == 2:
        ans += max(A[i+1] - A[i], A[i+2] - A[i+1])
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdin
n = int(stdin.readline().rstrip())
li = [int(stdin.readline().rstrip()) for _ in range(n)]
li.sort()
if n%2 == 1:
    mid = li[n//2]
    mae = li[:n//2]
    ushiro = li[n//2+1:]
    sono1 = -mid - mae[-1]
    sono1 += sum(ushiro)*2-sum(mae[:-1])*2
    sono2 = mid + ushiro[0]
    sono2 += sum(ushiro[1:])*2-sum(mae)*2
    print(max(sono1,sono2))
else:
    mae = li[:n//2]
    ushiro = li[n//2:]
    sono3 = -mae[-1] + ushiro[0]
    sono3 += sum(ushiro[1:])*2-sum(mae[:-1])*2
    print(sono3)

Submission status: Accepted

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

A.sort()
left = A[0]
right = A[N - 1]
ans = right - left
for i in range((N - 2) // 2):
    if i % 2 == 0:
        ans += right - A[1 + i]
        ans += A[N - 2 - i] - left
        right = A[1 + i]
        left = A[N - 2 - i]
    else:
        ans += left - A[1 + i]
        ans += A[N - 2 - i] - right
        left = A[1 + i]
        right = A[N - 2 - i]

if N % 2 == 1:
    ans += max(abs(right - A[N // 2]), abs(left - A[N // 2]))

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

if N % 2 == 0:
    s = N//2
    d = -2 * sum(A[:s]) + A[s-1] - A[s] + 2 * sum(A[s:])
else:
    s = N//2
    d1 = -2 * sum(A[:s]) - A[s] - A[s+1] + 2 * sum(A[s:])
    s += 1
    d2 = -2 * sum(A[:s]) + A[s-2] + A[s-1] + 2 * sum(A[s:])
    d = max(d1, d2)

print(d)

Submission status: Accepted

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

A.sort()

l,r = A[0],A[0]
cnt = 1
l_cnt = cnt
r_cnt = 1
ans1 = 0
while True:
    ans1 += abs(l-A[-r_cnt])
    l = A[-r_cnt]
    cnt += 1
    r_cnt += 1
    if cnt == N:
        break

    ans1 += abs(r-A[-r_cnt])
    r = A[-r_cnt]
    cnt += 1
    r_cnt += 1    
    if cnt == N:
        break

    ans1 += abs(l-A[l_cnt])
    l = A[l_cnt]
    cnt += 1
    l_cnt += 1
    if cnt == N:
        break

    ans1 += abs(r-A[l_cnt])
    r = A[l_cnt]
    cnt += 1
    l_cnt += 1
    if cnt == N:
        break

l,r = A[-1],A[-1]
cnt = 1
l_cnt = 0
r_cnt = 2
ans2 = 0
while True:
    ans2 += abs(l-A[l_cnt])
    l = A[l_cnt]
    cnt += 1
    l_cnt += 1
    if cnt == N:
        break

    ans2 += abs(r-A[l_cnt])
    r = A[l_cnt]
    cnt += 1
    l_cnt += 1
    if cnt == N:
        break

    ans2 += abs(l-A[-r_cnt])
    l = A[-r_cnt]
    cnt += 1
    r_cnt += 1
    if cnt == N:
        break

    ans2 += abs(r-A[-r_cnt])
    r = A[-r_cnt]
    cnt += 1
    r_cnt += 1    
    if cnt == N:
        break

print(max(ans1,ans2))

Submission status: Accepted

Solution code:
from collections import deque
import copy

N = int(input())
a = [int(input()) for i in range(N)]
a.sort()
b = copy.copy(a)

A = deque(a)

r = A[0]
l = A.popleft()

ans = 0
while True:
    if len(A) == 0:
        break
    c = A.pop()
    ans += abs(l-c)
    l = c
    if len(A) == 0:
        break
    c = A.pop()
    ans += abs(r-c)
    r = c
    if len(A) == 0:
        break
    c = A.popleft()
    ans += abs(l-c)
    l = c
    if len(A) == 0:
        break
    c = A.popleft()
    ans += abs(r-c)
    r = c

B = deque(b)
r = B[-1]
l = B.pop()
ans2 = 0
while True:
    if len(B) == 0:
        break
    c = B.popleft()
    ans2 += abs(l-c)
    l = c
    if len(B) == 0:
        break
    c = B.popleft()
    ans2 += abs(r-c)
    r = c
    if len(B) == 0:
        break
    c = B.pop()
    ans2 += abs(l-c)
    l = c
    if len(B) == 0:
        break
    c = B.pop()
    ans2 += abs(r-c)
    r = c
print(max(ans,ans2))

Submission status: Accepted

Solution code:
N = int(input())
A = [int(input()) for i in range(N)]
A.sort()
L, R = A[0], A[N-1]
S = R - L
x, y = 1, N - 2
while x <= y:
  a, b, c, d = abs(L-A[y]), abs(L-A[x]), abs(R-A[y]), abs(R-A[x])
  M = max(a, b, c, d)
  if M == a:
    L = A[y]
    y -= 1
    S += a
  elif M == b:
    L = A[x]
    x += 1
    S += b
  elif M == c:
    R = A[y]
    y -= 1
    S += c
  elif M == d:
    R = A[x]
    x += 1
    S += d
print(S)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import numpy as np
n = int(input())
A =sorted([int(input()) for _ in range(n)])
l = n//2
if n%2:
  a = 2*sum(A[n-(l-1):]) + A[n-l] + A[n-(l+1)] - 2*sum(A[:n-(l+1)])
  b = 2*sum(A[n-l:]) - A[n-(l+1)] - A[n-(l+2)] - 2*sum(A[:n-(l+2)])
  print(max(a, b))
else:
  t = 2*sum(A[n-(l-1):]) + A[n-l] - A[n-(l+1)] - 2*sum(A[:n-(l+1)])
  print(t)

Submission status: Accepted

Solution code:
N, *A = map(int, open(0))

A.sort()

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

Submission status: Accepted

Solution code:
from collections import deque
n=int(input())
a=[int(input()) for i in range(n)]
a.sort()
q=deque()
for i in range(n//2):
  if i%2==0:
    q.appendleft(a[n-i-1])
    q.append(a[i])
  else:
    q.appendleft(a[i])
    q.append(a[n-i-1])
ans=0
q1=list(q)
if n%2==0:
  for i in range(n-1):
    ans+=abs(q1[i]-q1[i+1])
  print(ans)
else:
  for i in range(len(q1)-1):
    ans+=abs(q1[i]-q1[i+1])
  print(ans+max(abs(a[n//2]-q1[0]),abs(a[n//2]-q1[len(q1)-1])))

Submission status: Accepted

Solution code:
def main():
  N, *A = map(int, open(0).read().split())
  A.sort()

  if N % 2:
    array1 = [-2] * (N // 2) + [1] * 2 + [2] * (N // 2 - 1)
    array2 = [-2] * (N // 2 - 1) + [-1] * 2 + [2] * (N // 2)
  
    ret1 = 0
    ret2 = 0
    for i, j, k in zip(A, array1, array2):
      ret1 += i * j
      ret2 += i * k
    ret = max(ret1, ret2)

  else:
    array1 = [-2] * (N // 2 - 1) + [-1] + [1] + [2] * (N // 2 - 1)
  
    ret = 0
    for i, j in zip(A, array1):
      ret += i * j
  
  print(ret)

  
if __name__=="__main__":
  main()

Submission status: Accepted

Solution code:
def main():
  N, *A = map(int, open(0).read().split())
  A.sort()

  if N % 2:
    array1 = [-2] * (N // 2) + [1] * 2 + [2] * (N // 2 - 1)
    array2 = [-2] * (N // 2 - 1) + [-1] * 2 + [2] * (N // 2)
  
    ret1 = 0
    ret2 = 0
    for i in range(N):
      ret1 += A[i]*array1[i] 
      ret2 += A[i]*array2[i]
    ret = max(ret1, ret2)

  else:
    array1 = [-2] * (N // 2 - 1) + [-1] + [1] + [2] * (N // 2 - 1)
  
    ret = 0
    for i in range(N):
      ret += A[i]*array1[i] 
  
  print(ret)

  
if __name__=="__main__":
  main()

Submission status: Accepted

Solution code:
import numpy as np


def main():
  N, *A = map(int, open(0).read().split())
  A.sort()
  A = np.array(A)

  if N % 2:
    array1 = np.array([-2] * (N // 2) + [1] * 2 + [2] * (N // 2 - 1))
    array2 = np.array([-2] * (N // 2 - 1) + [-1] * 2 + [2] * (N // 2))
  
    ret1 = np.dot(A, array1)
    ret2 = np.dot(A, array2)
    ret = max(ret1, ret2)

  else:
    array1 = np.array([-2] * (N // 2 - 1) + [-1] + [1] + [2] * (N // 2 - 1))
  
    ret = np.dot(A, array1)
  
  print(ret)
  
if __name__=="__main__":
  main()

Submission status: Accepted

Solution code:
N, *A = map(int, open(0).read().split())
A.sort()

if N % 2:
  array1 = [-2] * (N // 2) + [1] * 2 + [2] * (N // 2 - 1)
  array2 = [-2] * (N // 2 - 1) + [-1] * 2 + [2] * (N // 2)
  
  ret1 = 0
  ret2 = 0
  for i in range(N):
    ret1 += A[i]*array1[i] 
    ret2 += A[i]*array2[i]
  ret = max(ret1, ret2)

else:
  array1 = [-2] * (N // 2 - 1) + [-1] + [1] + [2] * (N // 2 - 1)
  
  ret = 0
  for i in range(N):
    ret += A[i]*array1[i] 
  
print(ret)

Submission status: Accepted

Solution code:
def calc(A):
    res = 0
    
    for i in range(N-1):
        res += abs(A[i+1]-A[i])
    
    return res

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

if N%2==0:
    l1 = A[:N//2]
    l2 = A[N//2:]
    l1.reverse()
    l2.reverse()
    B = [-1]*N
    
    for i in range(N):
        if i%2==0:
            B[i] = l1[i//2]
        else:
            B[i] = l2[i//2]
            
    ans = calc(B)
    print(ans)
else:
    l1 = A[:N//2]
    l2 = A[N//2:]
    B = [-1]*N
    B[0] = l2[0]
    B[-1] = l2[1]
    
    for i in range(1, N-1):
        if i%2==0:
            B[i] = l2[i//2+1]
        else:
            B[i] = l1[i//2]
    
    l1 = A[:N//2+1]
    l2 = A[N//2+1:]
    C = [-1]*N
    C[0] = l1[-1]
    C[-1] = l1[-2]
    
    for i in range(1, N-1):
        if i%2==0:
            C[i] = l1[i//2-1]
        else:
            C[i] = l2[i//2]
   
    ans = max(calc(B), calc(C))
    print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

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

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

A.sort()

ans = 0

for t in range(2):
	coef = [0] * N
	for i in range(N):
		k = 0
		if i == 0 or i == N-1:
			k = 1 
		else:
			k = 2
		if (t + i) % 2 == 1:
			k = -k
		coef[i] = k
	coef.sort()

	val = 0
	for i in range(N):
		val += coef[i] * A[i]

	ans = max(ans, val)

print(ans)

Submission status: Accepted

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

    def make1():
        d = deque(A)
        ret = deque([d.popleft()])
        for i in range((N-1)//2):
            if i & 1:
                j = d.popleft()
                k = d.popleft()
            else:
                j = d.pop()
                k = d.pop()
            if abs(ret[0] - j) < abs(ret[-1] - j):
                ret.appendleft(j)
                ret.append(k)
            else:
                ret.append(j)
                ret.appendleft(k)
        if len(d) == 1:
            j = d.pop()
            if abs(ret[0] - j) < abs(ret[-1] - j):
                ret.append(j)
            else:
                ret.appendleft(j)
        ans = 0
        for i in range(1, N):
            ans += abs(ret[i-1] - ret[i])
        return ans

    def make2():
        d = deque(A)
        ret = deque([d.pop()])
        for i in range((N-1)//2):
            if i & 1:
                j = d.pop()
                k = d.pop()
            else:
                j = d.popleft()
                k = d.popleft()
            if abs(ret[0] - j) < abs(ret[-1] - j):
                ret.appendleft(j)
                ret.append(k)
            else:
                ret.append(j)
                ret.appendleft(k)
        if len(d) == 1:
            j = d.pop()
            if abs(ret[0] - j) < abs(ret[-1] - j):
                ret.append(j)
            else:
                ret.appendleft(j)
        ans = 0
        for i in range(1, N):
            ans += abs(ret[i-1] - ret[i])
        return ans

    print(max(make1(), make2()))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,hypot,log #log2ないｙｐ
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
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N=I()
    A=LIN(N)
    
    def solve(odd):
        s1 = sorted(A)
        s2 = sorted(A,reverse=True)


        if odd:
            s1,s2 = s2,s1
        
        q = deque([s1.pop()])

        sign = False
        for i in range(N):
            if sign:
                v = s1.pop()
            else:
                v = s2.pop()
            q.appendleft(v)

            if len(s1)+len(s2)<=N:
                break
            
            if sign:
                v = s1.pop()
            else:
                v = s2.pop()
            q.append(v)
            
            if len(s1)+len(s2)<=N:
                break
            sign ^= 1

        res = 0
        before = q[0]
        for a in q:
            res += abs(before-a)
            before = a

        return res 

    print(max(solve(1),solve(0)))
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/tenka1-2018-beginner/tasks/tenka1_2018_c
# 直感的には大きい小さいを交互に並べれば良さそうだが...?

# Nが偶数なら交互でok
# Nが奇数なら、短い方を真ん中に入れれば良い

# 1 5 7 10
# 1 10 5 7 →16# 最後に行くに連れ差は少なくなってく
# 1 7 5 10 →13# 差がマイルドになるのでは?

# ソートしたとき一番最初と一番最後は必ず差が最大。
# それ以外の選び方をした場合差はそれより必ず小さくなるので、ソートの端から選んでいくのが最適だとわかる。
# しかし最後に関しては差が小さく微妙。実は中央値を先頭に付け足したほうが良い。

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

A.sort()


# もしNが偶数のとき
if N & 1 == 0:
    now = A[N // 2]
    ans = 0
    for i in range(N // 2):
        for idx in [i, -(i + 1)]:
            if idx == -N // 2:
                break
            ans += abs(now - A[idx])
            now = A[idx]
    print(ans)
else:  # Nが奇数のとき
    # med = A[N // 2]
    # med_score = max(A[0] - med, A[-1] - med)

    now = A[N // 2]
    ans1 = 0
    for i in range(N // 2):
        for idx in [i, -(i + 1)]:
            ans1 += abs(now - A[idx])
            now = A[idx]

    now = A[N // 2]
    ans2 = 0
    for i in range(N // 2):
        for idx in [-(i + 1), i]:
            ans2 += abs(now - A[idx])
            now = A[idx]
    # print(ans1, ans2)
    print(max(ans1, ans2))

Submission status: Accepted

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

a1 = []
a2 = []
a1.append(a[n//2])
a2.append(a[n//2])

for i in range((n-1)//2):
    a1.append(a[i])
    a1.append(a[n-i-1])
    
    a2.append(a[n-i-1])
    a2.append(a[i])
if not n%2:
    a1.append(a[n//2-1])
    a2.append(a[n//2-1])

ans1 = 0
ans2 = 0
for i in range(len(a1)-1):
    ans1 += abs(a1[i+1] -a1[i])
    ans2 += abs(a2[i+1]-a2[i])
print(max(ans1,ans2))