Editorial : Wishing Cards
This editorial matches the DP in n_k_k_k.cpp and explains how to drop the inner loop over $v$ so the running maximum is $O(n k^2)$ per test case instead of $O(n k^3)$.
After friend $j$ visits, Little A gains
$$ M_j = \max(b_1, b_2, \ldots, b_j) $$happiness. The answer is
$$ \sum_{j=1}^{n} M_j. $$Each $b_i$ must satisfy $0 \le b_i \le a_i$ and $\sum_{i=1}^{n} b_i \le k$.
Process friends in order. After the first $i-1$ friends, two numbers determine the future:
- the current prefix maximum $\mathrm{mx}$;
- the total cards used $\mathrm{sum}$.
Define
$$ \mathrm{dp}[\mathrm{mx}][\mathrm{sum}] $$as the maximum happiness achievable on the processed prefix with running maximum $\mathrm{mx}$ and total cards $\mathrm{sum}$. Only $\mathrm{mx}, \mathrm{sum} \le k$ matter.
Start with $\mathrm{dp}[0][0] = 0$ and every other entry at $-\infty$.
Suppose friend $i$ delivers $v$ cards with $0 \le v \le a_i$ and $\mathrm{sum} + v \le k$. From $(\mathrm{mx}, \mathrm{sum})$,
$$ \mathrm{new\_mx} = \max(\mathrm{mx}, v), \qquad \mathrm{new\_sum} = \mathrm{sum} + v, $$and this visit contributes $\mathrm{new\_mx}$ happiness. So
$$ \mathrm{ndp}[\mathrm{new\_mx}][\mathrm{new\_sum}] \leftarrow \max\bigl(\mathrm{ndp}[\mathrm{new\_mx}][\mathrm{new\_sum}],\; \mathrm{new\_mx} + \mathrm{dp}[\mathrm{mx}][\mathrm{sum}]\bigr). $$After all friends, the answer is $\max_{\mathrm{mx}, \mathrm{sum}} \mathrm{dp}[\mathrm{mx}][\mathrm{sum}]$.
There are $O(k^2)$ states. Trying every $v \in [0, a_i]$ for each state costs $O(k)$ per state, so one friend is $O(k^3)$ and a test case is $O(n k^3)$. That is the structure of a direct triple loop over $\mathrm{mx}$, $\mathrm{sum}$, and $v$.
The inner loop over $v$ is redundant in two different ways.
If $v \le \mathrm{mx}$, then $\mathrm{new\_mx} = \mathrm{mx}$ and the visit always adds $\mathrm{mx}$, independent of $v$.
From $(\mathrm{mx}, \mathrm{sum})$, any
$$ v \in \bigl[0,\; \min(a_i,\, \mathrm{mx},\, k - \mathrm{sum})\bigr] $$keeps the same row $\mathrm{mx}$ and only increases the total cards. For a target $t$,
$$ \mathrm{ndp}[\mathrm{mx}][t] \ge \mathrm{mx} + \max_{\mathrm{sum} \in [t-w,\, t]} \mathrm{dp}[\mathrm{mx}][\mathrm{sum}], $$where $w = \min(a_i, \mathrm{mx}, t)$ after clipping to valid sums.
For fixed $\mathrm{mx}$, each $t$ needs the maximum $\mathrm{dp}[\mathrm{mx}][\mathrm{sum}]$ over $\mathrm{sum}$ in a sliding window of width at most $k+1$. A deque for sliding-window maximum fills one row in $O(k)$ time, so all no-raise updates for one friend cost $O(k^2)$.
If $v > \mathrm{mx}$, then $\mathrm{new\_mx} = v$ and the visit adds $v$. With $\mathrm{new\_sum} = \mathrm{sum} + v$,
$$ \mathrm{ndp}[v][\mathrm{new\_sum}] \leftarrow \max\Bigl(\mathrm{ndp}[v][\mathrm{new\_sum}],\; v + \max_{\mathrm{mx} < v} \mathrm{dp}[\mathrm{mx}][\mathrm{new\_sum} - v]\Bigr). $$For each $\mathrm{sum}$, precompute prefix maxima
$$ \mathrm{best}[\mathrm{mx}][\mathrm{sum}] = \max_{m \le \mathrm{mx}} \mathrm{dp}[m][\mathrm{sum}] $$in $O(k)$ per row, hence $O(k^2)$ per friend. Each raise is then one lookup $\mathrm{best}[v-1][\mathrm{new\_sum} - v]$.
Loop $v$ from $1$ to $\min(a_i, k)$ and $\mathrm{new\_sum}$ from $v$ to $k$. That is $O(k^2)$ raise updates per friend.
Per friend:
- Copy or clear $\mathrm{ndp}$.
- Apply all no-raise transitions with sliding-window maxima on each row $\mathrm{mx}$.
- Apply all raise transitions with the prefix table $\mathrm{best}$.
- Swap $\mathrm{dp}$ and $\mathrm{ndp}$.
Total time per test case: $O(n k^2)$. Space: $O(k^2)$.
In one test case, $k \le 360$, so $k^2$ is at most about $1.3 \times 10^5$. The statement also bounds the sum of $k$ over all test cases by $1800$, which keeps the aggregate work of $k$-sized DP layers modest across the input file.
Input: $n = 5$, $k = 8$, $a = [2, 0, 5, 4, 3]$.
One optimal allocation is $b = [2, 0, 5, 0, 0]$. The prefix maxima are
$$ 2,\; 2,\; 5,\; 5,\; 5, $$so the happiness is $2 + 2 + 5 + 5 + 5 = 19$.
Friend $2$ must take $0$ cards. Friend $4$ can still contribute $5$ on their visit even with $b_4 = 0$, because the running maximum is already $5$.
- Use a large negative sentinel instead of true $-\infty$ when adding increments.
- Friends with $a_i = 0$ only allow $v = 0$; the no-raise path still applies when $\mathrm{mx} > 0$.
- The answer can be $0$ when every $a_i = 0$.
The optimized transitions are the same DP as in n_k_k_k.cpp; only the aggregation over $v$ changes.