Just Green Enough

Análisis oficial (C++, Java) 

Explicación

Primero, consideremos resolver este problema en 1D, donde elegimos intervalos de la lista $g(j)$, los valores de un pasto de $1\times N$.

Sea $g'(j)$ igual a $-1$ si $g(j)<100$, $0$ si $g(j)=100$, y $1$ si $g(j)>100$. Debemos hallar un rango de $j$ en el que no haya $-1$ y haya al menos un $0$. Precomputamos $g'(j)$. El objetivo ahora es contar la cantidad de intervalos sin $-1$ y con al menos un $0$.

Luego, barreemos $j$ de $1$ a $N$ y llevamos el último índice en el que encontramos $0$ y $-1$ como $j_0$ y $j_{-1}$, respectivamente. Para que un intervalo se elija, debe incluir un $0$, así que el índice inicial no puede ser posterior al último $0$ que encontramos; el intervalo no puede incluir un $-1$, así que el índice inicial debe ser posterior al último $-1$ que encontramos. Así, cualquier rango con índice inicial en el intervalo $(j_{-1}, j_0]$ e índice final en $j$ funciona, siempre que $j_{-1}<j_0$ y $g'(j)\in\{0,1\}$. Hay $j_0-j_{-1}$ intervalos; acumulamos esos números si se cumplen las condiciones para obtener la respuesta. Inicializamos tanto $j_0$ como $j_{-1}$ en $0$, de modo que al principio no produzcan acumulación, y que todas las posibilidades de $(0, j_0]$ se cuenten si todavía no ha aparecido un $-1$.

Ahora generalizamos esto a dos dimensiones, donde elegimos subrectángulos de un pasto de $N\times N$. Denotamos los valores del pasto $G(i, j)$ para $i,j\in[1,N]$. Primero consideramos los casos en los que los bordes del rectángulo incluyen $i=1$ e $i=N$, y nos queda elegir el intervalo para los bordes izquierdo y derecho. Como en el caso 1D, barreemos de izquierda a derecha el extremo derecho y construimos un $g'$ para seguir la viabilidad del extremo izquierdo por columna. Cualquier elemento $<100$ de una columna bloquea la selección, y cualquier elemento $=100$ la permite, así que $g'$ se marca $-1$ o $0$ si estas condiciones se cumplen para algún elemento de una columna, y $1$ en caso contrario. Luego procedemos como en el caso 1D para $g'$.

Ahora generalizamos al caso en que el subrectángulo puede tener bordes verticales arbitrarios $i=i_1$ e $i=i_2\geq i_1$. De forma naive, procederíamos como en el caso anterior, usando solo los elementos en $i\in[i_1,i_2]$ de cada columna para calcular $g'$; sin embargo, recalcular $g'$ cada vez es demasiado ineficiente. Por eso usamos un enfoque incremental: En cada $i_1$ posible, reiniciamos $g'(j)$ a $1$s, antes de recorrer $i_2$ y $j$. En cada $i_2$, $g'(j)$ da cuenta de $G(i_1\ldots i_2-1,j)$, así que lo actualizamos para dar cuenta de $G(i_2,j)$ en cada $j$ antes de usar el enfoque anterior. Llevar el arreglo $g'$ de forma acumulativa nos da complejidad $\mathcal O(N)$ por cada elección de filas superior e inferior, así que en total tenemos $\mathcal O(N^3)$.

Implementación

Complejidad temporal: $\mathcal O(N^3)$

#include <iostream>
 
using namespace std;
 
constexpr int MAX_N = 500;
 
// G en el problema
int a[MAX_N + 1][MAX_N + 1];
 
// g' en la explicación
int g_prime[MAX_N + 1];
 
int main() {
	int n;
	cin >> n;
 
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++) cin >> a[i][j];
 
	long long ans = 0;
	for (int i1 = 1; i1 <= n; i1++) {
		// Reiniciar g'
		for (int j = 1; j <= n; j++) g_prime[j] = 1;
 
		for (int i2 = i1; i2 <= n; i2++) {
			// i_0 e i_{-1} en la explicación, respectivamente
			int last_zero = 0, last_neg = 0;
			for (int j = 1; j <= n; j++) {
				// Actualizar g'
				if (a[i2][j] < 100) g_prime[j] = -1;
				if (a[i2][j] == 100 && g_prime[j] != -1) g_prime[j] = 0;
 
				// Actualizar últimos índices
				if (g_prime[j] == 0) last_zero = j;
				if (g_prime[j] == -1) last_neg = j;
 
				// Acumular
				if (g_prime[j] == 0 || g_prime[j] == 1) {
					ans += max(0, last_zero - last_neg);
				}
			}
		}
	}
 
	cout << ans << endl;
	return 0;
}