记录编号	394043	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	搭配营养	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.139 s
提交时间	2017-04-12 19:54:04	内存使用	8.10 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
typedef double db;
const int N=1010;
const db eps=1e-10;
int n,m;
db a[N][N],l[N],r[N],L[N],R[N];
void pivot(int x,int y){
	db t=-a[x][y];a[x][y]=-1;
	for (int i=0;i<=m;i++) a[x][i]/=t;
	for (int i=0;i<=n;i++)
	if (i!=x){
		db t=a[i][y];a[i][y]=0;
		for (int j=0;j<=m;j++) a[i][j]+=t*a[x][j];
	}
}
db simplex(){
	static int cnt=0;
	while (1){//初始化可行解 
		int x=0,y=0;
		for (int i=1;i<=n;i++)
			if (a[i][0]<-eps){x=i;break;}
		if (!x) break;
		for (int i=1;i<=n;i++)
			if (a[x][i]>eps) y=i;
		if (!y) puts("FoolMike"),exit(0);//无解 
		pivot(x,y);cnt++;
		if (cnt>=2e4) puts("FoolMike"),exit(0);//防止挂掉,其实并没有用 
	}
	//printf("%d\n",cnt);
	while (1){//求最优解 
		int x=0,y=0;
		for (int i=1;i<=m;i++)
			if (a[0][i]>eps){y=i;break;}
		if (!y) return a[0][0];
		db lim=1e10;
		for (int i=1;i<=n;i++)
			if (a[i][y]<-eps&&-a[i][0]/a[i][y]<lim)
				lim=-a[i][0]/a[i][y],x=i;
		pivot(x,y);
	}
}
int main()
{
	freopen("nutrition.in","r",stdin);
	freopen("nutrition.out","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<=n;i++){
		scanf("%lf%lf%lf%lf",&l[i],&r[i],&L[i],&R[i]);
		if (R[i]-L[i]>r[i]-l[i]) puts("FoolMike"),exit(0);
		a[i][0]=L[i]-l[i];
		a[i+n][0]=r[i]-R[i];
	}
	scanf("%d",&m);
	for (int i=1;i<=m;i++)
	for (int j=1;j<=n;j++){
		db k;
		scanf("%lf",&k);
		a[j][i]=k;
		a[j+n][i]=-k;
	}
	for (int i=1;i<=m;i++) a[0][i]=-1;
	n*=2;
	db ans=-simplex()*1e6;
	printf("%lld\n",(long long)(ans+0.5));
	return 0;
}