求助:WA声一片

回复帖子

@_Wallace_ 2019-04-13 07:03 回复

Code:

#include<cstdio>
#include<deque>
#include<cstring>
using namespace std;

const int N=5e5+3;
int s[N],x[N];
int n,k,d;
inline int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return f*x;}
int dp[N];

inline bool Judge(int g)
{
    register int i,j;
    memset(dp,-127,sizeof(dp));
    int Left=d-g<=0?1:d-g,Right=d+g;
    dp[0]=0;
    for(i=1;i<=n;i++)
    {
        for(j=i-1;j>=0;j++)
        {
            if(x[i]-x[j]<Left)continue;
            if(x[i]-x[j]>Right)break;
            dp[i]=max(dp[i],dp[j]+s[i]);
        }
        if(dp[i]>=k)return 1;
    }
    return 0;
}

inline int Binary_Search()
{
    int lb=-1,ub=x[n];
    while(lb<ub)
    {
        int mid=(lb+ub)>>1;
        if(Judge(mid))ub=mid;
        else lb=mid+1;
    }
    return lb;
}

signed main()
{
    register int i;
    scanf("%d%d%d",&n,&d,&k);
    int sum=0;
    for(i=1;i<=n;i++)x[i]=read(),s[i]=read(),sum+=s[i];
    if(sum<k) puts("-1");
    else printf("%d",Binary_Search());
    return 0;
}

没错这是最朴素的解法。

然而还是WA了。