SelectFromArrays
SRM 820 · 2021-12-27 · by misof
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.
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.
{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}
0
1
0
Returns: 60
Submissions are judged against all 172 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class SelectFromArrays with a public method int maxSum(vector<int> A, vector<int> B, vector<int> C, int NA, int NB, int NC) · 172 test cases · 2 s / 256 MB per case