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: r3mark

For the first subtask, straightforward $\mathcal O(N^2)$ ~\mathcal O(N^2)~ DP suffices.

Time Complexity: $\mathcal O(N^2)$ ~\mathcal O(N^2)~

For the second subtask, let $M_i = \min(A_i, B_i)$ ~M_i = \min(A_i, B_i)~. Keep a set of the smallest $j$ ~j~ 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: $\mathcal O(N \log N)$ ~\mathcal O(N \log N)~

Comments

There are no comments at the moment.