Longest Affordable Run of Machines

Hard

A workshop has n machines standing in a row. Starting machine i takes a one-off cost of startup[i], and keeping it running costs upkeep[i]. When k machines run together, the total cost is the largest startup among them plus k times the sum of their upkeep. You want to run a block of **adjacent** machines whose total cost does not exceed budget. Return the largest possible number of machines in such a block (0 if not even one fits).

Example 1

startup=[5, 2, 8, 3], upkeep=[1, 2, 1, 1], budget=20 → 3

Machines 1 to 3 cost max(2, 8, 3) + 3 · (2 + 1 + 1) = 8 + 12 = 20, exactly the budget. All four would cost 8 + 4 · 5 = 28.

Example 2

startup=[9, 10], upkeep=[3, 3], budget=11 → 0

Even a single machine costs 9 + 1 · 3 = 12 or 10 + 3 = 13, more than the budget, so the answer is 0.

Example 3

startup=[4, 4, 4], upkeep=[1, 1, 1], budget=13 → 3

Constraints

1 ≤ n ≤ 5 · 10⁴
len(startup) == len(upkeep) == n
1 ≤ startup[i], upkeep[i] ≤ 10⁵
1 ≤ budget ≤ 10¹⁵

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Queue Array Binary Search Prefix Sum Sliding Window Monotonic Queue Heap (Priority Queue)

Similar problems

Shortest Stretch Reaching a Total Hard Moving Window Maximum Hard A Dark Gap Between Street Lamps Hard Maximum Sum With Short Hops Hard Best Pair of Close Beacons Hard

Input

startup=[5, 2, 8, 3], upkeep=[1, 2, 1, 1], budget=20

Expected

Run checks the first 3 tests in your browser. Submit checks all 110 tests on the server, hidden ones included.