RT

求大佬帮忙调一调。

#include<deque>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,d,k;
int dis[500005],val[500005];
int l,r;
long long sum,dp[500005];
int max(int _a,int _b){return _a>_b?_a:_b;}
bool check(int _x)
{
	deque<int>q;
	memset(dp,-0x3f,sizeof(dp));
	dp[0]=0;
	q.push_back(0);
	for(int i=1;i<=n;i++)
	{
		while(!q.empty()&&dis[q.front()]<dis[i]-d-_x) q.pop_front();
		if(!q.empty()&&dis[q.front()]<=dis[i]-d+_x)
			dp[i]=dp[q.front()]+val[i];
		//else return false;
		//printf("Debug:%d %d %lld\n",_x,i,dp[i]);
		if(dp[i]>=k) return true;
		while(!q.empty()&&dp[q.back()]<dp[i]) q.pop_back();
		q.push_back(i);
	}
	return false;
}
int main()
{
	scanf("%d%d%d",&n,&d,&k);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&dis[i],&val[i]);
		if(val[i]>0) sum+=val[i];
	}
	if(sum<k){puts("-1");return 0;}
	r=max(dis[n],d);
	while(l<r)
	{
		int mid=(l+r)/2;
		if(check(mid)) r=mid;
		else l=mid+1;
	}
	printf("%d\n",r);
	return 0;
}