Problem 3002 --Horse

3002: Horse

正确率: $0.00\%$ 下一题

Time Limit	$1$ 秒/Second(s)	Memory Limit	$512$ 兆字节/Megabyte(s)
提交总数	$2$	正确数量	$0$
裁判形式	标准裁判/Standard Judge	我的状态	尚未尝试
难度		分类标签

Description

There is a horse which can jump over trees and he has to jump N trees sequentially.
Initially, the horse has zero energy.
Jumping trees, he loses energy (one unit of energy per unit of height) and he gets points as the amount of left energy (Left energy can be less than 0).
And his final score is the sum of all points that the horse gets after each jump.
The horse can do two types of tricks.
*Just before every jump, he can eat a tree. Of course, he jumps over the eaten tree which has no height.
*Just after every jump, he can have a break. After each break, he restores energy. It means that his energy becomes the total sum of heights of all eaten trees.
But he has limits, he can have at most K breaks and eat at most M trees.
You have to find the maximum score that the horse can gets.

Input

The first line contains an integer T (1 <= T <= 10) denoting the number of test cases.
The first line of each test case contains three integers N (1 <= N <= 10000), K (0 <= K <= min (50, N - 1)) and M (0 <= M <= min (50, N)).
The second line of each test case contains N integers h1, h2 … hn (1 <= hi <= 10000), where hi denote the height of ith tree.

Output

For each test case, print the maximum score that the horse can gets.

Sample Input复制

3
4 1 1
4 2 3 1
4 2 4
4 2 3 1
10 2 3
2 3 4 5 6 2 7 4 3 1

Sample Output复制

-1
17
25

提示

For the first test case, the answer is that the horse eats the first tree and has a break after the second jump.
For the second test case, the horse has breaks after the first and third jump and eats all trees.

赛题来源/所属竞赛 2019 Multi-University Training Contest 4 N/A

竞赛编号	竞赛名称	竞赛时间	访问比赛

本题记录	用户（点击查看用户）	运行号（点击购买题解）	时间
算法最快[$ $ms]
内存最少[$ $KB]
第一AC
第一挑战	淡意的温柔	590703	2020-06-05 08:33:53