Overview

Determine “how many times the initial combat power \(S\) needs to be increased” to defeat the monster on each floor, and output the minimum number of power-up potions used (or -1 if impossible).

Analysis

If Takahashi uses \(x\) power-up potions, his initial combat power becomes \(S+x\).
After that, his combat power increases each time he defeats a monster, so his combat power at any point is determined by “initial value + total strength of all monsters defeated so far.”

• The combat power just before fighting the monster on floor \(i\) (with strength \(E_i\)) is
  $\( P_i = (S+x) + \sum_{j=1}^{i-1} E_j \)$
• The condition to win is \(P_i \ge E_i\), so
  $\( (S+x) + \sum_{j=1}^{i-1} E_j \ge E_i \)\( Solving for \)x\(: \)\( x \ge E_i - \left(S + \sum_{j=1}^{i-1} E_j\right) \)$

In other words, we compute the lower bound on \(x\) (the deficit) required at each floor, and taking the maximum gives us “the minimum \(x\) that guarantees victory on all floors.”

Why a Naive Approach is Dangerous

For example, if you “increment \(x\) from 0 and simulate,” \(K\) can be up to \(10^{18}\), so this would be far too slow.
Binary search is also possible, but since the formula above allows us to directly compute the minimum \(x\), the problem can be solved in a single pass.

Concrete Example

Let \(S=3,\ E=[4,2,10]\).

• Before the 1st monster: \(S+x=3+x\), need \(3+x \ge 4 \Rightarrow x \ge 1\)
• Before the 2nd monster: \(3+x+4=7+x\), need \(7+x \ge 2 \Rightarrow x \ge -5\) (no deficit)
• Before the 3rd monster: \(3+x+4+2=9+x\), need \(9+x \ge 10 \Rightarrow x \ge 1\)

The maximum is \(1\), so we can see that a minimum of \(1\) power-up potion is sufficient.

Algorithm

1. Maintain \(pref = \sum_{j=1}^{i-1} E_j\) (the cumulative sum of strengths of monsters defeated so far).
2. For each monster \(E_i\), compute the deficit
   $\( need = E_i - (S + pref) \)$
3. Let \(req\) be the maximum of all \(need\) values (the minimum number of required power-up potions).
4. If \(req < 0\), clamp it to 0 (the case where you are already strong enough from the start).
5. If \(req \le K\), output \(req\); otherwise, output -1.

Complexity

• Time complexity: \(O(N)\) (just a single pass through the array)
• Space complexity: \(O(1)\) (only the cumulative sum and maximum value, excluding the input array)

Implementation Notes

• \(pref\) (cumulative sum) can be as large as approximately \((N-1)\times 10^9 \le 2\times 10^{14}\), so 64-bit integers are required (in Python this is handled automatically).

• Since the required number \(req\) is “the maximum of the deficits,” update it at each floor with req = max(req, need).

• Don’t forget to clamp \(req\) to 0 if it is negative at the end.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    N, S, K = data[0], data[1], data[2]
    E = data[3:]

    pref = 0
    req = 0
    for e in E:
        need = e - (S + pref)
        if need > req:
            req = need
        pref += e

    if req < 0:
        req = 0

    print(req if req <= K else -1)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.