Problem:


Score: 400 points

Problem Statement

Quickly after finishing the tutorial of the online game ATChat, you have decided to visit a particular place with N-1 players who happen to be there. These N players, including you, are numbered 1 through N, and the friendliness of Player i is A_i.

The N players will arrive at the place one by one in some order. To make sure nobody gets lost, you have set the following rule: players who have already arrived there should form a circle, and a player who has just arrived there should cut into the circle somewhere.

When each player, except the first one to arrive, arrives at the place, the player gets comfort equal to the smaller of the friendliness of the clockwise adjacent player and that of the counter-clockwise adjacent player. The first player to arrive there gets the comfort of 0.

What is the maximum total comfort the N players can get by optimally choosing the order of arrivals and the positions in the circle to cut into?

Constraints

All values in input are integers.

2 \leq N \leq 2 \times 10^5

1 \leq A_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \dots A_N

Output

Print the maximum total comfort the N players can get.

Sample Input 1

4
2 2 1 3

Sample Output 1

7

By arriving at the place in the order Player 4, 2, 1, 3, and cutting into the circle as shown in the figure, they can get the total comfort of 7.

They cannot get the total comfort greater than 7, so the answer is 7.

Sample Input 2

7
1 1 1 1 1 1 1

Sample Output 2

6



Sample input:
4
2 2 1 3


Sample output:
7

Submission status: Accepted

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function

import os
import sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip


def main():
    n = int(input())
    a = sorted([int(ai) for ai in input().split()], reverse=True)

    sol = a[0]
    for i in range(n - 2):
        sol += a[(i // 2) + 1]

    print(sol)


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import heapq
FAST_IO = 1
if FAST_IO:
    import io, sys, atexit
    rr = iter(sys.stdin.read().splitlines()).next
    sys.stdout = _OUTPUT_BUFFER = io.BytesIO()

    @atexit.register
    def write():
        sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
else:
    rr = raw_input
rri = lambda: int(rr())
rrm = lambda: map(int, rr().split())
rrmm = lambda n: [rrm() for _ in xrange(n)]

rrn = lambda n: [ rr() for _ in xrange(n)]

N = rri()
arr = rrm()
arr = sorted(arr)
def solve(N, arr):
    pq = []
    cur1 = arr.pop()
    ans = cur1
    cur2 = arr.pop()
    heapq.heappush(pq, (-cur2, (cur2, cur1)))
    heapq.heappush(pq, (-cur2,(cur1, cur2)))
    while arr:
        neg_max, (start, end) = heapq.heappop(pq)
        ans-=neg_max
        cur = arr.pop()
        heapq.heappush(pq, (-cur, (start, cur)))
        heapq.heappush(pq, (-cur, (cur, end)))
    return ans
print(solve(N, arr))

Submission status: Accepted

Solution code:
n = int(input())
l = list(map(int, input().split()))
cnt = 2
l.sort(reverse = True)
ans = l[0]
for i in l[1: ]:
    if cnt == n: break
    ans += i
    cnt -= -1
    if cnt == n: break
    ans += i
    cnt -= -1
print(ans)

Submission status: Accepted

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

import sys
import pprint
from collections import deque


sys.setrecursionlimit(10 ** 6)

class Logger:
	def __init__(self, debug):
		self.debug = debug
	def print(self, *args):
		if self.debug:
			pprint.pprint(args)


def main():
	log = Logger(0)
	n = int(sys.stdin.readline())
	a = list(map(int, sys.stdin.readline().split()))
	a = deque(sorted(a))
	if len(a) == 2:
		print(max(a))
		exit()
	if len(a) == 3:
		print(a[-1] + a[-2])
		exit()
	ans = 0
	a1 = a.pop()
	a2 = a.pop()
	a3 = a.pop()
	que = deque([[a1, a2], [a2, a3], [a3, a1]])
	ans += a1 + a2
	while len(a) != 0:
		log.print(que, ans)
		between = que.popleft()
		insert = a.pop()
		ans += min(between)
		que.append([between[0], insert])
		que.append([insert, between[1]])
	print(ans)




main()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))

A.sort(reverse=True)

ans = A[0]

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

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
a = list(reversed(sorted(a)))

ans = a[0]
idx = 1
n -= 2
while n > 0:
    if n == 1:
        ans += a[idx]
        n -= 1
    else:
        ans += 2*a[idx]
        n -= 2
    idx += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))
from collections import deque
#======================================================#
def main():
    n = II()
    aa = MII()
    aa.sort(reverse=True)
    dq = deque(aa)
    dq_p = deque()

    total = 0
    total += dq.popleft()
    next_point = dq.popleft()
    dq_p.append(next_point)
    dq_p.append(next_point)

    while dq:
        d = dq.popleft()
        dq_p.append(d)
        dq_p.append(d)
        total += dq_p.popleft()
    print(total)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
aa = sorted(a,reverse=True)
ans=0
if n%2 == 0:
    for i in range(n//2):
        ans = aa[i]*2+ans
else:
    for i in range((n+1)//2):
        ans = aa[i]*2+ans
    ans = ans - aa[(n-1)//2]
ans = ans - aa[0]
print(ans)

Submission status: Accepted

Solution code:
import heapq
N = int(input())
A = list(map(int,input().split()))
heap = []
for i in range(N):
    heapq.heappush(heap,-A[i])
if N==2:
    ans = -heapq.heappop(heap)
elif N==3:
    ans = -heapq.heappop(heap)-heapq.heappop(heap)
else:
    ans = 0
    ans = -heapq.heappop(heap)
    if N%2==0:
        for _ in range((N-2)//2):
            a = -heapq.heappop(heap)
            ans += 2*a
    else:
        for _ in range((N-3)//2):
            a = -heapq.heappop(heap)
            ans += 2*a
        a = -heapq.heappop(heap)
        ans += a
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
A = [int(x) for x in input().split()]
A.sort(reverse=True)
print(A[0] + sum(A[1:(n - 2) // 2 + 1]) * 2 +
      (0 if n % 2 == 0 else A[(n - 1) // 2]))

Submission status: Accepted

Solution code:
import sys


def main():
    N = int(sys.stdin.readline().rstrip())
    A = [int(x) for x in sys.stdin.readline().rstrip().split()]

    A.sort(reverse=True)

    B = []
    for j in range(N // 2 + 1):
        B.append(A[j])
        B.append(A[j])

    # print(B[:N])
    B[0] = 0

    print(sum(B[:N]))


main()

Submission status: Accepted

Solution code:
n = int(input())
arr = list(map(int,input().split()))
arr.sort(reverse=True)

if n % 2 == 0:
    ans = 2*sum(arr[:n//2]) -arr[0]
else:
    ans = 2*sum(arr[:n//2]) -arr[0] + arr[n//2]

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
ar=list(map(int,input().split()))
ar.sort(reverse=True)
ans=0
for i in range(1,n):
    ans+=ar[i//2]
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
a_list=list(map(int,input().split()))

a_list.sort()
a_list=a_list[::-1]

sumn=0
if N%2==0:
    sumn+=a_list[0]
    sumn+=2*sum(a_list[1:N//2])
else:
    sumn+=a_list[0]
    sumn+=2*sum(a_list[1:N//2])
    sumn+=a_list[N//2]

print(sumn)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))

a.sort()
a.reverse()

#ans = 0
#seq = [a[0]]
#
#seq.append(a[1])
#ans += a[0]
#
#l = 2
#for i in range(2, n):
#    pos = 0
#    m_ans, M_ans = 0, 0
#    for p in range(l):
#        np = p + 1
#        if np == l:
#            np = 0
#        m, M = min(seq[p], seq[np]), max(seq[p], seq[np])
#        if m >= m_ans and M >= m_ans:
#            pos = np
#            m_ans = m
#            M_ans = M
#    ans += m_ans
#    seq.insert(pos, a[i])
#    l += 1
#print(ans)

ans = 0
cur = 0
cnt = 1
for i in range(n - 1):
    if cnt == 2:
        cur += 1
        cnt = 0
    ans += a[cur]
    cnt += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
As = list(mapint())
As.sort(reverse=True)
from heapq import heappush, heappop

first = (As.pop(0))
hq = []
if N<2:
    print(0)
else:
    ans = 0
    second = As.pop(0)
    ans += first
    heappush(hq, (-second, -first))
    heappush(hq, (-second, -first))
    for a in As:
        s, f = heappop(hq)
        ans -= s
        heappush(hq, (-a, s))
        heappush(hq, (-a, f))

print(ans)

Submission status: Accepted

Solution code:
N = int(input())

A = list(map(int, input().split()))

sorted_A = sorted(A, reverse=True)

if N % 2 == 0:
    print(sorted_A[0] + 2*sum(sorted_A[1:N//2]))
elif N == 3:
    print(sorted_A[0] + sorted_A[N // 2])
else:
    print(sorted_A[0] + 2*sum(sorted_A[1:N//2]) + sorted_A[N//2])

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))

A.sort(reverse=True)

happiness = A.pop(0)
tree = [0] * N
tree[0] = A[0]

index = 0
appendIndex = 1
while(len(A)>appendIndex):
  happiness += tree[index]
  tree[appendIndex] = A[appendIndex]
  appendIndex += 1
  if(len(A)==appendIndex):
    break
  happiness += tree[index]
  tree[appendIndex] = A[appendIndex]
  appendIndex += 1
  index += 1

print(happiness)

Submission status: Accepted

Solution code:
import heapq

N=int(input())
A=list(map(int,input().split()))
A.sort(reverse=True)

place=[[-A[0],1]]
ans=0
for i in range(1,N):
    ans-=place[0][0]
    if place[0][1]==1:
        heapq.heappop(place)
    else:
        place[0][1]-=1
    heapq.heappush(place,[-A[i],2])
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort(reverse=True)
idx=-(-n//2)
ans=0
if n%2:
    for i in range(idx):
        if i==0 or i==idx-1:
            ans+=a[i]
        else:
            ans+=2*a[i]
else:
    for i in range(idx):
        if i==0:
            ans+=a[i]
        else:
            ans+=2*a[i]
print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N = int(input())
    A = sorted([int(x) for x in input().strip().split()], reverse=True)
    ans = A[0]
    for n in range(2, N):
        ans += A[n//2]
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)

ans = 0
for i in range(1, N):
    ans += A[i//2]
print(ans)

Submission status: Accepted

Solution code:
from collections import deque, defaultdict

N = int(input())
A = list(map(int, input().split()))

A.sort(reverse=True)

d = defaultdict(int)
d[A[0]] += 1
x = deque([A[0]])
ans = 0
for a in A[1:]:
    ans += x[0]
    d[x[0]] -= 1
    if d[x[0]] == 0:
        x.popleft()
    if d[a] == 0:
        x.append(a)
    d[a] += 2
print(ans)

Submission status: Accepted

Solution code:
n = int(input().strip())
A = list(map(int, input().strip().split()))
A.sort()
B=[0]*n
for i in range(n):
    B[i]=A[n-1-i]
x=0
if n%2==1:
 
    for i in range(int((n-1)//2+1) ):
        x+=2*B[i]
    x-=B[(n-1)//2]
    x-=B[0]
    
    print(x)
else:
    for i in range(int(n/2)):
        x+=2*B[i]
    
    x-=B[0]
    print(x)

Submission status: Accepted

Solution code:
n = int(input())

A = sorted(list(map(int, input().split())), reverse=True)

score_list = [0, A[0]]
for i in range(1, len(A)):
    score_list.append(A[i])
    score_list.append(A[i])
    
print(sum(score_list[:n]))

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort(reverse=True)
ans=0
if n%2==0:
  for i in range(n//2):
    ans=ans+a[i]*2
  print(ans-a[0])
else:
  for i in range(n//2):
    ans=ans+a[i]*2
  print(ans-a[0]+a[n//2])

Submission status: Accepted

Solution code:
from sys import stdin
import heapq as hq
input = stdin.readline

N = int(input())
A = list(map(int, input().split()))

A.sort(reverse=True)
ans = 0

ls = []
hq.heapify(ls)

hq.heappush(ls, [-A[0], -A[0]])

for i in range(1, N):
    c = A[i]
    a, b = hq.heappop(ls)
    ans += abs(max(a, b))
    hq.heappush(ls, [-min(abs(A[i]), abs(a)), -max(abs(A[i]), abs(a))])
    hq.heappush(ls, [-min(abs(A[i]), abs(b)), -max(abs(A[i]), abs(b))])

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
ans = 0
d = deque([A[0]])
#tmp = [A[0]]
for i in range(1,N,1):
  #print(i)
  #print(tmp)
  ans += d.popleft()
  d.extend([A[i],A[i]])
print(ans)

Submission status: Accepted

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

# 入力を整数に変換して受け取る
def input_int():
    return int(input())


# マイナス1した値を返却
def int1(x):
    return int(x) - 1


# 半角スペース区切り入力をIntに変換してMapで受け取る
def input_to_int_map():
    return map(int, input().split())


# 半角スペース区切り入力をIntに変換して受け取る
def input_to_int_tuple():
    return tuple(map(int, input().split()))


# 半角スペース区切り入力をIntに変換してマイナス1した値を受け取る
def input_to_int_tuple_minus1():
    return tuple(map(int1, input().split()))


def main():
    n = input_int()
    a_list = input_to_int_tuple()

    sorted_list = sorted(a_list, reverse=True)
    temp_cnt = n - 2
    ans = sorted_list[0]

    plus = False
    if temp_cnt % 2 == 0:
        temp_cnt //= 2
    else:
        temp_cnt //= 2
        plus = True

    if temp_cnt >= 1:
        ans += sum(sorted_list[1:temp_cnt + 1]) * 2

    if plus:
        ans += sorted_list[temp_cnt + 1]

    print(ans)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np

n = int(input())
a = input().split()
npa=np.array(a, dtype=int)

npa1=np.sort(npa)[::-1]

ninzuu=n-1
if (ninzuu % 2 != 0):
  ninzuu2=int((ninzuu-1)/2)
  atai=npa1[0]+sum(npa1[1:ninzuu2+1])*2
else:
  ninzuu2=int((ninzuu)/2)
  atai=npa1[0]+sum(npa1[1:ninzuu2])*2+npa1[ninzuu2]

print(atai)

Submission status: Accepted

Solution code:
# import sys
# readline = sys.stdin.readline
# generator = (readline().strip() for _ in range(N))

# N, M = map(int, input().split())
# As = list(map(int, input().split()))
# queries = (input() for _ in range(N))

import queue


def solve():
    N = int(input())
    As = list(map(int, input().split()))
    As.sort(reverse=True)

    score = 0

    q = queue.Queue()
    q.put(As[0])

    for a in As[1:]:
        score += q.get()
        q.put(a)
        q.put(a)

    return score


def main():
    print(solve())


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest
import heapq
import copy

def yn(b):
    print("Yes" if b==1 else "No")
    return

def resolve():
    readline=sys.stdin.readline

    #n,m,k=map(int, readline().rstrip().split())
    n=int(readline())
    arr=list(map(int, readline().rstrip().split()))
    arr.sort(reverse=True)
    c=[]
    heapq.heapify(c)
    ans=0
    for i in range(n):
        if i==0:
            heapq.heappush(c,(-1)*arr[i])
        else:
            ans+=heapq.heappop(c)*(-1)
            heapq.heappush(c,(-1)*arr[i])
            heapq.heappush(c,(-1)*arr[i])
    print(ans)
    #n=int(readline())
    #ss=readline().rstrip()
    #yn(1)

    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))

a.sort(reverse=True)
n -= 2
r = a[0]
i = 1
while n-2 >= 0:
    r += a[i]*2
    i += 1
    n -= 2
if n==1:
    r += a[i]
print(r)

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
sortA = sorted(A, reverse=True)
C = Counter(sortA)
for k in C.keys():
    C[k] = C[k] * 2    
sort_ai = sorted(C.keys(), reverse=True)
ii = 0
ans = 0
for i  in range(N):
    tmp = sort_ai[ii]
    ans += tmp
    C[tmp] -= 1
    if C[tmp] == 0:
        ii += 1
print(ans-sort_ai[0])

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
ans = a[0]
for i in range(n-2):
    ans += a[i//2+1]
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(x) for x in input().split()]

A = sorted(A, reverse=True)

score = 0
for i in range(N):
    if i == 0:
        score += 0
    elif i == 1:
        score += A[0]
    else:
        score += A[i//2]

print(score)

Submission status: Accepted

Solution code:
n = int(input())
la = [int(w) for w in input().split()]
la.sort(reverse=True)

ans = la[0]
cnt = n - 2
for a in la[1:]:
    if cnt >= 2:
        cnt -= 2
        ans += a * 2
    elif cnt == 1:
        cnt -= 1
        ans += a
    else:
        break
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))

A.sort(reverse=True)

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

Submission status: Accepted

Solution code:
# Contest No.: ABC173
# Problem No.: D
# Solver:      JEMINI
# Date:        20200705

import sys
import heapq

def main():
    n = int(input())    
    nums = list(map(int, sys.stdin.readline().split()))

    nums.sort()
    ans = 0

    # initial
    temp = nums.pop()
    ans += temp
    n -= 2

    for i in range(n // 2):
        ans += nums[-i - 1] * 2

    if n % 2:
        ans += nums[-(n // 2) - 1]
    
    
    print(ans)

    return

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math
N = int (input())
x = list(map(int, input().split()))
sum = 0
red = sorted(x)[::-1]
count = math.floor(N/2)
for i in range(count):
    sum += red[i] * 2
sum -= red[0]
desire = N - count*2
sum += desire * red[count]
print(sum)

Submission status: Accepted

Solution code:
import heapq

N = int(input())
A = [-int(x) for x in input().split()]
A.sort()
pq = []
heapq.heapify(pq)
heapq.heappush(pq, A[0])
ans = 0
for a in A[1:]:
    ans += heapq.heappop(pq)
    heapq.heappush(pq, a)
    heapq.heappush(pq, a)
print(-ans)

Submission status: Accepted

Solution code:
n = int(input())
ns = list(map(int, input().split()))
ns = sorted(ns, reverse=True)
if n % 2 == 1:
    a = n //2 + 1
    print(sum(ns[:a]) * 2 - ns[0] - ns[a-1])
    
else:
    a = n // 2
    print(sum(ns[:a]) * 2 - ns[0])

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort(reverse=1)
ans = a[0]
for i in range(n-2): ans += a[i//2+1]
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
list_A = list(map(int, input().split()))
list_A.sort(reverse=True)
ans = list_A.pop(0)
k = (n-2)//2
ans += 2*sum(list_A[:k])
if (n-2) % 2 == 1:
    ans += list_A[k]

print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")

n = int(input())
a = [int(x) for x in input().split()]
a.sort()
ans = a.pop()
a = a[::-1]

if n % 2 == 0:
    n -= 1

    n -= 1
    ans += 2*sum(a[:n//2])

else:
    n -= 1

    n -= 1
    ans += 2*sum(a[:n//2]) + a[n//2]
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
cnt = 0
s = -A[0]
for i in range(N // 2):
    cnt = i
    s += 2 * A[i]
if N % 2 == 1:
    s += A[cnt + 1]
print(s)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
ans = A[0]
i = 2
j = 1
while(True):
    if i == N:
        break
    ans += A[j]
    i += 1
    if i == N:
        break
    ans += A[j]
    i += 1
    j += 1

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort(reverse=True)

res = 0
for i in range(N):
    res += A[i//2]
print(res-A[0])

Submission status: Accepted

Solution code:
from sys import stdin
N = int(input())
A = [int(x) for x in stdin.readline().rstrip().split()]
A.sort(reverse=True)
ans = A[0]
cnt = 2
for i in range(1,N):
    ans += (A[i]*2)
    cnt += 2
    if cnt >= N:
        if cnt > N:
            ans -= A[i]
        break
if N == 2:
    ans = max(A)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A_list = sorted(list(map(int, input().split())), reverse=True)

res = A_list[0]
cnt = 2
for i in range(1, N):
    if N - cnt >= 2:
        res += 2 * A_list[i] 
        cnt += 2
    elif N - cnt == 1:
        res += A_list[i]
        break
    else:
        break
print(res)

Submission status: Accepted

Solution code:
N = int(input())
A_list = [int(n) for n in input().split()]
A_list.sort(reverse = True)
ans = 0

for i in range(1,N):
    ans += A_list[i // 2]

print(ans)

Submission status: Accepted

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

n=int(input().rstrip())
a=sorted([int(i) for i in input().split()],reverse=1)
nokori=n-2
i=1
ans=a[0]
while nokori>1:
    ans+=a[i]*2
    nokori-=2
    i+=1
if n%2:ans+=a[i]
print(ans)

Submission status: Accepted

Solution code:
import heapq

N = int(input())
A = list(sorted(map(int,input().split())))

first = A.pop()
Q = [(-first,first,first)]

ans = 0
for i in range(N-1):
    a = A.pop()
    b,c,d = heapq.heappop(Q)
    ans -= b
    heapq.heappush(Q,(-a,c,a))
    heapq.heappush(Q,(-a,d,a))

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
ans = max(a)
a.sort(reverse = True)
index = 1
for i in range(n-2):
    ans += a[index]
    if i % 2 == 1:
        index += 1
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
A.sort(reverse=True)
k=A[0]
ans=k
if(N % 2 ==0):
    l=int((N-2)/2)
    for i in range(l):
        ans+=2*A[i+1]
else:
    l=int((N-3)/2)
    for i in range(l):
        ans+=2*A[i+1]
    ans+=A[l+1]
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin, stdout

int_in = lambda: int(stdin.readline())
arr_in = lambda: [int(x) for x in stdin.readline().split()]
mat_in = lambda rows: [arr_in() for _ in range(rows)]
str_in = lambda: stdin.readline().strip()
out = lambda o: stdout.write("{}\n".format(o))
arr_out = lambda o: out(" ".join(map(str, o)))
bool_out = lambda o: out("YES" if o else "NO")
tests = lambda: range(1, int_in() + 1)
case_out = lambda i, o: out("Case #{}: {}".format(i, o))


def solve(n, a):
    a.sort(reverse=True)
    comfort = 0
    for i in range(1, len(a)):
        comfort += a[i // 2]

    return comfort


if __name__ == "__main__":
    n = int_in()
    a = arr_in()
    out(solve(n, a))

Submission status: Accepted

Solution code:
n=int(input())
a=sorted([int(i) for i in input().split()],reverse=True)
ans=0
for i in range(1,n):
  ans+=a[i//2]
  if i==n-1:
    print(ans)
    exit()
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))

a.sort(reverse=True)
ans = a[0]
cnt = 2
for i in range(1, n-2):
    ans += a[i]
    cnt += 1
    if cnt == n: break
    ans += a[i]
    cnt += 1
    if cnt == n: break

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
def resolve():
    N = int(input())
    A = list(map(int,input().split()))
    A.sort()
    ans = 0
    d = deque()
    d.append(A[N-1])
    for i in range(N-2,-1,-1):
        ans += d.popleft()
        d.append(A[i])
        d.append(A[i])
    print(ans)
resolve()

Submission status: Accepted

Solution code:
N=int(input())
huga = list(map(int, input().split()))
huga.sort(reverse=True)
s=0
if N%2==1:
    for i in range(1,(N-1)//2):
        s+=huga[i]
    print(huga[0]+huga[N//2]+2*s)
else:
    for i in range(1,N//2):
        s+=huga[i]
    print(huga[0]+2*s)

Submission status: Accepted

Solution code:
N=int(input())
A=sorted(list(map(int,input().split())),reverse=True)
ans=0
idx=0
c=1
for i in range(1,N):
    ans+=A[idx]
    c-=1
    if c==0:
        c=2
        idx+=1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))

A.sort()
A = A[::-1]

ans = A[0]
if N%2 ==0:
    for i in range((N-2)//2):
        for j in range(2):
            ans += A[i+1]
else:
    for i in range((N-3)//2):
        for j in range(2):
            ans += A[i+1]
    ans += A[(N-3)//2+1]
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
ans = 0
c = 0
ic = 1
for i in range(n-1):
    if i == 0:
        ans += a[0]
    else:
        ans += a[ic]
        c += 1
        if c == 2:
            c = 0
            ic += 1
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=sorted(list(map(int,input().split())),reverse=True)

print(a[0]+sum(a[1:(n-2)//2+1])*2+a[(n-2)//2+1]*((n-2)%2))

Submission status: Accepted

Solution code:
n = int(input())
listA = list(map(int, input().split()))
listA.sort()
listA.reverse()

i = 0
indexer = 0
flag = 0
count = 0
while i < len(listA):
    if i == 0:
        count+= 0
        i+=1
    elif i == 1:
        count+=listA[indexer]
        indexer+=1
        i+=1
    else:
        count+=listA[indexer]
        if flag:
            indexer+=1
            flag = 0
        else:
            flag = 1
        i+=1
print(count)

Submission status: Accepted

Solution code:
from collections import defaultdict as dd
import heapq
N = int(input())
a = list(map(int,input().split()))
res = 0
a = sorted(a, reverse=True)
dic=dd(list)
ls = [-a[0]]
heapq.heapify(ls)
for val in a[1:]:
    tmp = -heapq.heappop(ls)
    res += tmp
    heapq.heappush(ls,-val)
    heapq.heappush(ls,-val)
print(res)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
#pyrival orz
import os
import sys
from io import BytesIO, IOBase

"""
    for _ in range(int(input())):
    n,m=map(int,input().split())
    n=int(input())
    a = [int(x) for x in input().split()]
"""

def main():
    n = int(input())
    a = [int(x) for x in input().split()]
    a.sort(reverse=True)
    # print(a)
    ans=0
    k=n
    ans-=a[0]
    for x in a:
        if k==0:
            break
        if k==1:
            ans+=x
            break
        ans+=2*x
        k-=2
    print(ans)

# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int,input().split()))
A.sort(reverse=True)

if n%2==0:
    k = n//2
    print(A[0]+2*sum(A[1:k]))
else:
    print(A[0]+2*sum(A[1:n//2])+A[n//2])

Submission status: Accepted

Solution code:
N = int(input())
A = sorted(list(map(int, input().split())), reverse=True)

from collections import deque
q = deque([])

ans = 0
i = 0
for i in range(N):
    a = A[i]
    if i == 0:
        q.append(a)
    else:
        q.append(a)
        q.append(a)    
        s = q.popleft()
        ans += s

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = sorted(list(map(int, input().split())), reverse=True)

ans = 0
i = 0
for j in range(n - 1):
    ans += a[i]
    if j % 2 == 0:
        i += 1
print(ans)

Submission status: Accepted

Solution code:
import heapq
N = int(input())
*A, = map(int, input().split())
A.sort()
A.reverse()

ans = 0
hq = [(-A[0], A[0], A[0])]
for a in A[1:]:
    s, n, m = heapq.heappop(hq)
    ans += -s
    heapq.heappush(hq, (-min(a, n), n, a))
    heapq.heappush(hq, (-min(a, m), m, a))
print(ans)