原题
韦神提供的思路orz
首先一个显然的性质，所有的c可以提出来，方程变成ax^2+bx的形式
因为x的值是离散的，而m的值又不大
所以一开始让x都为1（注意！x是正整数），然后每次挑一个x让他加一
这样做怎么保证正确？
注意二次函数的性质，由于a>=1，当x递增时斜率，函数值的变化量是递增的
可以贪一个
每次去变化率最小的那个方程，让它的x加一
现在不取，后边也不会更优，所以正确
变化率相同时并不需要比较函数形状
因为由变化率递增的性质，就算取了较坏的函数，下一步还是取较好函数的相同变化量，然后再下一步必定会取到较好函数
代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #include<cmath> 6 using namespace std; 7 #define LL long long 8 int rd(){int z=0,mk=1; char ch=getchar(); 9 while(ch<'0'||ch>'9'){if(ch=='-')mk=-1; ch=getchar();} 10 while(ch>='0'&&ch<='9'){z=(z<<3)+(z<<1)+ch-'0'; ch=getchar();} 11 return z*mk; 12 } 13 struct nds{LL x; int y;}hp[110000]; int sz=0; 14 int n,m; 15 LL a[110000],b[110000],c[110000]; 16 int d[110000]; 17 LL cclt(LL x,int y){ 18 return x*x*a[y]+x*b[y]; 19 } 20 void ist(nds x){ 21 hp[++sz]=x; 22 for(int i=sz;i>1 && hp[i].x<hp[i>>1].x;i>>=1) swap(hp[i],hp[i>>1]); 23 } 24 void pp(){ 25 swap(hp[1],hp[sz--]); 26 for(int i=1;;){ 27 int mn=hp[i].x,mnid=i; 28 if((i<<1)<=sz && hp[i<<1].x<mn) mn=hp[i<<1].x,mnid=(i<<1); 29 if((i<<1|1)<=sz && hp[i<<1|1].x<mn) mn=hp[i<<1|1].x,mnid=(i<<1|1); 30 if(i==mnid) break; 31 swap(hp[i],hp[mnid]); 32 i=mnid; 33 } 34 } 35 void prvs(){ 36 sz=0; 37 } 38 int main(){ 39 //freopen("ddd.in","r",stdin); 40 while(scanf("%d%d",&n,&m)!=EOF){ 41 prvs(); 42 for(int i=1;i<=n;++i) a[i]=rd(),b[i]=rd(),c[i]=rd(); 43 LL bwl=0; 44 for(int i=1;i<=n;++i){ 45 d[i]=1; 46 ist((nds){cclt(d[i]+1,i)-cclt(d[i],i),i}); 47 bwl+=cclt(d[i],i)+c[i]; 48 } 49 for(int i=n+1;i<=m;++i){ 50 LL mn=hp[1].x; int mnid=hp[1].y; 51 ++d[mnid]; 52 pp(); 53 ist((nds){cclt(d[mnid]+1,mnid)-cclt(d[mnid],mnid),mnid}); 54 bwl+=mn; 55 } 56 printf("%lld\n",bwl); 57 } 58 return 0; 59 }