题目链接:https://codeforces.ml/contest/1428/problem/E
题意：给定n个数，要求将这些数拆分为k个数，是这些数的平方和最小。
题解：结构体，一开始想到的是每次分最大的数，平分。然鹅，1 3 10000.是分成3333 3333 3334显然更好。
换一换贪心思路。每一个数多拆分一种就有特定的平方和减小值，如10分成3：3 3 4，分成4 份：2 2 3 3减小值为8.
一个数分为k种，有特定的最小平方和（平分，见gv函数）。然后每一次只需要关注减小值最大的数。
代码：
#include <bits/stdc++.h>#define ll long long
#define pi acos(-1)
#define pb push_back
#define mst(a, i) memset(a, i, sizeof(a))
#define pll pair<ll, ll>
#define fi first
#define se second
#define dbg(x) cout << #x << "===" << x << endl
using namespace std;
template <class T> void read(T &x) {T res = 0, f = 1;char c = getchar();while (!isdigit(c)) {if (c == '-') f = -1;c = getchar();}while (isdigit(c)) {res = (res << 3) + (res << 1) + c - '0';c = getchar();}x = res * f;
}
void print(ll x) {if (x < 0) {putchar('-');x = -x;}if (x > 9) print(x / 10);putchar(x % 10 + '0');
}
const ll maxn = 1e5 + 10;
const ll mod = 1e9 + 7;ll n,k,x;
struct node{ll a,b,c;bool operator < (const node &b)const{return a<b.a;}
};
// ll gcd(ll a,ll b){return (b==0)?a:gcd(b,a%b);}
// ll qpow(ll a,ll p,ll mod){ll
// ans=1;a=a%mod;while(p){if(p&1)ans=(ans*a)%mod;p>>=1;a=(a*a)%mod;}return ans;}
// ll vis[maxn],prime[maxn],x=0;
// void oulasai(ll n){for(ll i=2;i<=n;i++){if(!vis[i]) prime[x++]=i;for(int
// j=0;j<x;j++){if(i*prime[j]>n) break;vis[i*prime[j]]=true;if(i%prime[j]==0)
// break;}}}
/*?组合数
ll fac[maxn],re[maxn],inv[maxn];
//void init(ll n){inv[0]=inv[1]=fac[0]=fac[1]=re[0]=re[1]=1;for(ll
i=2;i<=n;i++){fac[i]=fac[i-1]*i%mod;inv[i]=(mod-mod/i)*inv[mod%i]%mod;re[i]=re[i-1]*inv[i]%mod;}}
ll C(ll n,ll m){return fac[n]%mod*re[m]%mod*re[n-m]%mod;}
*/
// ll inv(ll a){return a==1?1:(ll)(mod-mod/a)*inv(mod%a)%mod;}
// void exgcd(ll a,ll b){if(b==0){x=1,y=0;g=a;return ;}exgcd(b,a%b);ll
// tmp=y;y=x-(a/b)*y;x=tmp;return ;}
/*
ll fa[maxn],dep[maxn],
ll find(ll x){ll r=x,p;while(r!=fa[r]) r=fa[r];while(x!=r)
p=fa[x],fa[x]=r,x=p;return r;} void merge(ll x,ll y){ll
fx=find(x),fy=find(y);if(dep[fx]<dep[fy])
fa[fx]=fy;else{fa[fy]=fx;if(dep[fx]==dep[fy]) dep[fx]++;}return ;}
*/ll gv(ll a,ll x){//?a被切成x份 ll m=a/x,t=a%x;return t*(m+1)*(m+1)+(x-t)*m*m;
}
priority_queue<node> q;
int main() {ll _s = 1;//read(_s);for (ll _ = 1; _ <= _s; _++) {read(n),read(k);ll ans=0;for(ll i=1;i<=n;i++){read(x);q.push({gv(x,1)-gv(x,2),x,2});ans+=x*x;}for(ll i=1;i<=k-n;i++){node now=q.top();q.pop();ll a=now.a,b=now.b,c=now.c;ans-=a;q.push({gv(b,c)-gv(b,c+1),b,c+1});}cout<<ans<<endl;}return 0;
}
//不正确，不轻易运行
/*
input:::
output:::*/