搜索+剪枝

//By:Komorebi_03
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e3+5;
const int M = 1e6+5;
int n,num,ans,p[N][N],q[N][N],sum[N][N];
bool vis[M];
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}

void init()
{
	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++)
			sum[i][j]=p[i][j]*q[j][i];
}

void dfs(int x)
{
	if(x==n+1)
	{
		ans=max(num,ans);
		return ;
	}
	int tot=0;
	for (int i=x;i<=n;i++)
	{
		int fk=0;
		for (int j=1;j<=n;j++)
			if(!vis[j])
				fk=max(fk,sum[i][j]);
		tot+=fk;
	}
	if(tot+num<=ans)
		return ;
	for (int i=1;i<=n;i++)
	{
		if(!vis[i])
		{
			num+=sum[x][i];
			vis[i]=true;
			dfs(x+1);
			vis[i]=false;
			num-=sum[x][i];
		}
	}
}

signed main()
{
	n=read();
	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++)
			p[i][j]=read();
	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++)
			q[i][j]=read();
	init();
	dfs(1);
	cout<<ans;
	return 0;
}