先给每个 赋值为 .
此时 ,和题目要求的 还差
每次选择一个 增加 ,重复 次。
每次操作时, 加在谁那里使得 最小,就加给谁。由于二次函数是单谷的 ,所以每次操作最优 整体最优。
由于 和 比较大,所以需要使用优先队列。
#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[100005],b[100005],c[100005],x[100005];
struct node{
int a,b,c,x,pos;
bool operator< (const node& g) const{
int nw=(2*x+1)*a+b;
int nw2=(2*g.x+1)*g.a+g.b;
return nw>nw2;
}
};
priority_queue<node> Q;
int n,m;
int calc(){
int res=0;
for(int i=1;i<=n;i++){
res+=a[i]*x[i]*x[i]+b[i]*x[i]+c[i];
}
return res;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i]>>b[i]>>c[i];
x[i]=1;
Q.push({a[i],b[i],c[i],x[i],i});
}
int C=m-n;
while(C--){
node g=Q.top();
Q.pop();
int i=g.pos;
x[i]++;
Q.push({a[i],b[i],c[i],x[i],i});
}
cout<<calc()<<endl;
return 0;
}