更新状态，WA，40
```cpp
#include<iostream>
#include<cstdio>
using namespace std;
int w[500001],s[500001],dp[500002],n,d,k,r,l,mid,dz[500002],dl,dr,maxr;
const int INF=1<<30;
void de(int num)
{
while (w[dz[dl]]<num && dl<=dr) dl++;
}
void jo(int num)
{
while (dp[dz[dr]]<=dp[num] && dl<=dr)
dr--;
dz[++dr]=num;
}
bool dp_cheak(int x)
{
for (int i=1;i<=500001;i++) dz[i]=500001,dp[i]=-INF;
int l=max(d-x,1),r=d+x;
dp[0]=0;
dl=1,dr=0,dz[1]=0;
int j=0;
for (int i=0;i<=n;i++)
{
de(w[i]-r);
while (w[j]<=w[i]-l && j<=n)
{
jo(j);
j++;
}
if (dl<=dr) dp[i]=dp[dz[dl]]+s[i];
else if (i!=0) dp[i]=-INF;
if (dp[i]>=k) return true;
}
return false;
}
int main()
{
scanf("%d%d%d",&n,&d,&k);
for (int i=1;i<=n;i++)
{
scanf("%d%d",&w[i],&s[i]);
r=max(r,w[i]);
}
l=0;
maxr=r;
r++;
while (l!=r)
{
mid=(l+r)/2;
if (dp_cheak(mid)) r=mid;
else l=mid+1;
}
if (l>maxr) cout<<-1;else cout<<l;
return 0;
}
```
by 为依相逢 @ 2019-03-06 21:15:01
WA 90
```cpp
#include<iostream>
#include<cstdio>
using namespace std;
int w[500002],s[500002],dp[500002],n,d,k,r,l,mid,dz[500002],dl,dr,maxr;
const int INF=1<<30;
void de(int num)
{
while (w[dz[dl]]<num && dl<=dr) dl++;
}
void jo(int num)
{
while (dp[dz[dr]]<=dp[num] && dl<=dr)
dr--;
dz[++dr]=num;
}
bool dp_cheak(int x)
{
for (int i=1;i<=500001;i++) dz[i]=500001,dp[i]=-INF;
int l=max(d-x,1),r=d+x;
dp[0]=0;
dl=1,dr=0,dz[1]=0;
int j=0;
for (int i=0;i<=n;i++)
{
while (w[j]<=w[i]-l && j<=n)
{
jo(j);
j++;
}
de(w[i]-r);
if (dl<=dr) dp[i]=dp[dz[dl]]+s[i];
else if (i!=0) dp[i]=-INF;
if (dp[i]>=k) return true;
}
return false;
}
int main()
{
scanf("%d%d%d",&n,&d,&k);
for (int i=1;i<=n;i++)
{
scanf("%d%d",&w[i],&s[i]);
r=max(r,w[i]);
}
l=0;
maxr=r;
r++;
while (l!=r)
{
mid=(l+r)/2;
if (dp_cheak(mid)) r=mid;
else l=mid+1;
}
if (l>maxr) cout<<-1;else cout<<l;
return 0;
}
```
by 为依相逢 @ 2019-05-02 21:43:55
上面那个发错代码了。。。
```cpp
#include<iostream>
#include<cstdio>
using namespace std;
int w[500002],s[500002],dp[500002],n,d,k,r,l,mid,dz[500002],dl,dr,maxr;
const int INF=1<<30;
void de(int num)
{
while (w[dz[dl]]<num && dl<=dr) dl++;
}
void jo(int num)
{
while (dp[dz[dr]]<=dp[num] && dl<=dr)
dr--;
dz[++dr]=num;
}
bool dp_cheak(int x)
{
for (int i=1;i<=500001;i++) dz[i]=500001,dp[i]=-INF;
int l=max(d-x,1),r=d+x;
dp[0]=0;
dl=1,dr=0,dz[1]=0;
int j=0;
for (int i=0;i<=n;i++)
{
while (w[j]<=w[i]-l && j<=n)
{
jo(j);
j++;
}
de(w[i]-r);
if (dl<=dr) dp[i]=dp[dz[dl]]+s[i];
else if (i!=0) dp[i]=-INF;
if (dp[i]>=k) return true;
}
return false;
}
int main()
{
scanf("%d%d%d",&n,&d,&k);
for (int i=1;i<=n;i++)
{
scanf("%d%d",&w[i],&s[i]);
r=max(r,w[i]);
}
l=0;
maxr=r;
r++;
while (l!=r)
{
mid=(l+r)/2;
if (dp_cheak(mid)) r=mid;
else l=mid+1;
}
if (l>maxr) cout<<-1;else cout<<l;
return 0;
}
```
by 为依相逢 @ 2019-05-02 21:51:54