Candies

Análisis oficial 

La solución oficial corre en tiempo $\mathcal{O}(BN^2 \log N)$, pero podemos usar bitsets para resolver este problema en tiempo $\mathcal{O}(BN^3 / 64)$.

En primer lugar, en lugar de cambiar la cantidad de caramelos de un paquete, podemos decir que Kristian primero descarta un paquete y luego agrega uno nuevo.

Observación 1

Después de descartar un paquete, si Kristian puede cumplir $K$ pedidos distintos, puede agregar un paquete de modo que pueda cumplir $2K$ pedidos distintos.

¿Por qué es esto cierto?

Pensemos en lo que ocurre cuando usamos un bitset para hacer DP de mochila. Imaginemos que el bitset actual que guarda qué pedidos puede cumplir Kristian es B y estamos en un paquete con a[i] caramelos.

Para la transición, simplemente hacemos B |= B << a[i].

Así, si el a[i] agregado es suficientemente grande, Kristian puede duplicar la cantidad de pedidos que puede cumplir.

Esto significa que el paquete descartado debe ser el que produce la mayor cantidad de pedidos que Kristian puede cumplir cuando se descarta.

Podemos hacer DP de mochila $N$ veces (considerando descartar cada paquete) para hallar este paquete en tiempo $\mathcal{O}(BN^3 / 64)$.

Observación 2

Si hay 2 subconjuntos de caramelos $A$ y $B$, el paquete nuevo no puede tener $\sum_{i \in A} i - \sum_{i \in B} i$ caramelos, ya que la cantidad de paquetes que Kristian puede cumplir no se duplicará en ese caso. Nótese que $B$ puede ser el conjunto vacío.

La cantidad de caramelos del paquete nuevo debe ser por lo tanto el menor entero positivo que no se puede expresar como $\sum_{i \in A} i - \sum_{i \in B} i$ para dos subconjuntos de caramelos $A$ y $B$.

Para hallar este número, podemos hacer de nuevo DP de mochila, pero esta vez usando tanto a[i] como -a[i] en lugar de solo a[i].

Esta DP de mochila también corre en $\mathcal{O}(BN^3 / 64)$, que es suficientemente rápido para 100 puntos.

Implementación

#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
using namespace std;
 
int a[100];
 
int main() {
	iostream::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) cin >> a[i];
	sort(a, a + n, greater<int>());
 
	pair<int, int> best = {0, -1};
	for (int i = 0; i < n; i++) {
		bitset<700000> dp;
		dp[0] = 1;
		for (int j = 0; j < n; j++) {
			if (j == i) continue;
			dp |= dp << a[j];
		}
		best = max(best, {dp.count(), i});
	}
 
	bitset<1400000> dp;
	dp[700000] = 1;
	for (int i = 0; i < n; i++) {
		if (i == best.second) continue;
		dp |= (dp << a[i]) | (dp >> a[i]);
	}
 
	cout << a[best.second] << ' ';
	for (int i = 1; i < 70000; i++)
		if (!dp[700000 + i]) return cout << i, 0;
	return 0;
}