Subtask 1

Brute force all ~5^N~ possibilities for each shopping deal (assigning it to one of the four regions or leaving it unused).

Time Complexity: ~\mathcal{O}(NM \cdot 5^N)~.

Subtask 2

Do a bitmask dynamic programming, considering the deals one by one while tracking which subset of the ~M~ items has been covered by a deal.

Time Complexity: ~\mathcal{O}(N \cdot 2^M)~.

Subtask 3

The key observation is that if four shopping deals are chosen, then it is always possible to assign their regions to cover the entire plane. Intuitively, we can assign each deal to a different "quadrant" of the plane. This fact can be verified by brute-forcing all arrangements of four points.~^1~

Using this observation, we should either choose the four cheapest shopping deals or brute force all ~\mathcal{O}(N^3)~ ways to use three or fewer deals, taking ~\mathcal{O}(M)~ time each to determine which items are covered.

Time Complexity: ~\mathcal{O}(N^3 M)~.

~^1~There is a related old math problem asking to prove that for any ~n~ points, it is possible to draw a sector with angle ~2\pi/n~ at each point so that the entire plane is covered (one source). The oldest reference appears to be from the Russian journal Kvant: No.11, 1981.

Subtasks 4, 5

The ~N~ points induce ~2N~ vertical and ~2N~ horizontal lines that divide the plane into ~(2N+1)^2~ rectangular areas, where every possible shopping deal region is a union of some of these areas. Apply coordinate compression to find the sum of the prices of all items in each area, and build a 2D prefix-sum array. Now for each of the ~\mathcal{O}(N^3)~ ways to use three or fewer deals, the sum of the prices of all items in the union of the chosen regions can be computed in ~\mathcal{O}(1)~ time using inclusion-exclusion.

Subtask 4 is created to reward implementations that fail to handle "degenerate" cases correctly, such as by treating the deals as inducing only ~N~ vertical and ~N~ horizontal lines cutting through their coordinates.

Time Complexity: ~\mathcal{O}(M \log N + N^3)~.

Subtasks 6, 7

At a high level, by maintaining some prefix optimum-like quantities, the ~\mathcal{O}(N^3)~ possible arrangements can all be considered in only ~\mathcal{O}(N^2)~ time. The challenge lies in finding an implementation without an unmanageable amount of casework. The author's solution has only ~4~ essentially different nontrivial cases.

First, process all ways to use ~0~, ~1~, ~2~, or ~4~ shopping deals. There are ~4~ essentially different cases for using exactly ~3~ shopping deals:

1. Two of the regions do not intersect at all.

   

   In this case, try all ~\mathcal{O}(N)~ possibilities for the third deal (~C~ in the above figure). For each possibility, sweep a line (~\ell~ in the above figure) separating the two remaining regions while maintaining running maximums of the additional savings from ~A~ in the first half (i.e., from items not already covered by ~C~), and additional savings from ~B~ in the second half.

2. The opposite "quadrant" of some region is completely uncovered.

   

   In this case, try all possibilities for ~C~, the deal whose opposite region is completely uncovered, as shown in the above figure. For each possibility, calculate the best savings from a deal ~A~ within the top-left quadrant of ~C~ and the best savings from a deal ~B~ within the bottom-right quadrant of ~C~. Since these two quadrants are disjoint, this ensures that no savings are double-counted. Be careful to ensure that ~A~ and ~B~ are not the same deal (e.g. by also computing second bests).

3. Only two opposite corners are covered.

   

   In this case, try all possibilities for ~C~, the deal that covers both of the other deals, as shown in the above figure. For each possibility, start by adding in the savings from all items in either the top-right or bottom-left quadrants from ~C~. Take the best savings from a deal ~A~ within the top-left quadrant of ~C~ and the best savings from a deal ~B~ within the bottom-right quadrant of ~C~.

4. Two deals cover each other and the last deal covers a remaining corner.

   

   In this case, try all combinations for the deals ~A~ and ~B~ that cover each other, as shown in the above figure. The other deal ~C~ should be the minimum cost deal in the top-left quadrant of the point ~D~ in the above figure, which can be found using a precomputed 2D prefix minimum array. Be careful to ensure that ~A~, ~B~, and ~C~ are all distinct (e.g. by also precomputing second and third bests).

Correctly implementing all of these cases and their rotations/reflections can get full points.

Subtask 6 is created to reward implementations that fail to handle "degenerate" cases correctly.

Time Complexity: ~\mathcal{O}(M \log N + N^2)~.