/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 366 点
問題文
高橋君は一本道の商店街で開催される宝石集めイベントに参加しています。商店街には左から順に N 個のお店が一列に並んでおり、i 番目 (1 \leq i \leq N) のお店には A_i 個の宝石が置かれています。
高橋君は最初、お店 S にいます。イベントのルールとして、高橋君はちょうど K 回の移動を行わなければなりません。1 回の移動では、現在いるお店から隣接するお店へ 1 つ移動します。すなわち、現在お店 p (1 \leq p \leq N) にいるとき、p-1 \geq 1 ならばお店 p-1 へ、p+1 \leq N ならばお店 p+1 へ移動できます。お店 1 より左やお店 N より右へ出ることはできません。同じお店を何度訪れてもかまいません。
高橋君は、訪れたお店（開始地点であるお店 S を含む）ごとに、そこに置かれている A_i 個の宝石を獲得できます。ただし、同じお店を複数回訪れた場合でも、宝石を獲得できるのは最初の 1 回のみです。
高橋君がちょうど 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
- 1 行目には、お店の数を表す整数 N 、高橋君の初期位置を表す整数 S 、移動回数を表す整数 K が、スペース区切りで与えられる。
- 2 行目には、各お店に置かれている宝石の個数を表す整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
出力
高橋君が獲得できる宝石の合計個数の最大値を 1 行で出力せよ。
入力例 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
Score : 366 pts
Problem Statement
Takahashi is participating in a gem collecting event held on a straight shopping street. There are N shops lined up in a row from left to right on the street, and the i-th shop (1 \leq i \leq N) has A_i gems placed in it.
Takahashi starts at shop S. According to the event rules, Takahashi must make exactly K moves. In one move, he moves from his current shop to an adjacent shop. That is, when he is currently at shop p (1 \leq p \leq N), he can move to shop p-1 if p-1 \geq 1, or to shop p+1 if p+1 \leq N. He cannot go to the left of shop 1 or to the right of shop N. He may visit the same shop multiple times.
For each shop Takahashi visits (including shop S where he starts), he can collect the A_i gems placed there. However, even if he visits the same shop multiple times, he can only collect the gems on the first visit.
Determine the maximum total number of gems Takahashi can collect when he makes exactly K moves.
Constraints
- 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
- All inputs are integers
Input
N S K A_1 A_2 \ldots A_N
- The first line contains an integer N representing the number of shops, an integer S representing Takahashi's initial position, and an integer K representing the number of moves, separated by spaces.
- The second line contains integers A_1, A_2, \ldots, A_N representing the number of gems placed in each shop, separated by spaces.
Output
Print the maximum total number of gems Takahashi can collect in one line.
Sample Input 1
5 3 2 10 20 30 40 50
Sample Output 1
120
Sample Input 2
4 1 3 5 100 1 10
Sample Output 2
116
Sample Input 3
12 6 8 3 15 8 20 7 50 6 12 30 4 25 10
Sample Output 3
144
Sample Input 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
Sample Output 4
922
Sample Input 5
2 1 1000000000 1000000000 0
Sample Output 5
1000000000