Overview

This problem asks us to determine whether we can reach Point \(N\) (the summit) starting from Point \(1\) (the base) by moving repeatedly without letting our stamina drop below \(0\), and if so, to find the maximum possible stamina upon arrival.

Analysis

1. Optimizing the Timing of Eating Rations

Although the problem statement says that rations can be kept and eaten later, it is always optimal to eat all rations immediately upon obtaining them.

The reasons are as follows: - There is no upper limit on stamina. - Even if we save rations for later, the total amount of recovered stamina remains the same. - In fact, by eating them immediately to increase our stamina, we minimize the risk of retiring due to stamina dropping below \(0\) at intermediate points.

Therefore, the optimal strategy is to “eat all rations at a point immediately after arriving there and passing the retirement check.”

2. Applying Dynamic Programming (DP)

Takahashi can only move from Point \(i\) to \(i+1\) or \(i+2\). This is a classic “stepping stone” type of problem, which can be solved using Dynamic Programming (DP).

We define the DP state as follows: - dp[i] : The maximum stamina after reaching Point \(i\) and eating all rations at that point (\(-1\) if unreachable)

Initial State

If the stamina after subtracting the consumption at Point \(1\) is \(0\) or greater, we can eat the ration \(R_1\) there. - When \(K - H_1 \geq 0\): dp[1] = K - H[1] + R[1] - When \(K - H_1 < 0\): dp[1] = -1 (retired at the start)

Transitions

When moving from Point \(i\), if dp[i] != -1, we transition to the next point \(next \in \{i+1, i+2\}\) as follows: 1. The stamina immediately after moving to Point \(next\) will be dp[i] - H[next]. 2. If this is \(0\) or greater, we can reach it without retiring. 3. If reached, we eat the ration \(R_{next}\) at Point \(next\), updating the stamina to dp[i] - H[next] + R[next]. 4. Update dp[next] with the maximum of this value. $\(\text{dp}[next] = \max(\text{dp}[next], \text{dp}[i] - H[next] + R[next])\)$

Algorithm

1. Store the stamina consumption \(H\) of each point and the recovery amount \(R\) of rations in arrays (set to \(0\) for points without rations).
2. Create a DP table dp of size \(N+1\), initialized to \(-1\).
3. Initialize the state for Point \(1\).
4. Loop \(i\) from \(1\) to \(N-1\) in order, and perform transitions from dp[i] to dp[i+1] and dp[i+2].
5. The final answer will be dp[N] (if unreachable, -1 is naturally output).

Complexity

• Time Complexity: \(O(N + M)\)

  • Reading the input takes \(O(N + M)\) time.
  • The DP transitions take \(O(N)\) in total because we explore a constant number of transitions (at most 2) from each point \(i\).
  • Therefore, the overall time complexity is \(O(N + M)\), which is fast enough to run well within the time limit under the constraint \(N \le 10^6\).

• Space Complexity: \(O(N)\)

  • The sizes of the arrays H and R to manage point information and the DP table dp are all \(N + 1\).
  • Therefore, the space complexity is \(O(N)\), which easily fits within the memory limit.

Implementation Details

• Preventing Overflow: The initial stamina \(K\) and recovery amounts \(R_j\) can be up to \(10^9\). If accumulated, the maximum stamina value can exceed the upper limit of a 32-bit signed integer (int type). Therefore, all variables and arrays managing stamina must use a 64-bit integer type (e.g., long long in C++).

• Fast I/O: Since \(N\) and \(M\) can be large, we use cin.tie(NULL); ios_base::sync_with_stdio(false); in C++ to speed up input and output.

  Source Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    // 高速入出力
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M;
    long long K;
    if (!(cin >> N >> M >> K)) return 0;

    vector<long long> H(N + 1);
    for (int i = 1; i <= N; ++i) {
        cin >> H[i];
    }

    vector<long long> R(N + 1, 0);
    for (int j = 0; j < M; ++j) {
        int P;
        long long val;
        cin >> P >> val;
        R[P] = val;
    }

    // dp[i] は地点 i に到達し、補給食を食べた後のスタミナの最大値
    // 到達不可能な場合は -1
    vector<long long> dp(N + 1, -1);

    // スタート地点での処理
    if (K - H[1] >= 0) {
        dp[1] = K - H[1] + R[1];
    }

    for (int i = 1; i < N; ++i) {
        if (dp[i] == -1) continue;

        // 地点 i + 1 への移動
        if (i + 1 <= N) {
            if (dp[i] - H[i + 1] >= 0) {
                dp[i + 1] = max(dp[i + 1], dp[i] - H[i + 1] + R[i + 1]);
            }
        }

        // 地点 i + 2 への移動
        if (i + 2 <= N) {
            if (dp[i] - H[i + 2] >= 0) {
                dp[i + 2] = max(dp[i + 2], dp[i] - H[i + 2] + R[i + 2]);
            }
        }
    }

    cout << dp[N] << "\n";

    return 0;
}

---

This editorial was generated by gemini-3.5-flash-high.