记录编号	569267	评测结果	AAAAAAAAAA
题目名称	[NOI 1999]棋盘分割	最终得分	100
用户昵称	op_组撒头屯	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2022-02-27 21:41:20	内存使用	0.00 MiB

#include <bits/stdc++.h>
using namespace std;
const int N=10;
int n;
double x,mp[N][N]={0},ans=2<<20;
void dfs(int pt,int x1,int y1,int x2,int y2,double now){
	if (sqrt(now/n)>=ans)return ;
	if (pt==n){
		double t=mp[x2][y2]-mp[x1-1][y2]-mp[x2][y1-1]+mp[x1-1][y1-1];
		ans=min(ans,sqrt((now+(t-x)*(t-x))/n));
		return ;
	}
	for (int i=x1;i<=x2-1;i++){
		double t1,t2;
		t1=mp[i][y2]-mp[i][y1-1]-mp[x1-1][y2]+mp[x1-1][y1-1];
		t2=mp[x2][y2]-mp[i][y2]-mp[x2][y1-1]+mp[i][y1-1];
		dfs(pt+1,x1,y1,i,y2,now+(t2-x)*(t2-x));
		dfs(pt+1,i+1,y1,x2,y2,now+(t1-x)*(t1-x));
	}
	for (int i=y1;i<=y2-1;i++){
		double t1,t2;
		t1=mp[x2][i]-mp[x1-1][i]-mp[x2][y1-1]+mp[x1-1][y1-1];
		t2=mp[x2][y2]-mp[x1-1][y2]-mp[x2][i]+mp[x1-1][i];
		dfs(pt+1,x1,y1,x2,i,now+(t2-x)*(t2-x));
		dfs(pt+1,x1,i+1,x2,y2,now+(t1-x)*(t1-x));
	}
	return ;
}
int main(){
	freopen ("division.in","r",stdin);
	freopen ("division.out","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<=8;i++){
		for (int j=1;j<=8;j++){
			double t;
			scanf("%lf",&t);
			mp[i][j]=mp[i-1][j]+mp[i][j-1]+t-mp[i-1][j-1];
		}
	}
	x=mp[8][8]/n;
	dfs(1,1,1,8,8,0);
	printf("%.3lf\n",ans);
	return 0;
}