C++14(g++5.4) 解法, 执行用时: 89ms, 内存消耗: 3284K, 提交时间: 2019-07-29 18:39:34

#include<bits/stdc++.h>
using namespace std;
struct node{
	int aa,b;
	long long p;
	bool operator <(const node& tt)const {
		return p>tt.p;
	}
};
priority_queue<node>q;
long long gao(int x,int t)
{
	long long ans=1ll*x*(x-t)*(x-t);
	return ans;
}
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		int x;
		cin>>x;
		long long h=gao(x,1)-gao(x,0);
		q.push(node{x,0,h});
	}
	for(int i=1;i<=m;i++)
	{
		node pp=q.top();
		q.pop();
		pp.b++;
		pp.p=gao(pp.aa,pp.b+1)-gao(pp.aa,pp.b);
		q.push(pp);
	}
	long long res=0;
	while(!q.empty())
	{
		node tp=q.top();
		q.pop();
		res+=gao(tp.aa,tp.b);
	}
	cout<<res<<'\n';
}

C++11(clang++ 3.9) 解法, 执行用时: 69ms, 内存消耗: 4708K, 提交时间: 2019-07-27 10:38:16

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node{
	ll a,s,c;
	int b;
	bool operator<(const node& x)const{
		return x.c>c;
	}
};
ll cal(ll x,ll y){
	return x*(x-y)*(x-y);
}
priority_queue<node>q;
int main(){
	int n,m;
	node t;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%lld",&t.a);
		t.b=0;
		t.s=cal(t.a,t.b);
		t.c=t.s-cal(t.a,t.b+1);
		q.push(t);
	}
	for(int i=1;i<=m;i++){
		t=q.top();
		q.pop();
		t.b++;
		t.s=cal(t.a,t.b);
		t.c=t.s-cal(t.a,t.b+1);
		q.push(t);
	}
	ll ans=0;
	while(!q.empty()){
		ans+=q.top().s;
		q.pop();
	}
	printf("%lld\n",ans);
}