Yakiniku Restaurants

Consideremos primero una solución naive. Si fijamos el rango de restaurantes que visitamos, siempre debemos visitarlos en orden de izquierda a derecha. Esto hará que perdamos $A_l + A_{l + 1} + ... + A_r$ unidades de felicidad. Luego, cada ticket $j$ debe gastarse en el restaurante $i \in [l, r]$ con el mayor valor de $B_{i, j}$. De forma naive, este enfoque corre en $\mathcal{O}(N^2 M)$.

Por suerte, nuestra función de felicidad $C(l, r)$ satisface la desigualdad del cuadrángulo (QI). Para ver por qué, usemos la definición alternativa de esta desigualdad que se da en el módulo principal:

Una función $C(l, r)$ satisface la desigualdad del cuadrángulo sii, cuando incrementamos $r$, decrementar $l$ solo puede volverse más caro. Formalmente, para todo $l \leq r$, $C(l - 1, r) - C(l, r) \leq C(l - 1, r + 1) - C(l, r + 1)$.

Como buscamos maximizar $C(l, r)$, en cambio queremos mostrar que incrementar $r$ solo puede disminuir la felicidad adicional que ganamos al decrementar $l$. Esto es bastante intuitivo: como la felicidad ganada de cada ticket es igual al máximo de todos los restaurantes en nuestro rango, el impacto de agregar un solo restaurante disminuye a medida que el rango se hace cada vez más grande.

Formalmente, sea $C_i$ el valor $\max_{j \in [l + 1, r]} B_{j,i}$, la felicidad máxima que podemos obtener del ticket $i$. Entonces, decrementar de $l + 1$ a $l$ cambia nuestra felicidad en

Todos los $C_i$ solo pueden aumentar cuando incrementamos $r$, y por lo tanto la expresión anterior solo puede disminuir.

Así, podemos aplicar el método de divide y vencerás descrito en el módulo principal para resolver este problema en $\mathcal{O}(NM \log N)$.

Implementación

Complejidad temporal: $\mathcal{O}(NM \log N)$

#include <bits/stdc++.h>
using namespace std;
 
#define int int64_t
 
const int N = 5e3 + 1;
const int M = 201;
const int K = 13;
int n, m, a[N];
 
// RMQ---Sparse table
int smax(int &a, int b) { return a = max(a, b); }
struct ST : array<array<int, N>, K> {
	void build() {
		for (int k = 0; k < K - 1; k++) {
			at(k + 1) = at(k);
			for (int i = 0; i < n - (1 << k); i++) {
				smax(at(k + 1).at(i), at(k).at(i + (1 << k)));
			}
		}
	}
 
	int query(int l, int r) {
		int k = __lg(r - l);
		return max(at(k).at(l), at(k).at(r - (1 << k)));
	}
} b[M];
 
// maximize C for right endpoints in range [x, y) and left endpoints in range [l, r]
int solve(int x, int y, int l, int r) {
	if (x == y) return 0;
	int i = (x + y) / 2;
	pair<int, int> opt = {0, i};
	for (int j = min(i, r); j >= l; j--) {
		int s = a[j] - a[i];
		for (int k = 0; k < m; k++) s += b[k].query(j, i + 1);
		opt = max(opt, {s, j});
	}
	if (y - x == 1) return opt.first;
	return max({opt.first, solve(x, i, l, opt.second), solve(i, y, opt.second, r)});
}
 
int32_t main() {
	cin >> n >> m;
	for (int i = 1; i < n; i++) cin >> a[i];
	partial_sum(a, a + n, a);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) cin >> b[j][0][i];
	}
	for (int i = 0; i < m; i++) b[i].build();
	cout << solve(0, n, 0, n - 1) << endl;
}