Hints: Wishing Cards

After friend $j$ visits, Little A gains $\max(b_1, b_2, \ldots, b_j)$ happiness. If you write $M_j$ for that prefix maximum, what is the total happiness in terms of $M_1, M_2, \ldots, M_n$?

You may choose each $b_i$ with $0 \le b_i \le a_i$ and $\sum_i b_i \le k$.

Answer to Hint 1: The total happiness is

$$ M_1 + M_2 + \cdots + M_n, $$

where $M_j = \max(b_1, \ldots, b_j)$ and the sequence $(M_j)$ is nondecreasing.

Process friends in order. After handling the first $i-1$ friends, what two numbers about the past choices are enough to know how much happiness the next visit can still add?

Answer to Hint 2: Keep the current prefix maximum and the total cards used so far. A natural DP state is

$$ \mathrm{dp}[\mathrm{mx}][\mathrm{sum}], $$

the best total happiness after some prefix with running maximum $\mathrm{mx}$ and total cards $\mathrm{sum}$.

When friend $i$ delivers $v$ cards, how do $\mathrm{mx}$, $\mathrm{sum}$, and the happiness total change?

Answer to Hint 3: If the state before friend $i$ is $(\mathrm{mx}, \mathrm{sum})$ and you set $b_i = v$ with $0 \le v \le a_i$ and $\mathrm{sum} + v \le k$, then

$$ \mathrm{new\_mx} = \max(\mathrm{mx}, v), \qquad \mathrm{new\_sum} = \mathrm{sum} + v, $$

and the happiness from this visit is $\mathrm{new\_mx}$. So one transition is

$$ \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). $$

If you loop over every $\mathrm{mx}$, $\mathrm{sum}$, and every $v \in [0, a_i]$, what is the worst-case time per test case?

Answer to Hint 4: There are $O(k^2)$ states and up to $O(k)$ values of $v$ per state, so one friend costs $O(k^3)$ and the whole test case costs $O(n k^3)$. That matches a direct implementation that tries every $v$ explicitly.

Split on whether $v$ is at most the old maximum or strictly larger. When $v \le \mathrm{mx}$, what are $\mathrm{new\_mx}$ and the happiness added on this visit?

Answer to Hint 5: If $v \le \mathrm{mx}$, then $\mathrm{new\_mx} = \mathrm{mx}$ and this visit adds exactly $\mathrm{mx}$ happiness, no matter which allowed $v$ you pick.

So from a fixed $(\mathrm{mx}, \mathrm{sum})$, every choice

$$ v \in \bigl[0,\; \min(a_i,\, \mathrm{mx},\, k - \mathrm{sum})\bigr] $$

lands in the same row $\mathrm{mx}$ and only increases $\mathrm{new\_sum}$. For a fixed $\mathrm{mx}$, if

$$ \mathrm{new\_sum} = t \quad \text{and} \quad t \in [\mathrm{sum},\; \mathrm{sum} + w], $$

with $w = \min(a_i, \mathrm{mx}, k - \mathrm{sum})$, what is the best candidate value for $\mathrm{ndp}[\mathrm{mx}][t]$ in terms of older $\mathrm{dp}[\mathrm{mx}][\cdot]$?

Answer to Hint 6: Every such move adds the same increment $\mathrm{mx}$, so

$$ \mathrm{ndp}[\mathrm{mx}][t] \ge \mathrm{mx} + \max_{\mathrm{sum} \in [t-w,\, t]} \mathrm{dp}[\mathrm{mx}][\mathrm{sum}] $$

for $w = \min(a_i, \mathrm{mx}, t)$ after clipping to $[0, k]$.

For fixed $\mathrm{mx}$, each $t$ asks for the maximum $\mathrm{dp}[\mathrm{mx}][\mathrm{sum}]$ over $\mathrm{sum}$ in a sliding window whose width is at most $k+1$. How fast can you fill one entire row $\mathrm{ndp}[\mathrm{mx}][0..k]$ this way?

Answer to Hint 7: A deque (or monotone queue) for sliding-window maximum does one row in $O(k)$ time, so all no-raise updates for friend $i$ cost $O(k^2)$.

Now suppose $v > \mathrm{mx}$, so $\mathrm{new\_mx} = v$ and this visit adds $v$. Writing $\mathrm{new\_sum} = \mathrm{sum} + v$, which older states $(\mathrm{mx}, \mathrm{sum})$ can lead to the same pair $(v, \mathrm{new\_sum})$?

Answer to Hint 8: You need $\mathrm{mx} < v$ and $\mathrm{sum} = \mathrm{new\_sum} - v$. For fixed $(v, \mathrm{new\_sum})$, the raise transition is

$$ \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). $$

If you precompute, for each $\mathrm{sum}$, the prefix maximum of $\mathrm{dp}[\cdot][\mathrm{sum}]$ over the first coordinate, how many $(v, \mathrm{new\_sum})$ pairs do you touch per friend?

Answer to Hint 9: For each $\mathrm{sum}$, build $\mathrm{best}[\mathrm{mx}] = \max_{m \le \mathrm{mx}} \mathrm{dp}[m][\mathrm{sum}]$ in $O(k)$. Then each raise is one table lookup: $O(1)$ per $(v, \mathrm{new\_sum})$ with $v \le \min(a_i, k - \mathrm{sum})$, for $O(k^2)$ raises per friend.

Together with Hint 7, one friend is $O(k^2)$ and a test case is $O(n k^2)$.

Initialize $\mathrm{dp}[0][0] = 0$ and all other entries to $-\infty$. After all $n$ friends, take the maximum $\mathrm{dp}[\mathrm{mx}][\mathrm{sum}]$ over $\mathrm{mx}, \mathrm{sum} \le k$.