```cpp
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#define LL long long
#define Cl(X,Y) memset((X),(Y),sizeof(X))
#define FOR(i,A,B) for(LL i=A;i<=B;i++)
#define BOR(i,A,B) for(LL i=A;i>=B;i--)
#define INF 0x3f3f3f3f
using namespace std;
const LL MAXn=5e5+10;
LL DP[MAXn],Head,Tail,L,R,Che;
LL Queue[MAXn],Total,Dis,Limit,Ans;
struct Node {
LL Loc,Pts;
}House[MAXn];
inline bool Check(LL l,LL r) {
Cl(Queue,0); Cl(DP,-1); Head=1,Tail=0;
DP[0]=0;int j=0;
FOR(i,1,Total) {
while(House[i].Loc-House[j].Loc>=l&&j<i) {
if(DP[j]!=-1) {
while(Head<=Tail && DP[j]>DP[Queue[Tail]]) Tail--;
Queue[++Tail]=j;
}
++j;
}
while(Head<=Tail && House[i].Loc-House[Queue[Head]].Loc>r) Head++;
if(Head<=Tail) DP[i]=DP[Queue[Head]]+House[i].Pts;
}
for(int i=1;i<=Total;i++) if(DP[i]>=Limit) return 1;
return 0;
}
inline void Work() {
L=0,R=House[Total].Loc;
while(L<=R) {
int lx,lr;
LL Mid=(L+R)>>1;
if(Mid<Dis) lx=Dis-Mid;
else lx=1;
lr=Dis+Mid;
if(Check(lx,lr)) R=Mid-1,Ans=Mid;
else L=Mid+1;
}
printf("%lld\n",Ans);
}
int main() {
scanf("%d %d %d",&Total,&Dis,&Limit);
FOR(i,1,Total) {
scanf("%lld %lld",&House[i].Loc,&House[i].Pts);
Che+=(House[i].Pts>0 ? House[i].Pts : 0);
}
if(Che<Limit) { printf("-1\n"); exit(0); }
Work();
return 0;
}
```
二分挂了吧
by widsnoy @ 2020-05-25 11:33:12
%%%%
by PXY_lover @ 2020-05-27 21:12:05