Clear the Array solution codechef
You are given an arrayof elements. You can do the following operations on that array:
- Remove the leftmost element of the array, with index , for the cost . This can be done any number of times if the array is non-empty (has at least element).
- Remove the rightmost element of the array, with index , for the cost . This can be done any number of times if the array is non-empty (has at least element).
- Remove both the leftmost and rightmost element, with indexes and respectively, for a fixed cost which is given. This operation can only be done times and only if the array has at least elements left. Clear the Array solution codechef
If the array has onlyelement left, then the rightmost element is the same as the leftmost element so the first and second operations will have the same cost.
You have to print the minimum cost to clear the array (remove all elements using one of the three operations above).
NOTE: The answer may not fit in 32-bit integers, so please use 64-bit data types in your programming language.
The first line of the input contains– the number of test cases. Then the test cases follow.
Each test case contains 2 lines of input.
The first line of each test case contains three integers:, , and separated by spaces.
The second line of each test case containsspace-separated positive integers, .
Output Format Clear the Array solution codechef
For each test case, output on one line the minimum cost to clear the array.
Sample Input 1
3 5 2 7 9 10 11 12 13 5 0 7 9 9 9 9 9 5 2 7 9 1 2 3 10
Sample Output 1 Clear the Array solution codechef
23 45 13
For the first test case, we can removefor cost , which makes the array . Then we can do the third operation to remove and for cost , which makes the array . We can again do the third operation to remove and for cost which clears the array.
The total cost is therefore, which is the minimum cost possible.