1463: 防御塔
Memory Limit：64 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：92
Solved：18
Description
卫兹南和迪纳斯正在玩游戏.
有$n$个防御塔排成一排,每个防御塔上都印有一个非负整数,表示摧毁它可以获得的分数.
卫兹南的力量为$w$,这意味着他每次出手可以摧毁$w$个相邻的防御塔(如果出手必须摧毁$w$个).
给定$k$次出手机会,卫兹南希望迪纳斯帮他计算获得的总分数的最大值.
例如:如果9个防御塔排成一排,分数依次为2,8,5,1,9,6,9,3,2,每次可以摧毁3个,给定2次出手机会,那么最多可以得到39分,两次出手分别得分:2+8+5=15以及9+6+9=24.
有$n$个防御塔排成一排,每个防御塔上都印有一个非负整数,表示摧毁它可以获得的分数.
卫兹南的力量为$w$,这意味着他每次出手可以摧毁$w$个相邻的防御塔(如果出手必须摧毁$w$个).
给定$k$次出手机会,卫兹南希望迪纳斯帮他计算获得的总分数的最大值.
例如:如果9个防御塔排成一排,分数依次为2,8,5,1,9,6,9,3,2,每次可以摧毁3个,给定2次出手机会,那么最多可以得到39分,两次出手分别得分:2+8+5=15以及9+6+9=24.
Input
第一行包含整数 $T$ ,表示共有 $T$ 组测试数据.
每组数据:
- 第一行包含整数$n$,$k$,$w$;
- 接下来$n$个数,其中第$i$个数表示第$i$个防御塔的分数.
数据范围:
$1\leq T\leq3$
$1\leq n\leq 30000$
$1\leq k\leq 300$
$1\leq w\leq n$
每组数据:
- 第一行包含整数$n$,$k$,$w$;
- 接下来$n$个数,其中第$i$个数表示第$i$个防御塔的分数.
数据范围:
$1\leq T\leq3$
$1\leq n\leq 30000$
$1\leq k\leq 300$
$1\leq w\leq n$
Output
每组数据输出一行结果,一个整数,表示可以获得的总分数的最大可能值.保证答案均小于$1e9$.
Sample Input Copy
1
9 2 3
2 8 5 1 9 6 9 3 2Sample Output Copy
39