A game has n levels in a row. Level j has a cost layers[j] and a requirement energy[j]. A run picks a starting level i, begins with K energy, and works through the levels from i towards the end, one after another. Playing level j:
- spend
layers[j]energy (your energy goes down by that much), then - if what you have left is at least
energy[j], you clear the level and move on; otherwise the run ends immediately.
A run also ends after the last level. Every run starts fresh with K energy.
Implement:
def max_levels(layers: list[int], energy: list[int], K: int) -> list[int]
Return a list whose i-th entry is the number of levels cleared by a run that starts at level i.
max_levels([1, 4, 1, 2, 2], [3, 0, 5, 1, 0], 7) # [2, 1, 3, 2, 1]
From level 0 you have 6 left after level 0 (need 3, fine), 2 after level 1 (need 0, fine) and 1 after level 2 (need 5, stop): 2 levels. From level 1: 3 left (fine), then 2 (need 5, stop): 1. From level 2: 6, 4, 2 against needs 5, 1, 0, all fine: 3, the end of the game.
max_levels([5, 1], [0, 0], 4) # [0, 1] 4 - 5 = -1 < 0 fails at once; from level 1, 4 - 1 = 3 >= 0
Constraints: 1 <= n <= 200,000, 0 <= layers[j], energy[j] <= 10^9, 0 <= K <= 10^15. Simulating every run separately is O(n^2) when runs are long, which is too slow.
Show hint
With prefix sums P, level j is cleared on a run from i exactly when P[j+1] + energy[j] <= K + P[i]. The right side only grows as i grows, so the first failing level never moves left: use two pointers.