Official Analysis

Explanation

Note that between any two disjoint rectangles, we can draw either a vertical or horizontal line between these two rectangles. We can consider every possible vertical and horizontal line, and find the two best rectangles between the lines.

Let's first consider every vertical line. Consider fixing the two rows of our rectangle. If we can calculate the best rectangle perimeter for every prefix and suffix of our available columns, we can find our answer by sweeping over the splitting point. The implementation below iterates on the right column and then uses two pointers to find the best left column. Similar logic can be applied to find the best result for every horizontal line.

Implementation

Time Complexity: $\mathcal{O}(l^{2}w + w^{2}l)$

Copy
#include <bits/stdc++.h>
using namespace std;

int main() {
	int l, w;
	cin >> l >> w;
	int n, k;
	cin >> n >> k;
	vector<vector<int>> grid(l + 1, vector<int>(w + 1));
	for (int i = 0; i < n; i++) {