dsa · hard
Capital Deployment Run
A fund starts with w capital and may complete at most k projects. Project i demands at least capital[i] on hand before it can be taken and pays a pure profit of profits[i] on completion (demand and profit are independent). At most one project runs at a time; after each completion the payout raises the on-hand capital immediately.
Arguments
k— the maximum number of projects to completew— the starting capitalprofits— profits[i] is the payout of project icapital— capital[i] is the on-hand demand of project i
Choose projects greedily to maximise the final capital after at most k completions and return it.
Example
k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]
Round 1: affordable projects are those with demand 0 — project 1 (profit 1). Take it → capital 1. Round 2: affordable now include projects 2 and 3 (demand 1); take profit 3 → capital 4.
k = 3, w = 0, profits = [1,2,3], capital = [0,1,2] → take profit 1 (capital 1), then profit 2 (capital 3), then profit 3 (capital 6) → 6.
Constraints
1 <= k <= 10^5 0 <= w <= 10^9 1 <= profits.length <= 10^5 profits.length == capital.length 1 <= profits[i] <= 10^4 0 <= capital[i] <= 10^9 Hidden tests include near-max size for this bound; a slower-than-intended solution TLEs.
Examples
Example 1
Input: 2 0 [1,2,3] [0,1,1] Expected: 4
Example 2
Input: 3 0 [1,2,3] [0,1,2] Expected: 6
Example 3
Input: 1 2 [1,2,3] [1,1,2] Expected: 5