【正经题解】跳房子

用 $dp$ [ $i$ ]表示跳到 $i$ 位时的最大收益，可知一定是从前面可以跳到第 $i$ 位的点中最大的，所以单调队列优化一下，保证队 列合理和最优，然后直接调用队首的就行了

#include<iostream>
#include<cstdio>
#include<cstring>
#include<deque>
using namespace std;
#define ll long long
ll x[500010],s[500010],dp[500010];
ll n,d,k;
bool work(ll g){
     memset(dp,0,sizeof(dp));
     ll maxx=d+g,QAQ=1;
     ll mini=max(QAQ,d-g);
     deque<int> q;
     int j=0;/*不要在循环里置，会被t的很惨,因为会有很多重复*/ 
     for(int i=1;i<=n;i++){
             for(;x[i]>=x[j]+mini;++j){
                     while(!q.empty()&&dp[j]>dp[q.back()])q.pop_back();/*把不是最优的去掉*/ 
                     q.push_back(j);
             }
             while(!q.empty()&&x[q.front()]+maxx<x[i])q.pop_front();/*把不可能的去掉*/ 
             if(q.empty())dp[i]=-999999999999;/*这里绝对会报错，但不多加几个9，最后的点会wa*/
             else dp[i]=s[i]+dp[q.front()];/*因为我们已经用 单调队列优化过了，所以队首一定最优*/ 
             if (dp[i]>=k)return 1;
     }
     return 0;
}
int main(){
    cin>>n>>d>>k;
    ll tmp=0;
    memset(x,0,sizeof(x));
    memset(s,0,sizeof(s));
    for(int i=1;i<=n;i++){
            scanf("%lld%lld",&x[i],&s[i]);
            if (s[i]>0)tmp+=s[i];
    }
    if (tmp<k){cout<<-1;return 0;};
    ll l=0,r=1005,mans=x[n];
    while(l<=r){
                ll mid=(r+l)/2;
                if (work(mid)){mans=mid;r=mid-1;}
                else l=mid+1;
    }
    cout<<mans;

    return 0;
}