C++14(g++5.4) 解法, 执行用时: 765ms, 内存消耗: 16212K, 提交时间: 2018-07-25 10:17:38

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ff(l,r) for(ll i=l;i<=r;i++)
ll a[500005];
ll sum1[500005],sum2[500005];
ll x[500005];

ll ad1(ll l,ll r)
{
	return sum1[r]-sum1[l-1];
}
ll ad2(ll l,ll r)
{
	return sum2[r]-sum2[l-1];
}
ll n,T;

ll check(ll t)
{
	//cout<<t<<endl;
	//l左，r右，m中 
	for(ll l=1,m=1,r=1;l<=n;l++)
	{
		while(r<n&&ad1(l,r)<t) r++;
		while(m<n&&ad1(l,m)*2<t) m++;
		if(ad1(l,r)>=t&&(x[m]*ad1(l,m)-ad2(l,m)+ad2(m,r)-x[m]*ad1(m,r)-(ad1(l,r)-t)*(x[r]-x[m]))<=T)
		{
			return true;
		}
	}
	for(ll r=n,m=n,l=n;r>=1;r--)
	{
		while(l>1&&ad1(l,r)<t) l--;
		while(m>1&&ad1(m,r)*2<t) m--;
		if(ad1(l,r)>=t&&(x[m]*ad1(l,m)-ad2(l,m)+ad2(m,r)-x[m]*(ad1(m,r))-(ad1(l,r)-t)*(x[m]-x[l]))<=T)
		return true;
	}
	return false;
}
/*
2 3
1 2
2 3
*/

int main()
{
	scanf("%lld%lld",&n,&T);T/=2;
	ff(1,n) scanf("%lld",&x[i]);
	ff(1,n) scanf("%lld",&a[i]);
	ff(1,n)
    {
        sum1[i]=sum1[i-1]+a[i];
        sum2[i]=sum2[i-1]+a[i]*x[i];
    }
	ll l=1,r=sum1[n];
	while(l<r)
	{
		ll mid=(l+r+1)/2;
		if(check(mid)) 
			l=mid;
		else 
			r=mid-1;
	}
	printf("%lld\n",l);
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 163ms, 内存消耗: 8188K, 提交时间: 2020-02-28 16:57:58

#include<bits/stdc++.h>
using namespace std;
#define ff(i,a,b) for(int i=a;i<=b;i++)
#define LL long long
const int mn=5e5+5;
int n,a[mn],x[mn];
LL t,s[mn];
int main()
{
	cin>>n>>t;
	t/=2;
	ff(i,1,n) scanf("%d",x+i);
	ff(i,1,n) scanf("%d",a+i);
	ff(i,1,n)
	s[i]=s[i-1]+a[i];
	int p=1,e=1,m=1;
	LL ans=0;
	while(e<=n)
	{
		t-=(x[e]-x[m])*a[e];
		e++;
		while(p<e)
		{
			while(m<e-1)
			{
				LL tem=(s[p-1]+s[e-1]-2LL*s[m])*(x[m+1]-x[m]);
				if(tem<=0) break;
				t+=tem;
				m++;
			}
			if(t>=0) break;
			t+=a[p]*(x[m]-x[p]);
			p++;
		}
		LL L=0,R=0;
		if(p>1) L=min(1LL*a[p-1],t/(x[m]-x[p-1]));
		if(e<=n) R=min(1LL*a[e],t/(x[e]-x[m]));
		ans=max(ans,s[e-1]-s[p-1]+max(L,R));
	}
	cout<<ans<<endl;
	return 0;
}