Official

D - Shipping Center Editorial by en_translator

We solve the problem for each query independently (we don’t need special precalculation).

Let us consider what is the optimal way to put the baggages into the boxes. We can obtain the maximum value in the following two ways:

  • Inspect the baggages in the decreasing order of values, and put each of them to the box with the minimum size that can contain it
  • Inspect the boxes in the increasing order of sizes, and put the baggage with the maximum value that each of them can contain
Proof
We only show the former. The latter can be shown in the same way. For simplicity, we assume that the values of baggages and the sizes of the boxes are pairwise distinct. (General cases can be boiled down to such case with proper transformation)
We will show that any packing can be transformed to such packing without decreasing the sum of values.
We perform the following operation for each baggage, in the decreasing order of their values.

Operation:
Let $A$ be the baggage currently focused.
Let us focus the minimum-sized box which contains the baggage with the value less than $A$ and in which we can put $A$, if exists. (We regard a box without a baggage in it as containing a baggage of value $0$)
・If such box does not exist, do nothing.
・Otherwise, if $A$ is currently not contained in any box, take the baggage out of the focused box, and put $A$ in instead.
・Otherwise, if $A$ is currently in the box with larger size than the focused box, swap the contents of those two boxes.
・Otherwise, if $A$ is currently in the box with smaller size than the focused box, do nothing.

The number of this operation is equal to the number of baggages, the sum of values of baggages in the boxes after each operation is non-decreasing, and after the operations have ended, the baggage in each box is same to the resulting baggage of the method mentioned at first.

In either of those two methods, the answer can be found within an \(O(NM)\) time for each query.

Also, one can use segment trees properly to solve within an \(O(N\log M)\) or \(O(M\log N)\) time for each query.

posted:
last update: