## Editorial for DMOPC '17 Contest 2 P6 - Lazy Days

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:

For the first subtask, straightforward DP suffices.

**Time Complexity:**

For the second subtask, let . Keep a set of the smallest of these values and their positions in the arrays. When adding the next value, check the rightmost one in the set before it and the leftmost one in the set after it and see whether or not switches are necessary. Using this, you can find out how many switches are necessary to achieve a certain answer. This result can be reversed to find out the largest possible answer for each number of switches.

**Time Complexity:**

## Comments