记录编号	23307	评测结果	AAAAAAAAAA
题目名称	[HAOI 2010]工厂选址	最终得分	100
用户昵称	苏轼	是否通过	通过
代码语言	C++	运行时间	1.487 s
提交时间	2011-03-07 13:59:50	内存使用	0.41 MiB

#include <cstdio>
#include <queue>

using namespace std;

FILE *fin = fopen("factory1.in", "r"),
	 *fout = fopen("factory1.out", "w");

struct hnode {
	signed char less;
	short fac;
};

inline bool operator < (const hnode &a, const hnode &b)
{
	return a.less < b.less;
}

int main ()
{
	unsigned short M, B;
	unsigned char N, H[51], C[50001];
	hnode A[50001];

	fscanf(fin, "%hu%hu%hhu%hhu", &M, &B, H, &N);

	for (unsigned short i=1; i<=M; i++)
		fscanf(fin, "%hd", &((A+i)->fac));
	for (unsigned short i=1; i<=N; i++)
		fscanf(fin, "%hhu", H+i);
	for (unsigned short i=1; i<=M; i++)
		fscanf(fin, "%hhu", C+i);

	int minp = 0x7FFFFFFF;
	unsigned char minf;
	for (unsigned char i=1; i<=N; i++)
	{
		int sum;
		priority_queue<hnode> heap;

		if ((sum = H[i] + H[0]) + B >= minp)
		{
			fscanf(fin, "%*[^\n]");
			continue;
		}

		for (unsigned short j=1; j<=M; j++)
		{
			unsigned char cij;
			fscanf(fin, "%hhu", &cij);
			sum += cij * A[j].fac;
			A[j].less = cij - C[j];
			heap.push(A[j]);
		}

		unsigned short count = B;
		while (count)
		{
			const hnode &top = heap.top();
			if (top.fac < count)
			{
				sum -= top.fac*top.less;
				count -= top.fac;
				heap.pop();
			}
			else
			{
				sum -= count * top.less;
				count = 0;
			}
		}

		if (sum < minp)
			minp = sum, minf = i;
	}

	fprintf(fout, "%hhd\n%d\n", minf, minp);

	fclose(fin);
	fclose(fout);

	return 0;
}