## Editorial for DMPG '16 S5 - Pizza Bag

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

First, let's solve the problem as if the pizza was a line instead of a cycle. (This is subtask 3.) If the goal is to find the longest segment equal in length to or shorter than , then the length of a segment can be quickly computed by building a prefix sum array on the line. If the sum of the range can be found by subtracting position of the prefix sum array from position , then for every position in the line, the largest sum segment ending at can be computed as the minimum of all positions in the range in the prefix sum array, subtracted from position . After building the prefix sum array, a set can be used to solve this (the sliding range minimum query problem) in , or alternatively, it can be solved in using a double ended queue.

To solve the problem for a cycle, just arbitrarily choose any starting point, take two periods, and treat it as a line.

## Comments