Wesley's Anger Contest 5 Problem 1 - Matryoshka Acorns

View as PDF

Submit solution


Points: 5 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem types

Besley the squirrel has a pile of N acorns, each with a size a_1, \dots, a_n. Besley is willing to sell all the acorns to Wesley at a price equal to its size, that is the i^{th} acorn costs a_i dollars.

Each acorn happens to be hollow on the inside, allowing for any acorn to be placed inside another acorn if one is strictly smaller than the other.

If Wesley places an acorn of size a_i inside another acorn of size a_j where a_i < a_j then he can buy both acorns for a cost of a_j dollars, as Wesley is convinced that Besley won't play any shenanigans.

Wesley can repeat this process as many times as he wants before he buys an acorn, or choose not to place any acorns inside another.

It must hold for all acorns that if an acorn contains other acorns, the acorns contained must all be strictly smaller in size and must all be distinct in size, that is, there cannot be two acorns nested at the same level.

Can you help Wesley determine the minimum cost required in order to purchase all the acorns?

Constraints

For this problem, you will NOT be required to pass all the samples in order to receive points. In addition, you must pass all previous subtasks to earn points for a specific subtask.

For all subtasks:

1 \le N \le 1\,000
1 \le a_i \le 1\,000\,000 for all 1 \le i \le N

Subtask 1 [50%]

1 \le a_i \le 2 for all 1 \le i \le N

Subtask 2 [50%]

No additional constraints.

Input Specification

The first line will contain N, representing the number of acorns.

The second line will contain N integers, a_1, \dots, a_n, representing the sizes of each acorn.

Output Specification

This problem is graded with an identical checker. This includes whitespace characters. Ensure that every line of output is terminated with a \n character and that there are no trailing spaces.

Output, on a single line, the minimum cost required for Wesley to buy all the acorns.

Sample Input 1

4
1 2 2 1

Sample Output 1

4

Sample Input 2

5
1 2 3 2 1

Sample Output 2

5

Sample Explanation 2

Besley can place acorn a_1 in acorn a_2 and acorn a_5 in acorn a_4. He can then place either acorn a_2 or acorn a_4 in acorn a_3, but not both.

The cost ends up being 5 dollars from 3 + 2.

Sample Input 3

6
2 4 6 1 2 3

Sample Output 3

8

Sample Explanation 3

Besley can end with two acorns of sizes 6 and 2 for a cost of 8 dollars.


Comments

There are no comments at the moment.