← 返回题目列表

AtCoder · awc0102_c

C. 收集宝石

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

分数: 366 分

问题陈述

高桥正在参加在一条笔直的商店街上举行的宝石收集活动。有 N 街上的商店从左到右一字排开, i第店 (1 \leq i \leq N) 有 A_i 宝石放置在其中。

高桥开始在商店 S。根据赛事规则,高桥必须准确地做出 K 移动。他一举从当前的商店搬到了邻近的商店。也就是说,当他当前在商店时 p (1 \leq p \leq N),他可以移动到商店 p-1 if p-1 \geq 1,或前往商店 p+1 if p+1 \leq N。他不能走到商店的左边 1 或商店右侧 N。他可能会多次光顾同一家商店。

对于高桥访问的每个商店(包括商店 S 他开始的地方),他可以收集 A_i 宝石放在那里。然而,即使他多次访问同一家商店,他也只能在第一次访问时收集宝石。

确定高桥在精确制作时可以收集的最大宝石总数 K 移动。

约束

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq S \leq N
  • 1 \leq K \leq 10^9
  • 0 \leq A_i \leq 10^9
  • 所有输入均为整数

输入

N S K
A_1 A_2 \ldots A_N
  • 第一行包含一个整数 N 代表店铺数量,整数 S 代表高桥的初始位置,一个整数 K 代表移动次数,以空格分隔。
  • 第二行包含整数 A_1, A_2, \ldots, A_N 代表每个商店放置的宝石数量,以空格分隔。

输出

打印高桥在一行中可以收集的最大宝石总数。


示例输入 1

5 3 2
10 20 30 40 50

示例输出 1

120

示例输入 2

4 1 3
5 100 1 10

示例输出 2

116

示例输入 3

12 6 8
3 15 8 20 7 50 6 12 30 4 25 10

示例输出 3

144

示例输入 4

30 17 25
12 0 45 23 78 5 90 34 11 67 8 56 100 3 29 74 41 62 18 95 7 36 84 21 50 69 14 88 2 31

示例输出 4

922

示例输入 5

2 1 1000000000
1000000000 0

示例输出 5

1000000000