Editorial for COCI '22 Contest 5 #5 Zastave
Submitting an official solution before solving the problem yourself is a bannable offence.
Let's look at the case . Let be the area of the flag with height . It follows . The function is increasing until and decreasing afterwards. It follows for the solution is and for the solution is . Notice:
Now for the general case. The function will be analogous to the previous but for any . Notice that the function is decreasing on the interval . If we were solving the discrete version, it would be enough to always take the element which would increase our solution the most, the correctness of this algorithm relies on the fact that the discrete derivative is decreasing. In the continuous case, the analogous solution is to always move the point which currently has the largest derivative. But, it is easier to fix a derivative and check whether the sum of 's such that is smaller than . Notice that for such :
Now it is enough to find such a with binary search. It is enough to do steps for the wanted precision. The final complexity is . There are some edge cases that need to be checked by hand.