好巧我一个小时前做过
by bamboo1030 @ 2022-08-27 21:45:23
@[Grace25](/user/359883) 这个错误你知道我觉得你会自扇一个大嘴巴，~~你的inf设的太大了炸longlong了~~
by bamboo1030 @ 2022-08-27 21:55:18
@[Grace25](/user/359883) 还有把ls的取值0改成1，题目说了最少跳1
by bamboo1030 @ 2022-08-27 21:58:34
@[bamboo123](/user/369181) 草是这样的吗（）
by Grace25 @ 2022-08-28 14:11:23
@[bamboo123](/user/369181) 这就去自扇大嘴巴
by Grace25 @ 2022-08-28 14:11:57
@[bamboo123](/user/369181) 改了但是还是不行。。。我可能太菜了QAQ
```cpp
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int N=500005;
const long long INF=0x7F;
long long n,d,k;
long long x[N],s[N];
long long l,r,mid;
long long dp[N];
deque<long long> q;
bool check(long long g){
long long ls=d-g>0?d-g:0;
long long rs=d+g;
for(int i=1;i<=n;i++) dp[i]=-INF;
dp[0]=0;
q.clear();
int las=1;
for(long long i=1;i<=n;i++){
while(x[las] < x[i]-rs) las++;
while(x[i]-ls >= x[las] && x[i]-rs <= x[las] && las<i){
while(q.size() && (dp[q.back()]<=dp[las] || x[q.back()]<x[i]-rs)) q.pop_back();
q.push_back(las);
las++;
}
while(q.size() && (x[q.front()])<x[i]-rs) q.pop_front();
if(q.size()) dp[i]=dp[q.front()]+s[i];
if(dp[i]>=k) return 1;
}
return 0;
}
int main(){
cin >> n >> d >> k;
for(long long i=1;i<=n;i++)
cin >> x[i] >> s[i];
l=0,r=x[n];
while(l<r){
mid=(l+r)/2;
if(check(mid)) r=mid;
else l=mid+1;
}
if(!check(l)){
cout << "-1";
return 0;
}
cout << l;
return 0;
}
```
by Grace25 @ 2022-08-28 15:23:32
@[Grace25](/user/359883) 我的第二条你可能没有注意到
by bamboo1030 @ 2022-08-28 16:35:00
@[bamboo123](/user/369181) 改了但还是没过，救命啊QAQ
by Grace25 @ 2022-08-28 19:52:56
@[Grace25](/user/359883) ls最小值是1啊你改了没
by bamboo1030 @ 2022-08-28 20:09:08
@[Grace25](/user/359883) 而且你这个inf设的又太小了…设成9e18吧
by bamboo1030 @ 2022-08-28 20:11:07