rt，开了O2就WA，没开就AC

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=2001;
int n,a[MAXN],dp[MAXN][MAXN],ans;
signed main() {
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	dp[1][n]=0;
	for(int k=n-1;k>=1;k--)
		for(int i=1;i+k-1<=n;i++)
			dp[i][i+k-1]=max(dp[i-1][i+k-1]+a[i-1]*(n-k),dp[i][i+k]+a[i+k]*(n-k));
	for(int i=1;i<=n;i++) ans=max(ans,dp[i][i]+a[i]*n);
	cout<<ans;
	return 0;
}