难道有人看题解不点赞的吗？

题目解析

这道题可以使用二分+动态规划，二分要花的金币数。
$l$ 初始值为 $0$，$r$ 初始值为 $10^9$。
每次二分有弹跳距离的下界和上界：
$mn=\max(1,d-mid)$
$mx=d+mid$

50pts：

简单的 $ok$ 函数：

bool ok(ll g) {
	memset(dp,-0x3f,sizeof(dp));
	dp[0]=0;
	ll ans=0;
	for(ll i=1; i<=n; i++) {
		for(ll j=i-1; j>=0; j--) {
			if(x[i]-x[j]>d+g) break;
			if(x[i]-x[j]>=max(1ll,d-g)) dp[i]=max(dp[i],dp[j]+s[i]);
		}
		ans=max(ans,dp[i]);
	}
	return ans>=k;
}

然后就发现程序超时，只有 $50$ 分。

100pts：

很明显需要优化 $ok$ 函数。
可以发现对于 $dp_i$ 需要维护 $[i-mn,i+mx]$ 的最大值。
欸，这不就是单调队列吗？
对于 $dp_i$：

• 先将所有满足 $j\lt i$ 且 $x_i-x_j \ge mn$ 的 $j$ 加进队尾。

while(j<i && x[i]-x[j]>=mn) {
	if(dp[j]>-1e18) {
		while(!q.empty() && dp[q.back()]<=dp[j]) q.pop_back();
		q.push_back(j);
	}
	j++;
}

• 接下来将队头 $x_i-x_{q.front()} \gt mx$ 的元素删去。

while(!q.empty() && x[i]-x[q.front()]>mx) q.pop_front();

• 最后将 $dp_i$ 赋值为 $x_{q.front()}+s_i$ 并算出答案。

if(!q.empty()) dp[i]=dp[q.front()]+s[i];
ans=max(ans,dp[i]);

呼，该说的都说完了，接下来就是……

AC 代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=5e5+10;
deque<ll> q;
ll n,d,k,l,r=1e9,x[N],s[N],dp[N];
bool ok(ll g) {
	q=deque<ll>();
	memset(dp,-0x3f,sizeof(dp));
	dp[0]=0;
	ll mn=max(1ll,d-g),mx=d+g,j=0,ans=0;
	for(ll i=1; i<=n; i++) {
		while(j<i && x[i]-x[j]>=mn) {
			if(dp[j]>-1e18) {
				while(!q.empty() && dp[q.back()]<=dp[j]) q.pop_back();
				q.push_back(j);
			}
			j++;
		}
		while(!q.empty() && x[i]-x[q.front()]>mx) q.pop_front();
		if(!q.empty()) dp[i]=dp[q.front()]+s[i];
		ans=max(ans,dp[i]);
	}
	return ans>=k;
}
int main() {

	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>d>>k;
	for(ll i=1; i<=n; i++) cin>>x[i]>>s[i];
	while(l<r) {
		ll mid=(l+r)>>1;
		if(ok(mid)) r=mid;
		else l=mid+1;
	}
	if(l>=1e9) cout<<-1;
	else cout<<l;
	return 0;
}

完结撒花~~