【CF1519D】Maximum Sum of Products-526互联

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,a[5000+10],b[5000+10],abpre[5000+10],absuf[5000+10],ans;
int main(){
	cin >> n;
	for(ll i=1;i<=n;i++)cin >> a[i];
	for(ll i=1;i<=n;i++)cin >> b[i];
	for(ll i=1;i<=n;i++)abpre[i]=abpre[i-1]+a[i]*b[i];
	for(ll i=n;i>=1;i--)absuf[i]=absuf[i+1]+a[i]*b[i];
	ans=abpre[n];
	for(ll i=1;i<=n;i++){
		ll sum=a[i]*b[i];
		for(ll j=1;i-j>=1&&i+j<=n;j++){		//[i-j,i+j]
			sum+=a[i-j]*b[i+j]+a[i+j]*b[i-j];
			ans=max(sum+abpre[i-j-1]+absuf[i+j+1],ans);
		}
	}
	for(ll i=1;i<=n;i++){
		ll sum=0;
		for(ll j=1;i-j+1>=1&&i+j<=n;j++){	//[i-j+1,i+j]
			sum+=a[i-j+1]*b[i+j]+a[i+j]*b[i-j+1];
			ans=max(sum+abpre[i-j+1-1]+absuf[i+j+1],ans);
		}
	}
	cout << ans;
	return 0;
}