Overview

This problem asks you to find the minimum number \(x\) of power-up potions to use, starting with initial combat power \(S\), in order to defeat the monster (with strength \(E_i\)) on each floor while aiming for the top floor. Under the rule that defeating a monster adds its strength to your combat power, we need to find the minimum \(x\) required to defeat all monsters.

Analysis

Let’s consider Takahashi’s combat power when he reaches floor \(i\). If he uses \(x\) potions, his initial combat power is \(S + x\).

• Combat power at floor 1: \(P_1 = S + x\)
• Combat power at floor 2: \(P_2 = (S + x) + E_1\) (after defeating the monster on floor 1)
• Combat power at floor 3: \(P_3 = (S + x) + E_1 + E_2\)
• Combat power at floor \(i\): \(P_i = (S + x) + \sum_{j=1}^{i-1} E_j\)

The condition to defeat the monster on floor \(i\) and advance to the next floor is \(P_i \geq E_i\). Substituting the expression for \(P_i\) above and rearranging for \(x\):

\((S + x) + \sum_{j=1}^{i-1} E_j \geq E_i\) \(x \geq E_i - S - \sum_{j=1}^{i-1} E_j\)

This expression shows that “to clear floor \(i\), at least \(E_i - S - \sum_{j=1}^{i-1} E_j\) potions are needed.”

To clear all floors (\(i = 1, 2, \ldots, N-1\)), we just need to prepare the maximum of the “required \(x\)” computed for each floor. However, if the original combat power is already sufficient (i.e., the computed result is 0 or less), there is no need to use potions, so the lower bound of \(x\) is 0.

Algorithm

1. Initialize the maximum required potions max_x to 0.
2. Initialize the cumulative sum of defeated monsters’ strengths prefix_sum_E to 0.
3. For each floor’s monster \(E_i\) from \(i = 1\) to \(N-1\), repeat the following:
   • Compute the value of \(x\) needed to clear that floor: needed. needed = E[i] - S - prefix_sum_E
   • If needed is greater than the current max_x, update max_x.
   • Add the current monster’s strength \(E_i\) to prefix_sum_E.
4. If the final max_x is at most \(K\), output max_x; otherwise, output -1.

Complexity

• Time complexity: \(O(N)\) For \(N\) floors, each monster is processed in a single loop, so the computation finishes in linear time.
• Space complexity: \(O(N)\) \(O(N)\) memory is used to store the input list of monster strengths.

Implementation Notes

• Handling large numbers: The cumulative sum of \(K\) and \(E_i\) can become very large values (up to around \(10^{18}\)), but since Python has no limit on integer size, we can compute directly without worrying about overflow.

• Fast input: Since \(N = 2 \times 10^5\) and the input size is large, reading all input at once using sys.stdin.read().split() is faster than repeatedly calling input(), reducing execution time.

  Source Code

import sys

def solve():
    # 入力を一括で読み込み、スペースや改行で分割します。
    # N=2*10^5 程度の入力サイズであれば、sys.stdin.read().split() が高速です。
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # ダンジョンの階層数 N、初期戦闘力 S、強化薬の最大使用個数 K を取得
    N = int(input_data[0])
    S = int(input_data[1])
    K = int(input_data[2])
    
    # 各階層のモンスターの強さ E_1, ..., E_{N-1} をリストに格納
    # E の要素数は N-1 個です。
    E = list(map(int, input_data[3:]))
    
    # 高橋君が階層 N に到達するために必要な追加の戦闘力（強化薬の使用個数）の最大値を保持します。
    # 初期値は 0（強化薬を使わなくても進める状態）とします。
    max_x = 0
    # これまでに倒したモンスターの強さの合計（戦闘力の上昇分）を保持します。
    prefix_sum_E = 0
    
    # 階層 1 から N-1 までの各階層についてシミュレーションします。
    # 階層 i に到達した時点での戦闘力 P_i は、
    # P_i = (初期戦闘力 S + 強化薬の使用個数 x) + (階層 1 から i-1 までのモンスターの強さの合計)
    # となります。
    # 階層 i+1 に進むための条件は P_i >= E_i です。
    # これを変形すると、 x >= E_i - S - (階層 1 から i-1 までのモンスターの強さの合計)
    # となります。
    
    for i in range(N - 1):
        # 現在の階層のモンスターの強さ E[i] に対して必要な x を計算します。
        # needed = E_i - S - prefix_sum_E
        needed = E[i] - S - prefix_sum_E
        
        # 全ての階層を突破するために、x は各階層で求められる needed の最大値以上である必要があります。
        if needed > max_x:
            max_x = needed
        
        # モンスターを倒すとその強さが戦闘力に加算されます。
        prefix_sum_E += E[i]
        
    # 求まった最小の x が、与えられた強化薬の最大個数 K 以内であるか判定します。
    if max_x <= K:
        print(max_x)
    else:
        # K 個以内で到達できない場合は -1 を出力します。
        print(-1)

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-thinking.