← 返回题目列表

Codeforces · 1389/B

B. 数组遍历

中文机器翻译题面 查看原题

给定一个数组 $$$a_1, a_2, \dots, a_n$$$,由 $$$n$$$ 正整数组成。

最初,您站在索引 $$$1$$$ 处,得分等于 $$$a_1$$$。您可以执行两种动作:

1. 向右移动 — 从当前索引 $$$x$$$ 到 $$$x+1$$$ 并将 $$$a_{x+1}$$$ 添加到您的分数中。仅当 $$$x<n$$$ 时才能执行此移动。
2. 向左移动 — 从当前索引 $$$x$$$ 到 $$$x-1$$$ 并将 $$$a_{x-1}$$$ 添加到您的分数中。仅当 $$$x>1$$$ 时才能执行此移动。此外,您不能连续向左移动两次或两次以上。

您想要精确执行 $$$k$$$ 步。此外,其中向左移动的次数不应超过 $$$z$$$。

您能获得的最高分数是多少?

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含三个整数 $$$n、k$$$ 和 $$$z$$$ ($$$2 \le n \le 10^5$$$, $$$1 \le k \le n - 1$$$, $$$0 \le z \le min(5, k)$$$) — 数组中的元素数量、应执行的移动总数以及最大移动次数向左移动即可执行。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^4$$$) - 给定的数组。

所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 10^5$$$。

输出

打印 $$$t$$$ 整数 - 对于每个测试用例输出,如果您总共进行了 $$$k$$$ 步,向左移动的次数不超过 $$$z$$$,并且连续向左移动的次数不超过 $$$z$$$,则您可以获得的最高分数。

示例

输入 #1

4
5 4 0
1 5 4 3 2
5 4 1
1 5 4 3 2
5 4 4
10 20 30 40 50
10 7 3
4 6 8 2 9 9 7 4 10 9

输出 #1

15
19
150
56

注意

在第一个测试用例中,您根本不允许向左移动。因此,您向右移动四步并获得分数 $$$a_1 + a_2 + a_3 + a_4 + a_5$$$。

在第二个示例中,您可以向左移动一次。所以我们可以遵循这些动作:右,右,左,右。分数将为 $$$a_1 + a_2 + a_3 + a_2 + a_3$$$。

在第三个示例中,您可以向左移动四次,但无论如何这都不是最佳的,您可以向右移动四次并获得分数 $$$a_1 + a_2 + a_3 + a_4 + a_5$$$。