/ Vijos / 题库 /

新生舞会

新生舞会

描述

学校组织了一次新生舞会,Cathy作为经验丰富的老学姐,负责为同学们安排舞伴。(学姐我要和你跳舞!)

有n个男生和n个女生参加舞会,一个男生和一个女生一起跳舞,互为舞伴。(学姐你的舞伴是我!)

Cathy收集了这些同学之间的关系,比如两个人之前是否认识,计算出ai,ja_{i,j},表示第i个男生和第j个女生一起跳舞时他们的喜悦程度。

Cathy还需要考虑两个人一起跳舞是否方便,比如身高体重差别会不会太大,计算得出bi,jb_{i,j},表示第i个男生和第j个女生一起跳舞的时候的不协调程度。

当然还需要考虑很多其它问题。

Cathy想用一个程序通过ai,ja_{i,j}bi,jb_{i,j}求出一种方案,再手动对方案进行微调。

Cathy找到你,希望你帮她写那个程序。

一个方案中有n对舞伴,假设每对舞伴的喜悦程度分别是a1,a2,,ana_1^{'},a_2^{'},\cdots,a_n^{'},假设每对舞伴的不协调程度分别是b1,b2,,bnb_1^{'},b_2^{'},\cdots,b_n^{'},令

C=a1+a2++anb1+b2++bnC={{a_1^{'}+a_2^{'}+\cdots+a_n^{'}} \over {b_1^{'}+b_2^{'}+\cdots+b_n^{'}}}

Cathy希望C值最大。

格式

输入格式

第一行一个整数n。

接下来n行,每行n个正整数,第i行第j个数表示ai,ja_{i,j}

接下来n行,每行n个正整数,第i行第j个数表示bi,jb_{i,j}

输出格式

一行一个数,表示C的最大值,四舍五入保留6位小数。选手输出的小数需与标准输出相等。

样例1

样例输入1

3
19 17 16
25 24 23
35 36 31
9 5 6
3 4 2
7 8 9

样例输出1

5.357143

限制

对于10%的数据,1n51\le n\le 5

对于40%的数据,1n181\le n\le 18

另外存在20%的数据,bi,j=1b_{i,j}=1

对100%的数据,1n1001\le n\le 1001ai,j1041\le a_{i,j}\le 10^41bi,j1041\le b_{i,j}\le 10^4

来源

SDOI 2017 Round1 Day2

信息

ID
2016
难度
5
分类
(无)
标签
递交数
76
已通过
27
通过率
36%
被复制
2
上传者

相关

在下列训练计划中:

RP++分类题库