## Editorial for DMOPC '18 Contest 4 P3 - Dr. Henri and Ionization

Remember to use this editorial

**only**when stuck, and**not to copy-paste code from it**. Please be respectful to the problem author and editorialist.**Submitting an official solution before solving the problem yourself is a bannable offence.**Author:

Note that we can always do the individual removals first, then all the pair removals at once. This way, we ignore the entire "opposite" condition. This simplifies the problem to choosing between pairs or individual removals. Now the problem is simply to choose between and values so that an even number of values is chosen and the sum is minimized. This can be done using dynamic programming. Specifically, let be the minimum sum where exactly values have been chosen so far, and we are only considering the first electrons (arbitrary ordering). Then . The final answer is .

**Time Complexity:**

For the full solution, note that only matters. So we only need to consider and . There are now only states rather than .

**Time Complexity:**

## Comments

In fact, you can sort the electrons by , and take two at a time, until it cannot be improved, which is an solution.