分析
设(dp[i])表示前(i)个贝壳可以获得的最大收益，
则(dp[i]=max{dp[j-1]+S(c[i]-c[j]+1)^2}[s_i==s_j])
可以发现当且仅当种类成立才满足此方程，那么要分种类进行，
若(j<k)，则(k)被弹出当且仅当
[frac{dp[k-1]+c[k]^2-dp[j-1]-c[j]^2}{2S(c[k]-c[j])}leq c[i]+1
]
用单调栈维护斜率递增的下凸壳即可
代码
#include <cstdio>
#include <cctype>
#include <stack>
#define rr register
using namespace std;
const int N=100011;
typedef long long lll;
stack<int>st[N/10];
lll dp[N]; int col[N],n,a[N],CNT[N];
inline signed iut(){
rr int ans=0; rr char c=getchar();
while (!isdigit(c)) c=getchar();
while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
return ans;
}
inline lll calc(int j,int x){return dp[j-1]+1ll*col[j]*x*x;}
inline double slope(int j,int i){
return (calc(i,a[i])-calc(j,a[j]))*1.0/(2ll*a[i]*col[i]-2ll*a[j]*col[j]);
}
signed main(){
n=iut();
for (rr int i=1;i<=n;++i) a[i]=++CNT[col[i]=iut()];
for (rr int i=1;i<=n;++i){
rr int t=col[i];
while (st[t].size()>1){
rr int t1=st[t].top(); st[t].pop();
if (slope(t1,st[t].top())>slope(t1,i)) {st[t].push(t1); break;}
}
st[t].push(i);
while (st[t].size()>1){
rr int t1=st[t].top(); st[t].pop();
if (slope(t1,st[t].top())>a[i]+1) {st[t].push(t1); break;}
}
rr int t1=st[t].top();
dp[i]=calc(t1,a[i]-a[t1]+1);
}
return !printf("%lld",dp[n]);
}