原题链接

题解

每个种族的贡献是互不干扰的，因此只需要计算每个族群在每个组数的情况下的解然后累加就行了，由于每个族群在组数大于等于 \(c_i\) 的时候解数不变，所以这里用到了差分小技巧
然后就是计算每个族群在每个组数下的解就行了

code

#define ll long long
#include<bits/stdc++.h>
using namespace std;
vector<ll> G[200005];
ll f[200005]={0};
ll func(ll a,ll k)//计算a个人，k个位置，能产生的最大贡献
{
    ll q1=a/k+1,x1=a%k,q2=a/k,x2=k-a%k;
    return q1*q1*x1*(x1-1)/2+q2*q2*x2*(x2-1)/2+q1*x1*q2*x2;
}
inline void read(ll &x) {
    x = 0;
    ll flag = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')flag = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    x *= flag;
}

inline void write(ll x)
{
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}

int main()
{
    ll t;
    read(t);
    while(t--)
    {
        memset(f,0,sizeof f);
        ll n,b,x,maxc=0;
        read(n);read(b);read(x);
        for(ll i=1;i<=n;i++)
        {
            ll c;
            read(c);
            maxc=max(c,maxc);
            for(ll j=1;j<c;j++)//不知道为什么不会T
            {
                ll cur=func(c,j);
                f[j]+=cur;
                f[j+1]-=cur;
            }
            f[c]+=func(c,c);//达成c之后f的值与c相同，实质是差分，后面要通过传递求回来
        }

        for(ll i=1;i<=maxc;i++)
        {
            f[i]+=f[i-1];
        }
        ll ans=0;
        for(ll i=1;i<=maxc;i++)
        {
            f[i]=f[i]*b-(i-1)*x;
            ans=max(ans,f[i]);
        }

        write(ans);
        putchar('\n');
    }
    return 0;

}