B - Walking Intervals That Include a Favorite Place Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 333 点

問題文

高橋君は N 個の区画が一列に並んだ散歩道を毎日歩いています。区画には左から順に 1, 2, \ldots, N の番号が付けられており、i 番目の区画の美しさは整数 A_i で表されます（美しさは負の値をとることもあります）。

高橋君には D 番目の区画というお気に入りの場所があります。高橋君は、散歩道の中から D 番目の区画を必ず含む 連続するちょうど K 個の区画からなる区間を 1 つ選び、その美しさの合計が最大となるようにしたいと考えています。

具体的には、区間の開始位置を表す整数 l を決めて、l 番目から l+K-1 番目までの連続する K 個の区画を選びます。このとき、l は以下の条件をすべて満たす必要があります。

  • 1 \leq l（区間が散歩道の左端からはみ出さない）
  • l + K - 1 \leq N（区間が散歩道の右端からはみ出さない）
  • l \leq D \leq l + K - 1（区間がお気に入りの D 番目の区画を含む）

このような l の選び方のうち、美しさの合計 A_l + A_{l+1} + \cdots + A_{l+K-1} が最大となるときの値を求めてください。

制約

  • 1 \leq N \leq 10^6
  • 1 \leq K \leq N
  • 1 \leq D \leq N
  • -10^9 \leq A_i \leq 10^9
  • 条件を満たす l が少なくとも 1 つ存在することが保証される。
  • 入力はすべて整数である。

入力

N K D
A_1 A_2 \ldots A_N
  • 1 行目には、区画の数 N、選ぶ連続区画の個数 K、お気に入りの区画の番号 D が、スペース区切りで与えられる。
  • 2 行目には、各区画の美しさ A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。A_i は i 番目の区画の美しさを表す。

出力

条件を満たす連続する K 個の区画の美しさの合計の最大値を 1 行で出力せよ。なお、答えが負の値になることもある。

入力例 1

7 3 4
2 -1 5 3 -2 4 1

出力例 1

7

入力例 2

5 2 3
-3 -5 -1 -4 -2

出力例 2

-5

入力例 3

15 5 8
1 -3 4 -2 5 1 -6 3 7 -1 2 8 -4 3 -5

出力例 3

19

入力例 4

20 7 12
3 -1 4 1 5 -9 2 6 -5 3 5 8 -3 7 2 -4 6 1 -2 3

出力例 4

21

入力例 5

1 1 1
-1000000000

出力例 5

-1000000000

Score : 333 pts

Problem Statement

Takahashi walks every day along a promenade consisting of N blocks arranged in a row. The blocks are numbered 1, 2, \ldots, N from left to right, and the beauty of the i-th block is represented by an integer A_i (the beauty can be negative).

Takahashi has a favorite place, which is the D-th block. He wants to choose an interval of exactly K consecutive blocks from the promenade that must include the D-th block, such that the total beauty is maximized.

Specifically, he decides an integer l representing the starting position of the interval, and selects K consecutive blocks from the l-th to the (l+K-1)-th. The value of l must satisfy all of the following conditions:

  • 1 \leq l (the interval does not extend beyond the left end of the promenade)
  • l + K - 1 \leq N (the interval does not extend beyond the right end of the promenade)
  • l \leq D \leq l + K - 1 (the interval includes the favorite D-th block)

Among all valid choices of l, find the maximum value of the total beauty A_l + A_{l+1} + \cdots + A_{l+K-1}.

Constraints

  • 1 \leq N \leq 10^6
  • 1 \leq K \leq N
  • 1 \leq D \leq N
  • -10^9 \leq A_i \leq 10^9
  • It is guaranteed that at least one valid l exists.
  • All input values are integers.

Input

N K D
A_1 A_2 \ldots A_N
  • The first line contains the number of blocks N, the number of consecutive blocks to choose K, and the favorite block number D, separated by spaces.
  • The second line contains the beauty of each block A_1, A_2, \ldots, A_N, separated by spaces. A_i represents the beauty of the i-th block.

Output

Print in one line the maximum total beauty of K consecutive blocks satisfying the conditions. Note that the answer may be negative.

Sample Input 1

7 3 4
2 -1 5 3 -2 4 1

Sample Output 1

7

Sample Input 2

5 2 3
-3 -5 -1 -4 -2

Sample Output 2

-5

Sample Input 3

15 5 8
1 -3 4 -2 5 1 -6 3 7 -1 2 8 -4 3 -5

Sample Output 3

19

Sample Input 4

20 7 12
3 -1 4 1 5 -9 2 6 -5 3 5 8 -3 7 2 -4 6 1 -2 3

Sample Output 4

21

Sample Input 5

1 1 1
-1000000000

Sample Output 5

-1000000000