#6562. 小奇探险

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: hzwer

题目描述

小奇去遗迹探险,遗迹里有 N 个宝箱,有的装满了珠宝,有的装着废品。

小奇有地图,所以它知道每一个宝箱的价值,但是它不喜欢走回头路,所以要按顺序拿这 N 个宝箱中的若干个。

拿宝箱很累的。一开始小奇的体力是 1 ,每得到一个宝箱之后,小奇得到的价值是体力 \times 宝箱的价值,之后它的体力就会变为原来的 k (0<k<1)

小奇不喜欢连续放过很多宝箱,所以任意一段长度为 M 的序列中,小奇一定要取走其中的一个宝箱。

现在小奇想知道它能得到的最大价值和。

输入格式

第一行,两个整数 N,M ,表示的含义如题目中所述;

第二行,一个小数 k ,表示的含义如题目中所述,最多 4 位小数;

第三行, N 个整数,第 i 个整数表示第 i 个宝箱的价值。

输出格式

输出一行,一个实数,表示小奇能得到的最大价值和,四舍五入保留两位小数。

样例

样例输入

3 2
0.1
1 2 3

样例输出

2.30

数据范围与提示

对于 30\% 的数据,有 1\le N\le 10
对于 60\% 的数据,有 1\le N\le 1000
对于 100\% 的数据,有 1\le N\le 100000 1\le M\le N 0<k<1 -10^9\le 所有宝箱的价值 \le 10^9
本题版权归 Trinkle23897 所有