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 ~1~s in any of the screenshots.

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

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

Time Complexity: ~\mathcal{O}(N \log N)~