# Noip2017跳房子（普及t4）

Posted by yjjr's blog on February 6, 2018

# T4

f[i]表示跳前i个格子，且停在第i个格子最大分数；

sc[i]表示第i个格子的分数。

#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;
}