Proficient.
Put your skills to the test.

Problem summary

A frog starts on lily 1 and must reach lily N, jumping only right. Visiting lily i earns A[i]; jumping from i to j costs (j−i)T[i] and is permitted only when j ≤ i+D[i]. Maximize total pleasure, including both endpoint lilies.

Constraints

1 ≤ N ≤ 100000; −10000 ≤ A[i] ≤ 10000; 1 ≤ T[i] ≤ 5; 1 ≤ D[i] ≤ 100000.

Worked example

An independently prepared example for this explanation.

7
-3 1 3
-5 2 8
16 5 4
15 2 9
6 5 15
-8 3 1
27 4 2

42

Solution analysis

1. Let best[j] be the best pleasure on arrival at j. A predecessor i contributes best[i]+iT[i]−jT[i]+A[j], provided its jump range has not expired.
2. Use one maximum heap for each of the five possible types. An entry stores best[i]+iT[i] and its last reachable position i+D[i]. Before querying a type, discard expired entries at the top. Buried expired entries cannot affect the maximum and will be discarded if they later reach the top.
3. The sample route 1→3→4→7 gains −3+16+15+27=55 from lilies and pays 2·1+1·5+3·2=13 for jumps, giving 42. The heap method compares this route against every legal predecessor implicitly.

Why it works

Process positions in increasing order, so predecessor scores are final. For each type, after removing expired tops, the heap top is the largest valid predecessor intercept. Taking the maximum over all five types is exactly the DP recurrence, hence induction gives the optimum at N.

Watch out. Expire an entry only when its last reachable position is strictly less than the current position. Include A[1]. Use 64-bit scores and avoid recursive traversal.

An independently written complete program with standard headers.

#include<iostream>
#include<queue>
#include<vector>
#include<utility>
#include<algorithm>
#include<limits>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int count;
    cin>>count;
    priority_queue<pair<long long,int>>heaps[6];
    long long answer=0;
    for(int i=1;i<=count;i++){
        long long pleasure;
        int type,reach;
        cin>>pleasure>>type>>reach;
        long long best=pleasure;
        if(i>1){
            best=numeric_limits<long long>::lowest()/4;
            for(int t=1;t<=5;t++){
                // Expired entries below the top are harmless until exposed.
                while(!heaps[t].empty()&&heaps[t].top().second<i){
                    heaps[t].pop();
                }
                if(!heaps[t].empty()){
                    best=max(best,pleasure+heaps[t].top().first-1LL*i*t);
                }
            }
        }
        heaps[type].push({best+1LL*i*type,i+reach});
        answer=best;
    }
    cout<<answer<<'\n';
}