Skip to Content
CTRL K

2019 - Feast

Complejidad temporal: O(Nlog⁡∑a[i])\mathcal{O}(N\log{\sum a[i]}).

Como en un problema normal de Aliens Trick, vamos a hacer búsqueda binaria sobre el máximo λ\lambda tal que el número de subarreglos usados es ≥k\geq k.

Ahora, para un λ\lambda dado, vamos a calcular el número de personas en un arreglo óptimo de comida tal que restamos λ\lambda por cada persona.

Sea dp[i][j:{0,1}]\texttt{dp}[i][j:\{0,1\}] la suma máxima de satisfacción de un arreglo de los primeros ii platos, dado que j=0/1j=0/1 indica si el plato ii se está usando. Sea cnt[i][j]\texttt{cnt}[i][j] el número de personas usadas en un arreglo óptimo de dp[i][j]\texttt{dp}[i][j].

Para las transiciones de dp\texttt{dp}, tenemos

{dp[i][0],cnt[i][0]}=max⁡{{dp[i−1][0],cnt[i−1][0]}{dp[i−1][1],cnt[i−1][1]} \{\texttt{dp}[i][0], \texttt{cnt}[i][0]\} = \max\begin{cases} \{\texttt{dp}[i - 1][0], \texttt{cnt}[i - 1][0]\}\\ \{\texttt{dp}[i - 1][1], \texttt{cnt}[i - 1][1]\} \end{cases}

y

{dp[i][1],cnt[i][1]}=max⁡{{dp[i−1][0]+a[i]−λ,cnt[i−1][0]+1}{dp[i−1][1]+a[i],cnt[i−1][1]} \{\texttt{dp}[i][1], \texttt{cnt}[i][1]\} = \max\begin{cases}\{\texttt{dp}[i - 1][0] + a[i] - \lambda, \texttt{cnt}[i - 1][0] + 1\}\\ \{\texttt{dp}[i - 1][1] + a[i], \texttt{cnt}[i - 1][1]\}\end{cases}

porque o bien empezamos un subarreglo nuevo o continuamos uno existente.

Como calcular dp\texttt{dp} toma tiempo O(N)\mathcal O(N), y hacemos búsqueda binaria en el rango [0,∑a[i]][0, \sum a[i]], la complejidad temporal es O(Nlog⁡∑a[i])\mathcal{O}(N\log{\sum a[i]}).

#include <bits/stdc++.h>
using namespace std;
 
const int N = 300000;
const long long INF = (long long)300000 * 1000000000;
const long double EPS = 1e-3;
 
int n, k, a[N + 1];
pair<long double, int> dp[N + 1][2];
 
bool check(long double lambda) {
	dp[0][0] = {0, 0}, dp[0][1] = {-INF, 0};
	for (int i = 1; i <= n; ++i) {
		dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
		dp[i][1] =
		    max(make_pair(dp[i - 1][1].first + a[i], dp[i - 1][1].second),
		        make_pair(dp[i - 1][0].first + a[i] - lambda, dp[i - 1][0].second + 1));
	}
	return max(dp[n][0], dp[n][1]).second >= k;
};
 
int main() {
	scanf("%d%d", &n, &k);
	for (int i = 1; i <= n; ++i) scanf("%d", a + i);
	long double lower = 0, upper = INF;
	while (lower + EPS < upper) {
		long double mid = (lower + upper) / 2;
		if (check(mid)) {
			lower = mid;
		} else {
			upper = mid;
		}
	}
	long double lambda = lower;
	check(lambda);
	printf("%lld\n", (long long)round(lambda * k + max(dp[n][0], dp[n][1]).first));
}
Fundamentos