Moneymanager | Topcoder Archive

Problem Statement

One day Hero realized that he has zero experience with practical projects. Thus, he decided to spend one whole year on projects, gaining some experience and making some money along the way. Hero already chose which projects he is going to do. All that remains is to choose the order in which he'll do them. Each project can be described by two positive integers a[i] and b[i]. More precisely, when Hero works on project i, the following two things happen, in order:

First, his work on the project increases his experience by a[i].
Then, when the project is done, he earns money for the project. The amount earned is (b[i] * E), where E is his total amount of experience at the moment of finishing the project.

The number of projects Hero has planned is even. In addition to the projects, Hero has one extra plan: after finishing exactly one half of the projects, he wants to attend a training camp. The training camp will increase his experience by X. He will not earn any money at the training camp. At the beginning, Hero has no experience and no money. You are given the int[]s a and b (both with the same number of elements; that number is even) and the int X. Find and return the maximum total amount of money Hero can earn during the year.

Definition

Class:: Moneymanager
Method:: getbest
Parameters:: int[], int[], int
Returns:: int
Method signature:: int getbest(int[] a, int[] b, int X)
(be sure your method is public)

Constraints

Number of elements in a will be between 2 and 50, inclusive.
Number of elements in a will be even.
a and b will contain the same number of elements.
Each element in a will be between 1 and 100,000, inclusive.
Each element in b will be between 1 and 10, inclusive.
X will be between 0 and 100,000, inclusive.

Examples

```
{1,1}
```
```
{2,1}
```
```
0
```
```
Returns: 5
```
An optimal solution: Hero works on project #1 (zero-based index). He first gains 1 experience and then he makes 1*1 = 1 money. Hero goes to the training camp and gains X=0 experience. Hero works on project #0. He first gains 1 experience and then he makes 2*2 = 4 money. The total amount of money earned during this solution is 1 + 4 = 5.
```
{1,1}
```
```
{1,5}
```
```
10
```
```
Returns: 61
```
An optimal solution: Hero works on project #0. He first gains 1 experience and then he makes 1*1 = 1 money. Hero goes to the training camp and gains 10 experience. Hero works on project #1. He first gains 1 experience and then he makes 5*12 = 60 money. The total amount of money earned during this solution is 1 + 60 = 61.
```
{4,4,6,6}
```
```
{2,2,3,3}
```
```
100
```
```
Returns: 726
```
One optimal solution: project #0, project #1, training camp, project #3, project #2.

{30,13,28,59,26,62,48,75,6,69,94,51}

{4,6,4,5,4,3,1,5,6,5,2,2}

Returns: 22096

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.