Output: Standard Output (stdout)
Memory limit: 128 megabytes
Time limit: 1.0 seconds
You have N skill points. The i-th skill point has a value of v_i, and can be used to either increase your attack by v_i points, or increase your accuracy by v_i percentage points.
Your average attack damage can be calculated by multiplying your attack by your accuracy – for example, with 40 attack and 50% accuracy, you would deal an average of 40 \times 0.5 = 20 damage per attack.
Initially, you have 0 attack and 0% accuracy. Note that your accuracy is capped at 100%, but you are allowed to assign a skill point that would otherwise take you above 100% accuracy.
Please find the maximum average attack damage possible by assigning the skill points optimally.
The first line contains a single integer, N, the number of skill points.
The second line contains N space-separated integers, v_1, v_2, \dots, v_N, the values of each skill point.
You should output a single integer – the maximum average attack damage multiplied by 100.
- 1 \le N \le 1000
- 1 \le v_i \le 100
- Subtask 1 (20%): All skill points have the same value.
- Subtask 2 (30%): v_i = i for all i (1 \le i \le N)
- Subtask 3 (20%): N \le 16
- Subtask 4 (30%): No further constraints apply.
In the first sample case, you should assign two skill points to attack, and two skill points to accuracy. This results in 120 attack and 120% accuracy (which gets capped to 100%), so the average attack damage multiplied by 100 is 120 \times 100 = 12000.
In the second sample case, one optimal solution is to assign skill points 1, 2, and 5 to attack, and skill points 3 and 4 to accuracy. This results in 8 attack and 7% accuracy, which gives 8 \times 7 = 56.
Sample Input 1
4 60 60 60 60
Sample Output 1
Sample Input 2
5 1 2 3 4 5
Sample Output 2
Sample Input 3
3 20 30 40
Sample Output 3