For the first subtask, we can try all possible ways to take out the space pirates. For each possible way, the space pirate will be taken out, and all neighbouring space pirates will have their energy reduced. A space pirate with a negative energy can be ignored.

Time complexity: ~\mathcal{O}(N! \cdot N^2)~

After reading the problem statement, we realize that the actual task is to find all groups of connected squares and to sum the maximum ship energy of each connected group.

We can treat the squares as a graph, where each square is a node and a square has an edge to another square if the two squares' Manhattan distance is less or equal to the sum of their corner radii. Now, we can perform a DFS in order to get each connected group. However, at every square, we need to check all other squares for an edge.

We can also find all connected groups by using a disjoint set instead of a DFS, but again, at every square, we need to check all other squares.

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

First, the corners of each space pirate need to be rotated so that all sides of the space pirate are parallel to the ~x~ and ~y~ axes. This can be accomplished by treating the coordinates as ~(x + y \cdot i)~ and multiplying this value by ~(1+i)~. Make sure to use 64-bit integers when performing this operation. The total time complexity is ~\mathcal{O}(N)~.

The next step is to compress the coordinates of each space pirate. Ideally, each space pirate now becomes a rectangle with coordinates between ~0~ and ~N~. The total time complexity is ~\mathcal{O}(N \log N)~.

After doing this, one can process the rectangles according to their ~x~. Each operation becomes either adding a rectangle, or removing a rectangle. This method is known as line sweep.

A possible data structure for adding and removing ranges is a segment tree, with each range containing two multisets/maps. The first map stores the rectangle IDs which completely covers this segment. The second map stores the rectangle IDs which use a part of this segment.

To add the rectangle with ID ~r~, it is possible to start at the root and move downward. All of the touching rectangle IDs should be stored in a set (called ~S~ in this editorial). If a rectangle uses a part of a completely covered segment, set ~S~ can grow in size (by reading from the first map). If a rectangle completely covers a segment, set ~S~ can also grow in size (by reading from both maps). Make sure all of the added segments are stored somewhere, such as ~m[r]~. The amortized time complexity of one insertion is ~\mathcal{O}(\log^2 N)~.

After the segment is placed, a disjoint set data structure can be used to join rectangles together. Make sure all of the elements in ~S~ point to the ID of the largest disjoint set. It is enough to define the size as the number of elements in the segment tree which still exists. Then all of the elements in ~S~ can be relabelled to the ID of the largest disjoint set. There are no updates to any of the ~m[r]~. At maximum, ~\mathcal{O}(N \log N)~ nodes have to be relabelled approximately ~\log N~ times each, therefore the total time complexity of all merges is ~\mathcal{O}(N \log^3 N)~. The runtime is usually lower in practice.

To delete a rectangle with ID ~r~, first get the root of the disjoint set. It is sufficient to remove the root once from all of the segments inside ~m[r]~. If the number of times is now ~0~, this root should be removed. The total time complexity of one deletion is ~\mathcal{O}(\log^2 N)~.

After all of the rectangles are read and the disjoint sets are finished, it will be easy to get the maximum energy value of each connected component.

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