P3957 跳房子
样例都过不了[欲哭无泪]
听说水区大佬多
帮忙看看呗

#include <bits/stdc++.h>
using namespace std;
int n, d, k, sum;
int dis[500005], score[500005], dp[500005];

bool check(int g){
	deque <int> dq;
	for(int i = 1;i <= n;i++){
		dp[i] = -2147483648;
	}
	dp[0] = 0;
	int las = 0;
	for(int i = 1;i <= n;i++){
		while(dis[las]<=dis[i]-d-g)las++;
		while(dis[i]-((d-g<0)?0:d-g)>=dis[las]&&dis[las]>=dis[i]-d-g&&las<i){
			while(!dq.empty()&&(dp[dq.back()]<=dis[las]||dis[dq.back()]<dis[i]-d-g)){
				dq.pop_back();
			}
			dq.push_back(las);
			las++;
		}
		while(!dq.empty()&&dq.front()<dis[i]-d-g){
			dq.pop_front();
		}		
		if(!dq.empty())dp[i] = dp[dq.front()]+score[i];
		if(dp[i]>=k)return true;
	}
	return false;
}

int main(){
	cin >> n >> d >> k;
	for(int i = 1;i <= n;i++){
		cin >> dis[i] >> score[i];
		if(score[i]>=0){
			sum+=score[i];
		}
	}
	if(sum<k){
		cout << "-1";
		return 0;
	}
	int l = 0, r = dis[n];
	while(l!=r){
		int mid = (l+r)/2;
		if(check(mid))r = mid;
		else l = mid+1;
	}
	cout << l;
	return 0;
}

基本对着题解写的
记得@我领关注！