萌新求助!! WA后5点

回复帖子

@DinnerHunt 2018-11-15 14:50 回复
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxd = 500005;
typedef pair<long long,int> P;
P que[maxd];
int n,d,k,pos[maxd],ff;
int left,right,flag[maxd];
long long dp[maxd],arr[maxd];
void add(int i)
{
    while(right>=left&&que[right].first <= dp[i]) right--;
    que[++right] = P(dp[i],i);
}
void del(int i)
{
    while(right>=left&&pos[que[left].second]<i) left++;
}
bool check(int s)
{
    memset(dp,0,sizeof(dp));
    memset(flag,0,sizeof(flag));
    int l = max(1,d-s),r = d+s,cnt=0;
    long long ans = -1e9;
    left = 0,right = -1;
    for(int i=1;i<=n;i++)
    {
        while(cnt<i&&pos[i] - pos[cnt] >= l&&!flag[i])
        {
            add(cnt);
            cnt++;
        }
        del(pos[i]-r);
        if(left<=right) dp[i] = (long long)(que[left].first + arr[i]);
        else flag[i] = 1;
        if(dp[i]>=(long long)k) return true;
    }
    //for(int i=1;i<=n;i++)
    //    printf("%d ",dp[i]);
    //printf("%d %d %d %d\n",ans,s,l,r);
    return false;
}
int main(){
    scanf("%d %d %d",&n,&d,&k);
    for(int i=1;i<=n;i++) scanf("%d %lld",&pos[i],&arr[i]);
    for(int i=1;i<=n;i++) if(arr[i]>0) ff+= arr[i];
    int l = 0, r = pos[n], ans=-1;
    while(l<=r)
    {
        int mid = (l+r) >> 1;
        if(check(mid))
        {
            ans = mid;
            r = mid-1;
        }
        else l = mid+1;                                                                                                                      
    }
    printf("%d",ans);
    return 0;
}