Estelle's Supper Box

Explicación

Estelle recibe $N$ tipos de cajas de cena, cada una con un valor de calorías y un valor de satisfacción.

Para cada uno de los $Q$ días, solo está disponible un subarreglo de cajas de $[l, r]$. De estas, puede elegir a lo sumo una de cada tipo, de modo que el total de calorías no exceda $x$.

El objetivo de cada consulta es calcular la satisfacción total máxima que puede obtener bajo esta restricción de calorías.

Esto es esencialmente un problema de mochila 0/1 (0-1 knapsack) sobre subarreglos, donde cada consulta nos pide resolver la mochila en un rango distinto.

Un enfoque naive resolvería la mochila de forma independiente para cada consulta en $\mathcal{O}(N \cdot X)$, lo cual es demasiado lento para las restricciones grandes.

Así, necesitamos una forma más eficiente de manejar múltiples consultas de mochila sobre rangos.

Algoritmo

Resolvemos este problema usando divide y vencerás sobre consultas combinado con DP de mochila.

Procesamos de forma recursiva un segmento $[l, r]$:

• Partimos en $mid = \lfloor (l + r)/2 \rfloor$
• Para las consultas completamente a la izquierda o a la derecha, recurrimos
• Para las consultas que cruzan $mid$, procesamos usando DP

Para las consultas que cruzan, precomputamos dos tablas de DP:

DP izquierda: $dpL[i][x] =$ satisfacción máxima usando ítems del rango $[i, mid]$ con calorías totales $\le x$

Transición:

• No tomar el ítem $i$: $dpL[i][x] = dpL[i+1][x]$
• Tomar el ítem $i$ (si $c[i] \le x$): $dpL[i][x] = \max(dpL[i][x], dpL[i+1][x - c[i]] + s[i])$

DP derecha: $dpR[i][x] =$ satisfacción máxima usando ítems del rango $[mid+1, i]$ con calorías totales $\le x$

Transición:

• No tomar el ítem $i$: $dpR[i][x] = dpR[i-1][x]$
• Tomar el ítem $i$ (si $c[i] \le x$): $dpR[i][x] = \max(dpR[i][x], dpR[i-1][x - c[i]] + s[i])$

Para una consulta $[l, r]$ que cruza $mid$, combinamos:

Esto parte efectivamente la mochila en mitades izquierda y derecha.

Cada consulta se procesa en $\mathcal{O}(X)$ por nivel.

Implementación

Complejidad temporal: $\mathcal{O}((N \log N + Q) \cdot X)$

 
#include <bits/stdc++.h>
using namespace std;
#define int long long
 
// BeginCodeSnip{Global Variables and Structs}
const int MAXN = 1e4 + 5;
const int MAXQ = 5e4 + 5;
const int MAXX = 2e3 + 5;
 
int cost[MAXN], val[MAXN], ans[MAXQ];
int dpL[MAXN][MAXX], dpR[MAXN][MAXX];
 
int n, q;
 
struct Query {
	int l, r, x, id;
};
// EndCodeSnip
 
// BeginCodeSnip{Divide and Conquer}
void divide_and_conquer(int l, int r, vector<Query> queries) {
	if (l == r) {
		for (int i = 0; i < (int)queries.size(); i++) {
			ans[queries[i].id] = val[l] * (cost[l] <= queries[i].x);
		}
		return;
	}
 
	int mid = (l + r) / 2;
 
	for (int x = 0; x < MAXX; ++x) dpL[mid + 1][x] = 0;
	for (int i = mid; i >= l; --i) {
		for (int x = 1; x < MAXX; ++x) {
			dpL[i][x] = dpL[i + 1][x];
			if (cost[i] <= x) {
				dpL[i][x] = max(dpL[i][x], dpL[i + 1][x - cost[i]] + val[i]);
			}
		}
	}
 
	for (int x = 0; x < MAXX; ++x) dpR[mid][x] = 0;
	for (int i = mid + 1; i <= r; ++i) {
		for (int x = 1; x < MAXX; ++x) {
			dpR[i][x] = dpR[i - 1][x];
			if (cost[i] <= x) {
				dpR[i][x] = max(dpR[i][x], dpR[i - 1][x - cost[i]] + val[i]);
			}
		}
	}
 
	vector<Query> left_queries, right_queries;
 
	for (int i = 0; i < (int)queries.size(); ++i) {
		if (queries[i].l <= mid && mid < queries[i].r) {
			for (int x = 0; x <= queries[i].x; ++x) {
				ans[queries[i].id] =
				    max(ans[queries[i].id],
				        dpL[queries[i].l][x] + dpR[queries[i].r][queries[i].x - x]);
			}
		} else if (queries[i].r <= mid) {
			left_queries.push_back(queries[i]);
		} else {
			right_queries.push_back(queries[i]);
		}
	}
 
	divide_and_conquer(l, mid, left_queries);
	divide_and_conquer(mid + 1, r, right_queries);
}
// EndCodeSnip
 
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
 
	// BeginCodeSnip{Getting Input}
	cin >> n;
	for (int i = 0; i < n; ++i) { cin >> cost[i] >> val[i]; }
 
	cin >> q;
	vector<Query> queries(q);
 
	for (int i = 0; i < q; ++i) {
		cin >> queries[i].l >> queries[i].r >> queries[i].x;
		queries[i].l--;
		queries[i].r--;
		queries[i].id = i;
	}
	// EndCodeSnip
 
	divide_and_conquer(0, n - 1, queries);
 
	for (int i = 0; i < q; ++i) { cout << ans[i] << '\n'; }
 
	return 0;
}