记录编号	395555	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	搭配营养	最终得分	100
用户昵称	再见	是否通过	通过
代码语言	C++	运行时间	0.782 s
提交时间	2017-04-16 17:53:27	内存使用	1.40 MiB

#include <cstdio>
#include <cstdlib>
#include <cmath>
const long double eps=1e-10;
const long double INF=1e18;

int n,m,N[310],cnt,x0,flag;
long double l,L,R,r,v,a[310][310],c[310],b[310],orc[310];

void change(int l,int e){
	N[l]=true; N[e]=false;
	v+=c[e]*b[l]/a[l][e];
	for(int i=x0;i<=cnt;i++)
		if(N[i])
			c[i]-=c[e]*a[l][i]/a[l][e];
	c[l]=-c[e]/a[l][e];
	for(int j=x0;j<=cnt;j++)
		if(!N[j])
			b[j]-=a[j][e]*b[l]/a[l][e];
	b[e]=b[l]/a[l][e];
	for(int j=x0;j<=cnt;j++)
		if(!N[j]){
			for(int i=x0;i<=cnt;i++)
				if(N[i])
					a[j][i]-=a[j][e]*a[l][i]/a[l][e];
			a[j][l]=-a[j][e]/a[l][e];
		}
	for(int i=x0;i<=cnt;i++)
		if(N[i])
			a[e][i]=a[l][i]/a[l][e];
	a[e][l]=1.0/a[l][e];
}

void work(){
	while(true){
		int e=-1,l=-1; long double MA=INF;
		for(int i=x0;i<=cnt;i++)
			if(N[i]&&c[i]>eps){
				e=i;
				break;
			}
		if(e<0) return;
		for(int i=x0;i<=cnt;i++)
			if(!N[i]&&a[i][e]>eps&&MA>b[i]/a[i][e]){
				MA=b[i]/a[i][e];
				l=i;
			}
		if(l<0) {flag=true; return;}
		change(l,e);
	}
}

bool init(){
	int l=0;
	for(int i=1;i<=cnt;i++)
		if(!N[i]&&(!l||b[l]>b[i]))
			l=i;
	if(b[l]>eps) return true;
	x0=0; N[0]=true;
	for(int i=1;i<=cnt;i++) 
		if(!N[i])
			a[i][0]=-1;
	for(int i=1;i<=cnt;i++)
		orc[i]=c[i],c[i]=0;
	c[0]=-1;
	change(l,0);
	work();
	if(v<-eps) return false;
	for(int i=1;i<=cnt;i++)
		c[i]=orc[i];
	if(!N[0]){
		int e=0;
		for(int i=1;i<=cnt;i++)
			if(N[i]){
				e=i;
				break;
			}
		change(0,e);
	}
	for(int i=1;i<=cnt;i++)
		c[i]=orc[i];
	for(int i=1;i<=cnt;i++)
		if(!N[i]&&fabs(c[i])>eps){
			v=v+c[i]*b[i];
			for(int j=1;j<=cnt;j++)
				if(N[j])
					c[j]-=c[i]*a[i][j];
			c[i]=0;
		}
	x0=1;
	return true;
}

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,&r,&L,&R);
		b[i]=r-R; b[i+n]=L-l;
	}
	scanf("%d",&m);
	for(int i=1;i<=m;i++)
		for(int j=1;j<=n;j++){
			long double x; scanf("%Lf",&x);
			a[j][n+n+i]=x;
			a[j+n][n+n+i]=-x;
		}
	for(int i=1;i<=m;i++) c[i+n+n]=-1;
	for(int i=1;i<=m;i++) N[i+n+n]=true;
	cnt=n+n+m;
	if(!init()){
		printf("FoolMike\n");
		return 0;
	}
	work();
	v=-v*1000000.0;
	printf("%.0lf",round(v));
	return 0;
}