The height of scaffold decreases monotonically as he moves. Thus, we can compute the maximum number of moves starting from each scaffold in ascending order of its height with a Dynamic Programming (DP).

Let \(dp_i\) be the maximum number of moves starting from scaffold \(i\). The answer to the original problem is the maximum value of \(dp\). Also, define a sequence \(p\) so that \(p_{H_i}=i\).

Then \(dp\) can be found as follows.

• Let \(dp=(0,0,\ldots,0)\).
• For \(i=1,2,\ldots,N\), do the following:
  • For each \(j\) with \(|p_i-j| \leq R, H_j \leq i-D\), let \(dp_{p_i} \leftarrow \max(dp_{p_i},dp_j+1)\).

If you enumerate \(j\) for each \(i\), the time complexity will be \(\mathrm{O}(ND)\) or \(\mathrm{O}(NR)\), which hardly fits in the execution time limit.

Let us reorganize the enumeration of \(j\) for each \(i\), namely the \(H_j \leq i-D\) part. Then the procedure above can be rephrased as follows:

• Initialize with \(dp=(0,0,\ldots,0), S=(-\infty,-\infty,\ldots,-\infty)\).
• For \(i=1,2,\ldots,N\) in order, do the following:
  • If \(D+1 \leq i\), set \(S_{p_{i-D}} \leftarrow dp_{p_{i-D}}\).
  • Set \(dp_{p_i} \leftarrow \max(dp_{p_i},M+1)\), where \(l=\max(1,p_i-R),r=\min(N,p_i+R),M=\max(S_{l},S_{l+1},\ldots,S_{r})\).

In this procedure, the bottleneck is finding the maximum value of a segment of \(S\), which can be optimized by managing \(S\) in a segment-max segment tree. Thus, the problem can be solved in a total of \(\mathrm{O}(N \log N)\) time.

Sample code (C++)

#include <bits/stdc++.h>
#include <atcoder/segtree>
using namespace std;
int op(int a, int b) {
    return max(a, b);
}
int e() {
    return -1e9;
}
int main() {
    int n, d, r;
    cin >> n >> d >> r;
    vector<int> h(n);
    for (auto &e : h)
        cin >> e;
    for (auto &e : h)
        e--;
    vector<int> p(n);
    for (int i = 0; i < n; i++)
        p[h[i]] = i;
    vector<int> dp(n, 0);
    atcoder::segtree<int, op, e> seg(n);
    for (int i = 0; i < n; ++i) {
        if (i - d >= 0) {
            seg.set(p[i - d], dp[i - d]);
        }
        int mx = seg.prod(max(0, p[i] - r), min(n, p[i] + r + 1));
        dp[i] = max(dp[i], mx + 1);
    }
    cout << *max_element(dp.begin(), dp.end()) << '\n';
}