[Solution] Three Arrays solution codechef

Three Arrays solution codechef – You are given three arrays AA, BB, and CC, all of length NN. You also have two integers k1k1 and k2k2.

[Solution] Three Arrays solution codechef

For every index 1≤i≤N1≤i≤N, you must choose exactly one of Ai,BiAi,Bi, or CiCi. Find the maximum possible sum of chosen elements, such that:

• At most k1k1 elements are picked from AA, and
• At most k2k2 elements are picked from BB

Input Format

• The first line of input contains an integer TT, denoting the number of test cases. TT test cases follow.
• Each test case consists of five lines of input.
• The first line of each test case contains the integer NN — the length of the arrays.
• The second line contains NN space-separated integers A1,A2,…,ANA1,A2,…,AN.
• The third line contains NN space-separated integers B1,B2,…,BNB1,B2,…,BN.
• The fourth line contains NN space-separated integers C1,C2,…,CNC1,C2,…,CN.
• The fifth line contains two space-separated integers k1k1 and k2k2.

Output Format

For each test case, output on a new line the maximum sum possible by selecting the elements under the specified constraints.

[Solution] Three Arrays solution codechef

• 1≤T≤1051≤T≤105
• 1≤N≤5⋅1051≤N≤5⋅105
• 1≤Ai,Bi,Ci≤1091≤Ai,Bi,Ci≤109
• 0≤k1,k2≤N0≤k1,k2≤N
• It is guaranteed that the sum of NN across all test cases doesn’t exceed 5⋅1055⋅105.

Sample Input 1 

2
4
10 4 8 5
9 7 6 6
5 5 7 11
2 1
5
12 44 32 12 32
43 32 12 32 31
34 12 43 23 41
3 4

Sample Output 1 

36
203

Three Arrays solution codechef Explanation

Test case 11: Choose A1=10,B2=7,A3=8A1=10,B2=7,A3=8 and C4=11C4=11, for a sum of 3636.

Test case 22: Choose B1=43,A2=44,C3=43,B4=32,C5=41B1=43,A2=44,C3=43,B4=32,C5=41, for a sum of 203203.

For Solution

“Click here“