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:
N=int(input())
B=list(map(int,input().split()))
A=sorted(B,reverse=True)
if N==2:
    print(A[0])
else:
    ans=0
    if N%2==1:
        if N==3:
            ans=A[0]+A[1]
        else:
            ans+=A[0]
            for i in range(1,N//2):
                ans+=2*A[i]
            ans+=A[N//2]
    else:
        ans+=A[0]
        for j in range(1,N//2):
            ans+=2*A[j]
    print(ans)

Submission status: Accepted

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

for i in range(1,(n+1)//2):
    k+=m[i]

if n%2==0:
    k+=m[(n+1)//2-1]
print(k)

Submission status: Accepted

Solution code:
import math
import bisect
import copy
#import time
import itertools
#map(int,input().split())
#int(x) for x in input().split()
#for _ in range(int(input()))

n=int(input())
l=[int(x) for x in input().split()]
l.sort(reverse=True)
ans=0
if n%2==0:
	n=n-2
	ans+=l[0]
	for i in range(1,len(l)):
		if n==0:
			break
		else:
			ans+=2*l[i]
			n-=2
else:
	n=n-2
	ans+=l[0]
	for i in range(1,len(l)):
		if n==1:
			break
		else:
			ans+=2*l[i]
			n-=2
	ans+=l[i]
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

ans = a[0]

nn = (n-2)//2
nnn = (n-2)%2

for i in range(nn):
    ans = ans + a[i+1]*2

if nnn == 1:
    ans = ans + a[i+2]

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
n=int(input())
a=list(map(int,input().split()))
a.sort(reverse=True)

sm=a[0]
i=1
c=n-2
while c>0:
  if c>=2:
    sm+=2*a[i]
    c-=2
  elif c==1:
    sm+=a[i]
    break
  else:
    break
 
  i+=1
print(sm)

Submission status: Accepted

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

A.sort(reverse=True)

comfort = list()
comfort.append(A[0])
for i in range(1, N):
    comfort.append(A[i])
    comfort.append(A[i])

ans = sum(comfort[:N-1])
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
arr=[int(i) for i in input().split()]
arr.sort(reverse=True)
i=0
j=1
res=arr[0]
n-=2
while n:
    k=min(2,n)
    res+=arr[j]*k
    n-=k
    j+=1
print(res)

Submission status: Accepted

Solution code:
import sys
from collections import deque
def I(): return int(sys.stdin.readline().rstrip())
def IL(): return map(int,sys.stdin.readline().rstrip().split())

def Main():
    n = I()
    a = list(IL())
    da = sorted(a,reverse=True)
    if n<=4:
        ans = sum(da[:-1])
        print(ans)
        return
    ans = sum(da[:3])
    idx = 0
    for i in range(4,n):
        if i<6:
            ans += da[i-3]
        elif i<8:
            ans += da[3]
        else:
            if i==8:
                idx = 4
            if i%2:
                idx += 1
            ans += da[i-idx]
    print(ans)
    return

if __name__=='__main__':
    Main()

Submission status: Accepted

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


def solve(N: int, A: "List[int]"):
    A = sorted(A, reverse=True)

    queue = [-A[0]]
    heapq.heapify(queue)

    answer = 0
    for i, a in enumerate(A[1:]):
        max_val = heapq.heappop(queue)
        answer += -max_val

        heapq.heappush(queue, -a)
        heapq.heappush(queue, -a)
    print(answer)

    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:
n = int(input())
A = sorted([int(i) for i in input().split()], reverse = True)
if n == 1:
    print(0)
else:
    ans = A[0]
    ans += 2*sum(A[1:(n-1)//2+1])
    if n%2:
        ans -= A[(n-1)//2]
    print(ans)

Submission status: Accepted

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

def main():
    n = int(input())
    a = list(map(int, input().split()))

    a.sort(reverse=True)
    if n % 2 == 0:
        conf = a[0]
        for i in range(1, n//2):
            conf += a[i] * 2
    else:
        conf = a[0]
        for i in range(1, (n-1)//2):
            conf += a[i] * 2
        conf += a[(n-1)//2]

    print(conf)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = sorted(map(int, input().split()))[::-1]

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

N = int(input())
A = list(map(int, sys.stdin.readline().rsplit()))
A.sort(reverse=True)

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

print(res)

Submission status: Accepted

Solution code:
a=int(input())
list1=list(map(int,input().split()))
list2=sorted(list1,reverse=True)
k=1
sum1=list2[0]
s=a-2
while(s>0) :

  if s==1 :
    sum1+=list2[k]
    break
  else :
    sum1+=list2[k]*2
    k+=1
    s-=2

print(sum1)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    A = list(map(int, input().split()))
    A.sort(reverse = True)
    ans = A[0]
    q, r = divmod(n - 2, 2)
    for a in A[1:1 + q]:
        ans += 2 * a
    if r == 1:
        ans += A[q + 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)
ans = A[0]
res = N - 2
q, m = divmod(res, 2)
for i in range(1, q+1):
    ans += 2 * A[i]
if m != 0:
    ans += A[i+1]

print(ans)

Submission status: Accepted

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())

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

a.sort(reverse=True)

ans = 0

ans += a[0]

for i in range(1, int(len(a)/2)):
    ans += a[i] * 2

if len(a) % 2 == 0:
    print(ans)
else:
    print(ans + a[int(len(a)/2)])

Submission status: Accepted

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

print(ans)

Submission status: Accepted

Solution code:
import math
N = int(input())
Arr = list(map(int,input().split()))
Arr.sort(reverse=True)
Sum = 0
for i in range(N//2):
    Sum += Arr[i]
for i in range(1,math.ceil(N/2)):
    Sum += Arr[i]
print(Sum)

Submission status: Accepted

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

x = math.ceil(len(b)/2)
y = b[:x]
z = sum(y*2)-y[0]
if len(b)%2==1:
    print(z-y[-1])
else:
    print(z)

Submission status: Accepted

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

A.sort(reverse=True)
syugo = [0]*N
syugo[0] = A[0]
syugo[1] = A[1]
flg = False
ans = A[0]
idx = 1
for i in range(2, N):
    if flg:
        ans += A[idx]
        flg = False
        idx += 1
    else:
        ans += A[idx]
        flg = True

print(ans)

Submission status: Accepted

Solution code:
#関数リスト
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

n = I()
mylist = LI()
mylist.sort(reverse=True)

result = mylist[0]

if n % 2==0:
    for i in range(1,n//2):
        result += mylist[i]*2
    print(result)
else:
    for i in range(1,n//2):
        result += mylist[i]*2
    temp = (n-1)//2
    result += mylist[temp]
    print(result)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Jul  5 21:45:44 2020

@author: NEC-PCuser
"""
import heapq

N = int(input())

a = list(map(int, input().split()))
a.sort(reverse=True)
ans = 0
b = [-a[0]]
heapq.heapify(b)
for i in range(1, N):
    ans -= heapq.heappop(b)
    heapq.heappush(b, -a[i])
    heapq.heappush(b, -a[i])
    
print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
x = [3,3]

temp = 3
for i in range(1,30):
    temp *= 2
    x.append(temp)
    
a.sort(reverse = True)
sepa = []
un = []
j,k = 0,0
for i in range(n):
    if j == x[k]:
        sepa.append(un)
        un = []
        un.append(a[i])
        k += 1
        j = 1
        
    else:
        un.append(a[i])
        j += 1
        
sepa.append(un)

if len(sepa) >= 3:
    ans = sepa[0][0] + (sepa[0][1] + sepa[0][2]) * 2
    for i in range(len(sepa)-2):
        for j in range(len(sepa[i+2])):
            ans += sepa[i+1][j//2]
            
else:
    p = [0,1,1,2,2]
    ans = 0
    for i in range(n-1):
        ans += sepa[0][p[i]]
            
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
lst = [int(i) for i in input().split()]
lst = sorted(lst)
count = 0
ans = 0
if n % 2 == 0:
    c = n//2
else:
    c = n//2+1
while count < c:
    if count == 0:
        num = lst.pop(-1)
        ans += num
    else:
        num = lst.pop(-1)
        ans += num * 2
    count += 1
if n % 2 == 1:
    ans -= num
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
num = [A[0]]
for a in A[1:]:
    num += [a] * 2

ans = sum(num[:N-1])
print(ans)

Submission status: Accepted

Solution code:
import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n=int(input())
a=sorted(lmp(),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()))

A = sorted(A, reverse=True)
ans = A[0]
A = A[1:]
ans += 2 * sum(A[:(N-2)//2])
if N % 2 == 1:
  ans += A[(N-2)//2]
print(ans)

Submission status: Accepted

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

    import heapq
    l = []
    heapq.heapify(l)
    heapq.heappush(l, -1 * a[0])
    # ne[0,0] = a[0]
    # ne[0,1] = a[0]
    ans = 0

    for i, aa in enumerate(a):
        if i == 0:
            continue
        v = heapq.heappop(l) * -1
        ans += v
        heapq.heappush(l,aa * -1)
        heapq.heappush(l,aa * -1)
    print(ans)
if __name__=='__main__':
    main()

Submission status: Accepted

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


ans+=A[0]
if (N-2)%2==0:
    ans+=sum(A[1:int((N-2)/2)+1])*2
else:
    ans+=sum(A[1:int((N-3)/2)+1])*2
    ans+=A[int((N-1)/2)]


print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

A = sorted(A, reverse=True)

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

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)//2):
    ans += (A[i+1]*2)
    
if N%2 == 1:
    ans += A[i+2]
    
print(ans)

Submission status: Accepted

Solution code:
import sys
from operator import itemgetter
from heapq import heappush

sys.setrecursionlimit(10**9)
input = sys.stdin.readline

def ii(): return int(input())
def mi(): return map(int, input().split())
def lmi(): return list(map(int, input().split()))
def lmif(n): return [list(map(int, input().split())) for _ in range(n)]
def ss(): return input().split()

def main():
    N = ii()
    A = lmi()

    A.sort(reverse=True)
    ans = 0
    for i in range(N-1):
        ans += A[(1+i)//2]

    print(ans)

    return

main()

Submission status: Accepted

Solution code:
n = int(input())
friendliness = [int(s) for s in input().split()]

friendliness.sort(reverse=True)
print(friendliness[0] + 2 * sum(friendliness[1:n//2]) + (n%2) * friendliness[n//2])

Submission status: Accepted

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


def ceil(a, b):
    return -(-a // b)


if n % 2 == 0:
    ans = sum(al[:n//2-1])
    top = al[:n//2]
    ans += top[-1]
    ans += sum(top[1:])
    print(ans)
else:
    ans = sum(al[:(n+1)//2-1])
    ans += sum(al[1:1+n//2])
    print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import deque
def main():
    N = int(input())
    A = deque(sorted(list(map(int, input().split()))))
    ans = A.pop()
    for i in range(N - 2):
        if i%2 == 0:
            x = A.pop()
        ans += x
    print(ans)
            
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n=int(input())
    a=sorted(map(int,input().split()),reverse=True)
    ans = a[0]
    c = 1
    for i in a[1:]:
        if c >= n-1:
            break
        c += 1
        ans += i
        if c >= n-1:
            break
        c += 1
        ans += i
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

sa = sorted(a,reverse=True)

c = 1
ans = sa[0]


for i in range(1, len(sa)):
    if n <= 0:
        break
    elif n == 1:
        ans += sa[i]
        n -= 1
    else:
        ans += sa[i]*2
        n -= 2
        # print(sa[i])

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# abc173_d.py
import math
N = int(input())
A = list(map(int,input().split()))
A.sort(reverse=True)
ans = 0
for i in range(N-1):
    ans += A[math.ceil(i/2)]
print(ans)

Submission status: Accepted

Solution code:
import math

n = int(input())
a = list(map(int, input().split()))
ans = 0

a = sorted(a, reverse=True)
for i in range(1,n):
    x = math.floor(i/2)
    ans += a[x]

print(ans)

Submission status: Accepted

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

l=[a[i//2] for i in range(n)]

print(sum(l[1:]))

Submission status: Accepted

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

Submission status: Accepted

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

if N == 2:
    print(max(A))
    exit(0)

A.sort(reverse=True)

ans = A[0]
cur = 1
for ix in range(len(A[2:])):
    ans += A[cur]
    if ix & 1:
        cur += 1

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = sorted([int(i) for i in input().split()], reverse=True)

S = A[0]
step = 2

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

print(S)

Submission status: Accepted

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from math import factorial, sqrt, ceil, gcd
from functools import lru_cache, reduce
from decimal import Decimal
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定
def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True


# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

def num_divisors_table(n):
    table = [0 for i in range(n + 1)]
    
    for i in range(1, n + 1):
        for j in range(i, n + 1, i):
            table[j] += 1
    
    return table

# ここから書き始める
n = int(input())
a = sorted(list(map(int, input().split())), reverse=True)

ans = a[0]
cnt = 1
for i in range(1, n):
    if cnt + 1 == n:
        break
    ans += a[i]
    cnt += 1
    if cnt + 1 == n:
        break
    ans += a[i]
    cnt += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def main():
    n = int(input())
    an = list(map(int, input().split()))
    an.sort(reverse=True)
    ans = 0
    for i in range(1, n):
        d=i//2
        ans +=an[d]
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import  math
from heapq import *
import fractions
import bisect
stdin = sys.stdin
     
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

N=int(input())
A=nl()
A.sort(reverse=True)

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

print(ans)

Submission status: Accepted

Solution code:
import heapq

n=int(input())
A=list(map(int, input().split()))
for i in range(n):
    A[i]=A[i]*(-1)
heapq.heapify(A)
ans=0
for i in range(n):
    a=heapq.heappop(A)
    if i==0:
        B=[a]
        heapq.heapify(B)
    else:
        b=heapq.heappop(B)
        ans=ans+b
        heapq.heappush(B, a)
        heapq.heappush(B, a)
print(-ans)

Submission status: Accepted

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10**9)
INF = 10**9
mod = 10**9+7

N = i()
A = l()
A.sort(reverse=True)
ans = 0
lis = [A[0]]
A = A[1:]
for i in range(N-1):
    lis.append(A[i])
    lis.append(A[i])
for i in range(N-1):
    ans += lis[i]
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

if n ==2:
    print(als[0])
    exit()

if n % 2==0:
    m = n//2
    res=sum(als[:m-1]) + sum(als[1:m])+als[m-1]

else:
    m = n//2
    res = sum(als[:m]) + sum(als[1:m+1])
    
print(res)

Submission status: Accepted

Solution code:
n = int(input())
a = sorted(list(map(int, input().split())))[::-1]
ans = -max(a)
cnt = 0

if n%2 == 0:
    for i in a:
        ans += i*2
        cnt += 2
        if cnt == n:
            print(ans)
            exit()
else:
    for i in a:
        ans += i*2
        cnt += 2
        if cnt >= n:
            print(ans - i)
            exit()

Submission status: Accepted

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

an.sort(reverse=True)

ans = an[0]

if n == 2:
    print(ans)
    exit()

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

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

print(S)

Submission status: Accepted

Solution code:
N=int(input())
A=sorted(list(map(int,input().split())))[::-1]

i=1
t=1
score=A[0]
while i<=N-1:
    if i+2<=N-1:
        score+=2*A[t]
        i+=2
        t+=1
    elif i+1<=N-1:
        score+=A[t]
        break
    else:
        break
    #print(i,t,score)
print(score)

Submission status: Accepted

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

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

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

ans = 0
for i, a in enumerate(A):
    if i==0:
        ans += a
        itr = 2
        if itr >= N:
            break
    else:
        ans += a
        itr += 1
        if itr >= N:
            break
        ans += a
        itr += 1
        if itr >= N:
            break

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
n=int(input())
a=list(map(int,input().split()))

a.sort(reverse=True)                    

comfort=0
q=deque()
q.append(a[0])
for i in range(1,n):
    comfort=comfort+q.popleft()
    q.append(a[i])
    q.append(a[i])

print(comfort)

Submission status: Accepted

Solution code:
import heapq
N=int(input())
A=list(map(int,input().split()))
A.sort(reverse=True)
count=0
Q=[]
heapq.heapify(Q) 
heapq.heappush(Q, (-A[0],-A[0],0))
for i in range(1,N):
    B=heapq.heappop(Q)
    count+=-B[0]
    heapq.heappush(Q, (-A[i],-A[i],B[1]))
    heapq.heappush(Q, (-A[i],-A[i],B[2]))
print(count)

Submission status: Accepted

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


a.sort(reverse=True)
cnt = a.pop(0)
if (n-2) % 2 == 0:
    tmp = 2 * sum(a[0:(n-2)//2])
else:
    tmp = 2 * sum(a[0:(n-2)//2]) + a[(n-2)//2]
cnt += tmp
print(cnt)

Submission status: Accepted

Solution code:
import numpy as np


n = int(input())
ajs_str = input().split()
ajs = [int(aj) for aj in ajs_str]

ajs_sorted = np.sort(ajs)[::-1]

score = ajs_sorted[0]
count = 1
current_idx = 1


max_idx = int( (n-2) / 2 )

for idx in range(1, 1+max_idx):
  score += 2 * ajs_sorted[idx]

if (n-2) % 2 != 0:
  score += ajs_sorted[1+max_idx]

print(score)

Submission status: Accepted

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

ans = a[0]
i = 0
for i in range(1, (n-2) // 2 + 1):
    ans += a[i] * 2
    
if (n-2) % 2 == 1 and not n-2 == 1:
    ans += a[i+1]
    
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

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

pq = [-A[0]]
ans = 0

for a in A[1:]:
    v = -heappop(pq)
    ans += v
    heappush(pq, -a)
    heappush(pq, -a)

print(ans)

Submission status: Accepted

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


circle = [arr[0]]

s = 0

i = 1
UNDEF = -1
while len(circle) != len(arr):
    new_circle = []
    for v in circle:
        new_circle.append(v)
        new_circle.append(UNDEF)
    circle = new_circle
    positions = list(range(1, len(circle), 2))
    weights = [UNDEF] * len(circle)
    for pos in positions:
        weights[pos] = min(circle[(pos - 1) % len(circle)], circle[(pos + 1) % len(circle)])

    positions.sort(key=lambda pos: weights[pos], reverse=True)
    # print(circle)
    # print(positions)
    # print(weights)
    j = 0
    while i < len(arr) and j < len(positions):
        circle[positions[j]] = arr[i]
        w = weights[positions[j]]
        i += 1
        j += 1
        s += w
    circle = [v for v in circle if v != UNDEF]

print(s)

Submission status: Accepted

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

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

n = I()
a = LI()
a.sort(reverse=True)
ans = a[0]
count = 1
for i in range(1, n):
    if n - 1 <= count + 2:
        ans += a[i] * (n-1 - count)
        break
    else:
        ans += a[i] * 2
        count += 2
print(ans)

Submission status: Accepted

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

comfort.sort(reverse=True)
# print(comfort)
ans = 0
for i in range(1,n):
    ans += comfort[(i)//2]
    # print((i-1)//2)

print(ans)

Submission status: Accepted

Solution code:
import heapq
def main():
    n = int(input())
    a = [int(t)for t in input().split()]

    a = sorted(a)
    ans = 0

    paired = []

    prev = a.pop()
    temp = a.pop()
    heapq.heappush(paired,(-temp,-prev))
    heapq.heappush(paired,(-temp,-prev))
    ans += prev

    
    for _ in range(n-2):
        temp = a.pop()
        pair = heapq.heappop(paired)

        ans -= pair[0]
        heapq.heappush(paired,(-temp,pair[0]))
        heapq.heappush(paired,(-temp,pair[1]))

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import heapq as hp
n = int(input())
a = list(map(int, input().split()))
b = n//2 +1
c = hp.nlargest(b, a)
ans = c[0]
for i in range(2,n):
    ans += c[i//2]
print(ans)