Overview

This is a problem where Takahashi moves from point \(1\) to point \(N\) while managing his stamina. We need to determine if he can reach the goal without his stamina dropping below \(0\) midway, and if possible, find the maximum final stamina.

Analysis

The key to solving this problem is “when to eat the rations.” Although the problem statement says “you can eat rations later,” assuming that “you eat all rations the moment you acquire them” does not affect the maximum final stamina or whether you retire midway.

This is because even if you save rations to eat later, the total amount of stamina remains the same. Also, if you were to eat rations when you are about to retire due to insufficient stamina, it is exactly the same as “having eaten them the moment you acquired them at a past point.” Thus, we can safely assume that any rations acquired at each point are consumed immediately on the spot.

Based on this observation, we can formulate the following Dynamic Programming (DP): - DP State: T[i] = the maximum stamina after reaching point \(i\), passing the retirement check, and consuming all rations obtained at point \(i\). If point \(i\) is unreachable, set this to \(-1\).

If we were to search all possible paths and eating timings using brute force, the number of combinations would explode, leading to TLE (Time Limit Exceeded). However, by assuming “immediate consumption” as described above, we can reduce the state to a single variable—the maximum stamina at point \(i\)—allowing for fast computation.

Algorithm

We compute the DP values sequentially from point \(1\) using a push-based DP (配るDP).

1. Initial State: Point \(1\) can be reached if the initial stamina \(K\) is at least the consumption \(H_1\) at point \(1\). Therefore, if \(K \ge H_1\), we set \(T[1] = K - H_1 + R_1\) (where \(R_i\) is the recovery amount of the ration at point \(i\), or \(0\) if there is none).

2. Transitions: If point \(i\) (\(1 \le i < N\)) is reachable (\(T[i] \ne -1\)), we try the following two transitions:

   • Move to point \(i+1\): If \(T[i] \ge H_{i+1}\), we can reach it without retiring. The stamina after reaching is \(T[i] - H_{i+1} + R_{i+1}\), so we update \(T[i+1]\) with this value (taking the maximum).
   • Move to point \(i+2\): If \(T[i] \ge H_{i+2}\), we can reach it without retiring. The stamina after reaching is \(T[i] - H_{i+2} + R_{i+2}\), so we update \(T[i+2]\) with this value (taking the maximum).

3. Answer: Finally, \(T[N]\) will be the maximum stamina after reaching point \(N\) and eating all available rations. If \(T[N] = -1\), it is unreachable, so output \(-1\).

Complexity

• Time Complexity: \(O(N)\) From each point \(i\), we only transition to at most two places (\(i+1\) and \(i+2\)), which allows us to compute the entire DP in linear time.
• Space Complexity: \(O(N)\) The sizes of the arrays \(T, H,\) and \(R\) are proportional to \(N\).

Implementation Details

• Since the constraints are \(N \le 10^6\) and \(H_i, R_i \le 10^9\), the stamina during calculation can reach around \(10^{15}\), which will overflow a standard 32-bit signed integer (int). Therefore, make sure to use 64-bit integers (long long in C++) for stamina-related variables.

• When managing the \(M\) rations, since there is at most one ration per point, you can simplify the implementation by preparing an array where the recovery amount is directly stored at the point’s index, like R[p] = r.

• Since the input size is large, it is recommended to speed up std::cin (using ios::sync_with_stdio(false); cin.tie(nullptr);) for safety.

  Source Code

#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N, M;
    long long K;
    if (!(cin >> N >> M >> K)) return 0;
    
    vector<long long> H(N + 1, 0);
    vector<long long> R(N + 1, 0);
    
    for (int i = 1; i <= N; ++i) {
        cin >> H[i];
    }
    
    for (int i = 0; i < M; ++i) {
        int p;
        long long r;
        cin >> p >> r;
        R[p] = r;
    }
    
    vector<long long> T(N + 1, -1);
    if (K >= H[1]) {
        T[1] = K - H[1] + R[1];
    }
    
    for (int i = 1; i < N; ++i) {
        if (T[i] == -1) continue;
        
        if (i + 1 <= N && T[i] >= H[i + 1]) {
            long long val = T[i] - H[i + 1] + R[i + 1];
            if (val > T[i + 1]) {
                T[i + 1] = val;
            }
        }
        
        if (i + 2 <= N && T[i] >= H[i + 2]) {
            long long val = T[i] - H[i + 2] + R[i + 2];
            if (val > T[i + 2]) {
                T[i + 2] = val;
            }
        }
    }
    
    cout << T[N] << "\n";
    return 0;
}

This editorial was generated by or-glm5.2-high.