Cow Dating

题目描述

由于对目前奶牛可用的平庸约会网站（例如 eHarmoony、Moosk、Plenty of Cows）不满意，农夫 John 决定推出一个新的奶牛约会网站，使用一套华丽的专有匹配算法，根据奶牛与公牛在各种共同兴趣上的契合程度进行配对。 Bessie 为了寻找情人节谷仓舞会的舞伴，决定试用该网站。建立账号后，FJ 的算法给了她一个包含 $N$ 个潜在匹配对象的列表（$1\leq N \leq 10^6$）。浏览列表时，Bessie 认为第 $i$ 头公牛以概率 $p_i$（$0<p_i<1$）接受她参加舞会的邀请。 Bessie 决定向列表中某个连续区间内的每一头公牛发送邀请。她一向很正直，只想要恰好一位舞伴。请帮助 Bessie 找到：如果她选择了最优的区间，收到恰好一份邀请被接受的最大概率是多少。

输入格式

第一行输入 $N$（$1 \leq N \leq 10^6$）。接下来的 $N$ 行中，每行包含 $10^6$ 倍的 $p_i$，为一个整数。 在至少 25% 的测试用例中，额外保证 $N \leq 4000$。

输出格式

输出 $10^6$ 倍的“收到恰好一份邀请被接受”的最大概率，向下取整到最近的整数。

3
300000
400000
350000

470000

提示

最大概率来自选择从第 2 头到第 3 头奶牛对应的区间。 注意：解决此题时需要对浮点精度稍加小心。建议至少使用 “double”（64 位浮点数），不要使用 “float”（32 位浮点数）。 题目贡献者：Ethan Guo

标签: USACO|2019|Platinum

来源

USACO|2019|Platinum