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:
import sys
input = sys.stdin.buffer.readline


#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

#import numpy as np

def main():
	n=II()
	A=LI()
	A.sort(reverse=True)

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

	if n%2:
		ans+=A[n//2]
	elif n>3:
		ans+=2*A[(n-1)//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
cnt = 0
while True:
    if cnt == 0:
        ans+= A[0]
    else:
        ans+=A[(cnt+1)//2]
    cnt+=1
    if cnt == N-1:
        break
print(ans)

Submission status: Accepted

Solution code:

n=int(input())
alist=list(map(int,input().split()))

alist.sort()

retrum=0

retrum+=alist.pop()
for i in range(n-2):
    if i%2==0:
        retrum+=alist[-1]
    if i%2==1:
        retrum+=alist.pop()
print(retrum)

Submission status: Accepted

Solution code:
import heapq
from collections import deque
b=[]
heapq.heapify(b)

n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
a = deque(a)

heapq.heappush(b,-1*a.popleft())
ans = 0

while len(a)>0:
  temp = a.popleft()
  point = -1*heapq.heappop(b)
  ans+=point
  heapq.heappush(b, -1*temp)
  heapq.heappush(b, -1*temp)
  
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
#import bisect
#import numpy as np
# from collections import deque
from collections import deque
# map(int, sys.stdin.read().split())
import itertools
import heapq

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


def main():
    N = int(input())
    A = list(map(lambda x: -1*int(x),input().split()))
    heapq.heapify(A)
    l = deque()
 #   print(A)
    score =0
    c = heapq.heappop(A)
    l.append(c)
    for i in range(N-1):
        c = heapq.heappop(A)
        l.append(c)
        l.append(c)
        current =l.popleft()
        score +=current

    print(-score)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import heapq

n = int(input())
a = list(map(int,input().split()))
a.sort(reverse=True)

h=[]

heapq.heappush(h,a[0]*(-1))
ans = 0
for i in range(1,n):
    ans-=heapq.heappop(h)
    heapq.heappush(h,a[i]*(-1))
    heapq.heappush(h,a[i]*(-1))
print(ans)

Submission status: Accepted

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

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
if N%2:
    print((A[0]+2*sum(A[1:N//2])+A[N//2]))
else:
    print((A[0]+2*sum(A[1:N//2])))

Submission status: Accepted

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

def linked_merge_sort(l): #マージソート
    if len(l) == 1:
        return
    q, r = divmod(len(l), 2)
    left = [l.pop() for _ in range(q)]
    right = [l.pop() for _ in range(q + r)]
    
    linked_merge_sort(left)
    linked_merge_sort(right)
    
    left.reverse()
    right.reverse()
    while left and right:
        if left[-1] <= right[-1]:
            l.append(left.pop())
        else:
            l.append(right.pop())
    while left:
        l.append(left.pop())
    while right:
        l.append(right.pop())
    return

linked_merge_sort(a)
b=[0]*n
for i in range(n):
    b[i]=a[n-1-i]
ans=0
for i in range(1,n):
    ans+= b[(i//2)]
print(ans)

Submission status: Accepted

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

loop = N // 2
for i in range(loop):
  Ans = Ans + (sort_A[i] * 2) 

Ans = Ans - sort_A[0]

if N % 2 == 1:
  Ans = Ans + sort_A[(N-1) // 2]

print(Ans)

Submission status: Accepted

Solution code:
n,ais = int(raw_input()), map(int, raw_input().split())
ais.sort(key = lambda x:-x)
n -=2
s = 0
s += ais[0]
i = 1
while(n):
	s += ais[i]
	n-=1
	if n:
		s += ais[i]
		n -=1
	i+=1

print s

Submission status: Accepted

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

a.sort(reverse=True)

ans = a[0]
n -= 1
for i in range(1, n):
    if n > 2:
        ans += a[i] * 2
        n -= 2
    elif n == 2:
        ans += a[i]
        n -= 1
    else:
        break

print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heapreplace

n = int(input())
a = sorted(map(int, input().split()), reverse=True)
h = [-a[0]]
c = 0
for i in range(1, n):
    c += heapreplace(h, -a[i])
    heappush(h, -a[i])
print(-c)

Submission status: Accepted

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

N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
point = 0
point += A[0]

cnt = 1
for a in A[1:]:
    for _ in range(2):
        point += a
        cnt += 1
        if cnt == N-1:
            break
    if cnt == N-1:
        break

if N == 2:
    print(A[0])
else:
    print(point)

Submission status: Accepted

Solution code:
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N = int(input())

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

ans = 0
cur = 0
for i in range(N - 1):
    ans += A[cur]
    if i < 1:
        cur += 1
    elif i % 2 == 0:
        cur += 1

print(ans)

Submission status: Accepted

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

A = sorted(A, reverse = True)

counter = A[0]

if N ==2:
    print(A[0])
    exit()

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

print(counter)

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:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import bisect_right
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
N = int(input())
A = list(map(int,input().split()))
A.sort(reverse =  True)
ans = A[0]
flag = 0
index = 1
for i in range(N-2):
    if flag == 0:
        ans += A[index]
        flag = 1
    else:
        ans += A[index]
        index += 1
        flag = 0
print(ans)

Submission status: Accepted

Solution code:
# @author 

import sys

class DChatInACircle:
    def solve(self, tc=0):
        n = int(input())
        a = [int(_) for _ in input().split()]
        a.sort()
        it = [a[-1]]
        for i in range(n - 2, -1, -1):
            it.append(a[i])
            it.append(a[i])
        print(sum(it[:n - 1]))


solver = DChatInACircle()
input = sys.stdin.readline

solver.solve()

Submission status: Accepted

Solution code:

# Author : raj1307 - Raj Singh
# Date   : 05.07.2020

from __future__ import division, print_function

import os,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 ii():  return int(input())
def si():  return input()
def mi():  return map(int,input().strip().split(" "))
def msi(): return map(str,input().strip().split(" "))
def li():  return list(mi())

def dmain():
    sys.setrecursionlimit(1000000)
    threading.stack_size(1024000)
    thread = threading.Thread(target=main)
    thread.start()
    
#from collections import deque, Counter, OrderedDict,defaultdict
#from heapq import nsmallest, nlargest, heapify,heappop ,heappush, heapreplace
#from math import log,sqrt,factorial,cos,tan,sin,radians
#from bisect import bisect,bisect_left,bisect_right,insort,insort_left,insort_right
#from decimal import *
#import threading
#from itertools import permutations
#Copy 2D list  m = [x[:] for x in mark] .. Avoid Using Deepcopy

abc='abcdefghijklmnopqrstuvwxyz'
abd={'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}
mod=1000000007
#mod=998244353
inf = float("inf")
vow=['a','e','i','o','u']
dx,dy=[-1,1,0,0],[0,0,1,-1]
def getKey(item): return item[1] 
def sort2(l):return sorted(l, key=getKey,reverse=True)
def d2(n,m,num):return [[num for x in range(m)] for y in range(n)]
def isPowerOfTwo (x): return (x and (not(x & (x - 1))) )
def decimalToBinary(n): return bin(n).replace("0b","")
def ntl(n):return [int(i) for i in str(n)]
def ncr(n,r): return factorial(n)//(factorial(r)*factorial(max(n-r,1)))

def ceil(x,y):
    if x%y==0:
        return x//y
    else:
        return x//y+1

def powerMod(x,y,p):
    res = 1
    x %= p
    while y > 0:
        if y&1:
            res = (res*x)%p
        y = y>>1
        x = (x*x)%p
    return res

def gcd(x, y):
    while y:
        x, y = y, x % y
    return x
    
def isPrime(n) : # Check Prime Number or not 
    if (n <= 1) : return False
    if (n <= 3) : return True
    if (n % 2 == 0 or n % 3 == 0) : return False
    i = 5
    while(i * i <= n) : 
        if (n % i == 0 or n % (i + 2) == 0) : 
            return False
        i = i + 6
    return True



def read():
    sys.stdin  = open('input.txt', 'r')  
    sys.stdout = open('output.txt', 'w') 




def main():
    


    #for _ in range(ii()):



    n=ii()
    a=li()
    a.sort(reverse=True)
    ans=a[0]
    p=1
    for i in range(2,n,2):
        if i==n-1:
            ans+=a[p]
        else:
            ans+=2*a[p]
            p+=1

    print(ans)

















    









    








# region fastio
# template taken from https://github.com/cheran-senthil/PyRival/blob/master/templates/template.py

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__":
    #read()
    main()
    #dmain()

# Comment Read()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
n = int(input())
a = sorted(map(int, input().split()))[::-1]
ans = 0
c = 0
while c < n - 1:
    ans += a[(c + 1) // 2]
    c += 1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(500000)

def input():
    return sys.stdin.readline()[:-1]

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]


def main():
    N = ii()
    A = list(mi())
    A.sort(reverse=True)
    ans = A[0]
    if N%2:
        ans += 2*sum(A[1:N//2+1])-A[N//2]
    else:
        ans += 2*sum(A[1:N//2])

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    friendly = list(map(int, input().split()))
 
    friendly.sort()
 
    ans = friendly[-1]
    
    FLAG = True
    index = N - 2
    
    
    for i in range(N - 2):
        if (FLAG):
            ans += friendly[index]
            FLAG = False
        else:
            ans += friendly[index]
            FLAG = True
            index -= 1
    
        
    print(ans)
 
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
A.sort(reverse=True)
N-=1
if N%2==0:
    ans=sum(A[:(N//2+1)])+sum(A[1:N//2])
else:
    ans=sum(A[:(N//2+1)])+sum(A[1:(N//2+1)])
print(ans)

Submission status: Accepted

Solution code:

def main():
    n = int(input())
    al = list(map(int, input().split()))
    al.sort(reverse=True)
    ans = 0

    for i in range(n):
        ans += al[i//2]

    ans -= al[0]
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# Template 1.0
import sys, re
from collections import deque, defaultdict, Counter, OrderedDict
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappush, heappop, heapify, nlargest, nsmallest
def STR(): return list(input())
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
def sortListWithIndex(listOfTuples, idx):   return (sorted(listOfTuples, key=lambda x: x[idx]))
def sortDictWithVal(passedDic):
    temp = sorted(passedDic.items(), key=lambda kv: (kv[1], kv[0]))
    toret = {}
    for tup in temp:
        toret[tup[0]] = tup[1]
    return toret
def sortDictWithKey(passedDic):
    return dict(OrderedDict(sorted(passedDic.items())))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

n = INT()

a = LIST()

a = sorted(a)[::-1]

ans = a[0]

a = a[1:]
i = 0
while(n-2>0):
    ans+=a[i]
    n-=1
    if(n-2==0):
        break
    ans+=a[i]
    i+=1
    n-=1
print(ans)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)

import heapq


class PriorityQueue:
    class Reverse:
        def __init__(self, val):
            self.val = val

        def __lt__(self, other):
            return self.val[0] > other.val[0]

        def __repr__(self):
            return repr(self.val)

    def __init__(self, x=None, desc=False):
        if not x:
            x = []
        if desc:
            for i in range(len(x)):
                x[i] = self.Reverse(x[i])
        self._desc = desc
        self._container = x
        heapq.heapify(self._container)

    @property
    def is_empty(self):
        return not self._container

    def pop(self):
        if self._desc:
            return heapq.heappop(self._container).val
        else:
            return heapq.heappop(self._container)

    def push(self, item):
        if self._desc:
            heapq.heappush(self._container, self.Reverse(item))
        else:
            heapq.heappush(self._container, item)

    def top(self):
        if self._desc:
            return self._container[0].val
        else:
            return self._container[0]

    def sum(self):
        return sum(self._container)

    def __len__(self):
        return len(self._container)


def main():
    def f(p, q):
        ret = (min(p, q), max(p, q))
        return ret

    n = int(readline())
    a = list(map(int, readline().split()))
    a.sort(reverse=True)
    ans = a[0]
    pq = PriorityQueue(desc=True)
    pq.push(f(a[0], a[1]))
    pq.push(f(a[0], a[1]))

    for x in a[2:]:
        first, second = pq.pop()
        ans += first
        pq.push(f(first, x))
        pq.push(f(second, x))

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq

n = int(input())
arr = list(map(int,input().split()))

arr.sort()
arr.reverse()

que = [0]
heapq.heapify(que)

ans = 0

for i in range(n):
    top = heapq.heappop(que)
    top = -top
    ans += top
    if i == 0:
        heapq.heappush(que, -arr[i])
    else:
        heapq.heappush(que,-arr[i])
        heapq.heappush(que,-arr[i])

    # print(que)

print(ans)

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:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
def main(N, A):
    A.sort(reverse=True)
    ans = A[0]
    for i in range(2, N):
        ans += A[i // 2]
    print(ans)

if __name__ == '__main__':
    input = sys.stdin.readline
    N = int(input())
    *A, = map(int, input().split())
    main(N, A)

Submission status: Accepted

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

def solve():
    N = int(readline())
    A = list(map(int, readline().split()))

    A.sort(reverse=True)

    q = deque()

    q.append(A[0])

    ans = 0
    for i in range(1, len(A)):
        v = q.popleft()
        ans += v
        q.append(A[i])
        q.append(A[i])

    print(ans)

solve()

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:
n = int(input())
a = list(map(int, input().split()))

newa = []

for num in a:
    newa.append(num)
    newa.append(num)

newa.sort(reverse=True)

ans=sum(newa[1:n])

print(ans)

Submission status: Accepted

Solution code:
'''
    Auther: ghoshashis545 Ashis Ghosh
    College: jalpaiguri Govt Enggineering College

'''
from os import path
import sys
from functools import cmp_to_key as ctk
from collections import deque,defaultdict as dd 
from bisect import bisect,bisect_left,bisect_right,insort,insort_left,insort_right
from itertools import permutations
from datetime import datetime
from math import ceil,sqrt,log,gcd
def ii():return int(input())
def si():return input()
def mi():return map(int,input().split())
def li():return list(mi())
abc='abcdefghijklmnopqrstuvwxyz'
mod=1000000007
#mod=998244353
inf = float("inf")
vow=['a','e','i','o','u']
dx,dy=[-1,1,0,0],[0,0,1,-1]

def bo(i):
    return ord(i)-ord('a')

file = 0

def solve():
    



    # for _ in range(ii()):

    n=ii()
    a=li()
    a.sort(reverse=True)
    if(n==1):
        print(0)
        exit(0)
    ans=a[0]
    k=n-2
    for i in range(1,n):
        if(k==0):
            break
        if(k==1):
            ans+=a[i]
            k-=1
        else:
            ans+=2*a[i]
            k-=2
    print(ans)










  
















if __name__ =="__main__":

    if(file):

        if path.exists('input1.txt'):
            sys.stdin=open('input1.txt', 'r')
            sys.stdout=open('output1.txt','w')
        else:
            input=sys.stdin.readline
    solve()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
N = int(input())
A = list(map(int, (input().split())))
A.sort(reverse=True)
if N%2:
    ans = A[0] + sum(A[1:(N-1)//2])*2 + A[(N-1)//2]
else:
    ans = A[0] + sum(A[1:N//2])*2
print(ans)

Submission status: Accepted

Solution code:
import sys
import heapq

input = sys.stdin.readline


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

    A.sort(reverse=True)
    A = [-a for a in A]

    q = [A[0]]
    heapq.heapify(q)
    ans = 0
    for a in A[1:]:
        max_v = heapq.heappop(q)
        ans += max_v
        heapq.heappush(q, a)
        heapq.heappush(q, a)

    ans = -ans
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

A.sort()

count = 0
ans = 0

for idx, a in enumerate(reversed(A)):
    count += 1
    ans += a
    if count == N - 1:
        break
    if idx != 0:
        count += 1
        ans += a
    if count == N - 1:
        break
print(ans)

Submission status: Accepted

Solution code:
import heapq

n = int(input())
data = list(map(int, input().split()))
data.sort(reverse=True)

q = []
heapq.heappush(q, -data[1])
heapq.heappush(q, -data[1])
result = data[0]

for i in range(2, n):
    result += -heapq.heappop(q)
    heapq.heappush(q, -data[i])
    heapq.heappush(q, -data[i])

print(result)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    friendly = list(map(int, input().split()))

    friendly.sort()

    ans = friendly[-1]
    
    FLAG = True
    index = N - 2
    
    
    for i in range(N - 2):
        if (FLAG):
            ans += friendly[index]
            FLAG = False
        else:
            ans += friendly[index]
            FLAG = True
            index -= 1
    
        
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7

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

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

Submission status: Accepted

Solution code:
import sys
def rs(): return sys.stdin.readline().rstrip()
def ri(): return int(sys.stdin.readline())
def ria(): return list(map(int, sys.stdin.readline().split()))
def ws(s): sys.stdout.write(s); sys.stdout.write('\n')
def wi(n): sys.stdout.write(str(n)); sys.stdout.write('\n')
def wia(a, sep=' '): sys.stdout.write(sep.join([str(x) for x in a])); sys.stdout.write('\n')


import heapq

def solve(n, a):
    a = sorted(a, reverse=True)
    ans = 0

    h = [-a[0]]
    heapq.heapify(h)

    for i in range(1, n):
        p = heapq.heappop(h)
        ans += -p
        heapq.heappush(h, -a[i])
        heapq.heappush(h, -a[i])

    return ans


def main():
    n = ri()
    a = ria()
    wi(solve(n, a))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
arr = list(map(int, input().split()))
arr.sort()
ans = 0
cnt = 1
for i in range(1,N):
    if cnt < 2:
        ans += arr[-1]
        cnt += 1
        if cnt == 2:
            cnt = 0
            arr.pop()
print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N = int(input())
    A = [int(x) for x in input().split()]

    A.sort(reverse=True)

    c = 0
    ans = A[0]

    for i in range(2, N):
        if i % 2 == 0:
            c += 1
        ans += A[c]

    print(ans)

    
    

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

A.sort(reverse=True)

dq = deque([])

ans = 0
dq.append(A[0])

for i in range(1, N):
    ans += dq.popleft()
    dq.append(A[i])
    dq.append(A[i])
print(ans)

Submission status: Accepted

Solution code:
import heapq as hq
N = int(input())
A = list(map(int,input().split()))
A.sort()
A.reverse()
ans = 0
seat = [-A[0]]
hq.heapify(seat)
for i in range(1, N):
	a = A[i]
	ans -= hq.heappop(seat)
	hq.heappush(seat, -a)
	hq.heappush(seat, -a)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())-2
a=list(map(int,input().split()))
a.sort(reverse=True)
ind=1
ans=a[0]
co=0
while n>0:
  co+=1
  ans+=a[ind]
  if co==2:
    co=0
    ind+=1
  n-=1
print(ans)

Submission status: Accepted

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

A.sort(reverse = True)

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import heapq


def solve(N: int, A: "List[int]"):
    A = list(reversed(sorted(A)))
    c = 0
    q = []
    heapq.heappush(q,(-A[0],A[0],A[0]))
    for i in range(1,N):
        a = A[i]
        pt = heapq.heappop(q)
        heapq.heappush(q,(-a,a,pt[1]))
        heapq.heappush(q,(-a,pt[2],a))
        c += -pt[0]
    print(c)
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
# import numpy as np
sys.setrecursionlimit(int(pow(10,6)))
# sys.stdin = open("input.txt", "r")
# sys.stdout = open("out.txt", "w")
mod = int(pow(10, 9) + 7)
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(*var, end="\n"): sys.stdout.write(' '.join(map(str, var))+end)
def L(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]

# @lru_cache(None)

t=1
# t=int(input())
for _ in range(t):
    n=L()[0]
    A=L()
    A.sort(reverse=True)
    ans=A[0]
    for i in range(1,n-1):
        if i%2:
            ans+=A[(i+1)//2]
        else:
            ans+=A[i//2]
    print(ans)

Submission status: Accepted

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

A.sort()

ans = 0
ans += A.pop()
count = n-2
for i in range(n):
    num = A.pop()
    if count == 0:
        break
    if count == 1:
        ans += num
        break

    ans += num*2
    count -= 2

print(ans)

Submission status: Accepted

Solution code:
from math import ceil

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

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

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
#print(a)
ans = a[0]

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

Submission status: Accepted

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

A.sort(reverse=True)
print(A[0] + sum(A[1:(N - 2) // 2 + 1]) * 2 + A[(N - 2) // 2 + 1] * (N % 2))

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
N = int(input())
A = sorted(list(map(int, input().split())), reverse=True)
gaps = [-A[0]]
ans = 0
for a in A[1:]:
    x = heappop(gaps)
    ans += -x
    heappush(gaps, -a)
    heappush(gaps, -a)
print(ans)