题意：
已知一个正整数数组 \(a\) 的长度是 \(m\) ，里面所有数字的和是 \(n\) 且任何两个相邻数字差的绝对值不超过 \(K\). 求 \(a\) 最大的可能方差乘上 \(m^2\) 的结果。如果 \(a\) 不存在输a出 \(-1\).
多测，\(n,k \le 10^8,m \le 100\)
首先特判 \(n<m\) 和 \(k=0\) 的情况，这是简单的。
考虑方差计算公式
\[s^2=\frac{1}{m}\sum_{i=1}^m (a_i-\overline{a})^2 \]其中 \(\overline{a}\) 为 \(a\) 的平均数。其乘上 \(m^2\) 后化简为
\(ms^2=(m\sum a_i^2)-n^2\).
所以我们只需要最大化 \(\sum a_i^2\) 的值即可。
考虑由基本不等式得到 \((x+y)^2>x^2+y^2\). 所以差尽可能大，即 \(x+1,y-1\) 会比 \(x,y\) 优秀.
因此考虑让前面的数差为 \(k\)，剩下的数字从后往前添加即可。（从前往后填会有一个位置差为 \(k+1\)）
但注意到每段非空所以开始的时候每一段都 \(+1\) 然后 \(n \leftarrow n-m\).
#include<bits/stdc++.h>
#define rep(i,a,b) for(ll i=(a);i<=(b);i++)
#define per(i,a,b) for(ll i=(a);i>=(b);i--)
#define op(x) ((x&1)?x+1:x-1)
#define odd(x) (x&1)
#define even(x) (!odd(x))
#define lc(x) (x<<1)
#define rc(x) (lc(x)|1)
#define lowbit(x) (x&-x)
#define Max(a,b) (a>b?a:b)
#define Min(a,b) (a<b?a:b)
#define next Cry_For_theMoon
#define il inline
#define pb(x) push_back(x)
#define is(x) insert(x)
#define sit set<int>::iterator
#define mapit map<int,int>::iterator
#define pi pair<int,int>
#define ppi pair<int,pi>
#define pp pair<pi,pi>
#define fr first
#define se second
#define vit vector<int>::iterator
#define mp(x,y) make_pair(x,y)
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef double db;
using namespace std;
const int MAXN=110;
ll T,n,m,k,c[MAXN],ans;
int main(){
scanf("%lld",&T);
while(T--){
scanf("%lld%lld%lld",&n,&m,&k);
if(n<m){printf("-1\n");continue;}
if(!k){printf("%d\n",(n%m)?-1:0);continue;}
ans=-n*n;
rep(i,1,m)c[i]=1;
n-=m;
rep(i,1,m){
//前i个+=k
ll use=i*k;
if(use>n || i==m){
ll rest=n;
rep(j,1,i)c[j]+=rest/i;
rest%=i;
rep(j,1,rest){
c[i-j+1]++;
}
break;
}else{
rep(j,1,i)c[j]+=k;
n-=use;
}
}
rep(i,1,m)ans+=m*c[i]*c[i];
cout<<ans<<endl;
}
return 0;
}