帮忙看下

回复帖子

@王悦铭 2018-11-09 22:09 回复
#include<bits/stdc++.h>
using namespace std;
int n,d,k,x[500010],s[500010],dp[500010],tot,l,r,mid;
bool can(int a)
{
    int max1=d+a,min1=max(1,d-a),ret=0;
    for(int i=1;i<=n;i++)
    {
        dp[i]=-2147000000;
        for(int j=0;j<i;j++)
            if(min1<=x[i]-x[j]&&x[i]-x[j]<=max1)
                dp[i]=max(dp[i],dp[j]+s[i]);
        ret=max(dp[i],ret);
    }
    return(ret>=k);
}
int lower__bound()
{
    l=1;
    r=max(x[n],d);
    while(l<r)
    {
        mid=(l+r)/2;
        if(can(mid))
            r=mid;
        else
            l=mid+1;
    }
    for(l-=5;l<=r+5;l++)
        if(can(l))
            return l;
}
int main()
{
    scanf("%d%d%d",&n,&d,&k);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&x[i],&s[i]);
        if(s[i]>0)
            tot+=s[i];
    }
    if(tot<k)
    {
        printf("-1\n");
        return 0;
    }
    printf("%d\n",lower__bound());
    return 0;
}

评测记录

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。