感觉贪心的做法比较自然🤔，推荐 这篇博客

非常经典牛逼的贪心思路：

考虑每次加入一个数，位置$i$的贡献为$V_i=k_i\times a_i+b_i$，其中$k_i$表示$i$以前被选的位置的个数，$b_i$表示$i$以后被选的数的和

发现每次都会加入当前贡献最大的数。想一想会发现非常对，可以用归纳+调整法证明。感觉就是拟阵啊？

这样，我们考虑分块，发现对于整块的询问本质上就是维护凸包（类似于斜率优化），这样就做完了

事实上我们不需要在凸包上二分，注意到询问的$k$是递增的，因此不断弹出队头元素即可

复杂度$O(n\sqrt{n})$。

$\text{remark}$ 别把凸优化学魔怔了。。。不是啥题都要用$DP$。。。

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define fi first
#define se second
#define db double
#define ull unsigned long long
#define inf 0x3f3f3f3f
using namespace std;
const int N=1e5+5;
const int B=350;
int n,vs[N],bl[N];
ll sm[N],sm2[N];
ll a[N];
int b[N];
ll calc(pair<ll,ll>a,pair<ll,ll>b){if(a.fi==0&&b.fi==0)return b.se;return a.fi*b.se-a.se*b.fi;
}
struct node{pair<ll,ll>s[B];int l,r,L,R,id[B];ll tag1,tag2;void build(){ll x=0,y=0;for(int i=R;i>=L;i--){sm[i]=x+(vs[i]?a[i]:0),x=sm[i];}for(int i=L;i<=R;i++){sm2[i]=y+vs[i],y=sm2[i];}l=1,r=0;for(int i=L;i<=R;i++){int x=b[i];if(vs[x])continue;pair<ll,ll>tmp={a[x],sm[x]+sm2[x]*a[x]};while(r-l+1>=2&&calc({s[r].fi-s[r-1].fi,s[r].se-s[r-1].se},{tmp.fi-s[r].fi,tmp.se-s[r].se})>=0)r--;s[++r]=tmp,id[r]=x;}}pair<ll,ll>query(){if(l>r)return {-inf,inf};while(r-l+1>=2&&calc({1,-tag1},{s[l+1].fi-s[l].fi,s[l+1].se-s[l].se})>0)l++;return {tag1*s[l].fi+s[l].se+tag2,id[l]};}
}f[B];
bool cmp(int x,int y){return a[x]<a[y];
}
void update(int x){vs[x]=1;f[bl[x]].build();for(int i=bl[x]+1;i<=bl[n];i++)f[i].tag1++;for(int i=1;i<bl[x];i++)f[i].tag2+=a[x];
}
signed main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=n;i++)cin>>a[i],bl[i]=(i-1)/B+1,b[i]=i;for(int i=1;i<=bl[n];i++)f[i].L=(i-1)*B+1,f[i].R=min(n,i*B),sort(b+f[i].L,b+f[i].R+1,cmp),f[i].build(),f[i].tag1=1;ll res=0;for(int i=1;i<=n;i++){pair<ll,ll>tmp={-inf,-inf};for(int j=1;j<=bl[n];j++)tmp=max(tmp,f[j].query());if(tmp.fi<=0)break;res+=tmp.fi,update(tmp.se);}cout<<res;
}