Tall Barn - Walkthrough

Distribute $K$ units among $N$ rooms. Each room $i$ has value $f_i(x)$ for $x$ units. get the highest total value. Direct DP: $O(NK)$ states, $O(K)$ transition = $O(NK^2)$. Too slow for large $K$. Aliens: penalize each unit by $\lambda$. Now the optimal uses some number of units. Binary search on $\lambda$ to hit exactly $K$. With penalty, each room's optimal allocation is independent. Total time: $O(N \log K)$

Time complexity: $O(n \log C)$. Space complexity: $O(n)$ per binary search iteration.