Distribute units among rooms. Each room has value for units. get the highest total value. Direct DP: states, transition = . Too slow for large . Aliens: penalize each unit by . Now the optimal uses some number of units. Binary search on to hit exactly . With penalty, each room's optimal allocation is independent. Total time:
Time complexity: . Space complexity: per binary search iteration.