CF1373D Maximum Sum on Even Positions

You are given an array $ a $ consisting of $ n $ integers. Indices of the array start from zero (i. e. the first element is $ a_0 $ , the second one is $ a_1 $ , and so on). You can reverse at most one subarray (continuous subsegment) of this array. Recall that the subarray of $ a $ with borders $ l $ and $ r $ is $ a[l; r] = a_l, a_{l + 1}, \dots, a_{r} $ . Your task is to reverse such a subarray that the sum of elements on even positions of the resulting array is maximized (i. e. the sum of elements $ a_0, a_2, \dots, a_{2k} $ for integer $ k = \lfloor\frac{n-1}{2}\rfloor $ should be maximum possible). You have to answer $ t $ independent test cases.

N/A

N/A