传送门
表示去年考普及组的时候失了智,现在看来并不是很难啊。
直接二分答案然后单调队列优化dp检验就行了。
注意入队和出队的条件。
代码:
#include<bits/stdc++.h>
#define N 500005
using namespace std;
inline int read(){
int ans=0,w=1;
char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans*w;
}
int n,d,k,x[N],s[N],q[N],f[N],hd,tl;
inline bool check(int mid){
hd=1,tl=0,q[1]=0;
int pos=0;
int l=max(d-mid,1),r=d+mid;
for(int i=1;i<=n;++i)f[i]=-1e9;
for(int i=1;i<=n;++i){
while(x[pos]<=x[i]-l){
if(f[pos]==-0x3f3f3f3f){++pos;continue;}
while(hd<=tl&&f[pos]>=f[q[tl]])--tl;
q[++tl]=pos,++pos;
}
while(hd<=tl&&x[q[hd]]<x[i]-r)++hd;
if(hd<=tl)f[i]=f[q[hd]]+s[i];
else f[i]=-0x3f3f3f3f;
if(f[i]>=k)return true;
}
return false;
}
int main(){
n=read(),d=read(),k=read();
for(int i=1;i<=n;++i)x[i]=read(),s[i]=read();
int l=0,r=100000,ans=-1;
while(l<=r){
int mid=l+r>>1;
if(check(mid))r=mid-1,ans=mid;
else l=mid+1;
}
printf("%d",ans);
return 0;
}