2148D.md (2217B)
1 Source: https://codeforces.com/problemset/problem/2148/D 2 3 D. Destruction of the Dandelion Fields 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 Farmer John has a lawnmower, initially turned off. He also has $n$ fields, with the $i$-th field having $a_i$ dandelions. He will visit all the fields in any order he wants, and each field exactly once. 22 23 FJ's lawnmower seems to have a mind of its own. Right before visiting a field, it checks if the field has an even or odd number of dandelions. If it has an odd number, then the lawnmower toggles its state (if it is off, it turns on; if it is on, it turns off). Then, if the lawnmower is on, it will cut all dandelions in that field. Otherwise, if the lawnmower is off, then FJ will simply visit the field and cut no dandelions. 24 25 If FJ visits the $n$ fields in optimal order, what is the maximum total number of dandelions he can cut? 26 27 Input 28 29 The first line contains an integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. 30 31 The first line contains an integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the number of fields. 32 33 The following line contains $n$ space-separated integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^9$) — the number of dandelions in each field. 34 35 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 36 37 Output 38 39 For each test case, output an integer on a new line: maximum dandelions FJ can cut if he visits all $n$ fields in optimal order. 40 41 Example 42 43 Input 44 45 ``` 46 3 47 48 3 49 50 2 4 6 51 52 4 53 54 4 2 1 6 55 56 4 57 58 1000000000 999999999 1000000000 999999999 59 ``` 60 61 Output 62 63 ``` 64 0 65 13 66 2999999999 67 ``` 68 69 Note 70 71 For the first test case, since there is no field with an odd number of dandelions, FJ can never turn his lawnmower on. Since his lawnmower is always off, he can never cut any dandelions, so the answer is $0$. 72 73 For the second test case, FJ can visit the third field first; then his lawnmower will turn on. Then he can visit the other fields in any order. Since his lawnmower is always on, dandelions in every field can be cut. 74 75 For the third test case, FJ can visit the fields in the following order: field $2$, field $1$, field $3$, then field $4$.