Skip to Content
CTRL K

Pyramid

Análisis oficial 

Explicación

Consideremos iterar sobre cada esquina superior izquierda posible de la base de nuestra pirámide. Queremos hallar la cámara dentro de la base de nuestra pirámide con la suma de alturas más chica.

Esto se reduce a hacer una consulta de mínimo en un rango 2D sobre cada esquina superior izquierda posible de nuestra cámara. Al iterar sobre cada fila, mantenemos un arreglo de deques monótonos indexados por columna. Cada deque monótono nos permite hallar la mejor cámara en la ventana deslizante de filas que puede tener una esquina superior izquierda para una cámara. Para mantener nuestra cola monótona, sacamos el elemento del frente si su índice de fila es demasiado chico para ser una cámara adecuada. Al agregar al final del deque monótono, primero sacamos cualquier elemento mayor o igual que este elemento actual. Luego, el mínimo de la ventana deslizante es el valor del frente del deque.

Ahora, al iterar sobre cada columna en la que puede estar la esquina superior izquierda de nuestra pirámide, mantenemos un deque monótono que nos permite hallar la mejor cámara posible para nuestra pirámide. Este deque monótono lleva la cuenta de la mejor cámara en nuestra ventana deslizante de columnas posibles para nuestra cámara. Lo mantenemos de forma similar a lo descrito antes: sacar el elemento del frente si su índice de columna es demasiado chico, y sacar todos los elementos más grandes al empujar al final. Este deque tiene garantizado el mejor resultado al frente porque los elementos que empujamos al deque son los mejores resultados de cada columna.

Notar que para alcanzar complejidad temporal O(NM)\mathcal{O}(NM), se necesitan sumas de prefijos 2D.

Implementación

Complejidad temporal: O(NM)\mathcal{O}(NM)

#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];
			grid_sum[i][j] +=
			    grid_sum[i - 1][j] + grid_sum[i][j - 1] - grid_sum[i - 1][j - 1];
		}
	}
 
	/** @return suma del rectángulo con esquinas en (r1, c1) y (r2, c2) */
	const auto rect_sum = [&](int row_1, int col_1, int row_2, int col_2) -> int {
		return grid_sum[row_2][col_2] - grid_sum[row_2][col_1 - 1] -
		       grid_sum[row_1 - 1][col_2] + grid_sum[row_1 - 1][col_1 - 1];
	};
	/** @return suma del rectángulo de la pirámide con esquina superior izquierda en (r, c) */
	const auto p_sum = [&](int row, int col) -> int {
		return rect_sum(row, col, row + a - 1, col + b - 1);
	};
	/** @return suma del rectángulo de la cámara con esquina superior izquierda en (r, c) */
	const auto c_sum = [&](int row, int col) -> int {
		return rect_sum(row, col, row + c - 1, col + d - 1);
	};
 
	// col_best[i] = mejores cámaras desde la columna i
	vector<deque<int>> col_best(m + 1);
	for (int i = 2; i + d - 1 < m; i++) {
		for (int j = 2; j + c - 1 < a; j++) {
			while (!col_best[i].empty() &&
			       c_sum(j, i) <= c_sum(col_best[i].front(), i)) {
				col_best[i].pop_front();
			}
			col_best[i].push_back(j);
		}
	}
 
	// res = {suma, esquina de la pirámide, esquina de la cámara}
	array<int, 5> res = {-1, -1, -1, -1, -1};
	for (int i = 1; i + a - 1 <= n; i++) {
		// rmq guarda las mejores cámaras de cada columna en un
		// deque monótono, para poder hallar el mínimo de la ventana deslizante
		deque<array<int, 2>> rmq;
 
		// inicializar la ventana deslizante
		for (int j = 2; j + d - 1 < b; j++) {
			while (!rmq.empty() && c_sum(col_best[j].front(), j) <=
			                           c_sum(rmq.back()[0], rmq.back()[1])) {
				rmq.pop_back();
			}
			rmq.push_back({col_best[j].front(), j});
		}
 
		// iterar sobre la pirámide elegida y hallar la mejor respuesta
		for (int j = 1; j + b - 1 <= m; j++) {
			// calcular la respuesta para esta ubicación de la pirámide
			const auto [row, col] = rmq.front();
			int cur = p_sum(i, j) - c_sum(row, col);
			res = max(res, {cur, i, j, row, col});
			// actualizar el deque de RMQ para la siguiente iteración
			if (col == j + 1) { rmq.pop_front(); }
			int nxt = j + b - d;
			if (nxt + d - 1 >= m) { break; }
			while (!rmq.empty() && c_sum(col_best[nxt].front(), nxt) <=
			                           c_sum(rmq.back()[0], rmq.back()[1])) {
				rmq.pop_back();
			}
			rmq.push_back({col_best[nxt].front(), nxt});
		}
 
		// actualizar el arreglo col_best para la siguiente iteración
		for (int j = 2; j + d - 1 < m; j++) {
			if (!col_best[j].empty() && col_best[j].front() <= i + 1) {
				col_best[j].pop_front();
			}
			int nxt = i + a - c;
			while (!col_best[j].empty() &&
			       c_sum(nxt, j) <= c_sum(col_best[j].back(), j)) {
				col_best[j].pop_back();
			}
			col_best[j].push_back(nxt);
		}
	}
 
	swap(res[1], res[2]);
	swap(res[3], res[4]);
	for (int i = 1; i < 5; i++) { cout << res[i] << " \n"[i % 2 == 0]; }
}
Fundamentos