Digging for Oil

Explicación

Queremos los tres cuadrados $K \times K$ disjuntos más grandes con las mayores sumas totales. Notamos que cada par de rectángulos debe estar en lados opuestos de alguna recta. Esto nos deja con dos configuraciones básicas: o bien hay dos rectas paralelas que dividen los cuadrados, o bien hay dos rectas perpendiculares. Las configuraciones se ilustran abajo:

Notamos que las soluciones deben contemplar todas las rotaciones posibles de estas configuraciones.

Configuración 1

En esta configuración, podemos hallar la respuesta para cada subrectángulo que no es el del medio usando el método de la Configuración 2. Sin embargo, necesitamos usar otra recurrencia para hallar el rectángulo del medio. Sin pérdida de generalidad, sean los subrectángulos dispuestos de arriba hacia abajo, ya que el orden izquierda-derecha se puede hallar de forma similar. Sea $dp_{i, j}$ la respuesta para las filas en el intervalo $[i,j]$ . Obviamente $dp_{i,i+l}$ no tiene respuestas si $l < k-1$ . También podemos hallar $dp_{i, i+k}$ de forma manual como caso base. Luego, notamos que $dp_{i,j}$ consiste en todos los cuadrados $K \times K$ contados en $dp_{i+1, j}$ y $dp_{i, j-1}$ . Entonces, solo quedan los cuadrados contados en la fila $i$ y en la fila $j$ , que son justamente $dp_{i, i+k-1}$ y $dp_{j-k+1, j}$ respectivamente. Así, la recurrencia es

dp_{i,j} = \max(\max(dp_{i+1, j},dp_{i,i+k-1}), \max(dp_{i, j-1}, dp_{j-k+1, j})).

Notamos que los intervalos deben recorrirse de menor a mayor.

Configuración 2

Basta usar sumas de prefijos. Desde cada esquina, hallamos la suma de los valores de todos los puntos que se pueden alcanzar viajando únicamente hacia esa esquina desde un punto $(i, j)$ , y guardamos el valor con $(i, j)$ . Podemos usar esto para hallar la cantidad total de petróleo de los cuadrados $K \times K$ en cada esquina de $(i, j)$ . Estos valores nos ayudan a hallar la cantidad máxima de petróleo en un cuadrado $K \times K$ en cada esquina de $(i, j)$ . Luego hacemos un análisis por casos para cada reflexión para obtener la respuesta.

Implementación

C++

Se puede rotar la grilla para facilitar la implementación.


#include <bits/stdc++.h>
 
using i64 = long long;
 
template <typename T> bool chmax(T &a, T b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}
 
constexpr i64 inf = i64(1E18);
 
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
 
	int N, M, K;
	std::cin >> N >> M >> K;
 
	std::vector<std::vector<i64>> A(N, std::vector<i64>(M));
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < M; ++j) { std::cin >> A[i][j]; }
	}
 
	i64 ans = 0;
 
	// Configuración 1 (rectas paralelas)
	for (int _ = 0; _ < 2; ++_) {
		std::vector<std::vector<i64>> pre(N, std::vector<i64>(M));
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < M; ++j) {
				pre[i][j] = A[i][j];
				if (i) pre[i][j] += pre[i - 1][j];
				if (j) pre[i][j] += pre[i][j - 1];
				if (i && j) pre[i][j] -= pre[i - 1][j - 1];
			}
		}
 
		auto sum = [&](int x1, int y1, int x2, int y2) {
			i64 res = pre[x2][y2];
			if (x1) res -= pre[x1 - 1][y2];
			if (y1) res -= pre[x2][y1 - 1];
			if (x1 && y1) res += pre[x1 - 1][y1 - 1];
			return res;
		};
 
		std::vector<i64> top1(N + 1, -inf), top2(N + 1, -inf);
		for (int i = 0; i + K - 1 < N; ++i) {
			chmax(top1[i + 1], top1[i]);
			for (int j = 0; j + K - 1 < M; ++j) {
				chmax(top1[i + K], sum(i, j, i + K - 1, j + K - 1));
			}
			chmax(top2[i + 1], top2[i]);
			for (int j = 0; j + K - 1 < M; ++j) {
				chmax(top2[i + K], top1[i] + sum(i, j, i + K - 1, j + K - 1));
			}
			for (int j = 0; j + K - 1 < M; ++j) {
				chmax(ans, top2[i] + sum(i, j, i + K - 1, j + K - 1));
			}
		}
 
		std::vector<std::vector<i64>> h(M, std::vector<i64>(N));
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < M; ++j) { h[j][i] = A[i][j]; }
		}
		A = std::move(h);
		std::swap(N, M);
	}
 
	// Configuración 2 (rectas perpendiculares)
	for (int _ = 0; _ < 4; ++_) {
		std::vector<std::vector<i64>> pre(N, std::vector<i64>(M));
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < M; ++j) {
				pre[i][j] = A[i][j];
				if (i) pre[i][j] += pre[i - 1][j];
				if (j) pre[i][j] += pre[i][j - 1];
				if (i && j) pre[i][j] -= pre[i - 1][j - 1];
			}
		}
 
		auto sum = [&](int x1, int y1, int x2, int y2) {
			i64 res = pre[x2][y2];
			if (x1) res -= pre[x1 - 1][y2];
			if (y1) res -= pre[x2][y1 - 1];
			if (x1 && y1) res += pre[x1 - 1][y1 - 1];
			return res;
		};
 
		std::vector<i64> top(N, -inf);
		for (int i = 0; i + K - 1 < N; ++i) {
			for (int j = 0; j + K - 1 < M; ++j) {
				chmax(top[i + K - 1], sum(i, j, i + K - 1, j + K - 1));
			}
		}
 
		for (int i = 1; i < N; ++i) { chmax(top[i], top[i - 1]); }
 
		std::vector<i64> lef(M, -inf), rig(M, -inf);
 
		for (int i = N - K; i >= 0; --i) {
			i64 mx = -inf;
			for (int j = 0; j < M; ++j) { chmax(mx, lef[j] + rig[j]); }
 
			chmax(ans, top[i] + mx);
			for (int j = 0; j + K - 1 < M; ++j) {
				chmax(lef[j + K - 1], sum(i, j, i + K - 1, j + K - 1));
			}
			for (int j = M - 1; j - K >= 0; --j) {
				chmax(rig[j - K], sum(i, j - K + 1, i + K - 1, j));
			}
			for (int j = 1; j < M; ++j) { chmax(lef[j], lef[j - 1]); }
			for (int j = M - 1; j >= 1; --j) { chmax(rig[j - 1], rig[j]); }
		}
 
		std::vector<std::vector<i64>> h(M, std::vector<i64>(N));
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < M; ++j) { h[M - j - 1][i] = A[i][j]; }
		}
		A = std::move(h);
		std::swap(N, M);
	}
 
	std::cout << ans << '\n';
 
	return 0;
}