比赛 |
Mike梦境膜你赛 |
评测结果 |
AAAAAAAAAAAAAAAAAAAA |
题目名称 |
搭配营养 |
最终得分 |
100 |
用户昵称 |
再见 |
运行时间 |
0.764 s |
代码语言 |
C++ |
内存使用 |
1.40 MiB |
提交时间 |
2017-04-14 21:09:05 |
显示代码纯文本
#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;
}