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:
from collections import deque
N = int(input())
A = deque(sorted([int(input()) for i in range(N)]))

X = deque([A.popleft()])
ans = 0
for i in range(N - 1):
    # Aのどちらから取り出してXのどちらに入れるか
    left_left = abs(X[0] - A[0])
    left_right = abs(X[-1] - A[0])
    right_left = abs(X[0] - A[-1])
    right_right = abs(X[-1] - A[-1])

    if left_left >= max(left_right, right_left, right_right):
        ans += left_left
        X.appendleft(A.popleft())

    elif left_right >= max(left_left, right_left, right_right):
        ans += left_right
        X.append(A.popleft())

    elif right_left >= max(left_left, left_right, right_right):
        ans += right_left
        X.appendleft(A.pop())

    else:
        ans += right_right
        X.append(A.pop())

print(ans)

Submission status: Accepted

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

A = sorted(A)
q = deque()
q.append(A[0])
i = 1
j = N - 1
mi = True
while i < N and j >= 0 and i <= j:
    if mi:
        p1, p2 = q[0], q[-1]
        q1, q2, q3, q4 = abs(A[j] - p1), abs(A[j] - p2), abs(A[i] - p1), abs(A[i] - p2)
        qm = max(q1, q2, q3, q4)
        if qm == q1:
            q.appendleft(A[j])
            j -= 1
        elif qm == q2:
            q.append(A[j])
            j -= 1
        elif qm == q3:
            q.appendleft(A[i])
            i += 1
        else:
            q.append(A[i])
            i += 1

num = 0
pre = q[0]
for i in range(1, N):
    num += abs(q[i] - pre)
    pre = q[i]

print(num)

Submission status: Accepted

Solution code:
import math
N = int(input())
A = [int(input()) for _ in range(N)]
A.sort()
B = A.copy()
B.reverse()
halfN = N / 2

def func(arr):
  ans = 0
  i = -1
  prev = [arr[0]]
  for _ in range(math.ceil((N-1)/2)):
    if i > 0:
      if i >= halfN:
        ans += max([abs(p - arr[i-1]) for p in prev])
      else:
        ans += abs(max(prev) - arr[i-1]) + abs(min(prev) - arr[i])
        prev = [arr[i-1], arr[i]]
    else:
      if -i >= halfN:
        ans += max([abs(p - arr[i]) for p in prev])
      else:
        ans += abs(max(prev) - arr[i-1]) + abs(min(prev) - arr[i])
        prev = [arr[i-1], arr[i]]
    i = -i-1 if i >= 0 else -i+1
  return ans

print(max(func(A), func(B)))

Submission status: Accepted

Solution code:
N = int(input())
l = []

for i in range(N):
    X = int(input())
    l.append(X)

l1 = sorted(l)
l2 = sorted(l, reverse=True)

if N%2 == 0:
    result = 0
    for i in range(N//2):
        if i == N//2-1:
            result = result + l2[i] - l1[i]
        else:
            result = result + 2 * l2[i] - 2 * l1[i]
    print(result)
else:
    result1 = 0
    for i in range(N//2):
        result1 += 2 * l2[i]
    for i in range(N//2 - 1):
        result1 -= 2 * l1[i]
    result1 = result1 - l1[N//2 - 1] - l1[N//2]

    result2 = 0
    for i in range(N//2 - 1):
        result2 += 2 * l2[i]
    for i in range(N//2):
        result2 -= 2 * l1[i]
    result2 = result2 + l1[N//2] + l1[N//2 + 1]
    print(max(result1, result2))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
a=sorted([int(input()) for i in range(n)])
a1=a[:n//2]
a2=a[n//2:]
a2.sort(reverse=True)
a2=[a2[-1]]+a2[:-1]
b=[]
for i in range(n):
  if i%2==0:
    b.append(a2[i//2])
  else:
    b.append(a1[i//2])
s=0
p=b[0]
for i in range(1,n):
  s+=abs(p-b[i])
  p=b[i]

if n%2==0:
  print(s)
  exit()
a1=a[:n//2+1]
a2=a[n//2+1:]
a2.sort(reverse=True)
a1=[a1[-1]]+a1[:-1]


b=[]
for i in range(n):
  if i%2==0:
    b.append(a1[i//2])
  else:
    b.append(a2[i//2])
t=0
p=b[0]
p
for i in range(1,n):
  t+=abs(p-b[i])
  p=b[i]
  
print(max(s,t))

Submission status: Accepted

Solution code:
def f(res):
    ans = 0
    # print(res)
    for i in range(n - 1):
        ans += abs(res[i] - res[i + 1])
    return ans
n = int(input())
l = sorted([int(input()) for _ in range(n)])
r = [[l[i], l[n - 1 - i]] for i in range(n//2)]
if n & 1:
    r += [[l[n//2]]]

res1, res2 = [], []

for p in r:
    res1 += p[::-1]
for p in r:
    res2 += p
res1 = [res1[-1]] + res1[:-1]
res2 = [res2[-1]] + res2[:-1]
ans = max(f(res1), f(res2))

print(ans)

Submission status: Accepted

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

if n % 2 == 0:
    for i in range(n//2):
        b.append(a[i])
        b.append(a[-(i+1)])
else:
    for i in range(n//2):
        b.append(a[i])
        b.append(a[-(i+1)])
    b.append(a[n//2])

ans = 0
for i in range(n-1):
    ans += abs(b[i] - b[i+1])
ans += abs(b[0] - b[n-1])
b.sort()
if n % 2 == 0:
    ans -= abs(b[n // 2] - b[n // 2 - 1])
else:
    ans -= min(abs(b[n//2] - b[n//2-1]), abs(b[n//2] - b[n//2+1]))

print(ans)

Submission status: Accepted

Solution code:
#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#

"""
Tenka1-2018 C
"""

n = int(input())
ali = [int(input()) for i in range(n)]
ali.sort()

if n % 2 is 1:
    m = (n-1)//2
    am = ali[m]
    asmall = ali[:m]
    abig = ali[m+1:]
    if 2*am-asmall[-1]-abig[0] > 0:
        ans = am-2*sum(asmall)+2*sum(abig)-abig[0]
    else:
        ans = -am+2*sum(abig)-2*sum(asmall)+asmall[-1]
else:
    m = n//2
    asmall = ali[:m]
    abig = ali[m:]
    ans = -2*sum(asmall)+2*sum(abig)-abig[0]+asmall[-1]

print(ans)

Submission status: Accepted

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

c = v[n // 2]
ans = 0
for i in range(n):
    ans += 2 * abs(v[i] - c)

if (n % 2 == 0):
    ans -= c - v[n//2 - 1]
else:
    ans -= min(v[n//2+1]-c, c-v[n//2-1])

print(ans)

Submission status: Accepted

Solution code:
def makelist(n, m):
    return [[0 for _ in range(m)] for _ in range(n)]


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


A.sort()

dp1 = [0]*N
dp2 = [0]*N

ans = 0
if N % 2 == 0:
    for i in range(N//2):
        ind = i * 2 + 1
        dp1[ind] = A[i]
            
    for i in range(N//2, N):
        ind = (i - N//2) * 2
        dp1[ind] = A[i]
        
    for i in range(N-1):
        ans += abs(dp1[i] - dp1[i+1])
else:
    # miniを多く
    dp1[0] = A[N//2-1]
    dp1[-1] = A[N//2]
    for i in range(N//2-1):
        ind = (i+1) * 2
        dp1[ind] = A[i]
    for i in range(N//2 + 1, N):
        ind = (i - (N//2+1)) * 2 + 1
        dp1[ind] = A[i]

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


    # maxを多く
    dp2[0] = A[N//2]
    dp2[-1] = A[N//2+1]
    for i in range(N//2):
        ind = i * 2 + 1
        dp2[ind] = A[i]
    for i in range(N//2 + 2, N):
        ind = (i - (N//2+1)) * 2
        dp2[ind] = A[i]

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
A = sorted([int(input()) for _ in range(N)])
ans = 0
if N%2 == 0:
    B = []
    for i in range(N//2)[::-1]:
        if i%2:
            B.append(-i-1)
        else:
            B.append(i)
    for i in range(N//2):
        if i%2:
            B.append(i)
        else:
            B.append(-i-1)
    S = [A[b] for b in B]
    for i in range(N-1):
        ans += abs(S[i+1] - S[i])
else:
    M = N//2
    B = list(range(1, M+2))[::-1] + list(range(1, M+1))
    S = []
    for i, b in enumerate(B):
        if i%2:
            S.append(A[-b])
        else:
            S.append(A[b-1])
    for i in range(N-1):
        ans += abs(S[i+1] - S[i])

    S = []
    for i, b in enumerate(B):
        if i%2:
            S.append(A[b-1])
        else:
            S.append(A[-b])
    tmp = 0
    for i in range(N-1):
        tmp += abs(S[i+1] - S[i])
    ans = max(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools
import numpy as np


# いっこ入力
n =int(input())

# n行の数をリストへ
a = [int(input()) for i in range(n)] 
a = sorted(a)
b=[0]*(n//2)
c=[0]*(n//2)
answer = 0
for i in range(0,n//2):
    b[i] = a[i]
    c[i] = a[n-i-1]
answer += c[0] - b[0]
for i in range(1,n//2):
    answer += c[i-1] - b[i]
    answer += c[i] - b[i-1]


if n % 2 == 1:
    answer += max(c[-1]-a[(n-1)//2],a[(n-1)//2]-b[-1])

print(answer)

Submission status: Accepted

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

a.sort()

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

    if(left == mid or right == mid): break
    ans1 += abs(a[right] - a[left])
    left += 1
    

left = 0
right = n - 1
mid = right // 2
if(right % 2 != 0): mid += 1
ans2 = abs(a[mid] - a[left])
while(True):
    if(left == mid or right == mid): break
    ans2 += abs(a[right] - a[left])
    left += 1

    if(left == mid or right == mid): break
    ans2 += abs(a[right] - a[left])
    right -= 1

if(ans1 > ans2): print(ans1)
else: print(ans2)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from collections import deque

n = ni()
a = []
for _ in range(n):
    a.append(ni())
    
mx_cent = [ai for ai in a]
mn_cent = [ai for ai in a]    

a.sort()
a = deque(a)

mx_cent = deque([ai for ai in a])
mn_cent = deque([ai for ai in a])


bmx = deque([mx_cent.pop()])
bmn = deque([mn_cent.popleft()])

cnt = 0


while len(mx_cent) > 1:
    lf = 0
    rt = 0
    if cnt % 2 == 0:
        lf = mx_cent.popleft()
        rt = mx_cent.popleft()
    else:
        lf = mx_cent.pop()
        rt = mx_cent.pop()
    
    bmx.appendleft(lf)
    bmx.append(rt)
    
    
    if cnt % 2 == 0:
        lf = mn_cent.pop()
        rt = mn_cent.pop()
    else:
        lf = mn_cent.popleft()
        rt = mn_cent.popleft()
    
    bmn.appendleft(lf)
    bmn.append(rt)
    
    cnt += 1


if len(mx_cent) == 1:
    last = mx_cent.pop()
    if abs(bmx[0] - last) > abs(bmx[-1] - last):
        bmx.appendleft(last)
    else:
        bmx.append(last)
        
    last = mn_cent.pop()
    if abs(bmn[0] - last) > abs(bmn[-1] - last):
        bmn.appendleft(last)
    else:
        bmn.append(last)

diffmx, diffmn = 0, 0        
for i in range(n-1):
    diffmx += abs(bmx[i+1] - bmx[i])
    diffmn += abs(bmn[i+1] - bmn[i])
    
print(max(diffmx, diffmn))

Submission status: Accepted

Solution code:
 
import collections, atexit, math, sys, bisect 
 
def getIntList():
    return list(map(int, input().split()))    
 
 
N, = getIntList()
#print(N)
za = []
for i in range(N):
    a = input()
    a = int(a)
    za.append(a)

za.sort()

if N%2==0:
    t = N//2
    s0 = sum(za[:t])
    s1 = sum(za[t:])
    res = s1*2 - s0 *2  - za[t] + za[t-1]
else:
    t = N//2 + 1
    s0 = sum(za[:t])
    s1 = sum(za[t:])
    res0 = s1 *2 - s0*2 + za[t-1] + za[t-2]
    t = t - 1
    s0 = sum(za[:t])
    s1 = sum(za[t:])
    res1 = s1 *2 - s0*2 -  za[t] - za[t+1]
    res = max(res1, res0)

print(res)

Submission status: Accepted

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

for i in range(N):
    A.append(int(input()))

A.sort()

if N % 2 == 0:
    start = N // 2 - 1
    end = start + 1
else:
    start = N // 2
    if A[start] - A[start-1] > A[start+1] - A[start]:
        end = start + 1
    else:
        end = start - 1

result = 0

for i in range(N):
    if i == start or i == end:
        result += abs(A[i] - A[start])
    else:
        result += abs(A[i] - A[start]) * 2

print(result)

Submission status: Accepted

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

ans = 0
if N%2 == 0:
    c1, c2 = A[N//2-1], A[N//2]
    del A[N // 2-1]
    del A[N // 2-1]
    for a in A:
        ans += abs(a-c1)*2
    ans += c2-c1
else:
    c = A[N//2]
    c1, c2 = A[N//2-1], A[N//2+1]
    ans -= min(abs(c-c1), abs(c-c2))
    for a in A:
        ans += abs(a-c) * 2
print(ans)

Submission status: Accepted

Solution code:
# encoding:utf-8
from collections import deque

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

	v1 = nums.popleft()
	v2 = nums.pop()
	ans = v2 - v1
	#print(v1, v2)
	
	while len(nums) > 0:
		w1 = abs(nums[-1] - v1)
		w2 = abs(nums[-1] - v2)
		w3 = abs(nums[0] - v1)
		w4 = abs(nums[0] - v2)
		max_w = max(w1, w2, w3, w4)
		
		if w1 == max_w:
			ans += w1
			v1 = nums.pop()
		elif w2 == max_w:
			ans += w2
			v2 = nums.pop()
		elif w3 == max_w:
			ans += w3
			v1 = nums.popleft()
		else:
			ans += w4
			v2 = nums.popleft()
		#print(v1, v2)
	print(ans)

	


if __name__ == '__main__':
	main()

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from sys import stdin
def main():
    n = int(stdin.readline())
    a = [int(stdin.readline()) for _ in xrange(n)]
    a.sort()
    h = n / 2
    def solve(l, m):
        res = sum(m) - sum(l)
        res *= 2
        if len(l) < len(m):
            res -= m[0] + m[1]
        else:
            res += l[-1] + l[-2]
        return res
    if n % 2:
        print max(solve(a[:h], a[h:]), solve(a[:h+1], a[h+1:]))
    else:
        ans = 0
        for i in xrange(n / 2):
            ans += a[i+h] - a[i]
        ans = ans * 2 + a[h-1] - a[h]
        print ans
main()

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
a = deque([])
for i in range(n):
  x = int(input())
  a.append(x)
a=sorted(a)
a1 = deque(a)
b = deque([])
b.append(a1.popleft())
i = 0
while a1:
  if i%2 == 1:
    b.append(a1.popleft())
    if a1 == deque([]):
      break
    b.appendleft(a1.popleft())
    i += 1
  else:
    b.append(a1.pop())
    if a1 == deque([]):
      break
    b.appendleft(a1.pop())
    i += 1
ans = 0
for i in range(1,n):
  ans += abs(b[i] - b[i-1])
a = deque(a)
b = deque([])
b.append(a.pop())
i = 0
while a:
  if i%2 == 0:
    b.append(a.popleft())
    if a == deque([]):
      break
    b.appendleft(a.popleft())
    i += 1
  else:
    b.append(a.pop())
    if a == deque([]):
      break
    b.appendleft(a.pop())
    i += 1
ans2 = 0
for i in range(1,n):
  ans2 += abs(b[i] - b[i-1])
ans = max(ans,ans2)
print(ans)

Submission status: Accepted

Solution code:
# C
N = int(input())
A_list = [0]*N
for i in range(N):
    A_list[i] = int(input())
res = 0
A_list_s = sorted(A_list)

if N % 2 == 0:
    bar = A_list_s[N // 2]
    for i in range(N // 2):
        res += 2*(bar - A_list_s[i]) + 2*(A_list_s[N-1-i] - bar)
    res -= bar - A_list_s[N // 2 - 1]
else:
    bar = A_list_s[N // 2]
    for i in range(N // 2):
        res += 2*(bar - A_list_s[i]) + 2*(A_list_s[N-1-i] - bar)
    res -= min(bar - A_list_s[N // 2 - 1], A_list_s[N // 2 + 1] - bar)
print(res)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(input()) for i in range(N)]
A.sort()
def calc(A):
    p = 0; q = N-2
    l = r = A[N-1]
    res = 0
    while p < q:
        a = A[p]; b = A[p+1]
        res += abs((l+r) - (a+b))
        p += 2
        l = a; r = b

        if not p < q:
            break

        a = A[q]; b = A[q-1]
        res += abs((l+r) - (a+b))
        l = a; r = b
        q -= 2

    if p == q:
        v = A[p]
        res += max(abs(l-v), abs(r-v))
    return res
s = calc(A)
A.reverse()
t = calc(A)

print(max(s, t))

Submission status: Accepted

Solution code:
import sys

n = int(input())
aaa = [int(line) for line in sys.stdin.readlines()]
aaa.sort()
if n % 2 == 0:
    m1, m2 = aaa[n // 2 - 1], aaa[n // 2]
    mid = sum(abs(a - m1) for a in aaa)
    ans = mid * 2 - (m2 - m1)
else:
    m1, m2, m3 = aaa[n // 2 - 1], aaa[n // 2], aaa[n // 2 + 1]
    mid = sum(abs(a - m2) for a in aaa)
    ans = mid * 2 - min(m2 - m1, m3 - m2)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = [int(input()) for _ in range(n)]
a = sorted(a)
res = a[-1]-a[0]
minn,maxx = a[0],a[-1]
for i in range(1,n//2):
    res += maxx - a[i]
    res += a[-1-i] - minn
    minn,maxx = a[i],a[-1-i]
if n%2==1:
    res += max(abs(maxx-a[n//2]),abs(minn-a[n//2]))
print(res)

Submission status: Runtime Error

Solution code:
import sys
n = int(input())
ls = [0] * n
for i in range(n):
    ls[i] = int(input())
ls.sort()
# 長さ2なら例外処理する
if n == 2:
    print(abs(ls[0],ls[1]))
    sys.exit()
if n % 2 == 1:
    # biggerを2つとる方
    smaller = ls[:n//2+1]
    bigger = ls[n//2+1:]
    diff_1 = 2 * sum(bigger) - 2*sum(smaller) + smaller[-1] + smaller[-2]
    # smallerを2つとる方
    smaller = ls[:n//2]
    bigger = ls[n//2:]
    diff_2 = -2 * sum(smaller) + 2 * sum(bigger) - bigger[0] - bigger[1]
    diff = max(diff_1,diff_2)
else:
    smaller = ls[:n//2]
    bigger = ls[n//2:]
    diff = 2 * sum(bigger) - min(bigger) - 2 * sum(smaller) + max(smaller)

print(diff)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
def solve():
  n = int(input())
  a = [int(input()) for _ in range(n)]
  query = deque([])
  a = sorted(a,reverse = True)
  big = []
  small = []
  for i in range(n):
    if i< n//2:
      big.append(a[i])
    else:
      small.append(a[i])
  small.sort()       
  if n%2 != 0:
    query.append(big.pop(0))
  else:
    if n == 2:
      query.append(big.pop(0))
    else:
      t,d = big[0],big[1]
      l,r = small[0],small[1]
      if big[0]+big[1]-small[0] >= abs(small[0]-big[0])+abs(small[1]-big[0]):
        query.append(small.pop(0))
      else:
        query.append(big.pop(0))
    
  number = 1
  noright = False
  
  while len(big) > 0 or len(small) > 0:
    if number %2 == 0:
      leftnumber = big.pop(0)
      if len(big)!= 0:
        rightnumber = big.pop(0)
      else:
        noright = True
    else:
      leftnumber = small.pop(0)
      if len(small) != 0:
        rightnumber = small.pop(0)
      else:
        noright = True
    query.appendleft(leftnumber)
    if not noright:
      query.append(rightnumber)
    number += 1
    noright = False

  ans = 0
  for i in range(len(query)-1):
    ans += abs(query[i+1]-query[i])
    
  query2 = [query[n-1]]
  for i in range(n-1):
    query2.append(query[i])
  ans2 = 0
  for i in range(len(query)-1):
    ans2 += abs(query2[i+1]-query2[i])
    
  query3 = [query[0]]
  for i in range(n-1):
    query3.append(query[i+1])
  ans3 = 0
  
  for i in range(len(query)-1):
    ans3 += abs(query3[i+1]-query3[i])
  print(max([ans,ans2,ans3]))
solve()

Submission status: Runtime Error

Solution code:
def swap(a, b, k):
    if k % 2 == 0:
        if a % 2 == 1:
            a -= 1
        return a/2, b+a/2
    if b % 2 == 1:
        b -= 1
    return int(a+b/2), int(b/2)


if __name__ == '__main__':
    a, b, k = list(map(int, input().split()))
    for i in range(k):
        a,b = swap(a,b,i)
    print(int(a), int(b))

Submission status: Runtime Error

Solution code:
from itertools import accumulate


class CoeffTable:
    def __init__(self, n):
        self.n = n
        if n == 2:
            (self.p2, self.p1, self.m1, self.m2) = (0, 1, 1, 0)
        if n % 2 == 0:
            self.p1 = self.m1 = 1
            self.p2 = self.m2 = (n - 1) // 2
        else:
            self.p1 = 0
            self.m1 = 2
            self.p2 = (n - 1) // 2
            self.m2 = (n - 2) // 2
        if self.p2 + self.p1 + self.m1 + self.m2 != n:
            raise ValueError(f"n = {n}, {str(self)}")

    def reverse(self):
        (self.p2, self.p1, self.m1, self.m2) = (
            self.m2,
            self.m1,
            self.p1,
            self.p2,
        )

    def cumsum(self):
        return list(accumulate([self.p2, self.p1, self.m1, self.m2]))

    def __str__(self):
        return (
            f"(p2, p1, m1, m2) = ({self.p2}, {self.p1}, {self.m1}, {self.m2})"
        )


def main(n, seq):
    seq = sorted(seq, reverse=True)
    coeff = CoeffTable(n)
    cm = coeff.cumsum()
    ans1 = (
        2 * sum(seq[0 : cm[0]])
        + 1 * sum(seq[cm[0] : cm[1]])
        - 1 * sum(seq[cm[1] : cm[2]])
        - 2 * sum(seq[cm[2] : cm[3]])
    )
    coeff.reverse()
    rcm = coeff.cumsum()
    ans2 = (
        2 * sum(seq[0 : rcm[0]])
        + 1 * sum(seq[rcm[0] : rcm[1]])
        - 1 * sum(seq[rcm[1] : rcm[2]])
        - 2 * sum(seq[rcm[2] : rcm[3]])
    )
    ans = max(ans1, ans2)
    print(ans)
    return


if __name__ == "__main__":
    n = int(input())
    sample = []
    for _ in range(n):
        sample.append(int(input()))
    main(n, sample)

Submission status: Runtime Error

Solution code:
def distance(a,b):
	return abs(a[0]-b[0])+abs(a[1]-b[1])


n=0

H,W=input().split()
H=int(H)
W=int(W)
r=[]
for i in range(H):
	r.append(input().split())
stones=[]
print(r)
for i in range(H):
	for j in range(W):
		if(r[i][0][j]=="#"):
			stones.append([j,i])

for i in range(len(stones)):
	for j in range(i+1,len(stones)):
		d=distance(stones[i],stones[j])
		for k in range(j+1,len(stones)):
			if(distance(stones[i],stones[k])>d or distance(stones[j],stones[k])>d):
				continue
			if(distance(stones[i],stones[k])==distance(stones[j],stones[k])==d):
				n+=1
				print(stones[i],stones[j],stones[k])
print(n)

Submission status: Runtime Error

Solution code:
import itertools
import sys
H, W = [int(i) for i in input().split(' ')]

cross = [[0] * (H + W -1) for _ in range(H + W - 1)]
for i, line in enumerate(sys.stdin):
    for j, c in enumerate(line.strip()):
        if c == "#":
            cross[i+j][i-j+W-1] = 1

across = [[0] + list(itertools.accumulate(xs)) for xs in cross]
r_cross = [[xs[i] for xs in cross] for i in range(H + W - 1)]
across2 = [[0] + list(itertools.accumulate(xs)) for xs in r_cross]

r = 0
for i in range(H+W-1):
    for j in range(H+W-1):
        if cross[i][j] != 1:
            continue
        for k in range(j+1, H+W-1):
            if cross[i][k] == 1:
                if i - (k-j) >= 0:
                    r += across[i - (k - j)][k+1] - across[i - (k - j)][j]
                if i + (k-j) < H + W - 1:
                    r += across[i + (k - j)][k+1] - across[i + (k - j)][j]

for i in range(H+W-1):
    for j in range(H+W-1):
        if cross[j][i] != 1:
            continue
        for k in range(j+1, H+W-1):
            if cross[k][i] == 1:
                if i - (k-j) >= 0:
                    r += across2[i - (k - j)][k] - across2[i - (k - j)][j+1]
                if i + (k-j) < H + W - 1:
                    r += across2[i + (k - j)][k] - across2[i + (k - j)][j+1]

print(r)

Submission status: Runtime Error

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

B = []
for i in range(N):
    if i==0 or i==N-1:
        B.append((-1)**i)
    else:
        B.append(((-1)**i)*2)
B.sort()

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

Submission status: Runtime Error

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

B = []
for i in range(N):
    if i==0 or i==N-1:
        B.append((-1)**i)
    else:
        B.append(((-1)**i)*2)
B.sort()

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

Submission status: Runtime Error

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

A.sort()

B = []
for i in range(N):
    if i==0 or i==N-1:
        B[].append((-1)**i)
    else:
        B[i].append(((-1)**i)*2)
B.sort()

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

Submission status: Runtime Error

Solution code:
#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#

"""
tenka1-2018 E
"""

from itertools import product
from itertools import combinations

h, w = map(int, input().split())
slili = [list(input()) for i in range(h)]

coinsetli = [set() for i in range(h+w)]
for i, j in product(range(h), range(w)):
    if slili[i][j] == '#':
        coinsetli[i+j+1].add(j-i)

coinacumdictli = [{} for i in range(h+w)]
for i in range(1, h+w):
    tmp = 0
    for j in range(-300, 301):
        if j in coinsetli[i]:
            tmp += 1
        coinacumdictli[i][j] = tmp

ansdouble = 0
for i in range(1, h+w):
    for x, y in combinations(coinsetli[i], 2):
        j = abs(x-y)
        x, y = (min(x, y), max(x, y))
        if i-j >= 1:
            ansdouble += coinacumdictli[i-j][y]+coinacumdictli[i-j][y-1] - coinacumdictli[i-j][x] - coinacumdictli[i-j][x-1]
        if i+j <= h+w-1:
            ansdouble += coinacumdictli[i+j][y]+coinacumdictli[i+j][y-1] - coinacumdictli[i+j][x] - coinacumdictli[i+j][x-1]

# repeat after reversing along the vertical axis
for i in range(h):
    slili[i].reverse()

coinsetli = [set() for i in range(h+w)]
for i, j in product(range(h), range(w)):
    if slili[i][j] == '#':
        coinsetli[i+j+1].add(j-i)

coinacumdictli = [{} for i in range(h+w)]
for i in range(1, h+w):
    tmp = 0
    for j in range(-300, 301):
        if j in coinsetli[i]:
            tmp += 1
        coinacumdictli[i][j] = tmp

for i in range(1, h+w):
    for x, y in combinations(coinsetli[i], 2):
        j = abs(x-y)
        x, y = (min(x, y), max(x, y))
        if i-j >= 1:
            ansdouble += coinacumdictli[i-j][y]+coinacumdictli[i-j][y-1] - coinacumdictli[i-j][x] - coinacumdictli[i-j][x-1]
        if i+j <= h+w-1:
            ansdouble += coinacumdictli[i+j][y]+coinacumdictli[i+j][y-1] - coinacumdictli[i+j][x] - coinacumdictli[i+j][x-1]

print(ansdouble//2)

Submission status: Runtime Error

Solution code:
try :
    #raise ModuleNotFoundError
    import numpy
    def dprint(*args, **kwargs):
        print(*args, **kwargs, file=sys.stderr)
    dprint('debug mode')
except Exception:
    def dprint(*args, **kwargs):
        pass

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
from collections import defaultdict
def inpl(): return list(map(int, input().split()))
H, W = inpl()
coins = []
grid = defaultdict(int)

z = 0
for h in range(H):
    for w, x in enumerate(input()):
        if x == "#":
            coins.append((w-h, w+h))
            #print(z, (w-h, w+h))
            z+= 1


ans = 0
check = set(coins)
for i in range(len(coins)):
    for j in range(i+1, len(coins)):
        a, b = coins[i]
        c, d = coins[j]
        if a == c or b == d:
            continue
        if (a, d) in check:
            pass
            #print((a, b), (c, d), (a, d))
        if (c, b) in check:
            pass
            #print((a, b), (c, d), (c, b))
        ans += ((a, d) in check) + ((c, b) in check)

print(ans)

Submission status: Runtime Error

Solution code:
import itertools
import numpy as np
import math
n = int(input())

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

xa = np.zeros((math.factorial(n),n)).astype(int)

xa.shape
for i, l in enumerate(itertools.permutations(x)):
    xa[i,:] = l

max_diff = np.abs(xa[:, 1:] - xa[:, :-1]).sum(axis=1).max()
print(max_diff)

Submission status: Runtime Error

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

As.sort()
#print(As)

def f(As):
    Bs = [0] * N
    iB = N // 2
    d = -2
    for A in As[:N//2]:
    #    print(A, iB, d)
        Bs[iB] = A
        iB += d
        if d > 0:
            d = -d - 2
        else:
            d = -d + 2
#    print(Bs)

    if N % 2:
        iB = N // 2 + 1
        d = -2
    else:
        iB = N // 2 - 1
        d = +2
    for A in reversed(As[N//2:]):
        Bs[iB] = A
        iB += d
        if d > 0:
            d = -d - 2
        else:
            d = -d + 2
#    print(Bs)

    ans = 0
    for i in range(N - 1):
        ans += abs(Bs[i + 1] - Bs[i])
#    print(ans)
    return ans

print(max(f(As), f(As[::-1])))

Submission status: Runtime Error

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

def f(a, offset=0):
    ans = 0
    # if len(a) % 2 == 0:
    #     last = a[0]
    # else:
    init = n // 2 + offset
    last = a[init]
    for i in range(n - 1):
        j = i // 2 if i % 2 == 0 else n - 1 - i // 2
        if j == init:
            break
        ans += abs(a[j] - last)
        last = a[j]
    return ans

# print(f(sorted(a)))
# print(f(sorted(a, reverse=True)))
a = sorted(a)
arev = sorted(a, reverse=True)
print(max(
    f(a),
    f(arev),
    f(a, offset = 1),
    f(arev, offset = 1),
))