记录编号	249565	评测结果	AAAAAAAAAA
题目名称	[SDOI 2016 Round1] 数字配对	最终得分	100
用户昵称	613	是否通过	通过
代码语言	C++	运行时间	0.033 s
提交时间	2016-04-13 00:36:09	内存使用	11.25 MiB

#include<bits/stdc++.h>
#define LL long long
#define LD double
using namespace std;//%I64d
#define eps 1e-15
#define maxn 1100
LD func[maxn],mts[maxn][maxn],ans,con[maxn];
bool bo[maxn];
LL ru[maxn];
LL n,m;
inline void pivot(LL x,LL pt)
{
	int y=ru[pt];
	for (int i=1;i<=n;i++) if (i!=x) mts[pt][i]/=mts[pt][x];con[pt]/=mts[pt][x];mts[pt][x]=1;
	bo[x]=true;bo[y]=false;ru[pt]=x;
	for (int i=1;i<=m;i++) if (i!=pt)
	{
		if (abs(mts[i][x])<eps) continue;
		for (int j=1;j<=n;j++) if (j!=x) mts[i][j]-=mts[i][x]*mts[pt][j];
		con[i]-=mts[i][x]*con[pt];
		mts[i][x]=0;
	}
	for (int i=1;i<=n;i++) if (i!=x) func[i]-=func[x]*mts[pt][i];
	ans+=con[pt]*func[x];
	func[x]=0;
}
int simplex()
{
	ans=0;
	while (1)
	{
		LD mx=-1;int id;
		for (int i=1;i<=n;i++)
		{
			if (bo[i]) continue;
			if (func[i]>mx) {mx=func[i];id=i;}
		}
		if (mx<eps) return 0;
		mx=1e15;int wei=0;
		for (int i=1;i<=m;i++)
		{
			if (mts[i][id]<eps) continue;
			if (con[i]/mts[i][id]<mx)
			{
				mx=con[i]/mts[i][id];
				wei=i;
			}
		}
		pivot(id,wei);
	}
}
LL a[40010],b[40010],c[40010],top;
vector<LL> des[40010];
LL val[40010];
bool isprime(LL x)
{
	for (LL i=2;i*i<=x;i++)
	{
		if (x%i==0) return false;
	}
	return true;
}
int main()
{
	freopen("menci_pair.in","r",stdin);
	freopen("menci_pair.out","w",stdout);
	LL pn;scanf("%lld",&pn);
	for (LL i=1;i<=pn;i++) scanf("%lld",&a[i]);
	for (LL i=1;i<=pn;i++) scanf("%lld",&b[i]);
	for (LL i=1;i<=pn;i++) scanf("%lld",&c[i]);

	for (LL i=1;i<=pn;i++)
	for (LL j=1;j<=pn;j++)
	{
		if (i==j) continue;
		if ((a[i]%a[j]==0)&&(isprime(a[i]/a[j])))
		{
			//mp[make_pair(i,j)]=++top;
			top++;
			des[i].push_back(top);
			des[j].push_back(top);
			val[top]=c[i]*c[j];
		}
	}
	for (LL i=1;i<=pn;i++)
	{
		m++;
		for (LL k=0;k<des[i].size();k++) mts[m][des[i][k]]=1;
		con[m]=b[i];
	}
	m++;
	for (LL i=1;i<=top;i++) mts[m][i]=-val[i];
	n=top;
	for (LL i=1;i<=m;i++)
	{
		bo[++n]=true;
		ru[i]=n;
		mts[i][n]=1;
	}
	for (LL i=1;i<=top;i++) func[i]=1;
	
	simplex();
	printf("%lld\n",(LL)(ans+0.1));
}