概要

各階のモンスターに勝つために「最初の戦闘力 \(S\) を何回だけ増やせばよいか」を求め、最小の強化薬使用数を出力します（不可能なら -1）。

考察

高橋君が強化薬を \(x\) 個使ったとすると、初期戦闘力は \(S+x\) になります。
その後はモンスターを倒すたびに戦闘力が増えるので、途中の戦闘力は「初期値＋これまで倒したモンスター強さの合計」で決まります。

• 階層 \(i\) のモンスター（強さ \(E_i\)）と戦う直前の戦闘力は
  $\( P_i = (S+x) + \sum_{j=1}^{i-1} E_j \)$
• 勝つための条件は \(P_i \ge E_i\) なので
  $\( (S+x) + \sum_{j=1}^{i-1} E_j \ge E_i \)\( これを \)x\( について解くと \)\( x \ge E_i - \left(S + \sum_{j=1}^{i-1} E_j\right) \)$

つまり、各階で必要になる \(x\) の下限（不足分）を計算し、その最大値を取れば「全階を通して必ず勝てる最小の \(x\)」になります。

素朴な方法が危ない理由

例えば「\(x\) を 0 から順に増やしてシミュレーション」すると、\(K\) が最大 \(10^{18}\) なので到底間に合いません。
二分探索も可能ですが、この問題は上の式から 最小 \(x\) を直接計算できる ため、1回の走査で解けます。

具体例

\(S=3,\ E=[4,2,10]\) とします。

• 1体目直前：\(S+x=3+x\)、必要 \(3+x \ge 4 \Rightarrow x \ge 1\)
• 2体目直前：\(3+x+4=7+x\)、必要 \(7+x \ge 2 \Rightarrow x \ge -5\)（不足なし）
• 3体目直前：\(3+x+4+2=9+x\)、必要 \(9+x \ge 10 \Rightarrow x \ge 1\)

最大は \(1\) なので、強化薬は最小 \(1\) 個でよいと分かります。

アルゴリズム

1. \(pref = \sum_{j=1}^{i-1} E_j\)（これまで倒したモンスター強さの累積和）を管理する。
2. 各モンスター \(E_i\) について、不足分
   $\( need = E_i - (S + pref) \)$ を計算する。
3. 全ての \(need\) の最大値を \(req\) とする（最小必要強化薬数）。
4. \(req<0\) なら 0 に丸める（最初から十分強い場合）。
5. \(req \le K\) なら \(req\)、そうでなければ -1 を出力。

計算量

• 時間計算量: \(O(N)\)（配列を1回なめるだけ）
• 空間計算量: \(O(1)\)（累積和と最大値のみ、入力配列を除く）

実装のポイント

• \(pref\)（累積和）は最大で約 \((N-1)\times 10^9 \le 2\times 10^{14}\) になるため、64bit整数相当が必要です（Pythonなら自動でOK）。

• 必要数 \(req\) は「不足分の最大値」なので、各階で req = max(req, need) と更新します。

• 最後に \(req\) が負なら 0 にするのを忘れないようにします。

  ソースコード

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()

---

この解説は gpt-5.2-high によって生成されました。