codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1373D.md (1669B)


      1 Source: https://codeforces.com/problemset/problem/1373/D
      2 
      3 D. Maximum Sum on Even Positions
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 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).
     22 
     23 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}$.
     24 
     25 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).
     26 
     27 You have to answer $t$ independent test cases.
     28 
     29 Input
     30 
     31 The first line of the input contains one integer $t$ ($1 \le t \le 2 \cdot 10^4$) — the number of test cases. Then $t$ test cases follow.
     32 
     33 The first line of the test case contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the length of $a$. The second line of the test case contains $n$ integers $a_0, a_1, \dots, a_{n-1}$ ($1 \le a_i \le 10^9$), where $a_i$ is the $i$-th element of $a$.
     34 
     35 It is guaranteed that the sum of $n$ does not exceed $2 \cdot 10^5$ ($\sum n \le 2 \cdot 10^5$).
     36 
     37 Output
     38 
     39 For each test case, print the answer on the separate line — the maximum possible sum of elements on even positions after reversing at most one subarray (continuous subsegment) of $a$.
     40 
     41 Example
     42 
     43 Input
     44 
     45 ```
     46 4
     47 8
     48 1 7 3 4 7 6 2 9
     49 5
     50 1 2 1 2 1
     51 10
     52 7 8 4 5 7 6 8 9 7 3
     53 4
     54 3 1 2 1
     55 ```
     56 
     57 Output
     58 
     59 ```
     60 26
     61 5
     62 37
     63 5
     64 ```