记录编号	56482	评测结果	AAAAAAAAAA
题目名称	[HAOI 2010]工厂选址	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.749 s
提交时间	2013-03-30 14:28:52	内存使用	11.19 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int m,n;//m个煤矿,n个备选厂址
//n<=50,m<=50000
int h0;//第一个电站的固定费用
int b;//第一个电站的需煤量
int a[50005]={0};//每个煤矿的年产量
int h[55]={0};//第i个备选厂址的固定费用
int c0[50005]={0};//第i个矿到第一个电厂的单位运费
int c[50005][55]={0};//第i个矿运到第j个厂址的单位运费
//注意:编号为1开始
int ans;//最佳厂址
long long lcost=0xffffffff;//最小花费
void read(void){
	scanf("%d%d%d%d",&m,&b,&h0,&n);
	int i,j;
	for(i=1;i<=m;i++) scanf("%d",&a[i]);
	for(i=1;i<=n;i++) scanf("%d",&h[i]);
	for(i=1;i<=m;i++) scanf("%d",&c0[i]);
	for(j=1;j<=n;j++){
		for(i=1;i<=m;i++) scanf("%d",&c[i][j]);
	}
}
class PAIR{
public:
	int num;//编号
	int sub;//差值
};
bool cmp(PAIR a,PAIR b){
	return a.sub>b.sub;
}//去1的单价-去2的单价越小越好
void relax(int x){//选取x厂,进行更新
	long long now=0;//现在的总费用
	long long carry=0;//总运费
	int coal=0;//一厂的煤
	now+=h[x];
	int i;
	PAIR s[50005]={0};//每个矿的编号和到两个厂的差值
	for(i=1;i<=m;i++){
		s[i].num=i;
		s[i].sub=c0[i]-c[i][x];
		carry+=a[i]*c0[i];//先全部运到一号厂
		coal+=a[i];
	}
	sort(s+1,s+1+m,cmp);
	i=1;
	while(1){
		if(coal-a[s[i].num]>=b){
			carry-=a[s[i].num]*c0[s[i].num];
			carry+=a[s[i].num]*c[s[i].num][x];
			coal-=a[s[i].num];
			//从一厂换到现在的厂
		}
		else{
			carry-=(coal-b)*c0[s[i].num];
			carry+=(coal-b)*c[s[i].num][x];
			coal=b;
			break;
		}
		i++;
	}
	now=carry+h[x]+h0;
	if(now<lcost){
		lcost=now;
		ans=x;
	}
}
int main(){
	freopen("factory1.in","r",stdin);
	freopen("factory1.out","w",stdout);
	read();
	for(int i=1;i<=n;i++) relax(i);
	printf("%d\n%lld\n",ans,lcost);
	return 0;
}