Official Analysis

Explanation

Consider iterating over every possible upper left corner of our pyramid's base. We want to find the chamber inside our pyramid's base with the smallest sum of heights.

This boils down to doing a 2D range minimum query on every possible upper left corner of our chamber. When iterating over each row, we maintain an array of monotonic deques indexed by column. Each monotonic deque allows us to find the best chamber in the sliding window of rows that can have an upper left corner for a chamber. To maintain our monotonic queue, we pop the front element if its row index is too small to be a suitable chamber. When adding to the back of the monotonic deque, we first pop any elements greater than or equal to this current element. Then, the sliding window minimum is the value at the front of the deque.

Now, when iterating on every column that our pyramid's upper left corner can be at, we maintain a monotonic deque that allows us to find the best chamber possible for our pyramid. This monotonic deque keeps track of the best chamber in our sliding window of possible columns for our chamber. We maintain it in a similar fashion as described before: pop the front element if its column index is too small, and pop all bigger elements when pushing to the back. This deque is guaranteed to have the best result at the front because the elements we are pushing into the deque are the best results in each column.

Note that in order to achieve $\mathcal{O}(NM)$ time complexity, 2D prefix sums are required.

Implementation

Time Complexity: $\mathcal{O}(NM)$

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

int main() {
	int m, n, b, a, d, c;
	cin >> m >> n >> b >> a >> d >> c;
	vector<vector<int>> grid_sum(n + 1, vector<int>(m + 1));
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> grid_sum[i][j];