Maximum sum in 3-array
Time Limit: 2.0 s
Memory Limit: 512.0 MB
Description
Life is sorted when you find true happiness. True happiness exist when you find out a supportive partner. Nayem is searching for a partner, but still he can not manage single one. Roy stick up for him, told that if he solve this problem then ready for assist him a partner.
The Problem is very simple,
You are given 3 array A[], B[], C[] of equal length \(N\)
You need to construct an Array D[] in following way,
Array D[] has exaclty N elements.
All selective elements comes from A[], B[] or C[].
You can select only one of \(Ai,Bi,Ci\)-th element for all i from 1 to \(N\). in other words if you select the 2nd element from array A[] then you cannot take the 2nd elements of array B[] and C[] and vice versa.
you can not select same index twice from any array and two consecutive elements from any array.
Total sum of array D[] is as maximum as possible.
Unfortunately, Nayem is busy with his job, so he need your help to solve this problem.
Input
First line takes an integer \(T\) : number of testcases
in each of the testcase :
first line takes an integer \(N\) : size of the array D[]
second line takes \(N\) integers : elements of array A[]
third line takes \(N\) integers : elements of array B[]
fourth line takes \(N\) integers : elements of array C[]
\(1 <= T <= 100\)
\(1 <= N <= 10^5\)
\(-10^4 <= Ai,Bi,Ci <= 10^4\)
Output
Output 1 integer in each of T lines : The maximum possible sum of the array D[]
Sample
Input | Output |
---|---|
|
|
In the first test case,
we can construct D[] by the following way,
1st index from A[]. D={6}.
second index from B[]. D={6,4}. note we can not select two consecutive elements from any array.
3rd index from C [], D={6,4, 3}.
4 th index from A [], D={6,4,3,1}.
so total sum of D is 14 which is maximum.
Information
- ID
- 1046
- Difficulty
- 8
- Category
- (None)
- Tags
- (None)
- # Submissions
- 52
- Accepted
- 8
- Accepted Ratio
- 15%
- Uploaded By
Related
In following contests: