#P2460. [SDOI2007] 科比的比赛

[SDOI2007] 科比的比赛

题目描述

NBA球星云集,谁是最厉害的呢?没有定论。

Nba总裁大卫*斯特恩最近闲得无聊,决定举办一场球员单挑大赛。

比赛是这样的:首先,我们给每人都打上个分数,表示了每个人的整体能力。然后让每个参赛队员都打n场比赛,首先看谁赢得最多,然后看谁打赢的人的能力值的和最大。

本人一向支持科比(我不支持),当然希望他赢。现在让我们和科比一起去赢得这场比赛吧!!

(科比照片一张)

假设总共比赛有m+1个人参加,告诉你科比和另外m个人的比赛的胜利可能性,你的任务就是求出在科比赢了的所有比赛的可能性最大的前提下(误差不超过1e-10),科必打赢的人的最大能力值的和是多少?当然当一个人被你打败,他就不会再参加比赛了。

这里需要注意的是,科比能打赢其他人的可能性在不同场次是不同的。比如在比赛前期科比的手感不太好,对抗在内线称霸的人因为无法发挥外线的实力,而难以得分(接奥尼儿图一张)

中期时别人手感变好,状态起来,有实力的人会给科比制造很大的麻烦(接韦德图一张)

后期时消耗太多体力,对自己的命中率下降,难以发挥正常水平,所以对抗体力好的球员时占劣势(后接纳什图一张)

现在给你每场比赛科比对每个参赛者的获胜可能性,和每个人的能力值,帮助科比赢得比赛吧。

输入格式

第一行n,m(1<=n<<=10,n<=m<=100000),意义如题所述

接下来一行m个整数表示其他m个人的能力值si(1<=si<=100)

接下来是1个n*m的矩阵,描述在每场碰到每个人的获胜可能vij(0<=vij<=1)

输出格式

第一行输出最大获胜可能性

第二行输出最大能力值和

Special Judge

3 4
91 92 93 94
0.5 0.5 0.5 0.5
0.5 0.5 0.5 0.5
0.5 0.5 0.5 0.5
0.125
279