Total score of dungeon runs

Array Binary Search Prefix Sum

30.5% acceptance

Feb 25, 2026

107

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

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn total_score(hp: i32, damage: Vec<i32>, requirement: Vec<i32>) -> i64 {
    let n = damage.len();
    // prefix[i] = damage[0] + ... + damage[i-1] (strictly increasing since damage[i] >= 1)
    let mut prefix = vec![0i64; n + 1];
    for i in 0..n { prefix[i + 1] = prefix[i] + damage[i] as i64; }
    // For room i, starting room j (j <= i) earns a point iff:
    //   hp - (prefix[i+1] - prefix[j]) >= requirement[i]
    //   prefix[j] >= requirement[i] + prefix[i+1] - hp
    // Since prefix is sorted, use binary search to count valid j in [0..=i].
    let mut total = 0i64;
    for i in 0..n {
      let threshold = requirement[i] as i64 + prefix[i + 1] - hp as i64;
      let pos = prefix[..=i].partition_point(|&x| x < threshold);
      total += (i + 1 - pos) as i64;
    }
    total
  }
}