C++(g++ 7.5.0) 解法, 执行用时: 26ms, 内存消耗: 5152K, 提交时间: 2023-04-24 21:08:51

#include<bits/stdc++.h>
using namespace std;
#define int long long
int s[100005],cnt[100005],x[100005],y[100005],dp[100005],num[100005];
vector<int>q[100005];
double xie(int a,int b)
{
    return (y[a]-y[b])/(x[a]-x[b]);
}
signed main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>s[i];
        cnt[i]=++num[s[i]];
    }
    for(int i=1;i<=n;i++)
    {
        int w=s[i];
        int l=q[w].size()-1;
        x[i]=w*(cnt[i]-1);
        y[i]=dp[i-1]+w*(cnt[i]-1)*(cnt[i]-1);
        while(l>0&&xie(q[w][l-1],q[w][l])<xie(q[w][l],i))
        {
            q[w].pop_back();l--;
        }
        q[w].push_back(i);
        l++;
        while(l>0&&xie(q[w][l-1],q[w][l])<2*cnt[i])
        {
            q[w].pop_back();l--;
        }
        int temp=q[w][l];
        dp[i]=dp[temp-1]+w*(cnt[i]-cnt[temp]+1)*(cnt[i]-cnt[temp]+1);
    }
    cout<<dp[n]<<endl;
    return 0;
}

C++(clang++11) 解法, 执行用时: 535ms, 内存消耗: 3708K, 提交时间: 2020-11-01 14:04:29

#include<bits/stdc++.h>
#define LL long long
#define pb push_back
using namespace std;
const int N=1e5+5;
int n,a[N];LL dp[N];
vector<int>v[N];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=1,l,stp,edp;i<=n;i++){
		v[a[i]].pb(i);l=v[a[i]].size()-1;
		stp=max(l-500,0);edp=min(l,10000);
		for(int j=0;j<=edp;j++)dp[i]=max(dp[i],dp[v[a[i]][j]-1]+(LL)a[i]*(l-j+1)*(l-j+1));
		for(int j=stp;j<l;j++)dp[i]=max(dp[i],dp[v[a[i]][j]-1]+(LL)a[i]*(l-j+1)*(l-j+1));
		int pl=0,pr=l;
		while(pl+500<pr){
			int mid=pl+(pr-pl)/3,mid2=pr-(pr-pl)/3;
			LL tv=dp[v[a[i]][mid]-1]+(LL)a[i]*(l-mid+1)*(l-mid+1),tv2=dp[v[a[i]][mid2]-1]+(LL)a[i]*(l-mid2+1)*(l-mid2+1);
			if(tv>tv2)pr=mid2;else pl=mid;
		}
		for(int j=pl;j<=pr;j++)dp[i]=max(dp[i],dp[v[a[i]][j]-1]+(LL)a[i]*(l-j+1)*(l-j+1));
	}
	printf("%lld\n",dp[n]);
	return 0;
}