C++14(g++5.4) 解法, 执行用时: 60ms, 内存消耗: 14316K, 提交时间: 2020-06-06 16:49:39

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn=1e5+10;
int n,t;
long long v[maxn],sum,f[22][maxn],ans,p[maxn],k;
long long ck(int ll,int rr)
{
	int kk=0; while ((1<<(kk+1))<(rr-ll+1)) kk++;
return max(f[kk][ll],f[kk][rr-(1<<kk)+1]);
}
int main()
{
	scanf("%d%lld",&n,&k); t=-1;
	for (int i=1;i<=n;i++) 
	{
		scanf("%lld",&p[i]);
		if (p[i]>0 && t==-1) t=i;
	}
	for (int i=1;i<=n;i++) scanf("%lld",&v[i]);
	if (t==-1)
	{
		sum=0;
		for (int i=n;i>=1;i--) 
		{
			sum+=v[i];
			if (abs(p[i])<=k) ans=max(ans,sum);
		}
		printf("%lld\n",ans);
		return 0;
	}
	if (t==1)
	{
		sum=0;
		for (int i=1;i<=n;i++) 
		{
			sum+=v[i];
			if (abs(p[i])<=k) ans=max(ans,sum);
		}
		printf("%lld\n",ans);
		return 0;
	}
	ans=-1e18;
	if (p[t]-1!=0) ans=0;
	if (p[t-1]+1!=0) ans=0;
	sum=0;
	for (int i=t;i<=n;i++) 
	{
		sum+=v[i]; f[0][i]=sum;
		if (p[i]<=k) ans=max(ans,sum);
	}
	sum=0;
	for (int i=t-1;i>=1;i--)
	{
		sum+=v[i]; f[0][i]=sum;
		if (abs(p[i])<=k) ans=max(ans,sum);
	}
	for (int j=1;(1<<j)<=n;j++)
	 for (int i=1;i+(1<<j)-1<=n;i++)
	  f[j][i]=max(f[j-1][i],f[j-1][i+(1<<(j-1))]);
	for (int i=1;i<t;i++)
	if (2ll*abs(p[i])<=k)
	{
		long long now=f[0][i],len=k-2ll*abs(p[i]);
		int lc=upper_bound(p+t,p+n+1,len)-p-1;
		if (lc<t) continue;
		ans=max(ans,now+ck(t,lc));
	}
	for (int i=t;i<=n;i++)
	if (2ll*p[i]<=k)
	{
		long long now=f[0][i],len=k-2ll*p[i];
		int lc=lower_bound(p+1,p+t,-len)-p;
		if (lc>=t) continue;
		ans=max(ans,now+ck(lc,t-1));
	}
	printf("%lld\n",ans);
return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 30ms, 内存消耗: 3296K, 提交时间: 2020-06-17 19:25:58

#include<bits/stdc++.h>
using namespace std;

int A[100005],B[100005],W[100005],Max1[100005]={0},Max2[100005]={0};
int main()
{
    int i,j,n,x,s,a=0,b=0,ans=0;
    scanf("%d%d",&n,&x);
    for(i=1;i<=n;i++)
    {
    	scanf("%d",&j);
    	if(j<0)A[++a]=-j;
    	else B[++b]=j;
	}
	for(i=1;i<=n;i++)scanf("%d",&W[i]);
	for(i=1;i<=a/2;i++)swap(W[i],W[a-i+1]),swap(A[i],A[a-i+1]);
	for(s=0,i=1;i<=a;i++)s+=W[i],Max1[i]=max(s,Max1[i-1]);
	for(s=0,i=1;i<=b;i++)s+=W[a+i],Max2[i]=max(s,Max2[i-1]);
	if(a&&A[1]==1&&b&&B[1]==1)ans=max(W[1],W[1+a]);
	for(s=0,i=1;i<=a&&A[i]<=x;i++)
	{
		j=upper_bound(B+1,B+1+b,x-2*A[i])-B-1;
		s+=W[i],ans=max(ans,s+Max2[j]);
	}
	for(s=0,i=1;i<=b&&B[i]<=x;i++)
	{
		j=upper_bound(A+1,A+1+a,x-2*B[i])-A-1;
		s+=W[a+i],ans=max(ans,s+Max1[j]);
	}
	printf("%d\n",ans);
}