/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
遊園地に、N 個のゴンドラが円形に並んだ観覧車があります。ゴンドラには 1 から N まで番号が付けられており、ゴンドラ i（1 \leq i \leq N）の美しさは A_i です。ゴンドラは円形に並んでいるため、ゴンドラ N の次はゴンドラ 1 です。
この観覧車の乗り場からは、円周上で連続するちょうど M 個のゴンドラが見えます。観覧車は任意の位置まで回転させることができるので、見えるゴンドラの組を自由に選べます。
観覧車を最適な位置まで回転させたとき、乗り場から見える M 個のゴンドラの美しさの合計の最大値を求めてください。
制約
- 1 \leq M \leq N \leq 5 \times 10^5
- -10^9 \leq A_i \leq 10^9
- 入力はすべて整数である
入力
N M A_1 A_2 \ldots A_N
- 1 行目には、ゴンドラの個数 N と、乗り場から見える連続したゴンドラの個数 M が、スペース区切りで与えられる。
- 2 行目には、各ゴンドラの美しさ A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
出力
乗り場から見える連続する M 個のゴンドラの美しさの合計の最大値を 1 行で出力せよ。
入力例 1
5 3 1 2 3 4 5
出力例 1
12
入力例 2
4 2 -5 -2 -3 -4
出力例 2
-5
入力例 3
12 5 8 -3 6 1 -2 4 7 -5 9 -1 3 2
出力例 3
21
入力例 4
20 7 5 -8 12 7 -3 9 -10 4 6 -2 11 -5 13 -7 8 1 -4 10 -6 14
出力例 4
36
入力例 5
1 1 -1000000000
出力例 5
-1000000000
Score : 300 pts
Problem Statement
At an amusement park, there is a Ferris wheel with N gondolas arranged in a circle. The gondolas are numbered from 1 to N, and the beauty of gondola i (1 \leq i \leq N) is A_i. Since the gondolas are arranged in a circle, gondola 1 comes after gondola N.
From the boarding platform, exactly M consecutive gondolas along the circumference are visible. Since the Ferris wheel can be rotated to any position, you can freely choose which set of gondolas is visible.
When the Ferris wheel is rotated to the optimal position, find the maximum possible sum of the beauty values of the M gondolas visible from the boarding platform.
Constraints
- 1 \leq M \leq N \leq 5 \times 10^5
- -10^9 \leq A_i \leq 10^9
- All input values are integers.
Input
N M A_1 A_2 \ldots A_N
- The first line contains the number of gondolas N and the number of consecutive gondolas visible from the boarding platform M, separated by a space.
- The second line contains the beauty values of each gondola A_1, A_2, \ldots, A_N, separated by spaces.
Output
Print the maximum possible sum of the beauty values of M consecutive gondolas visible from the boarding platform, on a single line.
Sample Input 1
5 3 1 2 3 4 5
Sample Output 1
12
Sample Input 2
4 2 -5 -2 -3 -4
Sample Output 2
-5
Sample Input 3
12 5 8 -3 6 1 -2 4 7 -5 9 -1 3 2
Sample Output 3
21
Sample Input 4
20 7 5 -8 12 7 -3 9 -10 4 6 -2 11 -5 13 -7 8 1 -4 10 -6 14
Sample Output 4
36
Sample Input 5
1 1 -1000000000
Sample Output 5
-1000000000