## Editorial for DMOPC '21 Contest 6 P2 - Gacha Luck

**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.**

Author:

The subtasks could be approached using any combination of prefix sum arrays, dynamic programming, or cleverly implemented brute force. For the sake of concision, we will only describe a greedy approach that is sufficient for full marks.

*Lemma:* There exists some optimal solution which does not include any s in any of the screenshots.

*Proof:* Suppose there exists some optimal solution with a positive number of s. Pick any of any screenshot in this solution. This screenshot will have some portion to the left of this with a value of , and it will also have some portion to the right of this with a value of . The total value of this screenshot can be calculated as . However, it is not hard to see that one of and will have a value that is no less than , WLOG let it be . Then, we can replace this screenshot with a screenshot of only the right portion, effectively reducing the total number of s by while maintaining at least as good of a score. Since we can repeat this process as long as a exists in an optimal solution, it follows that we can always find an optimal solution with no s.

With this observation, it is clear that we only need to consider s, and it is always the best to take an entire block of s all at once. So, we may simply sort all of the blocks of s in non-increasing length and take the longest blocks.

**Time Complexity:**

## Comments