Overview

This problem asks whether it is possible to reach the goal (point \(N\)) from the start (point \(1\)) by moving either \(+1\) or \(+2\) at each step without retiring, and if possible, to find the maximum final stamina. At each point, stamina depletion, retirement check, food acquisition, and food consumption occur in this exact order.

Analysis

The key point of this problem is that food can be consumed at any time, can be carried without any limit on quantity, and there is no upper limit on stamina.

From this, we can deduce the following:

• The higher the stamina, the more advantageous it is for subsequent retirement checks (since there is no upper limit, there is no disadvantage to having more).
• Therefore, it is always optimal to consume all acquired food immediately. There is absolutely no reason to save it for later.

However, there is a caveat. The order of events at each point is:

\[ \text{Depletion} \to \text{Retirement Check} \to \text{Food Acquisition} \to \text{Food Consumption} \]

Thus, food acquired at a certain point cannot be used for the retirement check at that same point (because the check happens first). It can only be used for checks at subsequent points.

In other words, if we adopt the strategy of “consuming everything immediately,” the stamina available for the retirement check upon arriving at point \(j\) is:

\[ (\text{Stamina when leaving the previous point}) - H_j \]

If this value is \(0\) or greater, the player does not retire, and then acquires and consumes the food \(R_j\) at point \(j\). We can simplify the process this way.

A naive search of “which food to eat at what timing” would result in exponential complexity. However, based on the observation above, we can fix the strategy to “consume everything immediately.” Consequently, we only need to consider how to choose the path (whether to move \(+1\) or \(+2\)). This can be solved using simple Dynamic Programming (DP).

Algorithm

Let \(\mathrm{dp}[j]\) be defined as the stamina at the moment of arriving at point \(j\), passing the retirement check, and consuming all food in hand, including the food at point \(j\). If point \(j\) is unreachable, we set \(\mathrm{dp}[j] = -\infty\).

Initial State (Point \(1\))

The check value is the initial stamina \(K\) minus \(H_1\). - If \(K - H_1 \geq 0\), then \(\mathrm{dp}[1] = K - H_1 + R_1\) - Otherwise, \(\mathrm{dp}[1] = -\infty\) (failed at the start)

Here, points without food are treated as having \(R = 0\).

Transitions (\(j \geq 2\))

Since we can reach point \(j\) from either point \(j-1\) or point \(j-2\), the maximum stamina when departing the previous point is:

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

(ignoring any unreachable states). The retirement check is passed if \(\mathrm{best} - H_j \geq 0\), which is equivalent to \(\mathrm{best} \geq H_j\). In this case:

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

If the check is not passed, we set \(\mathrm{dp}[j] = -\infty\).

Answer

If \(\mathrm{dp}[N]\) is not \(-\infty\), output its value; otherwise, output \(-1\).

Complexity

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

The DP transition at each point takes constant time, and we only need to visit each point from \(1\) to \(N\) once.

Implementation Points

• Use a very small value (e.g., \(-4\times10^{18}\) in the implementation) as a sentinel representing “unreachable”. When checking, compare with NEG/2 or similar to prevent false positives due to overflow or accidental matches. It is crucial to verify best > NEG/2 (whether it is reachable) before checking best >= H[j].

• The stamina values, \(K\), \(H_i\), and \(R_j\), can be up to \(10^9\) each, and since \(N\) can also be large, the accumulated stamina can exceed the range of a standard 32-bit int. Be sure to use 64-bit integers (long long).

• Since \(N\) can be up to \(10^6\) and the input size is large, fast I/O methods (such as bulk reading with fread) are recommended (especially in slower languages like Python).

• Since there is at most one food item at each point, you can store them directly in an array like R[P_j] = R_j. This naturally treats points without food as having \(0\).

  Source Code

#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;
}

---

This editorial was generated by claude4.8opus-high.