Leadership | Topcoder Archive

Problem Statement

You are playing a strategic game. In the game you control some units. Each unit has a power, and all powers are nonnegative integers. For each valid i, you currently have units[i] units that each have power i.

You have just cast a spell that gives all your units the leadership ability. A unit with this ability can be activated exactly once. When a unit with leadership is activated, the power of each other unit is increased by the power of the activated unit. Units have to be activated one at a time.

Maximize the total power of your units, and return that total modulo 10^9 + 7.

Definition

Class:: Leadership
Method:: maximizePower
Parameters:: int[]
Returns:: int
Method signature:: int maximizePower(int[] units)
(be sure your method is public)

Notes

Units that were already activated still receive bonuses to their power when other units get activated later.

Constraints

units will contain between 0 and 50 elements, inclusive.
Each element of units will be between 0 and 10^9, inclusive.

Examples

```
{47}
```
```
Returns: 0
```
All these units have power 0. We may activate them all we want, the total power will remain zero.
```
{1, 1}
```
```
Returns: 3
```
If we first activate the unit with power 0 and then the one with power 1, we will get units with power 1 and 1. If we do it in the other direction, we will get units with power 1 and 2, which gives us a better total.
```
{1, 2}
```
```
Returns: 14
```
We have three units: A with power 0, B with power 1, and C with power 1. One optimal solution is to activate B (powers become 1, 1, 2), then activate C (powers become 3, 3, 2) and then activate A (powers become 3, 6, 5). The total power at the end is 14.
```
{0, 0, 4}
```
```
Returns: 98
```
In the end, these four units will have powers 16, 24, 28 and 30, in some order. (That order depends on the order in which we activate them.)
```
{4, 3, 2, 1}
```
```
Returns: 21754
```
```
{0, 1000}
```
```
Returns: 734781982
```
Remember to do calculations using modular arithmetics and watch out for integer overflows.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.