codeforces-scrape

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

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$.