TouchStone
  Please Login
ログイン 登録
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P4086
  • 問題
  • P4086【SDOI2017】新生舞会
    制限 : 時間制限 : 12000 MS   メモリ制限 : 131072 KB
    審判説明 : 1s,128MB
    問題説明

    学校组织了一次新生舞会,Cathy 作为经验丰富的老学姐,负责为同学们安排舞伴。

    \(n\) 个男生和 \(n\) 个女生参加舞会,一个男生和一个女生一起跳舞,互为舞伴。
    Cathy 收集了这些同学之间的关系,比如两个人之前是否认识,计算得出 \(a_{i, j}\),表示第 \(i\) 个男生和第 \(j\) 个女生一起跳舞时他们喜悦程度。
    Cathy 还需要考虑两个人一起跳舞是否方便,比如身高体重差别会不会太大,计算得出 \(b_{i, j}\) 表示第 \(i\) 个男生和第 \(j\) 个女生一起跳舞时的不协调程度。

    当然,还需要考虑很多其他间题。

    Cathy 想先用一个程序通过 \(a_{i, j}\)\(b_{i, j}\) 求出一种方案,再手动对方案进行微调。
    Cathy 找到你,希望你帮她写那个程序。

    一个方案中有 \(n\) 对舞伴,假设每对舞伴的喜悦程度分别是 \(a'_1, a'_2, \ldots, a'_n\),假设每对舞伴不协调程度分别是 \(b'_1, b'_2, \ldots, b'_n\)。令

    \[ C = \frac{a'_1 + a'_2 + \cdots + a'_n}{b'_1 + b'_2 + \cdots + b'_n} \]

    Cathy 希望 C 值最大。

    入力形式

    第一行一个整数 \(n\)
    接下来 \(n\) 行,每行 \(n\) 个正整数,第 \(i\) 行第 \(j\) 个数表示 \(a_{i, j}\)
    接下来 \(n\) 行,每行 \(n\) 个正整数,第 \(i\) 行第 \(j\) 个数表示 \(b_{i, j}\)

    出力形式

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

    サンプル入力

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

    サンプル出力

    5.357143

    ヒント

    样例输入

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

    样例输出

    5.357143
    

    对于 \(10\%\) 的数据,\(1 \leq n \leq 5\)
    对于 \(40\%\) 的数据,\(1 \leq n \leq 18\)
    另外存在 \(20\%\) 的数据,\(b_{i, j} = 1\)
    对于 \(100\%\) 的数据,\(1 \leq n \leq 100, 1 \leq a_{i, j} \leq 10 ^ 4,1 \leq b_{i, j} \leq 10 ^ 4\)


    ソース  感谢1879570236获取数据并搬运,nodgd优化排版