记录编号	268852	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016]最小函数值	最终得分	100
用户昵称	洛克索耶夫	是否通过	通过
代码语言	C++	运行时间	0.605 s
提交时间	2016-06-12 20:10:21	内存使用	6.04 MiB

#include<bits/stdc++.h>
using namespace std;

int Read()
{
	int a = 0, minus = 1;
	char ch = getchar();
	if(ch == '-')       minus = -1;
	while(ch < '0' || ch > '9'){
		ch = getchar();
		if(ch == '-')	minus = -1;
	}
	while(ch >= '0' && ch <= '9'){
		a = a * 10 + ch - '0';
		ch = getchar();
	}
	return a * minus;
}

int a[500100], b[500100], c[500100];
struct Node{
	long long num, i, x;
	//num:函数值, i:第几个函数
	Node()
	{
		num = i = x = 0;
	} 
	bool operator < (const Node& a)const
	{
		return a.num <num;
	}
	//运算符'<'重载 
};
Node node;
priority_queue <Node> Q;

inline int f(const int& i, const int& x) 
{
	return a[i] * x * x + b[i] * x + c[i]; 
} 

int main()
{
	freopen("minval.in", "r", stdin);
	freopen("minval.out", "w", stdout);
	int n = Read(), m = Read();
	for(int i = 1; i <= n; i++){
		a[i] = Read(); b[i] = Read(); c[i] = Read();
		//函数都在增区间内
	}	
		
	for(int i = 1; i <= n; i++){
		node.num = f(i, 1);
		node.x = 1;
		node.i = i;
		Q.push(node);
	}
		
	for(int i = 1; i <= m; i++)	{
		Node tmp = Q.top();
		printf("%lld ", tmp.num); Q.pop();
		tmp.x++;
		tmp.num = f(tmp.i, tmp.x);
		Q.push(tmp);
	}
		
	fclose(stdin);
	fclose(stdout);
	return 0;
}
/*
3 10
4 5 3
3 4 5
1 7 1

9 12 12 19 25 29 31 44 45 54
*/