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.
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 and have read
the covers of book
. He will definitely not reduce his inspiration if he read book
instead of book
.
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 books, he can maximally read next
books. To determine his inspiration we can use prefix sums. We can do this for every possible
. Total time complexity:
.
Comments