luogu P3957 跳房子 二分+斜率优化dp

#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=500005;
const int inf=1e9;
ll num[N],pos[N];
ll dp[N];
ll q[N];
int n,d,lim;
bool check(int mind,int maxd,int lim)
{
	int hh=0,tt=0;
	int j=0;
	memset(dp,-1,sizeof dp);
	memset(q,0,sizeof q);
	dp[0]=0;
	for(int i=1; i<=n; i++)
	{
		while(pos[i]-pos[j]>=mind&&j<i)
		{	
			//能走到
			if(dp[j]!=-1)
			{
				while(hh<tt&&dp[q[tt-1]]<=dp[j])
					tt--;
				q[tt++]=j;
			}
			++j;
		}
		while(hh<tt&&pos[i]-pos[q[hh]]>maxd)
			hh++;
		if(hh<tt)
			dp[i]=dp[q[hh]]+num[i];
	}
	for(int i=1; i<=n; i++)
		if(dp[i]>=lim)
			return 1;
	return false;
}
int main()
{
	cin>>n>>d>>lim;
	for(int i=1; i<=n; i++)
		cin>>pos[i]>>num[i];
	int l=0,r=inf;
	while(l<r)
	{
		int mid=l+r>>1;
		if(check(max(d-mid,1),d+mid,lim))
			r=mid;
		else
			l=mid+1;
	}
	if(r!=inf)
		cout<<r<<endl;
	else
		cout<<"-1"<<endl;
	return 0;
}