Approach

A brute force approach would be to try every way of splitting the suspects, and then recursing on those splits - then taking the maximum score attained.

This would clearly be exponential with respect to ~N~, and thus too slow for the given constraints.

Observation 1

We need to find a smarter way of splitting the groups. Since our goal is to maximise the sum, we want each number to contribute as many times as possible. With a test case of ~[4,4,4,4]~:

• Splitting equally into two every time results in ~[4,4,4,4], [4,4], [4,4], [4], [4], [4], [4]~
• Splitting off one number every time results in ~[4,4,4,4], [4], [4,4,4], [4], [4,4], [4], [4]~

Only removing 1 suspect each time results in other suspects contributing more times than otherwise.

Observation 2

We also need to decide which suspect we are going to split off at each turn. Taking the sample test case ~[6,7,8]~:

• You have to create a 1-2 split no matter what, and the 1 will not contribute after this turn
• You will have a group of 2, which you split into 1-1 and those groups will not contribute after that turn

So, it is reasonable to pick the smallest possible number every time you split off a single number.

Observation 3

Now that we have decided the splitting method, we need to compute the actual result. Taking the sum of X numbers is ~O(X)~ - and since our group sizes are ~N, N-1, \ldots, 2, 1, 1~ this will result in ~O(N^2)~ work, which will not pass constraints.

What we can notice is that with our chosen way of splitting it, the amount we add to our score decreases by the single suspect we excluded the previous day (except the very last day, when we exclude two suspects): With the test case ~[4,4,1,9,2]~:

• First day: split into ~[1], [4,4,9,2]~ and our score increases by ~(1+2+4+4+9)~
• Second day: split into ~[2], [4,4,9]~ and our score increases by ~(2+4+4+9)~
• Third day: split into ~[4], [4,9]~ and our score increases by ~(4+4+9)~
• Fourth day: split into ~[4], [9]~ and our score increases by ~(4+9)~
• Last day: no groups left, our score increases by ~0~

Since we are looking to remove the smallest number each time, we need to sort our array.

So we start off by adding our initial total to the score. Then, we can iterate over our sorted array and reduce the total we will add the next day as we iterate.

Combining these observations, we end up at an ~O(N \log N)~ time and ~O(N)~ space solution.

Solution (Python)

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

if N == 1:
    print(suspects[0])

else:
    suspects.sort()

    current_total = sum(suspects)
    ans = 0

    for index in range(N-1):
        ans += current_total
        current_total -= suspects[index]

    print(ans)

Extra

This is not something that affects the asymptotic time complexity, but a neat trick to do it in one pass after sorting :)

A simple observation that can be made is that with our chosen way of splitting it, you will always have:

• 1 number that contributes once to the final sum
• 1 number that contributes twice to the final sum
• ...
• 1 number that contributes ~(N-2)~ times to the final sum
• 2 numbers that contribute ~(N-1)~ times to the final sum (because the final partition will always be two numbers)

From this, we can form the following expression:

~a_0 + 2a_1 + \ldots + (N-2)a_{N-3} + (N-1)(a_{N-2} + a_{N-1})~

This problem can also be solved via Huffman Coding in a similar way, which is left as an exercise for the reader.

Bonus Solution (Python)

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

if N == 1:
    print(suspects[0])

else:
    suspects.sort()

    ans = 0
    for idx in range(len(suspects)-2):
        ans += suspects[idx] * (idx + 1)

    ans += (N-1) * (suspects[N - 2] + suspects[N - 1])

    print(ans)