708. The Most Machines You Can Afford
Machine i has a startup cost c[i] and a running cost r[i]. Running a CONSECUTIVE block
of machines costs
(the largest startup cost in the block) + (block length) * (total running cost of the block)
Print the largest number of consecutive machines whose cost stays within the budget, or 0 if
even one machine is too expensive.
``` c = 3 6 1 3 4 r = 2 1 3 4 5 budget = 25 -> 3
c = 11 12 19 r = 10 8 7 budget = 19 -> 0 ```
## The cost is not a sum
Three quantities move with the window: its MAXIMUM startup cost, its total running cost, and its LENGTH. The length multiplies the running total, so the cost grows faster than linearly as the window widens.
That is enough for a window to work, because all three rise when the window grows and fall when it shrinks, so the cost as a whole is monotone in the window. It is not enough for a plain running sum, because the maximum has to survive the left edge moving.
## The deque again
Keep a deque of indices with decreasing startup costs, so its front is the window maximum. Keep the running total as an ordinary variable.
for hi in 0 .. n-1:
while deque and c[deque.back] <= c[hi]: pop back
push hi; total += r[hi]
while lo <= hi and c[deque.front] + (hi - lo + 1) * total > budget:
total -= r[lo]
if deque.front == lo: pop front
lo += 1
best = max(best, hi - lo + 1)
## The front is popped by index, not by value
When the left edge advances past the index at the front, that index leaves the window and only then is it removed. Popping the front whenever its VALUE is no longer the maximum is wrong, and it is the usual way this goes astray.
## Why the answer can be 0
A single machine whose own cost already exceeds the budget shrinks the window to empty. The
lo <= hi guard stops the left edge overtaking the right, and the recorded length is 0.
5 with running cost 1 and budget 5 costs 5 + 1 * 1 = 6, so the answer is 0 while a
budget of 6 gives 1. That pair is the sharpest test of the formula.
## Overflow
length * running total reaches 2 * 10^5 times 2 * 10^9, which is 4 * 10^14. The
product needs 64 bits even though both factors look small.
## Cost
Time O(n). Space O(n).
Constraints - `1 ≤ n ≤ 200000` - `1 ≤ each cost ≤ 10^6` - `1 ≤ budget ≤ 10^15`
Input
The first line contains two integers n and the budget.
The second line contains n startup costs.
The third line contains n running costs.
Output
Print one integer, the largest affordable number of consecutive machines.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.