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: Wrong Answer

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

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


print(ans)

Submission status: Wrong Answer

Solution code:
i = int(input())
j = list(map(int, input().split()))
j.sort()
j = j[1:]
print(sum(j))

Submission status: Wrong Answer

Solution code:
from collections import deque

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

a.sort(reverse=True)
d = deque()

d.append(a[0])
s = 0

for i in range(1, n):
  s += min(d[0], d[-1])
  if d[0] >= d[-1]:
    d.appendleft(a[i])
  else:
    d.append(a[i])

print(s)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = sorted(list(map(int,input().split())), reverse=True)
ans = -a[0]
print(ans)
cnt = 0
if n%2==0:
    while True:
        if cnt==n:
            break
        ans += a[0]*2
        cnt += 2
        del a[0]
    print(ans)
if n%2==1:
    n = n+1
    while True:
        if cnt==n:
            break
        ans += a[0]*2
        cnt += 2
        del a[0]
    print(ans-a[0])

Submission status: Wrong Answer

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 = []
	for i,val in enumerate(A):
		if i == 0:
			ansans.append(val)
		else:
			if ansans[-1] == val:
				ansans.append(val)
			ansans.append(val)

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

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: Wrong Answer

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
from collections import deque
A = sorted(A,reverse=True)
Q = deque(A[0:2])
ans = 0
ans += A[0]
for a in A[2:]:
    if Q[0] > Q[-1]:
        Q.appendleft(a)
        ans += Q[-1]
    else:
        Q.append(a)
        ans += Q[0]
print(ans)

Submission status: Wrong Answer

Solution code:

N=input()
N=int(N)

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

Submission status: Wrong Answer

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

A.sort(reverse=True)
#print(A)
s = [A[0]]
s.append(A[1])

ans = A[0]
for i in range(2,len(A)):
    s.append(A[i])
    #print(min(s[0],s[i-1]))
    ans += min(s[0],s[i-1])
print(ans)

Submission status: Wrong Answer

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

li.sort(reverse=True)
ans=sum(li)-li[-1]
print(ans)

Submission status: Wrong Answer

Solution code:
import os
import sys
from io import BytesIO, IOBase
# from collections import defaultdict as dd
# from collections import deque as dq
# import itertools as it
# from math import sqrt, log, log2
# from fractions import Fraction
import heapq
def main():
    n = int(input())
    nums = list(map(int, input().split()))
    nums.sort(reverse=True)
    if n<=3:
        print(sum(nums[:2]))
        exit()
    

    hp = list()
    ans = 0
    # Push the first three intervals
    heapq.heappush(hp, (-nums[1], nums[0]))
    heapq.heappush(hp, (-nums[2], nums[0]))
    heapq.heappush(hp, (-nums[2], nums[1]))
    ans = sum(nums[:2])

    i = 3
    while i < n:
        comfort, big = heapq.heappop(hp)
        ans += -comfort

        small = -comfort

        curr = nums[i] # what enters the circle

        #push the smaller interval
        heapq.heappush(hp, (-curr, small))
        heapq.heappush(hp, (-curr, big))
        i += 1
    print(ans)






































# region fastio
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")
# endregion
 
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#D
N = int(input())
an = list(map(int,input().split()))

an.sort()
bn = sorted(an,reverse = True)

Sum1 = 0
Sum2 = 0

Sum1 = sum(an) - an[0]
Sum2 = sum(bn) - bn[0]

if Sum1 >= Sum2:
    print(Sum1)
else:
    print(Sum2)

Submission status: Wrong Answer

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

ret = 0
array = []
array.append(A.pop())
while len(A) > 0:
    #print('array', array)
    comfort = [0 for i in range(len(array))]
    for i in range(len(comfort)):
        comfort[i] = min(array[i-1], array[i])
    #print('comfort', comfort)
    val = max(comfort)
    ret += val
    print('ret', ret)
    array.insert(comfort.index(val), A.pop())

print(ret)

Submission status: Wrong Answer

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

print(sum(li) -1)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort(reverse=True)
l = [max(A)]
ret = 0
A.remove(max(A))
while True:
    if len(A) == 0:
        break
    n = max(A)
    ret += l[-1]
    l.append(max(A))
    A.remove(max(A))
print(ret)

Submission status: Wrong Answer

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

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

    print(a)
    a.sort(reverse=True)
    ans = 0

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

    print(ans)
    return


if __name__ == "__main__":
    main()
    sys.exit(0)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from collections import Counter

def m():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort(reverse=True)
    ans = A[0]
    c = Counter(A[1:])
    d = list(c.items())
    d.sort(reverse=True, key=lambda x:x[0])
    tmp = []
    for k,v in d:
        for i in range(2+(v-1)):
            tmp.append(k)
    ans += sum(tmp[:N-2])
    return ans
print(m())

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort(reverse=True)
del a[-1]
print(sum(a))

Submission status: Wrong Answer

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

cnt = N
if N == 2:
    ans = max(A)
else:
    ans = sum(A[:2])
    cnt = N - 3
    A = A[2:]
    chk = 0
    for a in A:
        if cnt == 0:
            break
        elif cnt == 1:
            ans += a
            break
        ans += 2*a
        cnt -= 2
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
ans = 0
for i in A:
  ans += i
print(ans-1)

Submission status: Wrong Answer

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

    ans = sum(A) - min(A)

    print(ans)


resolve()

Submission status: Wrong Answer

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


a.sort(reverse = True)

ans = 0
c = 0
s = a[0]
while len(a)>=2 and s == a[0]:
	s = a.pop(0)
	ans += s

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

print(ans)

Submission status: Wrong Answer

Solution code:
def main(N, A):
    # 席順
    l = A[:2]
    # 心地よさ合計
    ans = A[0]
    # 最小値の初期値
    minimum = A[0]
    memo_a = A[1]

    for a in A[2:]:
        minimum = min(minimum, memo_a)
        ans += minimum
        # l.insert(l.index(minimum), a)
        memo_a = a
    print(ans)

if __name__ == '__main__':
    N = int(input())
    A = list(map(int, input().split()))
    A.sort(reverse = True)
    main(N, A)

Submission status: Wrong Answer

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()
    com = sum(a)
    com -= a[0]
    print(com)

Submission status: Wrong Answer

Solution code:
# D

n = int(input())
a_l = [int(x) for x in input().split()]

a_l.sort(reverse = True)
ans = -a_l[0]
now = a_l[0]
for i in range(n):
    if i%2 == 0:
        ans += now
    else:
        ans += now
        now = a_l[i]
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
print(int(sum(A)-min(A)))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = max(a)
a.pop()
for i in range(n-2):
    ans += max(a)
    a.pop()
print(ans)

Submission status: Wrong Answer

Solution code:

n=int(input())
x=[int(x) for x in input().split()]
x.sort(reverse=True)
f=1
ans=x[0]
c=1
for i in range(1,n):
    if c+(n-i-1)<=n:
        c+=(n-i-1)
        ans+=(n-i-1)*x[i]
    break
print(ans)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

print (sum(a)-min(a))

Submission status: Wrong Answer

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

from pprint import pprint
import sys

sys.setrecursionlimit(10 ** 6)
INF = float('inf')


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

res = 0
for i in range(N):
    if i == 0:
        continue
    res += A[i-1]

print(res)

Submission status: Wrong Answer

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

print(sum(friendly) - min(friendly))

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
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)
A.pop()
print(sum(A))

Submission status: Wrong Answer

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

max1 = None
max2 = None
count = 0
for k in K:
    if max1 is None and max2 is None:
        max1 = k
    elif max2 is None:
        max2 = k
        count += max1
    else:
        count += max2
print(count)

Submission status: Wrong Answer

Solution code:
import sys
import os
import itertools
import numpy as np
from collections import deque

def main():
    if os.getenv("ENV")=='LOCAL':
        sys.stdin = open(os.path.dirname(__file__)+'/input.txt', 'r')

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

    # A.sort(reverse=True)
    # print(A)
    s=sum(A)-min(A)
    print(s)
    # comfort

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

b=[a[0],a[1]]
ans=a[0]
for i in range(n-2):
    if b[0]<b[1]:
        ans+=b[0]
        b=b[1:]
        b+=[a[i+2]]
    else:
        ans+=b[1]
        b=b[:1]
        b+=[a[i+2]]
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
m=list(map(int, input().split()))
ans=0

m.sort(reverse=True)

for _ in range(1,n):
  ans=ans+m[_-1]
  
print(ans)

Submission status: Wrong Answer

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


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


if __name__ == '__main__':
    main(sys.stdin.readline, print)

Submission status: Wrong Answer

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

print(sum(list(reversed(sorted(A)))[:-1]))

Submission status: Wrong Answer

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

A.sort(reverse=True)
comfort = A[0]
for i in range(2, len(A)):
    comfort += min(A[i - 1], A[i - 2])
print(comfort)

Submission status: Wrong Answer

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

a.sort(reverse=True)

score = a[0]

for i in range(2,n):
    score += min(a[i-1],a[i-2])

print(score)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(x) for x in input().split()]
al = sum(A)
B = min(A)
print(al-B)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = sorted(map(int, input().split()), reverse=True)
res = 0
min_f = A[0]
for a in A[1:]:
    res += min_f
    min_f = a
print(res)

Submission status: Wrong Answer

Solution code:
N = int(input())

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

A.sort(reverse = True)

# print(A)
score = 0

i = 1

while i < N:
    val = A[i-1]

    if i == 1:
        score += val
    else:
        score += min(A[i-1],A[i-2])

    # print(val,score)

    i += 1

print(score)

Submission status: Wrong Answer

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

c = 0
if n%2 == 0:
  t = (n-2)//2
  print(x[n//2] + sum(x[0:t]) + sum(x[1:t+1]))
    
if n%2 == 1:
  t = (n-1)//2
  print(sum(x[0:t]) + sum(x[1:t+1]))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, acos, asin, atan, sqrt, tan, cos, pi
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]


mod = 10 ** 9 + 7


n = I()
A = LI()
A.sort(reverse=True)
ret = 0
for i in range(n - 1):
    ret = ret + A[i]

print(ret)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
n, *a = map(int, open(0).read().split())
a.sort(reverse=1)
print(sum(a[:0--n // 2]) * 2 - max(a) - a[n // 2] * n % 2)

Submission status: Wrong Answer

Solution code:

def resolve():
    n = int(input())
    a = list(map(int, input().split()))
    a = sorted(a)[::-1]
    mina = a[0]
    maxa = a[0]
    ans = 0
    for i in range(1,n):
        ans += mina
        mina = min(a[i], mina)
        maxa = max(a[i], maxa)

    print(ans)

resolve()

Submission status: Wrong Answer

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

alist.sort()
print(sum(alist)+alist[-2]-alist[1]-alist[0])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
input = sys.stdin.readline
n = int(input())
a = [int(_) for _ in input().split()]
print(sum(a)-min(a))

Submission status: Wrong Answer

Solution code:
count = int(input())
people=input().split(" ")
people1=[]

for i in range(count):
    people1.append(int(people[i]))

people1.sort(reverse=True)
#print(people1)

ans_list=[]
ans=0
for i in range(len(people1)):
    if i ==0:
        left = people1[i]
        right = people1[i]
    elif i%2 != 0:
        ans = ans + min(left,right)
        left = people1[i]
    else:
        ans = ans + min(left,right)
        right = people1[i]

print(ans)