WOSS Dual Olympiad 2023 Team Round P1: Combining Candy Canes

View as PDF

Submit solution

Points: 5
Time limit: 2.0s
Memory limit: 1G

Authors:
Problem type

Yanzi has N candy canes. The ith candy cane has a length of li. She wants to become the ultimate candy master, which means she needs to merge all her candy canes together with her magical power! The energy required to merge two candy canes of lengths li and lj is the minimum of li and lj. After, she ends up with a single candy cane of length li+lj. Yanzi is super lazy, so she wants to know the minimum amount of energy she needs to use to merge all her candy canes into one. Can you find this value for her?

Constraints

1N106

1li106

Input Specification

The first line contains a single integer N.

The second line contains N space-separated integers li, the lengths of the candy canes.

Output Specification

Output a single integer, the minimum cost to combine all the candy canes together.

Sample Input

Copy
5
4 7 3 9 8

Sample Output

Copy
22

Explanation

Combine the canes with lengths 3 and 9, costing 3.

Combine the canes with lengths 12 and 7, costing 7.

Combine the canes with lengths 19 and 8, costing 8.

Combine the canes with lengths 27 and 4, costing 4.


Comments

There are no comments at the moment.