这是 WA 40 pts 代码：

#include <bits/stdc++.h>
#define int long long
#define INF 9e18

using namespace std;

const int N = 5e5 + 5;

int n, d, k;
int x[N], s[N], dp[N], q[N];

bool check(int m) {
	int l = 1, r = 0, j = 0, a = max(d - m, 1ll), b = d + m;
	for (int i = 1; i <= n; i ++) q[i] = 0;
	for (int i = 1; i <= n; i ++) {
		dp[i] = -INF;
		while (l <= r && x[i] - x[q[l]] > b) l ++;
		while (j < i && x[i] - x[j] >= a) {
			while (l <= r && dp[q[r]] <= dp[j]) r --;
			q[ ++ r] = j;
			j ++;
		}
		if (l > r) continue;
		if (dp[q[l]] != -INF) dp[i] = dp[q[l]] + s[i];
		if (dp[i] >= k) return true;
	}
	return false;
}

signed main() {
	cin >> n >> d >> k;
	for (int i = 1; i <= n; i ++) cin >> x[i] >> s[i];
	int l = 0, r = 1e9, ans = -1;
	while (l <= r) {
		int mid = (l + r) >> 1;
		if (check(mid)) r = mid - 1, ans = mid;
		else l = mid + 1;
	}
	cout << ans;
	return 0;
}

其错误原因在于，需要先从队尾添加元素，再从队头弹出元素。即，将 check 函数中，第 17 ~ 21 行与第 22 行互换，变为：

while (j < i && x[i] - x[j] >= a) {
	while (l <= r && dp[q[r]] <= dp[j]) r --;
	q[ ++ r] = j;
	j ++;
}
while (l <= r && x[i] - x[q[l]] > b) l ++;

这样即可通过。求问原因。