Editorial for COCI '22 Contest 5 #4 Slastičarnica
Submitting an official solution before solving the problem yourself is a bannable offence.
Let be the maximum number of customers we can serve if we still have cakes at the table. For the first subtask, we can use the simple transition:
where is a function that returns if it is possible to satisfy customer with the cakes , and otherwise. Time complexity is or , depending on the implementation of the function .
Similarly, for the second subtask if all are equal to , then we only need to check and to determine .
That leads us to the complete solution. Is it possible somehow to check only neighbouring states and get the required solution? It is! Instead of memorizing only the maximum number of customers we can serve, we will memorize two more things: the biggest number of cakes that is possible to give to the current customer outside the left and the right border. For example, let be the number of cakes we can give to the current customer outside of the left border. Two things need to be satisfied:
- (it is possible to give all the cakes to the current customer)
- (all the cakes have sweetness greater or equal to the required value)
Now we do not need to check every state, only the neighbouring ones. When one of the counters becomes equal to , we can give those cakes to the current customer, and increase the customer number by . Total time complexity is .