Editorial for DMOPC '18 Contest 6 P5 - Quadrat Sampling
Submitting an official solution before solving the problem yourself is a bannable offence.
In order to maximize the raw total, each goose should fly to a cell covered by as many quadrats as possible so that it can be counted the maximum number of times. Thus, we seek where is the number of quadrats covering the cell at row and column .
For the first subtask, we can use a 2D prefix sum array to compute all in per quadrat plus post-processing. Then, for each goose, we can go over all the cells that it can reach to find the one covered by the most quadrats.
For the second subtask, we can sweep the rows from top to bottom, keeping a data structure such as a segment tree that allows for efficient range addition updates and range maximum queries. When we reach the beginning or the end of quadrat , we add 1 to or subtract 1 from the cells from to . When we reach goose , we query the cells from to to find its .
We can then do a similar sweep from left to right to find for each goose.
For the final subtask, we must first compress the coordinates so that the maximum row and column are . Then, we can do the same thing as in the second subtask.