[Solution] Three Arrays solution codechef

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

[Solution] Three Arrays solution codechef

For every index 1iN1≤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

  • 1T1051≤T≤105
  • 1N51051≤N≤5⋅105
  • 1Ai,Bi,Ci1091≤Ai,Bi,Ci≤109
  • 0k1,k2N0≤k1,k2≤N
  • It is guaranteed that the sum of NN across all test cases doesn’t exceed 51055⋅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

Leave a Comment