Lemon Melon Cookie

The answer is impossible if more than $N$ lemon cookies or more than $N$ melon cookies are already fixed.

Otherwise, exactly $N-\#M$ undecided positions must become melon cookies. Changing position $i$ from lemon to melon adds cost $i$, so the earliest available positions should be chosen.

The time complexity is $O(N)$ per test case and the extra space complexity is $O(1)$.

Solution written by GPT5