Sequence

Intuición

Después de jugar un rato con algunos arreglos, probablemente se observe que el orden de los cortes no importa.

¿Por qué es esto cierto?

Consideremos el caso en que $k = 2$. Sean $A$, $B$ y $C$ las sumas de los 3 arreglos. Si se parte $[A, B, C]$ en $[A], [B, C]$ y luego en $[A], [B], [C]$, entonces se obtienen $AB + AC + BC$ puntos. Si en cambio se parte el arreglo en $[A, B], [C]$ y luego $[A], [B], [C]$, se siguen obteniendo $AB + AC + BC$ puntos.

Un argumento similar vale para $k > 2$.

¡Ahora hemos simplificado mucho el problema! Sin pérdida de generalidad, supongamos que hacemos los cortes de izquierda a derecha.

Formular una DP

Primero, sea $p_i$ la suma de $a_j$ para todo $j \leq i$.

Sea $dp[i][j]$ la cantidad máxima de puntos que podemos obtener si hemos hecho $j$ cortes y el $j$-ésimo corte está entre $a_i$ y $a_{i + 1}$.

Tenemos la siguiente recurrencia:

La respuesta es $dp[n - 1][k + 1]$ (suponiendo que hacemos un corte extra al final del arreglo, lo cual no afecta la respuesta).

Calcular esto de forma naive tomaría tiempo $\mathcal{O}(n^2k)$, pero podemos hacerlo mucho mejor.

Usar CHT

Miremos de nuevo la recurrencia de la DP. ¿Se ve cómo efectivamente está hallando el máximo de varias funciones lineales en un punto?

Podemos reordenar la recurrencia para que quede

Recordemos que una función lineal se puede definir como $y = mx + c$.

En este caso, tenemos $m = -p_l$, $x = p_{n - 1} - p_i$ y $c = dp[l][j - 1]$.

Esto significa que podemos usar CHT (con un deque) para calcular la respuesta en $\mathcal{O}(nk)$: ¡una mejora significativa!

Una última optimización

Lamentablemente, si implementamos esta solución de forma directa, nos pasamos del límite de memoria.

Nótese que $dp[i][j]$ solo depende de $dp[l][j - 1]$. Esto significa que, en lugar de guardar $k$ arreglos de $dp[i]$, podemos simplemente guardar dos arreglos $dp$ y alternar entre ellos.

Esto baja la memoria usada a $\mathcal{O}(n)$, que alcanza para pasar.

Implementación

Complejidad temporal: $\mathcal{O}(nk)$

Complejidad de memoria: $\mathcal{O}(n)$

#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;
 
int n, k;
int where[201][100001];
ll pref[100001]{0}, dp[2][100001], q[100001], l = 1, r = 1;
 
bool case1(int x, int y, int i) {
	return (dp[0][y] - dp[0][x] >= (pref[y] - pref[x]) * (pref[n] - pref[i]));
}
 
bool case2(int x, int y, int i) {
	return ((dp[0][y] - dp[0][x]) * (pref[i] - pref[y]) <=
	        (dp[0][i] - dp[0][y]) * (pref[y] - pref[x]));
}
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> k;
	FOR(i, 1, n + 1) {
		int x;
		cin >> x;
		pref[i] = pref[i - 1] + x;
	}
 
	fill(dp[0], dp[0] + n + 1, 0);
	FOR(i, 1, k + 1) {
		q[r++] = 0;
		FOR(j, 1, n + 1) {
			while (r - l > 1 && case1(q[l], q[l + 1], j)) l++;
 
			ll x = q[l];
			dp[1][j] = dp[0][x] + (pref[j] - pref[x]) * (pref[n] - pref[j]);
			where[i][j] = x;
 
			while (r - l > 1 && case2(q[r - 2], q[r - 1], j)) r--;
			q[r++] = j;
		}
		l = r = 1;
		FOR(j, 1, n + 1) dp[0][j] = dp[1][j];
	}
 
	ll mx = -1;
	int indx = -1;
	FOR(i, 1, n + 1) {
		if (dp[0][i] > mx) mx = dp[0][i], indx = i;
	}
	cout << mx << '\n';
	FOR(i, 0, k) {
		cout << indx << ' ';
		indx = where[k - i][indx];
	}
	cout << '\n';
	return 0;
}