Submission #66415030

---

Source Code Expand

#include<bits/stdc++.h>
#include<atcoder/segtree>
using namespace std;

using S=int;
S op(S x,S y){return max(x,y);}
S e(){return (int)-1e9;}

int main(){
	int n,d,r;
	cin >> n >> d >> r;
	vector<int>h(n);
	for(int i=0;i<n;i++)cin >> h[i];

	vector<pair<int,int>>temp;
	for(int i=0;i<n;i++){
		temp.push_back({h[i],~i});
		temp.push_back({h[i]-d,i});
	}
	sort(temp.rbegin(),temp.rend());

	atcoder::segtree<S,op,e>seg(n);
	vector<int>dp(n,-1e9);
	for(auto[v,i]:temp){
		if(i<0){
			i=~i;
			dp[i]=max(0,seg.prod(max(0,i-r),min(n,i+r+1))+1);
		}else{
			seg.set(i,dp[i]);
		}
	}

	cout << *max_element(dp.begin(),dp.end()) << endl;
}

Submission Info

Judge Result