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 math
from math import gcd
INF = float("inf")

import sys
input=sys.stdin.readline
import itertools
from collections import Counter

def main():
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    ans = 0 + a[-1]
    for i in range(n-2):
        k = a[-((i+4)//2)]
        ans += k
    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]
cnt = 1
for i in range(1, n):
    if cnt == n - 1:
        break
    ans += a[i]
    cnt += 1
    if cnt == n - 1:
        break
    ans += a[i]
    cnt += 1
print(ans)

Submission status: Accepted

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

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

    # 降順にぶちこむ人を選んでいく。
    # 実際に手で書けばわかるが、ある数がn個あるとき、
    # n*2回心地よさを感じるようになる。
    # ただし、最初の1個目だけは心地よさ0なので、そこを考慮する
    dic = {}
    for a in As:
        if not a in dic: dic[a] = 0
        dic[a] += 1

    keys = []
    for key in dic.keys():
        keys.append(key)
    keys.sort(reverse=True)

    ans = 0
    n = N - 1
    dic[keys[0]] -= 1
    ans += keys[0]
    n -= 1

    for i, key in enumerate(keys):
        if dic[key] == 0:
            continue

        if (dic[key]*2) <= n:
            ans += key*(dic[key]*2)
            n -= dic[key]*2
        else:
            ans += key*n
            n -= n
            break

    print(ans)


if __name__ == "__main__":
    solve()

Submission status: Accepted

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

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

    # 降順にぶちこむ人を選んでいく。
    # 実際に手で書けばわかるが、ある数がn個あるとき、
    # n+1回心地よさを感じるようになる。
    dic = {}
    for a in As:
        if not a in dic: dic[a] = 0
        dic[a] += 1

    keys = []
    for key in dic.keys():
        keys.append(key)
    keys.sort(reverse=True)

    ans = 0
    n = N - 1
    dic[keys[0]] -= 1
    ans += keys[0]
    n -= 1

    for i, key in enumerate(keys):
        if dic[key] == 0:
            continue

        if (dic[key]*2) <= n:
            ans += key*(dic[key]*2)
            n -= dic[key]*2
        else:
            ans += key*n
            n -= n
            break

    print(ans)


if __name__ == "__main__":
    solve()

Submission status: Accepted

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

aa = a + a
aa.sort(reverse=True)

ans = 0
for i in range(1, n):
    ans += aa[i]

print(ans)

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest
import os
import heapq

# 再帰処理上限(dfs作成時に設定するのが面倒なので限度近い値を組み込む)
sys.setrecursionlimit(999999999)


# 検索用タグ、優先度付きキュー、値の大きい物から取得

# 実装を行う関数
def resolve(test_def_name=""):
    n = int(input())
    a_s = list(map(int, input().split()))

    a_s.sort(reverse=True)

    # 優先度付きキューの作成
    que = []
    heapq.heapify(que)

    ans = 0
    # 大きい値から順番に処理していく
    for cnt, a in enumerate(a_s):
        # 大きい値から順番に処理していくため、値を反転(優先度付きキュー利用時の注意)
        a = -a
        if cnt == 0:
            # ループ一回目の時だけ、こっちを通過。
            heapq.heappush(que, a)
            continue

        # キューから値の取り出し
        target = heapq.heappop(que)
        ans += -target
        # 現在の値を追加できるパターンが2つできるので、それをキューに追加
        heapq.heappush(que, a)
        heapq.heappush(que, a)

    print(ans)


# テストクラス
class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """4
2 2 1 3"""
        output = """7"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """7
1 1 1 1 1 1 1"""
        output = """6"""
        self.assertIO(test_input, output)

    # 自作テストパターンのひな形(利用時は「tes_t」のアンダーバーを削除すること
    def test_1original_1(self):
        test_input = """4
2 2 3 3"""
        output = """9"""
        self.assertIO(test_input, output)


# 実装orテストの呼び出し
if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        # AtCoder提出時の場合
        resolve()

    else:
        # 自PCの場合
        unittest.main()

Submission status: Accepted

Solution code:
n = int(input())
arr = [int(x) for x in input().split()]
arr = sorted(arr)
arr.reverse()
d = []
d.append(1)
current = 0
s = 0
for i in range(1,len(arr)):
    d[current] -= 1
    s += arr[current]
    if d[current] == 0:
        current += 1
    d.append(2)
print(s)

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:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

def main():
  n = int(input())
  la = list(map(int, input().strip().split()))
  la.sort(reverse=True)
  ans = sum(la[:(n+1)//2]) * 2 - la[0] - (la[(n+1)//2-1] if n%2==1 else 0)
  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]
N -= 2
for i in range(1, N):
    if N >= 2:
        ans += A[i]*2
        N -= 2
    elif N  == 1:
        ans += A[i]
        N -= 1
    else:
        break
print(ans)

Submission status: Accepted

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

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

a.sort(reverse=True)

m = (n-1)//2

if (n-1) % 2 == 1:
    print(sum(a[:m]) + sum(a[1:m+1]) + a[m])
else:
    print(sum(a[:m]) + sum(a[1:m+1]))

Submission status: Accepted

Solution code:
n = int(input())
a = sorted(list(map(int, input().split())), reverse=True)
sum_com = 0
distinct_a = sorted(list(set(a)), reverse=True)
comfort = {i: 0 for i in distinct_a}
comfort[a[0]] = 1
max_com = 0

for ai in a[1:]:
    sum_com += distinct_a[max_com]
    if distinct_a[max_com] == ai:
        comfort[distinct_a[max_com]] += 1
    else:
        comfort[distinct_a[max_com]] -= 1
        comfort[ai] += 2
        if comfort[distinct_a[max_com]] == 0:
            max_com += 1

print(sum_com)

Submission status: Accepted

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

Submission status: Accepted

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

ans = 0
for i in range(n-1):
    ans += aa[(i + 1) // 2]
#     print(ans)

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:
  for i in range(1,int(N/2)):
    ans = ans + A[i]*2
if N%2 == 1:
  for i in range(1,int((N-1)/2)):
    ans = ans + A[i]*2
  ans += A[int((N-1)/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 = A[0]
    for i in range(N//2-1):
        ans += 2*A[i+1]
else:
    ans = A[0]
    for i in range(N//2-1):
        ans += 2*A[i+1]
    ans += A[N//2]

print(ans)

Submission status: Accepted

Solution code:

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

X.sort(reverse=True)
ans = 0
cnt = 0
j = 0
for i in range(N):
    if i == 0:
        continue
    elif i == 1:
        ans += X[j]
        j += 1
    else:
        ans += X[j]
        cnt += 1
        if cnt == 2:
            j += 1
            cnt = 0

print(ans)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
A.sort(reverse=True)
"""
10       9       8          0+10+9
10   7   9   6   8   5      +9+8+8
10 4 7 3 9 2 6 1 8 0 5 -1   +7+7+6+6  +5+5
                            +4+4+3+3+2+2+1+1+..."""
ans=A[0]

if N>=3:
    ans+=A[1]
if N>=4:
    ans+=A[1]
if N>=5:
    ans+=A[2]
if N>=6:
    ans+=A[2]
if N>=7:
    if N%2:
        ans+=sum(A[3:3+(N+1-6)//2])*2
        ans-=A[3+(N-6)//2]
    else:
        ans+=sum(A[3:3+(N-6)//2])*2
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
l = list(map(int,input().split()))
l.sort()
largest = l[-1]
que = deque(l)
cnt = n
ans = 0
while cnt > 0:
    x = que.pop()
    ans += x
    cnt -= 1
    if cnt != 0:
        ans += x
        cnt -= 1
print(ans-largest)

Submission status: Accepted

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

Submission status: Accepted

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

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())

conf = 0
from heapq import heapify, heappop, heappush
As.sort(reverse=True)
m = As.pop(0)
s = As.pop(0)
conf += m
Q = []
heappush(Q, -s)
heappush(Q, -s)
for a in As:
    s = heappop(Q)
    conf -= s
    heappush(Q, -a)
    heappush(Q, -a)
print(conf)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort()
if N==2:
    print(max(A))
    exit()

ans = A.pop()
n = N-2
while A:
    a = A.pop()
    for _ in range(2):
        n -= 1
        ans += a
        if n==0:
            print(ans)
            exit()

Submission status: Accepted

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

ans = A[0]
cnt = 1
for a in A[1:]:
    if cnt + 1 < N:
        ans += a
        cnt += 1

    if cnt+ 1 < N:
        ans += a
        cnt += 1
print(ans)

Submission status: Accepted

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

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

for i in range(1, N):
    l.append(A[i])
    l.append(A[i])

print(sum(l[:N-1]))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(read())


def ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from functools import reduce
from math import gcd


def lcm(a, b):
    # 最小公倍数
    g = gcd(a, b)
    return a // g * b

# https://atcoder.jp/contests/abc173/tasks/abc173_d
# 大きい方から使いそう


N = a_int()
A = ints()
A.sort(reverse=True)
ans = A[0]
cnt = 1
for a in A[1:]:
    if cnt == N - 1:
        break
    ans += a
    cnt += 1
    if cnt == N - 1:
        break
    ans += a
    cnt += 1

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

a.sort(reverse=True)

count = 0
if N % 2 == 0:
  for i in range(int(N/2)):
    count += 2 * a[i]
  count -= a[0]
else:
  for i in range(int((N+1)/2)):
    count += 2 * a[i]
  count -= a[0]
  count -= a[int((N-1)/2)]
    
print(count)

Submission status: Accepted

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

Submission status: Accepted

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

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
arr=list(map(int,input().split()))
arr.sort()
count=3
comfort=arr[n-1]
pos=n-2
while(count<=n):
	comfort+=arr[pos]
	if(count%2==0):
		pos-=1
	count+=1
print(comfort)

Submission status: Accepted

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

ans = 0

for i in range(N-1):
    ans += a[(i+1)//2]
print(ans)

Submission status: Accepted

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

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

print(answer)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**7)
import bisect
import heapq
import itertools
import math
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from math import gcd
from operator import add, itemgetter, mul, xor
def cmb(n,r,mod):
  bunshi=1
  bunbo=1
  for i in range(r):
    bunbo = bunbo*(i+1)%mod
    bunshi = bunshi*(n-i)%mod
  return (bunshi*pow(bunbo,mod-2,mod))%mod
mod = 10**9+7
def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return map(int,input().split())
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]

#bisect.bisect_left(list,key)はlistのなかでkey未満の数字がいくつあるかを返す
#bisect.bisect_right(list, key)はlistのなかでkey以下の数字がいくつあるかを返す
#これを応用することで
#len(list) - bisect.bisect_left(list,key)はlistのなかでkey以上の数字がいくつあるかを返す
#len(list) - bisect.bisect_right(list,key)はlistのなかでkeyより大きい数字がいくつあるかを返す
#これらを使うときはあらかじめlistをソートしておくこと！
n = I()
a =LI()
a.sort(reverse=True)
ans = 0
for i in range(n):
  ans += a[i//2]
print(ans - a[0])

Submission status: Accepted

Solution code:
import heapq

#入力:[n1,n2,...nk](int:整数配列)
def input_array():
	return list(map(int,input().split()))

n=int(input())
A=input_array()
sortA=sorted(A,reverse=True) #降順にソート

ans=0
q=[]
heapq.heappush(q,-sortA[0])

for i in range(1,n):
	tmp=heapq.heappop(q)
	tmp*=-1
	ans+=tmp
	heapq.heappush(q,-sortA[i])
	heapq.heappush(q,-sortA[i])
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
*A, = map(int, input().split())
A.sort(reverse=True)
k = (N+1)//2

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

print(ans)

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

Solution code:
def solve():
  N = int(input())
  A = list(map(int, input().split()))
  A.sort(reverse=True)
  ans = A[0]
  cnt = 1
  for i in range(1,N-1):
    ans += A[i]
    cnt += 1
    if cnt==N-1:
      break
    ans += A[i]
    cnt += 1
    if cnt==N-1:
      break
  return ans
print(solve())

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
# 全部のパターンだとN**2
# 仕組み的に低い人ほどあとにきた方がうまくいきそうに見える
A.sort(reverse=1)
s = A[0]
for i in range(N-2):
    p = i
    if i % 2 == 1:
        p -= 1
    s += A[p//2+1]
print(s)

Submission status: Accepted

Solution code:
# ------------------- fast io --------------------
import os
import sys
from io import BytesIO, IOBase

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")

# ------------------- fast io --------------------
from math import gcd, ceil

def pre(s):
    n = len(s)
    pi = [0] * n
    for i in range(1, n):
        j = pi[i - 1]
        while j and s[i] != s[j]:
            j = pi[j - 1]
        if s[i] == s[j]:
            j += 1
        pi[i] = j
    return pi


def prod(a):
    ans = 1
    for each in a:
        ans = (ans * each)
    return ans

def lcm(a, b): return a * b // gcd(a, b)


def binary(x, length=16):
    y = bin(x)[2:]
    return y if len(y) >= length else "0" * (length - len(y)) + y


for _ in range(int(input()) if not True else 1):
    #n, k = map(int, input().split())
    #a, b = map(int, input().split())
    #c, d = map(int, input().split())
    n = int(input())
    a = sorted(list(map(int, input().split())), reverse=True)
    #b = list(map(int, input().split()))
    ans = 0
    for i in range(n-1):
        ans += a[(i+1)//2]
    print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

sorted_A = sorted(A, reverse=True)
a = N // 2

answer = 2*sum(sorted_A[0:a]) - sorted_A[0]

if N % 2 == 1:
    answer += sorted_A[a]

print(answer)

Submission status: Accepted

Solution code:
import math

def resolve():

    n = int(input())
    values = list(map(int, input().split(' ')))

    values.sort(reverse=True)

    ans = 0

    for i in range(1, n):

        ans += values[math.floor(i / 2)]

    print(ans)


resolve()

Submission status: Accepted

Solution code:
from math import ceil
n=int(input())
lst=list(map(int, input().split()))
cut=ceil(n/2)
lst=sorted(lst,reverse=True)
arr=lst[:cut]
f=arr[0]
if n%2==0:
    for i in range(1,len(arr)):
        f+=2*arr[i]
else:
    for i in range(1,len(arr)):
        if i==len(arr)-1:
            f+=arr[i]
        else:
            f+=2*arr[i]
print(f)

Submission status: Accepted

Solution code:
import heapq
n = int(input())
A = list(map(int, input().split()))
A = sorted(A, reverse=True)
ans = 0
q = []
heapq.heappush(q, A[0]*-1)
for i in range(1, n):
    tmp = heapq.heappop(q)
    ans += tmp
    heapq.heappush(q, A[i] * -1)
    heapq.heappush(q, A[i] * -1)

print(ans*-1)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
a=[-int(j) for j in input().split()]
a.sort()
import heapq
l=[a[0]]
heapq.heapify(l)
ans=0
for i in a[1:]:
    heapq.heappush(l,i)
    heapq.heappush(l,i)
    p=heapq.heappop(l)
    ans-=p
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

# print(A)
mina = min( A )
maxa = max( A )

A.sort()
A.reverse()

sum = 0
for i in range(n-1):
    sum +=A[(i+1)//2]
    # print(A[(i+1)//2])

# print(mina)
# print(maxa)
# print(sum)
print(sum)

Submission status: Accepted

Solution code:

if __name__ == '__main__':
    n = int(input())
    a = list(map(int,input().split()))
    asort = sorted(a,reverse=True)
    if n % 2 == 0:
        use = n // 2
        res = sum(asort[:use])*2 - max(asort)
    else:
        use = n // 2 + 1
        res = sum(asort[:use])*2 - max(asort) - min(asort[:use])
    print(res)

Submission status: Accepted

Solution code:
n = input()
friendliness = [int(item) for item in input().split()]
friendliness.sort()
def of_ans():
    sum_ = 0
    idx = 1
    while idx < len(friendliness):
        sum_ += friendliness[len(friendliness) - (idx // 2) - 1]
        idx += 1
    return sum_
print(of_ans())

Submission status: Accepted

Solution code:
import math
N = int(input())
A = sorted(list(map(int, input().split())),reverse=True)
s = A[0]

for i in range(1,N-1):
    s += A[math.ceil(i/2)]

print(s)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
A = sorted([int(x) for x in input().split()], reverse=True)

A = deque(A)
L = deque()

# print(A, L)
ans = A.popleft()
L.append(A.popleft())
F = True
for i in range(2, N):
    if F:
        ans += L[0]
        F = not F
    else:
        ans += L.popleft()
        L.append(A.popleft())
        F = not F
print(ans)

Submission status: Accepted

Solution code:
num=int(input().rstrip())
m=input().rstrip().split()
main=[]
for i in m:
    main.append(int(i))
sample=sorted(main,reverse=True)
result=0
for i in range(2,num+1):
    if i%2==0:
        y=i/2-1
        result+=sample[int(y)]
    else:
        y=(i+1)/2-1
        result+=sample[int(y)]
print(result)

Submission status: Accepted

Solution code:
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import product,permutations,combinations,combinations_with_replacement
from collections import defaultdict,Counter
from bisect import bisect_left,bisect_right
from math import gcd,ceil,floor,factorial
# from fractions import gcd
from functools import reduce
from pprint import pprint
from statistics import mean,median,mode

INF = float("inf")

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse_flag):
    data.sort(key=lambda x:x[col],reverse=reverse_flag)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def mycount(ls,x):
    # lsはソート済みであること
    l = bisect_left(ls,x)
    r = bisect_right(ls,x)
    return (r-l)

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

def I():
    return int(input())

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

def RI():
    return list(map(int,input().split()))

def CI(n):
    return [ int(input()) for _ in range(n) ]

def LI(n):
    return [ list(map(int,input().split())) for _ in range(n) ]

def S():
    return input()

def MS():
    return input().split()

def RS():
    return list(input().split())

def CS(n):
    return [ input() for _ in range(n) ]

def LS(n):
    return [ list(input().split()) for _ in range(n) ]

# ddict = defaultdict(lambda: 0)
# ddict = defaultdict(lambda: 1)
# ddict = defaultdict(lambda: int())
# ddict = defaultdict(lambda: list())
# ddict = defaultdict(lambda: float())

# https://www.youtube.com/watch?v=GXZZB5vO78c
n = I()
a = RI()
b = deepcopy(a)
b.sort(reverse=True)
# print(a)
# print(b)

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

Submission status: Accepted

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

A.sort(reverse=True)
score = A[0]
count = 1
for a in A[1:]:
    if count == len(A) - 1:
        break
    if count == (len(A) - 2):
        score += a
        count += 1
        continue
    score += a * 2
    count += 2

print(score)

Submission status: Accepted

Solution code:
def solve(string):
    n, *a = map(int, string.split())
    a = sorted(a, reverse=True)
    ans = sum(a[:(n + 1) // 2]) * 2 - a[0]
    ans -= a[(n + 1) // 2 - 1] if n % 2 else 0
    return str(ans)


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
comfort = list(map(int,input().split()))
comfort_reverse = np.sort(comfort)[::-1]

ans = comfort_reverse[0]

if N > 2:
    for i in range(N-2):
        num = i // 2 + 1
        ans += comfort_reverse[num]

print(ans)

Submission status: Accepted

Solution code:
n = int(input())

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

A.sort()
A.reverse()

ans = A[0]

L = [0 for i in range(n-1)]

j = 0
for i in range(n-2):
  if L[j] < 2:
    L[j] += 1
    ans += A[j+1]
  else:
    while L[j] >= 2:
      j += 1
    L[j] += 1
    ans += A[j+1]
print(ans)

Submission status: Accepted

Solution code:
# 降順にしたものを考え、最大のやつは1回、あとのやつは2回ずつ使える
n = int(input())
a = sorted(list(map(int, input().split())), reverse=True)
ans = a[0]
count = n - 2
idx = 1
while count > 0:
    count_of_count = 2
    while count_of_count > 0 and count > 0:
        count -= 1
        count_of_count -= 1
        ans += a[idx]
    idx += 1
print(ans)

Submission status: Accepted

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

a.sort()
a.reverse()
t = n - 1
ans = 0
for i in range(n):
    lim = 2
    if i == 0:
        lim = 1
    for j in range(lim):
        if t > 0:
            ans += a[i]
            t -= 1
print(ans)

Submission status: Accepted

Solution code:
#  =========     /\       /|    |====/|
#      |        /  \       |    |   / |
#      |       /____\      |    |  /  |
#      |      /      \     |    | /   |
#  ========= /        \  =====  |/====|  
#  code

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

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math

n = int(input())
values = list(map(int, input().split(' ')))

values.sort(reverse=True)
sum = 0

for i in range(1, n):
    sum += values[math.floor(i/2)]

print(sum)