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())
A = sorted(list(map(int,input().split())))
s = A[N-1]
v = N - 2
for i in range(N-2,-1,-1):
    s += A[i] * min(v,2)
    v -= min(v,2)
print(s)

Submission status: Accepted

Solution code:
n,*a=map(int,open(0).read().split())
a=sorted(a)[::-1]
print(sum(a[:n//2])*2-a[0]+a[n//2]*(n%2!=0))

Submission status: Accepted

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

sorted=sorted(a,reverse=True)
#print(len(sorted[2:])//2)
ans=sorted[0]

for i in range(len(sorted[2:])//2):
  ans+=sorted[1+i]*2
  #print(ans)
  

if len(a)%2==1:
  ans+=sorted[1 + len(sorted[2:])//2]
  #print(111)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
la = list(map(int, input().split()))*2
la.sort(reverse=True)
print(sum(la[1:n]))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N=ii()
    A=list(mi())

    A.sort(reverse=True)
    B = [A[0]]
    for i in range(1,N):
        B.append(A[i])
        B.append(A[i])
    
    print(sum(B[:N-1]))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
##a = int(stdin.readline().rstrip())
##b, c = [int(x) for x in stdin.readline().rstrip().split()]
##s = stdin.readline().rstrip()
##a = list(set(b))  重複を削除
##a = list(map(int,[int(x) for x in stdin.readline().rstrip().split()])) a[0, 1, 2, ...]
##a = [[0] * 2 for _ in range(n)]  a[0,0]
##v = [s[i: i+2] for i in range(0, len(s), 2)]
##  s="12345678" を v=["12","34","56","78"] にするイメージ
##s = "".join(list)リストを文字列に変換[""]は区切り文字
##a.sort(key=itemgetter(1))リストをソートできるよ(from operator import itemgetterが必要)
##sort_p = sorted(p) 昇順ソート

# -*- coding: utf-8 -*-
from sys import stdin
from operator import itemgetter
from collections import deque, Counter
import math
import pprint
from functools import reduce
import numpy as np
import random
import bisect
import copy
# stdin = open("sample.txt")


MOD = 1000000007
INF = float('inf')
alpha = ["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]

def keta(kazu): # 入力されたintを桁ごとに分解，リストで出力
    kazu_str = str(kazu)
    kazu_list = [int(kazu_str[i]) for i in range(0, len(kazu_str))]
    return kazu_list

def gcd(*numbers): # 最小公倍数
    return reduce(math.gcd, numbers)

def combination(m,n): # mCn
    
    if n > m:
        return 'すまん'
    return math.factorial(m) // (math.factorial(m-n) * math.factorial(n))

def pow_k(x,n):  # (x**n)の計算の高速化
    if n == 0:
        return 1
    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2
    return K * x

def fact(n): # nの素因数分解の結果を辞書で出力 fuct(24) → {2: 3, 3: 1}
    arr = {}
    temp = n
    for i in range(2,int(n**0.5)+1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr[i] = cnt
    if temp != 1:
        arr[temp] = 1
    if arr == {}:
        arr[n] = 1
    return arr


    
def main():
    n = int(stdin.readline().rstrip())
    a_kari = list(map(int,[int(x) for x in stdin.readline().rstrip().split()]))
    a = sorted(a_kari,reverse=True)
    ans = 0
    
    for i in range(n-1):
        if i == 0:
            ans += a[0]
        else:
            ans += a[(i+1)//2]
    print(ans)

main()

Submission status: Accepted

Solution code:
import os
import sys
from collections import defaultdict, Counter
from itertools import product, permutations,combinations, accumulate
from operator import itemgetter
from bisect import bisect_left,bisect
from heapq import heappop,heappush,heapify
from math import ceil, floor, sqrt, gcd
from copy import deepcopy
from functools import reduce

def main():

    n = int(input())
    lists = list(map(int, input().split()))
    lists.sort(reverse=True)
    ans = 0
    count = n-1
    for i in range(n):
        if i == 0:
            ans += lists[i]
            count -= 1
        else:
            for j in range(2):
                if count > 0:
                    ans += lists[i]
                    count -= 1
        

    print(ans)

        

if __name__ == "__main__":
    main()

Submission status: Accepted

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

ans = 0

t = N - 1

for i in range(N):
    lim = 1 if i == 0 else 2
    for j in range(lim):
        if (t > 0):
            ans += A[i]
            t -= 1

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
p = 0
ans = 0
for i in range(len(A)):
    if i == 0:
        continue
    if i == 1 or i % 2 == 0:
        p = A.pop()
    ans += p
print(ans)

Submission status: Accepted

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

lsA.pop(0)
ans = sum(lsA[:N-1])
print(ans)

Submission status: Accepted

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

ans = A.pop()
n -= 2

while n > 0:
    if n >= 2:
        ans += A.pop() * 2
        n -= 2
    elif n == 1:
        ans += A.pop()
        n -= 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:
# coding: utf-8
import sys
# from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
sys.setrecursionlimit(10 ** 7)
from heapq import heappop, heappush
#from collections import OrderedDict, defaultdict
#import math
#from itertools import product, accumulate, combinations, product
#import bisect# lower_bound etc
#import numpy as np
#from copy import deepcopy
#from collections import deque
#import numba

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

    val_list = []
    heappush(val_list, (-min(A[0], A[1]), A[1], A[0], 1))
    heappush(val_list, (-min(A[0], A[1]), A[1], A[0], 1))
    ans = A[0]

    for a in A[2:]:
        val, a1, a2, edge = heappop(val_list)
        ans += -val
        if edge != 1:
            heappush(val_list, (-a, a, a1, 0))
            heappush(val_list, (-a, a, a2, 0))
        else:
            heappush(val_list, (-a, a, a1, 1))
            heappush(val_list, (-a, a, a2, 0))
    print(ans)



if __name__ == "__main__":
    run()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    n = II()
    a = LI()
    a.sort()
    ans = 0
    a = a[::-1]
    for i in range(1, n):
        ans += a[i // 2]
    print(ans)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    N = int(rl())
    A = list(map(int, rl().split()))
    
    A.sort(reverse=True)
    B = [A[0]]
    for ai in A[1:]:
        B += [ai, ai]
    ans = sum(B[:N - 1])
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
def resolve():
    import sys
    sys.setrecursionlimit(10 ** 6)  # 再帰関数の再帰の深さを設定
    to_index = lambda x: int(x) - 1  # 入力した数字に1を引いたものを返す
    print_list_in_2D = lambda x: print(*x, sep="\n")  # リストの要素を改行を挟んで表示する関数

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

    def map_int_input(): return map(int, input())

    MII = map_int_input

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

    def MII_to_index(): return map(to_index, input())

    def MII_split_to_index(): return map(to_index, input().split())

    # 入力全てを整数に変換したものの配列を受け取る
    def list_int_inputs(): return list(map(int, input()))

    LII = list_int_inputs

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

    # 2次元リスト化
    def LII_2D(rows_number): return [LII() for _ in range(rows_number)]

    def LII_split_2D(rows_number): return [LII_split() for _ in range(rows_number)]

    from collections import deque
    N = input_int()
    friendlinesses = LII_split()

    s_fris = sorted(friendlinesses, reverse=True)

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# モジュールのインポート
import math


def get_input() -> tuple:
    """
    標準入力を取得する.

    Returns:\n
        tuple: 標準入力
    """
    N = int(input())
    A = list(map(int, input().split()))

    return N, A


def main(N: int, A: list) -> None:
    """
    メイン処理.

    Args:\n
        N (int): プレイヤー数（2 <= N <= 2*10**5）
        A (list): フレンドリーさ
    """
    # 求解処理
    A = sorted(A, reverse=True)
    ans = 0
    for n in range(1, N + 1):
        if n == 1:
            continue
        ans += A[math.ceil(n / 2) - 1]

    # 結果出力
    print(ans)


if __name__ == "__main__":
    # 標準入力を取得
    N, A = get_input()

    # メイン処理
    main(N, A)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    ans = 0
    a.sort()
    for i in range(1, n):
        ans += a[n - i // 2 - 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)
if n % 2 == 0:
    ans = sum(a[:n // 2]) * 2 - a[0]
else:
    ans = sum(a[:(n - 1) // 2]) * 2 - a[0] + a[(n - 1) // 2]
print(ans)

Submission status: Accepted

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

a1 = sorted(a, reverse=True)
com = 0

if n == 2:
    com = a1[0]
elif n%2 ==0:
    c = int(n/2)
    com = sum(a1[0:c])
    com += sum(a1[1:c])
else:
    c = int(n//2)
    com += sum(a1[0:c+1])
    com += sum(a1[1:c])
    
print(com)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# モジュールのインポート
import math

# 標準入力を取得
N = int(input())
A = list(map(int, input().split()))

# 求解処理
A = sorted(A, reverse=True)
ans = 0
for n in range(1, N + 1):
    if n == 1:
        continue
    ans += A[math.ceil(n / 2) - 1]

# 結果出力
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

a.sort(reverse=True)
con_sum = a[0]
j = 0

for i in range(1,n-1):
    if i % 2 == 1:
        j += 1        
        con_sum += a[j]
    else:
        con_sum += a[j]

print(con_sum)

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
dis=deque([A[0]])
num=0
for i in range(1,len(A)):
    num+=dis.popleft()
    dis.append(A[i])
    dis.append(A[i])
print(num)

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
A = list(map(int, input().split()))
#A=[1,1,1,1,1,1,1]
#N=7
A.sort(reverse=True)
dis=deque([A[0]])
num=0
for i in range(1,len(A)):
    num+=dis.popleft()
    #L.insert(ind+1,A[i])
    dis.append(A[i])
    dis.append(A[i])
print(num)
#print(L)
#print(dis)

Submission status: Accepted

Solution code:
import itertools
import functools
import math
from collections import Counter
from itertools import combinations
import re


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

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

print(ans)

Submission status: Accepted

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

c = sorted(c)
ans = 0

for i in range(1,len(c)):
  ans += c[len(c) - 1 - i//2]

print(ans)

Submission status: Accepted

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

a.sort(reverse=True)

min_comfort = max(a)
sum_comfort = max(a)
i = 0
j = 1
counter=0
while i < n - 2:
    tmp = a[j]
    sum_comfort += tmp
    counter+=1
    if counter ==2:
        counter=0
        j+=1
    i+=1
    # print(i,j)
print(sum_comfort)

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(1, n - 1):
    ans += a[-(-i//2)]

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = [int(x) for x in 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 = tuple(map(int, input().split()))
A = sorted(A, reverse=True)
from collections import deque
q = deque([])
ans = A[0]

for a in A[1:n-1]:
    q.append(a)
    q.append(a)
    ans += q.popleft()
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort(reverse = True)
# 一番でかいのは一回、それ以外は二回まで寄与できる
# 上から貪欲
left = N-1
index = 0
ans = 0
while left > 0:
    if index == 0:
        ans += A[index]
        left -= 1
        index += 1
    else:
        if left == 1:
            ans += A[index]
            left -= 1
            index += 1

        else:
            ans += A[index]*2
            left -= 2
            index += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
import copy

class PriorityQueue:

    #初期化
    def __init__(self,heap):
        self.heap = heap
        heapify(self.heap)
    
    #値の追加
    def push(self,item):
        heappush(self.heap,item)
    
    #値の取り出し
    def pop(self):
        return heappop(self.heap)
    
    #値を追加して取り出し
    def pushpop(self,item):
        return heappushpop(self.heap,item)
    
    #データ構造の中身を見る
    def __call__(self):
        return self.heap
    
    #heapの長さ
    def __len__(self):
        return len(self.heap)


if __name__ == "__main__":
    n = int(input())
    a = list(map(int,input().split()))
    a.sort(reverse=True)
    heap = []
    q = PriorityQueue(heap)
    q.push(-a[0])
    ans = 0
    for i in range(n-1):
        p = q.pop()
        ans += -p
        q.push(-a[i+1])
        q.push(-a[i+1])
    print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
def d_chat_in_a_circle():
    N = int(input())
    A = sorted([int(i) for i in input().split()])
    return sum(A[(N - 1) - (k // 2)] for k in range(1, N))

print(d_chat_in_a_circle())

Submission status: Accepted

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

Submission status: Accepted

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

maxval = a[0]
cc = {maxval: 1}

ans = 0
idx = 0

for i in range(1, n):
    if a[i] in cc:
        cc[a[i]] += 2
    else:
        cc[a[i]] = 2
    cc[maxval] -= 1
    ans += maxval
    if cc[maxval] == 0:
        while 1:
            idx += 1
            if maxval > a[idx]:
                maxval = a[idx]
                break

print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

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

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
ans = 0
for i in range(1, N):
    ans += A[N - i//2 - 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(1,n):
    ans += a[i//2]
print(ans)