SelectFromArrays | Topcoder Archive

Problem Statement

We have three equally long arrays A, B, C.

In each array we want to paint a few of its elements green: exactly NA elements of A, exactly NB elements of B, and exactly NC elements of C.

No two green elements may share the same index. For example, A[7] and C[7] cannot both be green.

Calculate and return the largest possible sum of green elements.

Definition

Class:: SelectFromArrays
Method:: maxSum
Parameters:: int[], int[], int[], int, int, int
Returns:: int
Method signature:: int maxSum(int[] A, int[] B, int[] C, int NA, int NB, int NC)
(be sure your method is public)

Constraints

A will have between 1 and 200 elements, inclusive.
B will have the same number of elements as A.
C will have the same number of elements as A.
Each element of A, B and C will be between 0 and 10^6, inclusive.
NA will be between 0 and 5, inclusive.
NB will be between 0 and 5, inclusive.
NC will be between 0 and 5, inclusive.
NA + NB + NC will not exceed the length of A.

Examples

```
{1, 1, 1, 1, 1, 1, 1, 1}
```
```
{1, 1, 1, 1, 1, 1, 1, 1}
```
```
{1, 1, 1, 1, 1, 1, 1, 1}
```
```
2
```
```
1
```
```
2
```
```
Returns: 5
```
With all elements of the arrays being equal, all choices are equally good. One valid solution is to paint A[0], A[4], B[3], C[1], and C[6] green.
```
{10, 20, 30, 40, 50}
```
```
{10, 20, 50, 40, 30}
```
```
{20, 50, 10, 40, 30}
```
```
1
```
```
1
```
```
1
```
```
Returns: 150
```
Here we can paint the maximum of each array green, and that is clearly optimal.
```
{0, 0, 0, 0, 0, 0, 47, 53}
```
```
{0, 0, 0, 0, 0, 0, 47, 53}
```
```
{0, 0, 0, 0, 0, 0, 47, 53}
```
```
2
```
```
3
```
```
2
```
```
Returns: 100
```
We can only paint one of the 47s and one of the 53s green. Regardless of what we do, the green elements can never have a sum greater than 100.
```
{10, 11, 12, 13, 15, 15, 16, 17, 18, 19}
```
```
{20, 21, 22, 23, 24, 25, 26, 27, 28, 29}
```
```
{30, 31, 32, 33, 34, 35, 36, 37, 38, 39}
```
```
2
```
```
2
```
```
2
```
```
Returns: 160
```
The optimal solution here is to select A[4] and then one element at each of the indices 5 to 9, with one of those elements being selected in A, two in B and two in C.

{10, 20, 30}

{60, 50, 40}

{70, 90, 80}

Returns: 60

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.