| [Home|Training|Problems|Contests|C Language] | [Login|Register] |
|
Problems Status Rank Statistics |
Problem A
Children's Day
Time Limit: 1000ms
Memory Limit: 65536kb Description
"池塘边的榕树上,知了在声声叫着夏天 草丛边的秋千上,只有蝴蝶停在上面 黑板上老师的粉笔还在拼命叽叽喳喳写个不停 等待着下课等待着放学等待游戏的童年 " 在一年前赢得了小镇的最佳草坪比赛后，小W变得很懒，再也没有修剪过草坪。现在，新一轮的最佳草坪比赛又开始了，小W希望能够再次夺冠。 然而，小W的草坪非常脏乱，因此，小W只能够让他的奶牛通过啃草来完成这项工作。小W有N(1 <= N <= 100,000)只排成一排的奶牛，编号为1...N。每只奶牛的效率是不同的，奶牛i的效率为E_i(0 <= E_i <= 1,000,000,000)。 靠近的奶牛们很熟悉，因此，如果小W安排超过K只连续的奶牛，那么，这些奶牛就会罢工去开派对:)。因此，现在小W需要你的帮助，计算小W可以得到的最大效率，并且该方案中没有连续的超过K只奶牛。 Input
第1行一个数字T（T不超过20），表示Case数量。对每一个Case：* 第1行：空格隔开的两个整数N和K； * 后跟N行，每行有一个整数E_i，表示奶牛i的效率。 Output
每个case输出一行，表示可以得到的最大的效率值。
Sample Input
1 5 2 1 2 3 4 5 Sample Output
12 |