T4
感觉在pj组放这道题是不是有些难了，难度大于NOIP2015D2T1那道跳石子
老套路先二分答案+DP
f[i]表示跳前i个格子，且停在第i个格子最大分数；
sc[i]表示第i个格子的分数。
转移：f[i]=max(f[j])+sc[i] 前提是从j可以跳到i
显然，这种时间复杂度太大
需要再次使用单调队列优化
发现转移中j的位置是随着i的右移而右移的
对于格子j，如果dis[i]-dis[j]>=机器人能跳的最小距离，显然f[j]是可以进队的
但是要维护整个队列单调递减，每次直接去队头就好了
注意要把最小值置极小，否则会WA
#include<bits/stdc++.h>
#define rep(i,a,b) for(register int i=a;i<=b;i++)
#define dep(i,a,b) for(register int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
using namespace std;
const ll maxn=5e5+6,inf=1844387848000;
ll dis[maxn],sc[maxn],f[maxn],n,d,k,x,y;
bool check(int x)
{
deque<ll>que;
ll from=0,stepl=max(d-x,(ll)1),stepr=d+x;
rep(i,1,n){
while(dis[from]+stepl<=dis[i]){
while(!que.empty()&&f[que.back()]<=f[from])que.pop_back();
que.push_back(from++);
}
while(!que.empty()&&dis[que.front()]+stepr<dis[i])que.pop_front();
if(!que.empty())f[i]=f[que.front()]+sc[i];
else f[i]=-inf;
if(f[i]>=k) return 1;
}
return 0;
}
int main()
{
cin>>n>>d>>k;
ll sum=0;
rep(i,1,n){
cin>>x>>y;
dis[i]=x;sc[i]=y;
if(y>0)sum+=y;
}
if(sum<k){cout<<"-1\n";return 0;}
int l=1,r=dis[n],mid;
while(l<r){
mem(f,0);
mid=(l+r)/2;
if(check(mid))r=mid;
else l=mid+1;
}
cout<<r<<endl;
return 0;
}
