Editorial for COCI '23 Contest 4 #2 Knjige


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.

It will always be optimal for all books that Marko reads (the whole book) to be adjacent. Why? Let us presume they are not adjacent. Then there would exist a place where Marko read book i and have read the covers of book i+1. He will definitely not reduce his inspiration if he read book i+1 instead of book i.

From that, we can conclude that the solution will always have first a few books that Marko has read only covers of, and then a few that he has read whole. If he skipped first x books, he can maximally read next y = \lfloor\frac{n - b \times x}{a}\rfloor books. To determine his inspiration we can use prefix sums. We can do this for every possible x. Total time complexity: \mathcal{O}(n).


Comments

There are no comments at the moment.