Editorial for COCI '22 Contest 4 #2 Zrinka
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.
Submitting an official solution before solving the problem yourself is a bannable offence.
The first two subtasks can be solved using a greedy approach.
For full points, we will use dynamic programming.
Let represent the solution if we only consider the first
positions of the first array, the first
positions of the second array, and if the largest number is in the first array, then
, otherwise
(and the largest number is in the second array).
For the transition we need only to consider states:
, so the final complexity is
.
Comments