题目描述

《神犇岛探险》是极其自虐的一款游戏。kAc浪费了无数人参之后,终于到了该游戏的奖励关。

奖励关是这样的:

有N个物品摆在kAc面前,按照顺序编号为1..n。第i个物品有价值a[i],价值可正可负。

kAc按照顺序依次经过这些物品。每经过一个物品的时候,他可以选择拿走或者不拿走。

kAc的初始体力值是1。每拿走一个物品后,他的体力值变为以前的k倍。(0 < k < 1)

为了增加难度,游戏规定:任意连续M个物品中,至少有一个要被拿走。

得分的计算方法:对于每一个拿走的物品,得分为该物品的价值*拿走该物品时的体力值。总得分为所有拿走物品的分数和。

请注意,第一个物品用以计算的体力值是1而不是k,第二个物品用以计算的体力值是k而不是k^2,...以此类推。

求他能得到的最高分。

对于30%:N <= 10

对于60%:N <= 1000

对于100%:N <= 100000, 1 <= M <= N ,所有物品的价值的绝对值<=10^9

时限:1s

内存限制:256MB

输入格式

第一行两个整数N,M

接下来一个实数k

接下来一行N个整数,分别表示这N个物品的价值。

输出格式

一个保留5位小数的实数,表示答案。

样例输入
样例输出
提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论