Solution 1

~\mathcal O(n^8)~: Try all possible placements of squares, add their interior totals. Such a solution should score around ~10\%~.

Solution 2

~\mathcal O(n^6)~: Try all possible placements of squares, using precomputed cumulative sums to allow the sum under an area to be determined in ~\mathcal O(1)~. Such a solution should score around ~30\%~.

Solution 3

~\mathcal O(n^2)~: Observe that no matter how you place three squares, it is possible to separate one of them with either a horizontal or vertical cut. For example:

XXZZ
XXZZ_________cut
YY           here
YY

There are ~\mathcal O(n)~ possible cuts. Without loss of generality, assume the answer is a horizontal cut leaving two pieces in the region above and one in the region below. Of the side with two pieces, these pieces can be separated by either a horizontal or vertical dividing line. This means that the square can be in one of two configurations (or any of the three other rotations of these):

+----+--------+   +-------------+
|    |        |   |      A      |
| A  |   B    |   +-------------+
|    |        |   |      B      |
|    |        |   |             |
+----+--------+   +-------------+
|             |   |             |
|     C       |   |      C      |
+-------------+   +-------------+
Configuration 1   Configuration 2

We can precompute the best square in any region that contains a corner square in ~\mathcal O(n^2)~ time. This means that we can determine the best solution for all possible horizontal and vertical cuts in the first configuration as each region shares a corner. To do so, we simply consider all possible values of horizontal and vertical cuts, summing the best solution in each region.

For the second configuration, the same precomputed table can be used to solve for regions A and C. However we cannot use our precomputed table to solve for region B. We additionally need to precompute the best square for each set of ~k~ rows, which can be performed in ~\mathcal O(n^2)~. We can then solve for the best solution in the region B by incrementally making region B larger, one row at a time: starting with region B being precisely ~k~ rows tall, we can obtain the best solution for region B from our row lookup table. Each time we successively increase the size of region B by one row, we can determine the best solution for region B by taking the maximum of the previous solution for B and the best solution that includes the row just added.

All possible cuts for configurations can be considered in ~\mathcal O(n^2)~ time. Consider all possible cuts for all possible configurations and all four possible rotations of these configurations and output the best solution found.