传送门

诶嘿嘿随便一交就是最优解

首先指出一个阅读理解问题：去掉一段lemon后，两边的lemon是不会拼起来的。

所以这个操作实际上就是序列划分成若干区间使贡献最大。

设$f(i)$为前$i$个lemon的最大值。

容易得到$f(i)=\max\limits_{j<i}\{f(j)+w(j,i)\}$，其中$w(j,i)$为区间$[j,i]$的最大的$a_0t^2$。

这个$w(j,i)$不太好算啊，而且也没有决策单调性

用三半规管想一想的话，会发现一个显然的性质：划分的子段两端点颜色一定相同且选择的$a_0$就是端点的颜色。再向两边扩展是没有贡献的，不如自成一段。

令$s_i$为$\sum\limits_{j\le i}[a_j=a_i]$。

方程改为$f(i)=\max\limits_{j\le i,a_j=a_i}\{f(j-1)+a_i(s_i-s_j+1)^2\}$。

这一看就是斜率优化了，化一化式子：

$f(i)+2a_is_is_j\sim f(j-1)+a_is_j(s_j-2)$

看起来还不能斜率优化，不过有$a_i=a_j$嘛：

$f(i)+2a_is_is_j\sim f(j-1)+a_js_j(s_j-2)$

在同种颜色里斜率递增，横坐标递增，求最大截距。每种颜色开一个单调队列维护上凸包即可。（不过因为是添加和删除都是在队尾进行，用单调栈就能维护）

代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>

#define maxn 100005    
#define inf 0x3f3f3f3f

using namespace std;

inline int read(){
    int x=0,y=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return y?-x:x;
}
struct triple{
    long long y;int x,p;
    triple(int X=0,long long Y=0,int P=0){x=X,y=Y,p=P;}
    friend double operator / (const triple &a,const triple &b){return double(a.y-b.y)/(a.x-b.x);}
};
vector<triple>q[10005];
long long f[maxn],a[maxn],s[maxn],tax[10005];
inline void push(triple d,int c){
    triple t;
    while(q[c].size()>1&&(*(q[c].end()-1))/(*(q[c].end()-2))<d/(*(q[c].end()-1)))q[c].pop_back();
    q[c].push_back(d);
}
inline int get(double k,int c){
    while(q[c].size()>1&&(*(q[c].end()-1))/(*(q[c].end()-2))<k)q[c].pop_back();
    return (q[c].end()-1)->p;
}
int main(){
    int n=read();
    long long ans=0,ma=0;
    for(register int i=1;i<=n;++i){
        s[i]=++tax[a[i]=read()];
        push(triple(s[i],1ll*a[i]*s[i]*(s[i]-2)+f[i-1],i),a[i]);
        int j=get(s[i]*a[i]<<1,a[i]);
        f[i]=f[j-1]+1ll*a[i]*(s[i]-s[j]+1)*(s[i]-s[j]+1);
    }
    printf("%lld\n",f[n]);
}