Este artículo detalla una solución eficinete mediante programación dinámica para el problema de control de ira en un aula, referenciado como P14169 en Luogu. El enfoque inicial implica definir un estado tridimensional para capturar la ira acumulada según el minuto, posición del profesor y energía consumida.

Definimos \( dp_{i,j,k} \) como el valor máximo de ira total hasta el minuto \( i \), con el profesor situado detrás del estudiante \( j \), habiendo utilizado una cantidad de energía \( k \). La transición se basa en los movimientos posibles del profesor en el minuto anterior:

\[ dp_{i,j,k} = \max_{p} \left\{ dp_{i-1,j+p,k-|p|} \right\} + anger_{i,j} \] donde \( anger_{i,j} \) representa el incremento de ira cuando el profesor está detrás del estudiante \( j \) en el minuto \( i \), y \( p \) denota el desplazamiento (positivo o negativo) dentro de los límites de energía y posición.

Los valores iniciales se establecen como \( dp_{0,j,0} = 0 \) para todo \( j \in [1,n] \). La respuesta final se obtiene maximizando sobre todas las posiciones y energías al último minuto: \( \max_{j=1}^n \max_{k=0}^T dp_{m,j,k} \).

Para calcular \( anger_{i,j} \), se utiliza una técnica de sumas prefijas. Primero, se precalculan las sumas acumuladas de los valores de ira base para cada minuto:

for (int i = 1; i <= m; i++)
    for (int j = 1; j <= n; j++)
        prefix_sum[i][j] = prefix_sum[i][j-1] + base_anger[i][j];

Luego, \( anger_{i,j} \) se determina como la suma en el intervalo [max(1, j-X), min(n, j+X)]:

for (int i = 1; i <= m; i++)
    for (int j = 1; j <= n; j++)
        anger[i][j] = prefix_sum[i][min(n, j+X)] - prefix_sum[i][max(1, j-X)-1];

La complejidad temporal inicial es \( \mathcal{O}(mn^2T) \), lo cual es ineficiente. Se optimiza transformando la ecuación DP para separar las transiciones hacia la derecha e izquierda. Introducimos dos arreglos auxiliares: \( right\_max_{i,j,k} \) para capturar el máximo al moverse hacia la derecha con energía decreciente, y \( left\_max_{i,j,k} \) para movimientos hacia la izquierda.

\[ right\_max_{i,j,k} = \max \left( right\_max_{i,j+1,k-1}, dp_{i,j,k} \right) \] \[ left\_max_{i,j,k} = \max \left( left\_max_{i,j-1,k-1}, dp_{i,j,k} \right) \] Con condiciones base adecuadas, la ecuación DP se simplifica a:

\[ dp_{i,j,k} = \max \left( right\_max_{i-1,j,k}, left\_max_{i-1,j,k} \right) + anger_{i,j} \] Esto reduce la complejidad temporal a \( \mathcal{O}(mnT) \).

Sin embargo, el uso de arreglos tridimensionales lleva a una complejidad espacial de \( \mathcal{O}(mnT) \), lo que puede exceder los límites de memoria. Se observa que la dimensión temporal \( i \) solo es relevante para el cálculo actual, por lo que se puede eliminar para reutilizar espacio. Los arreglos se modifican a dos dimensiones, procesando minuto a minuto y actualizando in-place.

La implementación final en C++ utiliza arreglos redimensionados y ciclos optimizados:

#include<iostream>
#include<cstring>
using namespace std;
const int MAX_N = 315, MAX_T = 315;
int dp[MAX_N][MAX_T], base_anger[MAX_N][MAX_N], anger[MAX_N][MAX_N];
int prefix_sum[MAX_N][MAX_N], right_max[MAX_N][MAX_T], left_max[MAX_N][MAX_T];
int n, m, X, T;

int readInt() {
    int value = 0, sign = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') sign = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        value = (value << 3) + (value << 1) + (ch ^ 48);
        ch = getchar();
    }
    return value * sign;
}

void solve() {
    n = readInt(); m = readInt(); X = readInt(); T = readInt();
    memset(dp, 0, sizeof(dp));
    memset(prefix_sum, 0, sizeof(prefix_sum));
    memset(anger, 0, sizeof(anger));
    memset(right_max, 0, sizeof(right_max));
    memset(left_max, 0, sizeof(left_max));
    
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            base_anger[i][j] = readInt();
    
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            prefix_sum[i][j] = prefix_sum[i][j-1] + base_anger[i][j];
    
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            anger[i][j] = prefix_sum[i][min(n, j+X)] - prefix_sum[i][max(1, j-X)-1];
    
    for (int minute = 1; minute <= m; minute++) {
        for (int pos = 1; pos <= n; pos++)
            for (int energy = 0; energy <= T; energy++)
                dp[pos][energy] = max(right_max[pos][energy], left_max[pos][energy]) + anger[minute][pos];
        
        for (int pos = n; pos >= 1; pos--) // Orden inverso crucial para right_max
            for (int energy = 0; energy <= T; energy++) {
                if (pos == n || energy == 0)
                    right_max[pos][energy] = dp[pos][energy];
                else
                    right_max[pos][energy] = max(right_max[pos+1][energy-1], dp[pos][energy]);
            }
        
        for (int pos = 1; pos <= n; pos++)
            for (int energy = 0; energy <= T; energy++) {
                if (pos == 1 || energy == 0)
                    left_max[pos][energy] = dp[pos][energy];
                else
                    left_max[pos][energy] = max(left_max[pos-1][energy-1], dp[pos][energy]);
            }
    }
    
    int result = 0;
    for (int pos = 1; pos <= n; pos++)
        for (int energy = 0; energy <= T; energy++)
            result = max(result, dp[pos][energy]);
    
    printf("%d\n", result);
}

signed main() {
    int test_cases = readInt();
    while (test_cases--) solve();
    return 0;
}

Este enfoque logra una complejidad temporal de \( \mathcal{O}(mnT) \) y espacial de \( \mathcal{O}(nT) \), cumpliendo con los requisitos de eficiencia.