Hacker

Análisis oficial 

Intuición

En este problema, se nos pide jugar un juego en el que los jugadores se turnan para reclamar elementos no reclamados de un arreglo circular que son adyacentes a uno de sus elementos reclamados previamente (o cualquier elemento no reclamado en sus primeros turnos). Ambos jugadores intentan maximizar la suma de los valores de los elementos elegidos.

Tras jugar un rato con el juego, podemos hacer algunas observaciones importantes.

Observación 1

Como cada jugador solo puede elegir un elemento no adyacente a ningún otro elemento una vez (el primer movimiento), los elementos que reclama cada jugador deben formar un subarreglo. Además, notamos que cualquier movimiento de cualquiera de los jugadores incrementará la longitud del subarreglo que controla en uno, y ambos jugadores siempre tendrán un movimiento válido. Por lo tanto, como el primer jugador mueve primero, el subarreglo que controla será de longitud $\left \lceil{\frac{n}{2}}\right \rceil$.

Observación 2

Consideremos la siguiente estrategia: para algún movimiento del primer jugador que se extiende a la izquierda o a la derecha, hacer el movimiento opuesto.

Usando esta estrategia, el segundo jugador puede forzar al primer jugador a controlar cualquier subarreglo de longitud $\left \lceil{\frac{n}{2}}\right \rceil$ que contenga el primer movimiento del primer jugador, según el primer movimiento del segundo jugador.

Calcular la solución

Usando estas observaciones, la respuesta es igual a:

donde $S_x$ representa un conjunto de sumas de todos los subarreglos de longitud $\left \lceil{\frac{n}{2}}\right \rceil$ que contienen $x$ en el arreglo circular $\texttt{c}$.

Transformar el arreglo circular

Primero, para lidiar con el aspecto circular del arreglo, concatenémoslo consigo mismo para crear un arreglo de longitud $2n$ y llamémoslo $\texttt{a}$. Ahora, solo necesitamos calcular subarreglos en un arreglo lineal, donde $S_x = S'_x \cup S'_{x + n} (1 \leq x \leq n)$ donde $S'_x$ representa el conjunto de subarreglos que contienen $x$ en $\texttt{a}$.

Usar un conjunto ordenado

Si recorremos $x$ $(1 \leq x \leq 2n)$ en $\texttt{a}$, entonces podemos guardar el conjunto ordenado corriente $S'_x$ y usarlo para actualizar $S_{x \bmod n}$. Para $x \geq 0$, agregamos la suma sobre el subarreglo $[x, x + \left \lceil{\frac{n}{2}}\right \rceil - 1]$ a $S'x$ (se puede calcular esto usando sumas de prefijos). Además, si $x \geq \left \lceil{\frac{n}{2}}\right \rceil$, quitamos la suma sobre $[x - \left \lceil{\frac{n}{2}}\right \rceil + 1, x]$. Luego, podemos calcular el valor mínimo de $S'x$ para algún $x$ consultando el valor más pequeño del conjunto ordenado.

Implementación

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
using vi = vector<int>;
#define pb push_back
#define rsz resize
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
 
using pi = pair<int, int>;
#define f first
#define s second
#define mp make_pair
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	vi a(2 * n + 1);
	a[0] = 0;
	multiset<int> vals;
	int SZ = (n + 1) / 2;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		a[n + i] = a[i];
	}
	for (int i = 1; i <= 2 * n; i++) { a[i] += a[i - 1]; }
	int ans = 0;
	vi ret(n + 1, INT_MAX);
	for (int i = 1; i <= 2 * n; i++) {
		if (i + SZ - 1 <= 2 * n) { vals.insert(a[i + SZ - 1] - a[i - 1]); }
		if (i > SZ) { vals.erase(vals.find(a[i - 1] - a[i - 1 - SZ])); }
		int prev = ((i - 1) % n) + 1;
		ret[prev] = min(ret[prev], *vals.begin());
	}
	for (int i = 1; i <= n; i++) { ans = max(ans, ret[i]); }
	cout << ans << '\n';
}