WOSS Dual Olympiad 2023 Team Round P1: Combining Candy Canes

View as PDF

Submit solution

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

Problem type

Yanzi has N candy canes. The ith candy cane has a length of l_i. 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 l_i and l_j is the minimum of l_i and l_j. After, she ends up with a single candy cane of length l_i + l_j. 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?


1 \leq N \leq 10^6

1 \leq l_i \leq 10^6

Input Specification

The first line contains a single integer N.

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

Output Specification

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

Sample Input

4 7 3 9 8

Sample Output



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.


There are no comments at the moment.