Expert.
Put your skills to the test.

Problem summary

Start at the first element of a nonzero integer array and finish at the last. A block consists of t >= 1 forward jumps of the same integer length k >= 2. On resting after the block, receive t times the value at its final position. Intermediate landing positions give no reward unless you end a block there. Maximize the total reward.

Source clarification. The extracted PDF prints k > 1 followed by a footnote marker; the condition is k >= 2, not k > 11.

Constraints

3 <= N <= 200000; 1 <= |A[i]| <= 10^9; 4 seconds; 600 MB.

Worked example

Original statement sample, using the documented local driver for grader tasks.

5
1 2 -1 3 100

200

Solution analysis

1. Let best[i] be the best reward on resting at zero-based position i. A block from j to i contributes ((i-j)/k)*A[i], where k divides i-j and k >= 2. Position 1 is unreachable, while best[0]=0. A single jump from any j <= i-2 is handled by a running prefix maximum.
2. For a positive final reward, replacing a composite jump length by one of its prime factors only increases the number of paid jumps. For a prime p <= sqrt(N), group previous j by j mod p. Its contribution is best[j] - floor(j/p)*A[i] + floor(i/p)*A[i]. Thus each previous position becomes a line with slope -floor(j/p) and intercept best[j]. Maintain an upper convex hull for each prime and residue. Slopes arrive in decreasing order, but queries A[i] need not be ordered, so binary-search the hull.
3. Why can large primes be omitted? If the prime jump length p > sqrt(N) is repeated t >= 2 times, then t < sqrt(N). A prime divisor q of t divides the total displacement and permits at least p jumps. Since q <= sqrt(N), a small-prime hull is at least as good. A block with t=1 is already covered by the prefix maximum. If A[i] is negative, extra repeated jumps only worsen its reward, so a single jump from the same start dominates.
4. In the sample, two length-2 jumps reach positions 1,3,5. Resting only at 5 earns 2*100=200; resting at 3 first earns -1+100=99. Insert best[i] only after querying, so no zero-length block is used.

Why it works

The recurrence considers every possible final block. Negative-reward blocks are dominated by one jump. Positive-reward blocks are dominated by either a single jump or a block with a prime length at most sqrt(N), as proved above. Each hull evaluates exactly those valid earlier positions with the required residue. Induction on i therefore proves the computed optimum.

Watch out. Do not allow length-1 jumps or collect rewards at intermediate positions automatically. Query before insertion. Do not assume reward queries are monotone. Position 1 in zero-based indexing cannot be reached. Use exact hull comparisons.

The judge submission uses jumps.h without main. Compile with -DLOCAL for the sample driver. Exact convex-hull cross-products use the GCC/Clang __int128 extension; the remaining implementation uses C++17.

#include<algorithm>
#include<cmath>
#include<iostream>
#include<vector>
#ifndef LOCAL
#include"jumps.h"
#endif
using namespace std;
struct PrizeLine{
    long long slope;
    long long intercept;
    long long value(long long x)const{
        return slope*x+intercept;
    }
};
struct PrizeHull{
    vector<PrizeLine>lines;
    void add(PrizeLine current){
        while(lines.size()>=2){
            PrizeLine first=lines[lines.size()-2];
            PrizeLine second=lines.back();
            // Slopes decrease. Discard a line which is never strictly best.
            __int128 left=(__int128)(second.intercept-first.intercept)*(second.slope-current.slope);
            __int128 right=(__int128)(current.intercept-second.intercept)*(first.slope-second.slope);
            if(left>right){
                break;
            }
            lines.pop_back();
        }
        lines.push_back(current);
    }
    long long query(long long x)const{
        int left=0;
        int right=(int)lines.size()-1;
        while(left<right){
            int middle=(left+right)/2;
            if(lines[middle].value(x)<=lines[middle+1].value(x)){
                left=middle+1;
            }
            else{
                right=middle;
            }
        }
        return lines[left].value(x);
    }
};
long long max_prize(vector<int>A){
    int n=(int)A.size();
    int limit=(int)sqrt(n);
    vector<int>primes;
    for(int candidate=2;candidate<=limit;++candidate){
        bool prime=true;
        for(int divisor=2;divisor*divisor<=candidate;++divisor){
            if(candidate%divisor==0){
                prime=false;
                break;
            }
        }
        if(prime){
            primes.push_back(candidate);
        }
    }
    vector<vector<PrizeHull>>hulls;
    for(int prime:primes){
        hulls.emplace_back(prime);
        for(int residue=0;residue<prime;++residue){
            hulls.back()[residue].lines.reserve((n-1-residue)/prime+1);
        }
        hulls.back()[0].add({0,0});
    }
    const long long unreachable=-4000000000000000000LL;
    vector<long long>best(n,unreachable);
    best[0]=0;
    long long prefixBest=unreachable;
    for(int position=2;position<n;++position){
        prefixBest=max(prefixBest,best[position-2]);
        best[position]=prefixBest+A[position];
        if(A[position]>0){
            for(int index=0;index<(int)primes.size();++index){
                int prime=primes[index];
                const PrizeHull&hull=hulls[index][position%prime];
                if(!hull.lines.empty()){
                    best[position]=
                        max(best[position],hull.query(A[position])+1LL*(position/prime)*A[position]);
                }
            }
        }
        for(int index=0;index<(int)primes.size();++index){
            int prime=primes[index];
            hulls[index][position%prime].add({-position/prime,best[position]});
        }
    }
    return best.back();
}
#ifdef LOCAL
int main(){
    int n;
    cin>>n;
    vector<int>values(n);
    for(int&value:values){
        cin>>value;
    }
    cout<<max_prize(values)<<'\n';
}
#endif