A6002. 小奇探险
编程题
普及+/提高
知识点
题目描述
小奇去遗迹探险，遗迹里有 $N$ 个宝箱，有的装满了珠宝，有的装着废品。
小奇有地图，所以它知道每一个宝箱的价值，但是它不喜欢走回头路，所以要按顺序拿这 $N$ 个宝箱中的若干个。
拿宝箱很累的。一开始小奇的体力是 $1$，每得到一个宝箱之后，小奇得到的价值是体力 $\times$ 宝箱的价值，之后它的体力就会变为原来的 $k$ 倍 $(0<k<1)$。
小奇不喜欢连续放过很多宝箱，所以任意一段长度为 $M$ 的序列中，小奇一定要取走其中的一个宝箱。
现在小奇想知道它能得到的最大价值和。
小奇有地图，所以它知道每一个宝箱的价值，但是它不喜欢走回头路，所以要按顺序拿这 $N$ 个宝箱中的若干个。
拿宝箱很累的。一开始小奇的体力是 $1$，每得到一个宝箱之后，小奇得到的价值是体力 $\times$ 宝箱的价值，之后它的体力就会变为原来的 $k$ 倍 $(0<k<1)$。
小奇不喜欢连续放过很多宝箱，所以任意一段长度为 $M$ 的序列中，小奇一定要取走其中的一个宝箱。
现在小奇想知道它能得到的最大价值和。
输入格式
第一行，两个整数 $N,M$，表示的含义如题目中所述；
第二行，一个小数 $k$，表示的含义如题目中所述，最多 $4$ 位小数；
第三行，$N$ 个整数，第 $i$ 个整数表示第 $i$ 个宝箱的价值。
第二行，一个小数 $k$，表示的含义如题目中所述，最多 $4$ 位小数；
第三行，$N$ 个整数，第 $i$ 个整数表示第 $i$ 个宝箱的价值。
输出格式
输出一行，一个实数，表示小奇能得到的最大价值和，四舍五入保留两位小数。
输入输出样例
输入 #1
3 2 0.1 1 2 3
输出 #1
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 所有**
对于 $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 所有**