Total Score of Dungeon Runs
medium · 30.5% accepted · 108 likes · top 8%
array · binary search · prefix sum
Description
You are given a positive integer hp and two positive 1-indexed integer arrays damage and requirement.
There is a dungeon with n trap rooms numbered from 1 to n. Entering room i reduces your health points by damage[i]. After that reduction, if your remaining health points are at least requirement[i], you earn 1 point for that room.
Let score(j) be the number of points you get if you start with hp health points and enter the rooms j, j + 1, ..., n in this order.
Return the integer score(1) + score(2) + ... + score(n), the sum of scores over all starting rooms.
Note: You cannot skip rooms. You can finish your journey even if your health points become non-positive.
Solution