题意分析
首先，花费的金币越多，灵活性越高，能够获得的分数也就越高。
因此，能够获得的分数是具有单调性的，考虑二分答案。
判断花费 $g$ 金币时能够获得的最高分数，考虑 DP。
设 $dp_i$ 为跳到第 $i$ 个格子时的最高分数。
则有：
\[dp_i=s_i+\max_{x_i-d-g\leq x_j\leq x_i+\max(1,d-g)} dp_j\]特别地，若 $j$ 不存在，则代表 $i$ 不能够被跳到，设此时其最高分数为 $-\infty$。
这显然是一个 $\mathcal O\left(n^2\right)$ 的 DP，考虑到 $n\leq5\times10^5$，会 $\text{TLE}$。
但是注意到 $j$ 的取值是一段区间 $[l,r]$，且 $l,r$ 会随 $i$ 增加而增加，即 $l,r$ 具有单调性。
因此可以使用单调队列优化 DP。
即维护一个“滑动窗口”，队列内单调递减，且队首维护为合法的最大 $dp_j$ 的 $j$。
需要注意的是，会存在这样一种情况：在 $i-1$ 时 $p$ 没有入过队，$p$ 在滑动窗口和 $i-1$ 之间；而在 $i$ 时，滑动窗口跑到了 $p$ 的右边，$p$ 就被“跳过了”。
此时 $p$ 仍然需要入队，即使不久就会被弹出。因为这样才能让 $p+1,p+2,p+3,\cdots$ 有可能入队，否则指针 $p$ 就停留在那里不动了，永远不会入队。
AC 代码
时间复杂度：$\mathcal O\left(n\log V\right)$，其中 $V$ 为答案的值域，有 $V=\max(d,x_n)\leq10^9$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
typedef long long ll;
constexpr const int N=5e5,S=1e5;
struct grid{
int x,s;
}a[N+1];
int n,d,k;
bool noAns(){
ll sum=0;
for(int i=1;i<=n;i++){
if(a[i].s>0){
sum+=a[i].s;
}
}
return sum<k;
}
//跳到i时的最大分数
ll dp[N+1];
bool check(int g){
fill(dp+1,dp+n+1,-1ll*N*S-1);
deque<int>q;
q.push_back(0);
for(int i=1,p=0;i<=n;i++){
while(a[p].x<=a[i].x-max(1,d-g)){
while(q.size()&&dp[q.back()]<=dp[p]){
q.pop_back();
}
q.push_back(p++);
}
while(q.size()&&(a[q.front()].x<a[i].x-d-g||a[i].x-max(1,d-g)<a[q.front()].x)){
q.pop_front();
}
if(q.size()){
dp[i]=dp[q.front()]+a[i].s;
if(dp[i]>=k){
return true;
}
}
/*for(int j=0;j<i;j++){
if(a[i].x-d-g<=a[j].x&&a[j].x<=a[i].x-max(1,d-g)){
dp[i]=max(dp[i],dp[j]);
}
}
dp[i]+=a[i].s;
*/
}
return false;
}
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>d>>k;
for(int i=1;i<=n;i++){
cin>>a[i].x>>a[i].s;
}
if(noAns()){
cout<<-1<<'\n';
}else{
int l=0,r=max(a[n].x,d);
while(l<r){
int mid=l+r>>1;
if(check(mid)){
r=mid;
}else{
l=mid+1;
}
}
cout<<r<<'\n';
}
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
