概要

スタート（地点 \(1\)）からゴール（地点 \(N\)）まで、\(+1\) または \(+2\) の移動でリタイアせずに到達できるかを判定し、到達可能なら最終的なスタミナの最大値を求める問題です。各地点で消耗・リタイア判定・補給食入手・補給食使用がこの順で行われます。

考察

この問題の最大のポイントは「補給食はいつ食べてもよく、個数制限なく持ち運べて、スタミナに上限がない」という点です。

ここから次のことが言えます。

• スタミナは大きければ大きいほど、その後のリタイア判定で有利になります（上限がないのでデメリットはありません）。
• したがって、入手した補給食はその場で全部食べてしまうのが常に最適です。後で食べる意味（温存する利点）は一切ありません。

ただし注意点があります。各地点での処理順は

\[ \text{消耗} \to \text{リタイア判定} \to \text{補給食の入手} \to \text{補給食の使用} \]

なので、ある地点で入手した補給食は、その地点のリタイア判定には使えません（判定が先に行われるため）。使えるのは次の地点以降の判定です。

つまり「その場で全部食べる」という戦略をとると、ある地点 \(j\) に到着したときのリタイア判定で使えるスタミナは、

\[ （\text{直前の地点を出発したときのスタミナ}） - H_j \]

であり、この値が \(0\) 以上ならリタイアせず、その後に地点 \(j\) の補給食 \(R_j\) を入手して食べる、という形に整理できます。

素朴に「どの補給食をどのタイミングで食べるか」を全探索すると指数的になりますが、上記の観察により「全部その場で食べる」と決め打ちできるため、考えるべきは経路の選び方（\(+1\) か \(+2\) か）だけになります。これは単純な動的計画法（DP）で解けます。

アルゴリズム

\(\mathrm{dp}[j]\) を「地点 \(j\) に到達し、リタイア判定を通過し、地点 \(j\) の補給食まで含めて手持ちをすべて食べ終えた時点でのスタミナ」と定義します。到達不可能な場合は \(-\infty\) とします。

初期状態（地点 \(1\)）

初期スタミナ \(K\) から \(H_1\) を引いたものが判定値です。 - \(K - H_1 \geq 0\) なら \(\mathrm{dp}[1] = K - H_1 + R_1\) - そうでなければ \(\mathrm{dp}[1] = -\infty\)（スタートで失敗）

ここで補給食がない地点は \(R = 0\) として扱います。

遷移（\(j \geq 2\)）

地点 \(j\) へは地点 \(j-1\) または地点 \(j-2\) から来られるので、出発時のスタミナの最大値は

\[ \mathrm{best} = \max(\mathrm{dp}[j-1],\ \mathrm{dp}[j-2]) \]

です（到達できない側は無視）。リタイア判定を通過できるのは \(\mathrm{best} - H_j \geq 0\) すなわち \(\mathrm{best} \geq H_j\) のときで、そのとき

\[ \mathrm{dp}[j] = \mathrm{best} - H_j + R_j \]

通過できなければ \(\mathrm{dp}[j] = -\infty\) とします。

答え

\(\mathrm{dp}[N]\) が \(-\infty\) でなければその値を出力し、\(-\infty\) なら \(-1\) を出力します。

計算量

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

各地点の DP 遷移は定数時間で、地点を \(1\) から \(N\) まで一度ずつ見るだけです。

実装のポイント

• 「到達不可能」を表す番兵として非常に小さい値（例では \(-4\times10^{18}\)）を使い、判定では NEG/2 などと比較することで「オーバーフローや偶然の一致による誤判定」を防いでいます。best >= H[j] の判定の前に必ず best > NEG/2（到達可能か）を確認するのが重要です。

• スタミナの値は \(K, H_i, R_j\) がそれぞれ最大 \(10^9\) で、\(N\) も大きいため累積すると int の範囲を超えます。64bit 整数（long long）を必ず使用してください。

• \(N\) が最大 \(10^6\) あり、入力サイズが大きいため、fread による一括読み込みなど高速な入力処理が望ましいです（Python など遅い言語では特に注意）。

• 補給食は地点ごとに高々 \(1\) 個なので、R[P_j] = R_j のように配列に直接格納すれば、補給食のない地点は自然に \(0\) として扱えます。

  ソースコード

#include <bits/stdc++.h>
using namespace std;

int main(){
    int N, M; long long K;
    // fast read
    static char buf[1<<25];
    int len = fread(buf,1,sizeof(buf),stdin);
    int pos=0;
    auto readInt=[&]() -> long long {
        while(pos<len && (buf[pos]<'0'||buf[pos]>'9') && buf[pos]!='-') pos++;
        bool neg=false;
        if(pos<len && buf[pos]=='-'){neg=true;pos++;}
        long long x=0;
        while(pos<len && buf[pos]>='0'&&buf[pos]<='9'){x=x*10+(buf[pos]-'0');pos++;}
        return neg?-x:x;
    };
    N=(int)readInt(); M=(int)readInt(); K=readInt();
    vector<long long> H(N+1), R(N+1,0);
    for(int i=1;i<=N;i++) H[i]=readInt();
    for(int j=0;j<M;j++){
        long long p=readInt(), r=readInt();
        R[(int)p]=r;
    }
    
    const long long NEG = -(long long)4e18;
    vector<long long> dp(N+1, NEG);
    
    if(K - H[1] >= 0){
        dp[1] = K - H[1] + R[1];
    } else {
        dp[1] = NEG;
    }
    
    for(int j=2;j<=N;j++){
        long long best = NEG;
        if(dp[j-1] > NEG/2) best = max(best, dp[j-1]);
        if(j-2>=1 && dp[j-2] > NEG/2) best = max(best, dp[j-2]);
        if(best > NEG/2 && best >= H[j]){
            dp[j] = best - H[j] + R[j];
        } else {
            dp[j] = NEG;
        }
    }
    
    if(dp[N] > NEG/2) printf("%lld\n", dp[N]);
    else printf("-1\n");
    return 0;
}

---

この解説は claude4.8opus-high によって生成されました。