Destruction of the Dandelion Fields

Let’s strip away the story and look at the machine.

The mower starts off. For each field:

• if $a_i$ is even, the mower state does not change;
• if $a_i$ is odd, the mower toggles;
• after that, if the mower is on, this field gets cut.

So the only fields that actually control anything are the odd ones.

Even fields

An even field never changes the mower state. That means if the mower is off, visiting an even field cuts nothing. If the mower is on, visiting an even field cuts all of it.

So if there are no odd fields at all, the mower never turns on. The answer is just $0$. Brutal, but fair.

If there is at least one odd field, we can visit an odd field first. Since the mower starts off, that first odd field toggles it on and gets cut. After that, we can immediately visit every even field, and since evens do not toggle anything, they all get cut.

Therefore:

• if there is at least one odd field, all even fields can always be cut;
• if there are no odd fields, nothing can be cut.

Odd fields

Now suppose there are $k$ odd fields.

Ignore evens for a second. Every odd field toggles the mower. Starting off:

• 1st odd field turns mower on, so it is cut;
• 2nd odd field turns mower off, so it is not cut;
• 3rd odd field turns mower on, so it is cut;
• 4th odd field turns mower off, so it is not cut;
• and so on.

So among the odd fields, exactly the fields in odd positions of the odd-field order are cut.

That count is:

$$\left\lceil \frac{k}{2} \right\rceil$$

The important greedy bit: FJ controls the order, so he controls which odd fields land in those cut positions. There is no hidden constraint here. Put the biggest odd values in the cut positions, and dump the smaller odd values into the off-toggle positions. No need to overthink it; this is a sorting problem wearing a fake mustache.

So we should cut the largest $\lceil k/2 \rceil$ odd values.

Final formula

Let:

• $E$ be the sum of all even $a_i$;
• odd be the list of all odd $a_i$;
• $k = |odd|$.

If $k = 0$, answer is:

$$0$$

Otherwise, answer is:

$$E + \text{sum of the largest } \left\lceil \frac{k}{2} \right\rceil \text{ odd values}$$

Implementation details:

• Use long long, because sums can exceed 32-bit int.
• Sort odd values in descending order.
• Add the first (k + 1) / 2 odd values.

Time complexity per test case is $O(n \log n)$ because of sorting the odd values. Across all test cases, this is easily fine for $\sum n \le 2 \cdot 10^5$.