概要

地点 \(1\) から地点 \(N\) まで、毎回 \(+1\) または \(+2\) 進みながら、スタミナが負にならないように進めるかを判定します。
補給食は「食べるタイミング」を考える必要がなく、到達可能な各地点での最大スタミナを動的計画法で管理します。

考察

この問題で重要なのは、補給食をいつ食べるかです。

各地点での処理順は、

1. 消耗
2. リタイア判定
3. 補給食の入手
4. 補給食の使用

です。

つまり、ある地点 \(i\) に到達するときには、地点 \(i\) の補給食はまだ使えません。
そのため、地点 \(i\) に到達できる条件は、到達前のスタミナが \(H_i\) 以上であることです。

一方で、補給食を入手した後は、食べるタイミングを遅らせるメリットはありません。

理由は次の通りです。

• スタミナに上限はない
• 補給食を早く食べても損をしない
• スタミナが多いほど、以降の地点に到達しやすくなる
• 最終的には残りの補給食をすべて食べた後のスタミナを最大化する

したがって、「入手した補給食はすぐに食べる」と考えても最適解を失いません。

これにより、状態として持つべきものは非常に単純になります。

\(dp[i]\) を、

地点 \(i\) に到達し、その地点までに入手した補給食をすべて食べた後の最大スタミナ

とします。

地点 \(i\) には、地点 \(i-1\) または地点 \(i-2\) から来ることができます。
ただし、地点 \(i\) の消耗 \(H_i\) を受けた直後にスタミナが負になるとリタイアなので、遷移元のスタミナが \(H_i\) 以上である必要があります。

例えば地点 \(i-1\) から来る場合、

• 地点 \(i-1\) 処理後のスタミナが \(dp[i-1]\)
• 地点 \(i\) の消耗で \(H_i\) 減る
• 生存できれば、地点 \(i\) の補給食 \(R_i\) を得てすぐ食べる

ので、

\[ dp[i] = dp[i-1] - H_i + R_i \]

となります。ただしこれは \(dp[i-1] \geq H_i\) の場合のみ可能です。

同様に地点 \(i-2\) から来る場合も考え、より大きい方を採用します。

素朴にすべての移動経路を試すと、各地点で \(+1\) 進むか \(+2\) 進むかの選択があるため、経路数は指数的に増えてしまいます。
また、補給食をいつ食べるかまで考えるとさらに複雑になります。

しかし、補給食は「入手したらすぐ食べる」としてよいため、各地点について最大スタミナだけを管理すれば十分です。

アルゴリズム

まず、各地点にある補給食の回復量を配列 \(R\) に記録します。
補給食がない地点では \(R_i = 0\) とします。

初期地点は地点 \(1\) です。

地点 \(1\) に到達した時点でまず \(H_1\) 消耗します。
もし

\[ K < H_1 \]

なら、最初の地点でリタイアするため答えは \(-1\) です。

そうでなければ、地点 \(1\) 処理後のスタミナは

\[ K - H_1 + R_1 \]

です。

以降、地点 \(2\) から地点 \(N\) まで順に計算します。

地点 \(i\) について、以下を調べます。

• 地点 \(i-1\) から来られるか
• 地点 \(i-2\) から来られるか

地点 \(i-1\) から来る場合、\(dp[i-1] \geq H_i\) なら到達可能で、

\[ dp[i] = dp[i-1] - H_i + R_i \]

です。

地点 \(i-2\) から来る場合、\(dp[i-2] \geq H_i\) なら到達可能で、

\[ dp[i] = dp[i-2] - H_i + R_i \]

です。

このうち大きい方を \(dp[i]\) とします。
どちらからも来られない場合は、その地点は到達不可能として \(-1\) にします。

また、遷移には直前の2つの値だけが必要です。
そのため、配列全体を持たずに、

• dp_prev2: \(dp[i-2]\)
• dp_prev1: \(dp[i-1]\)

だけを持って更新できます。

最終的に \(dp[N]\) が答えです。
到達できなければ \(-1\) になります。

計算量

• 時間計算量: \(O(N + M)\)
• 空間計算量: \(O(N)\)

実装のポイント

補給食の情報は、長さ \(N\) の配列 R にまとめておくと扱いやすいです。

R = [0] * N
for _ in range(M):
    p, r = map(int, input().split())
    R[p - 1] = r

地点番号は入力では \(1\) 始まりですが、Python の配列は \(0\) 始まりなので、p - 1 に注意します。

また、到達不可能な状態を -1 で表します。
スタミナは \(0\) 以上なら生存可能なので、-1 は番兵として安全に使えます。

遷移では、地点 \(i\) に入る前のスタミナが \(H_i\) 以上である必要があります。

if dp_prev1 >= h:
    best = dp_prev1 - h + R[i]

if dp_prev2 >= h:
    cand = dp_prev2 - h + R[i]
    best = max(best, cand)

最後に、ローリング更新を行います。

dp_prev2, dp_prev1 = dp_prev1, best

これにより、DP 配列全体を持たずに計算できます。

ソースコード

import sys

def main():
    input = sys.stdin.buffer.readline

    N, M, K = map(int, input().split())
    H = list(map(int, input().split()))

    R = [0] * N
    for _ in range(M):
        p, r = map(int, input().split())
        R[p - 1] = r

    if K < H[0]:
        print(-1)
        return

    dp_prev2 = -1
    dp_prev1 = K - H[0] + R[0]

    for i in range(1, N):
        h = H[i]
        best = -1

        if dp_prev1 >= h:
            best = dp_prev1 - h + R[i]

        if dp_prev2 >= h:
            cand = dp_prev2 - h + R[i]
            if cand > best:
                best = cand

        dp_prev2, dp_prev1 = dp_prev1, best

    print(dp_prev1)

if __name__ == "__main__":
    main()

---

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