Subtask 1

A brute force algorithm will suffice for this subtask. After the ~j~-th minute, simply consider all ~N^j~ ways of assigning the first ~j~ worms to the ~N~ pigeons.

Time complexity: ~\mathcal O(M (N + M) N^M)~

Subtask 2

A slightly better brute force algorithm is required for this subtask. Rather than consider all possible ways of assigning the worms, it can be quickly realized that the smallest worms should be assigned to the smallest pigeons.

First, we will need to sort the beak sizes. After the ~j~-th minute, we should also sort the first ~j~ worm diameters. Then, we can find the maximum possible flock satisfaction by linearly searching for it. In other words, for all ~1 \le k \le M~, we should try to feed the ~k~ smallest worms to the smallest pigeon, then feed the next ~k~ smallest worms to the next smallest pigeon, and so on. If this assignment works, then ~k~ is a possible flock satisfaction; otherwise, ~k~ is not.

Time complexity: ~\mathcal O(N \log N + M^3)~

Subtask 3

This subtask requires the following observation:

Lemma: For all ~1 \le i \le N~, define the "sub-satisfaction" of the ~i~-th smallest pigeon to be the number of worms that pigeon can eat, divided by ~i~ (and rounded down). Then, the maximum possible satisfaction of the flock equals the minimum sub-satisfaction among all pigeons.

The rationale for this observation is as follows: Using the greedy algorithm explained in Subtask 2, if we try to feed ~k~ worms to every pigeon, the largest worm that the ~i~-th smallest pigeon will eat is the (~k \times i~)-th smallest worm. If ~k~ is larger than or equal to the pigeon's sub-satisfaction, then the pigeon can eat the worm; otherwise, the pigeon cannot.

Using this lemma, we can now develop the following algorithm: First, we need to sort the beak sizes. We will need to keep track of the number of worms each pigeon can eat over time. After the ~j~-th minute, we need to update these counts for the ~N~ pigeons, based on whether or not each pigeon can eat the ~j~-th worm. Then, we can easily compute the sub-satisfaction of each pigeon after each minute, which allows us to find the maximum possible satisfaction of the flock.

Time complexity: ~\mathcal O(N \log N + NM)~

Subtasks 4 and 5

The intended solution relies on offline processing. In other words, instead of processing the worms one-by-one, we will process all of the worms together before outputting any answers. First, a large inefficiency in the Subtask 3 solution was that the sub-satisfaction of a pigeon could become much larger than the satisfaction of the flock. We can notice that the flock's satisfaction cannot be higher than ~\frac M N~, since there would not be enough worms to increase the flock's satisfaction. Thus, by limiting a pigeon's sub-satisfaction to ~\frac M N~, we can process each pigeon a fewer number of times. Also, we need a way to quickly find the ~(ki)~-th earliest worm that the ~i~-th smallest pigeon can eat, for all ~1 \le k \le \frac M N~ and ~1 \le i \le N~. That way, we can set flags for when each pigeon's sub-satisfaction increases, and we would have to set these flags at most ~N \times \frac M N = M~ times. This can be done by building a BBST of the worms' surfacing times, then processing the pigeons in order from smallest to largest, and adding a worm to the BBST when the pigeon is large enough to eat it. (Clearly, this requires sorting both the pigeons and the worms by size).

After we finish this pre-processing, we can loop through the ~M~ minutes to determine the ~M~ answers. As we iterate through the loop, the flags will indicate when each pigeon's sub-satisfaction increases. To determine the minimum sub-satisfaction among all pigeons, we can simply keep track of the frequency of each sub-satisfaction value.

Subtask 4 was added as a "fail-safe" for submissions with some inefficiency (e.g. An extra log factor, a large constant factor, etc.)

Note: One can alternatively use a range query tree such as a segment tree or binary-indexed tree.

Time complexity: ~\mathcal O(N \log N + M \log M)~