Maximum Glutton

Análisis oficial (C++) 

Explicación

Cualquier secuencia válida de platos consumidos debe tener la siguiente estructura:

• Antes del último plato, la suma de dulzura y de salinidad están ambas dentro de los límites
• El último plato termina violando una o más de las restricciones

¡Notar esta estructura hace el problema mucho más fácil! El problema original exigía preocuparse por el orden en que se consumen los platos, pero si la suma de dulzura y de salinidad está dentro de los límites, entonces podemos consumir los platos en cualquier orden.

Lo que queda es modelar un estado de DP. El estado de DP más trivial sería $\texttt{dp}[i][j][k]$, que indicaría si podemos o no comer $i$ platos con una suma de dulzura $j$ y una suma de salinidad $k$. Sin embargo, podemos eliminar la dimensión $k$, porque siempre queremos minimizar nuestra suma de salinidad.

Así, nuestro estado final de DP es $\texttt{dp}[i][j]$ igual a la salinidad mínima si comemos $i$ platos con una suma de dulzura $j$. Luego, las transiciones siguen la forma típica de una DP de mochila (knapsack), que es

si estamos considerando un ítem con dulzura $a$ y salinidad $b$.

Con esto, recorremos todos los estados de DP y hallamos el último valor de $i$ para el que hay un valor de DP $\leq Y$. Como podemos comer un último ítem, la respuesta que imprimimos es $\min(i + 1, n)$.

Implementación

Complejidad temporal: $\mathcal{O}(N^2 X)$

#include <bits/stdc++.h>
 
constexpr int INF = 1e9;
 
int main() {
	int n, x, y;
	std::cin >> n >> x >> y;
 
	// dp[i][j] = suma mínima de salinidad si comemos i platos con suma de dulzura j
	// notamos que consideramos un tamaño máximo de n - 1, ya que más que eso es inútil
	std::vector dp(n, std::vector<int>(x + 1, INF));
	dp[0][0] = 0;
 
	for (int dish = 0; dish < n; dish++) {
		int a, b;
		std::cin >> a >> b;
 
		// iteramos en orden inverso para no necesitar un nuevo arreglo de DP
		for (int i = n - 1; i >= 1; i--) {
			for (int j = x; j >= a; j--) {
				dp[i][j] = std::min(dp[i][j], dp[i - 1][j - a] + b);
			}
		}
	}
 
	for (int i = n - 1; i >= 0; i--) {
		for (int j = 0; j <= x; j++) {
			if (dp[i][j] <= y) {
				std::cout << i + 1 << '\n';
				return 0;
			}
		}
	}
}