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: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import itertools
import random
from collections import deque
from decimal import *

input = sys.stdin.readline

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N = inputInt()
	A = inputList()

	A.sort()
	A = A[::-1]
	ans = 0
	maxs = 0
	cnt = 0

	ansans = []
	pgt = Queue()
	for i,val in enumerate(A):
		if i == 0:
			pgt.enqueue(val)
		else:
			tmp = pgt.dequeue()
			ansans.append(tmp)

			pgt.enqueue(val)

			if tmp == val:
				pass
			else:
				pgt.enqueue(val)

	print(sum(ansans))


class Queue:
    def __init__(self, queue = None):
        if type(queue) is type([]):
            self.queue = queue
        else:
            self.queue = []

    def enqueue(self, e):
        self.queue.append(e)
        return self.queue

    def dequeue(self):
        try:
            qEl = self.queue[0]
            del self.queue[0]
            return qEl
        except IndexError:
            return None

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A_list = list(map(int,input().split()))
A_list.sort(reverse = True)
cmfrt = 0
mx_cmfrt = 0
counter = 0
reached_list = [A_list[0],A_list[0]]
for j in range(1, len(A_list)):
    for i in range(1, len(reached_list)):
        cmfrt = min(reached_list[i-1], reached_list[i])
        if cmfrt > mx_cmfrt:
            mx_cmfrt = cmfrt
            insrt_pst = i
    reached_list.insert(insrt_pst,A_list[j])
    counter += mx_cmfrt
    mx_cmfrt = 0
print(counter)

Submission status: Time Limit Exceeded

Solution code:
# /usr/bin/python3
# -*- coding: utf-8 -*-
from queue import Queue
from queue import LifoQueue as Stack
from math import sqrt, floor, ceil, log2, log10, pi
from fractions import gcd
from itertools import permutations, combinations
from operator import itemgetter
from functools import cmp_to_key


INF=1001001001
__MOD__=(10**9)+7
yn = 'YNeos'
judge = False
cnt = 0
ans = None


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

def intinput():
    return int(input())

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

def lineinputs(func=intinput):
    datas = []
    while True:
        try:
            datas.append(func())
        except EOFError:
            break
    return datas

class ModInt():
    def __init__(self, x):
        self.__x = (x % __MOD__)
    def __add__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x + other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x + other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __radd__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x + self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x + self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __sub__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x - other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x - other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rsub__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x - self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x - self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __mul__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x * other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x * other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rmul__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x * self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x * self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __truediv__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x * other.__modinv())%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x * other.__modinv())%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rtruediv__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x * self.__modinv())%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x * self.__modinv())%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __pow__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__(pow(self.__x, other.__x, __MOD__)))
        elif type(other) == ModInt:
            return self.__class__(pow(self.__x, other.__x, __MOD__))
        else:
            raise Exception("Not Int or Not ModInt")
    def __rpow__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__(pow(other.__x, self.__x, __MOD__)))
        elif type(other) == ModInt:
            return self.__class__(pow(other.__x, self.__x, __MOD__))
        else:
            raise Exception("Not Int or Not ModInt")

    def __modinv(self, m=__MOD__):
        a = self.__x
        if a == 0:
            raise ZeroDivisionError()
        if gcd(a, m) != 1:
            raise Exception("%sの逆数は求まりません。" % a)
        b, u, v = m, 1, 0
        while b != 0:
            t = a//b;
            a -= t*b
            a, b = b, a
            u -= t * v
            u, v = v, u
        u %= m
        if u < 0:
            u += m
        return u
    def __int__(self):
        return self.__x
    def __str__(self):
        return str(self.__x)



if __name__ == '__main__':
    N = intinput()
    a_arr = list(mulinputs())
    l = len(a_arr)
    is_odd = l % 2
    a_arr.sort(reverse=True)

    # 出力
    ans = a_arr.pop(0)
    for _ in range(int(l//2)-1):
        ans += (a_arr.pop(0) * 2)
    if is_odd:
        ans += a_arr.pop(0)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:

def resolver(N, A):
    A.sort(reverse=True)
    circle = []
    ans = 0

    for a in A:
        if len(circle) == 0:
            circle.append(a)
        elif len(circle) == 1:
            ans += circle[0]
            circle.append(a)
        else:
            idx = max(range(len(circle)), key=lambda i: min(circle[i-1], circle[i]))
            ans += min(circle[idx-1], circle[idx])
            circle.insert(idx, a)

    return ans

def main():

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort(reverse=True)
d=[a[0]]
ans=0
for i in range(1,n):
  tmp=max(d)
  ans=ans+tmp
  d.remove(tmp)
  d.append(a[i])
  d.append(a[i])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import itertools
import random
from decimal import *

input = sys.stdin.readline

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N = inputInt()
	A = inputList()

	A.sort()
	A = A[::-1]
	ans = 0
	maxs = 0
	cnt = 0

	ansans = []
	pgt = Queue()
	for i,val in enumerate(A):
		if i == 0:
			pgt.enqueue(val)
		else:
			tmp = pgt.dequeue()
			ansans.append(tmp)

			pgt.enqueue(val)

			if tmp == val:
				pass
			else:
				pgt.enqueue(val)

	print(sum(ansans))


class Queue:
    def __init__(self, queue = None):
        if type(queue) is type([]):
            self.queue = queue
        else:
            self.queue = []

    def enqueue(self, e):
        self.queue.append(e)
        return self.queue

    def dequeue(self):
        try:
            qEl = self.queue[0]
            del self.queue[0]
            return qEl
        except IndexError:
            return None

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
if __name__ == '__main__':
    n = int(input())
    a = [int(i) for i in input().split()]
    a.sort(reverse=True)
    ans = 0
    list = []
    for i in a:
        if len(list) > 0:
            ans+=max(list)
            list.remove(max(list))
            list.append(i)
            list.append(i)
        else:
            list.append(i)


    print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
#
# Author: Tetsuya Ishikawa <tiskw111@gmail.com>
# Date  : July 05, 2020
##################################################### SOURCE START #####################################################

import heapq

N = int(input().strip())
As = list(map(lambda s: -int(s), input().strip().split()))

heapq.heapify(As)

for n in range(N):
    a = - heapq.heappop(As)
    if   n == 0:
        g, gs = 0, [a]
    elif n == 1:
        g, gs = gs[0], [a, a]
    else:
        max_g = max(gs)
        idx_g = gs.index(max_g)
        g += gs[idx_g]
        gs[idx_g] = a
        gs.insert(idx_g, a)

print(g)

##################################################### SOURCE FINISH ####################################################
# vim: expandtab tabstop=4 shiftwidth=4 fdm=marker

Submission status: Time Limit Exceeded

Solution code:

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

h.sort()
h.reverse()

en = []
ans = 0

for i, j in enumerate(h):
    # en.append(j)
    # print([h[0],h[0]])
    if i == 0:
        en.append((h[0],h[0]))
    else:
        mintmp = min(en[0])
        maxtmp = max(en[0])
        ans += mintmp
        en.append((maxtmp, h[i]))
        en.append((mintmp, h[i]))
        en.pop(0)

    # print(en)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def sellect_sort(arr):
    for ind, ele in enumerate(arr):
        min_ind = min(range(ind, len(arr)), key=arr.__getitem__)
        arr[ind], arr[min_ind] = arr[min_ind], ele
    return arr
  
N=input()
N=int(N)

A=input().strip().split()
A=[int(s) for s in A]
A_arr=sellect_sort(A)
print(sum(A_arr[1:]))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
a = sorted(a, reverse=True)
l = []
res = 0
for i in range(n):
  if not l:
    l.append(a[i])
  else:
    max_idx = 0
    max_f = 0
    for j in range(len(l)):
      if max_f < min(l[j], l[j-1]):
        max_idx = j
        max_f = min(l[j], l[j-1])
    l.insert(max_idx, a[i])
    res += max_f

print(res)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
lol=[int(n) for n in input().split()]
ans = 0
x=max(lol)
ans += x
lol.remove(x)
n = n-2
if(n%2==0):
    for i in range(int(n/2)):
        ans+=(max(lol)*2)
        lol.remove(max(lol))
    print(ans)
else:
    for i in range(int((n-1)/2)):
        ans+=(max(lol)*2)
        lol.remove(max(lol))
    ans +=max(lol)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
l = [int(x) for x in input().split()]
l.sort(reverse=True)
ans = 0
room = [l[0]]
for i in range(1, N):
    ans += room.pop(0)
    room.append(l[i])
    room.append(l[i])
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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[0]
  if i % 2 == 0:
    del A[0]
    
print(ans)

Submission status: Time Limit Exceeded

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

points = []
for i in range(N):
  points = points + [As[i]] * (i+1)
print(sum(points[:N-1]))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
LOCAL = len(sys.argv) > 1 and sys.argv[1] == 'LOCAL'


def dprint(*args):
  if LOCAL:
    print(*args)


# import bisect

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

a.sort(reverse=True)

ans = 0
que = []
diff = set()
for i, e in enumerate(a):
  if len(que) == 0:
    que.append(e)
    diff.add((e, 0))
  else:
    ii = max(diff)[1]
    que.insert(ii, e)
    # bisect.bisect(diff, (e, i))
    diff.add((e, i))
    ans += min(que[ii - 1], que[(ii + 1) % len(que)])
  dprint(que)
  dprint(diff)
  dprint(ans)


print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

## Library

import sys
from fractions import gcd
import math
from math import ceil,floor
import collections
from collections import Counter
import itertools
import copy

## input

# N=int(input())
# A,B,C,D=map(int, input().split())
# S = input()
# yoko = list(map(int, input().split()))
# tate = [int(input()) for _ in range(N)]
# N, M = map(int,input().split()) 
#    P = [list(map(int,input().split())) for i in range(M)]
#    S = []
#    for _ in range(N):
#        S.append(list(input()))

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

A.sort(reverse=True)

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

if N == 3:
    print(A[0]+A[1])
    sys.exit()

B = []
B.append(A[1])
B.append(A[2])
B.append(A[2])
ans = A[0]+A[1]

for i in range(3,N):
    ans += max(B)
    B.pop(0)
    B.append(A[i])
    B.append(A[i])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

inputs = []

my_input = input().split(" ")

for i in range(len(my_input)):
	inputs.append(int(my_input[i]))

inputs.sort(reverse=True)

circle = [inputs[0], inputs[1]]
comfort = inputs[0]
inputs = inputs[2:]

for number in inputs:
	min_number = 999999999999
	best_index_pair = None
	for i in range(len(circle)):
		curr_friend = circle[i]
		if i == len(circle) - 1:
			next_index = 0
			next_friend = circle[0]
		else:
			next_index = i + 1
			next_friend = circle[i + 1]

		if min(curr_friend, next_friend) < min_number:
			min_number = min(curr_friend, next_friend)
			best_index_pair = (i, next_index)

	comfort += min(circle[best_index_pair[0]], circle[best_index_pair[1]])
	circle.insert(best_index_pair[1], number)

print(comfort)

Submission status: Time Limit Exceeded

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

comfort = A[0]
wa = [A[0], A[1]]

for ni in A[2:]:
    maxc = -1
    maxi = -1
    for wi in range(len(wa)):
        c = min((wa + [wa[0]])[wi:wi+2])
        if maxc < c:
            maxc = c
            maxi = wi
    wa.insert(maxi + 1, ni)
    comfort += maxc

print(comfort)

Submission status: Time Limit Exceeded

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:
        first = a
    elif i==1:
        ans += first
        pre = [A[1], A[1]]
    else:
        ans += pre[0]
        pre = pre[1:]
        pre.append(a)
        pre.append(a)

print(ans)

Submission status: Time Limit Exceeded

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

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

a_sorted = sorted(A, key=lambda x: -x)

circle = [a_sorted[0]]
ans = 0
for a in a_sorted:
    tmp = 0
    tmp_idx = -1
    for i in range(len(circle) - 1):
        cand = min(circle[i], circle[i + 1])
        if cand > tmp:
            tmp = cand
            tmp_idx = i
    ans += tmp
    circle.insert(tmp_idx + 1, a)

print(ans)

Submission status: Time Limit Exceeded

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

ans = 0
while N > 0:
  point = between.pop()
  ans += point

  A = As.pop()
  N -= 1
  between = [A, A] + between
print(ans)

Submission status: Time Limit Exceeded

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


a.sort(reverse=True)
cnt = a.pop(0)
for i in range(n-2):
    if i % 2 == 0:
        cnt += a[0]
    else:
        cnt += a.pop(0)

print(cnt)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

for i in range(n):
	if i==0:
		conf = [A[i]]
		ans = 0
	else:
		add = max(conf)
		ans+= add
		conf.remove(add)
		conf+=[A[i], A[i]]
	#print(conf, ans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

n = int(input())
a = list(map(int,input().split()))
perm = permutations([x for x in range(n)])
lst = []
for i in perm:
    res = 0
    for x in range(1,len(i)):
        res += a[i[x]]
    lst.append(res)
print(max(lst))

Submission status: Time Limit Exceeded

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

a.sort()
a.reverse()

ans = 0
seq = [a[0]]

seq.append(a[1])
ans += a[0]

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

Submission status: Time Limit Exceeded

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

ans = 0
B = []
for a in A:
    if len(B)==0:
        ans += 0
        B.append(a)
    elif len(B)==1:
        ans += B[0]
        B.append(a)
    else:
        max_ = min(B[0],B[-1])
        idx = len(B)-1
        for i in range(len(B)-1):
            if min(B[i],B[i+1]) > max_:
                max_ = min(B[i],B[i+1])
                idx = i
        ans += max_
        B = B[:idx] + [a] + B[idx:]

print(ans)

Submission status: Time Limit Exceeded

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

A.sort(reverse=True)

happiness = A.pop(0)
tree = []
tree.append(A.pop(0))

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

print(happiness)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
a.sort()
a = a[::-1]

cur = [a[0], a[1]]
now = a[0]
for i in a[2:]:
    loc = 0
    maxer = min(cur[0], cur[-1])
    for j in range(1, len(cur)):
        temp = min(cur[j - 1], cur[j])
        if temp > maxer:
            loc = j
            maxer = temp
    now += maxer
    cur = cur[:loc] + [i] + cur[loc:]

print(now)

Submission status: Time Limit Exceeded

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

## Library

import sys
from fractions import gcd
import math
from math import ceil,floor
import collections
from collections import Counter
import itertools
import copy

## input

# N=int(input())
# A,B,C,D=map(int, input().split())
# S = input()
# yoko = list(map(int, input().split()))
# tate = [int(input()) for _ in range(N)]
# N, M = map(int,input().split()) 
#    P = [list(map(int,input().split())) for i in range(M)]
#    S = []
#    for _ in range(N):
#        S.append(list(input()))

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

A.sort(reverse=True)

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

if N == 3:
    print(A[0]+A[1])
    sys.exit()

B = []
B.append(A[0])
B.append(A[1])
B.append(A[2])
ans = A[0]+A[1]

for i in range(3,N):
    tmp = min(B[0],B[len(B)-1])
    point = len(B)
    for j in range(len(B)-1):
        if tmp < min(B[j],B[j+1]):
            tmp = min(B[j],B[j+1])
            point = j
    ans += tmp
    B.insert(point+1,A[i])

print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

n = inp()
x = ip()
if n < 3:
    print(max(x))
    exit()
x.sort(reverse=True)
k = n - 2
ans = x[0]
x.pop(0)
while k:
    t = x.pop(0)
    ans += t
    k -= 1
    if k == 0:
        break
    ans += t
    k -= 1
print(ans)

Submission status: Time Limit Exceeded

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

A.sort(reverse=True)


comfort = 0

comfort_list = []

for a in A:
    if comfort_list == []:
        comfort_list.append(a)
    else:
        max_comfort = comfort_list.pop(0)
        comfort += max_comfort
        comfort_list.append(min(a, max_comfort))
        comfort_list.append(min(a, max_comfort))

print(comfort)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort(reverse=True)
res = a[0]
a.pop(0)
cnt = n - 2
while cnt > 0:
    if cnt >= 2:
        res += a.pop(0) * 2
        cnt -= 2
    
    elif cnt == 1:
        res += a.pop(0)
        cnt -= 1
    
print(res)

Submission status: Time Limit Exceeded

Solution code:

N = int(input())

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

A.sort(reverse=True)
ans = A.pop(0)
N -= 2

while N > 0:
    if N >= 2:
        ans += A.pop(0)*2
        N -= 2
    else:
        ans += A.pop(0)
        N -= 1

print(ans)

Submission status: Time Limit Exceeded

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

A.sort(reverse=True)

line = [A[0]]
comfort = 0
for a in A[1:]:
    diff_comfort = [min(line[(i + 1) % len(line)], line[i])
                    for i in range(len(line))]
    pos = min(range(len(line)), key=lambda i: diff_comfort[i])
    comfort += diff_comfort[pos]
    line.insert(pos + 1 if pos < len(line) - 1 else 0, a)
print(comfort)

Submission status: Time Limit Exceeded

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

Submission status: Accepted

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

ans, que = 0, [a[0]]
for i, ai in enumerate(a[1:]):
    ans += que[i]
    que += [ai, ai]
print(ans)

Submission status: Accepted

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

ans, que, cnt = 0, [a[0]], 0
for i in a[1:]:
    ans += que[cnt]
    que += [i, i]
    cnt += 1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
p = list(map(int, input().split()))
p.sort(reverse=True)
#追加していく際に追加した数の両脇を固める
s = 0
for i in range(1,n):
    s += p[i//2]

print(s)

Submission status: Accepted

Solution code:
n = int(input())

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

ans = a[0]

cnt = 1
i = 1
while cnt < n-1:
    cnt += 2
    ans += a[i] * 2
    i += 1

if cnt == n:
    ans -= a[i-1]

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import heapq as hq

n = int(input())
a = [int(_) for _ in input().split()]

a.sort()
p = a.pop()
q = []
hq.heappush(q, (-p, -p))
ans = 0
for _ in range(n - 1):
    p = a.pop()
    b1, b2 = hq.heappop(q)
    ans += -b1
    hq.heappush(q, sorted((b1, -p), reverse=True))
    hq.heappush(q, sorted((b2, -p), reverse=True))
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()

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

A.sort(reverse=True)
N -= 2
ans = A[0]
A.pop(0)
if N % 2 == 0:
    for i in range(N//2):
        ans += A[i] * 2
else:
    for i in range(N//2):
        ans += A[i] * 2
    ans += A[N//2]

print(ans)

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

Solution code:
from sys import stdin

input = stdin.readline

N = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
res = a[0]
cnt = N - 2
cur = 1
while cnt:
    if cnt == 1:
        res += a[cur]
        break
    else:
        res += a[cur] * 2
        cur += 1
        cnt -= 2

print(res)

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

a.sort(reverse=True)

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

print(cnt)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
A = 2*list(map(int, input().split()))
A.sort()
print(sum(A[N:-1]))

Submission status: Accepted

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

list.sort(A, reverse=True)
ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
A.sort()
S = -A[-1]

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

Submission status: Accepted

Solution code:
# ABC 173 D

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

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = sorted(list(map(int, input().split())))[::-1]
    if N % 2 == 1:
        print(sum(A[:N//2]) + sum(A[1:N//2+1]))
    else:
        print(sum(A[:N//2-1]) + sum(A[1:N//2]) + A[N//2-1])


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

x = A[N-1]

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

print(x)

Submission status: Accepted

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

a.sort()

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

print(suma)

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-k//2-1]
print(ans)