/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 333 点
問題文
高橋君はスマートフォンのリズムゲームをプレイしています。このゲームでは、N 個のノーツが順番に流れてきます。
各ノーツ i（1 \leq i \leq N）には、基本スコア A_i が設定されています。
このゲームには「ボーナスタイム」という特殊なシステムがあります。高橋君は、ゲーム開始前に連続する K 個のノーツからなる区間をちょうど 1 つ選び、ボーナスタイムとして設定します。具体的には、ある整数 s（1 \leq s \leq N - K + 1）を選び、ノーツ s, s+1, \ldots, s+K-1 をボーナスタイムの対象とします。
ボーナスタイムの対象となったノーツから得られるスコアは基本スコアの 2 倍、それ以外のノーツから得られるスコアは基本スコアそのままです。最終的な得点は、すべてのノーツから得られるスコアの合計です。
s を選んだときの得点を式で表すと、
\sum_{\substack{i=1 \\ i \notin [s, s+K-1]}}^{N} A_i + \sum_{i=s}^{s+K-1} 2A_i = \sum_{i=1}^{N} A_i + \sum_{i=s}^{s+K-1} A_i
となります。すなわち、得点は全ノーツの基本スコアの合計に、ボーナスタイム対象区間の基本スコアの合計を加えたものです。
高橋君はハイスコアを狙っています。ボーナスタイムを設定する区間を最適に選んだとき、獲得できる得点の最大値を求めてください。
制約
- 1 \leq K \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9（1 \leq i \leq N）
- 入力はすべて整数である
入力
N K A_1 A_2 \ldots A_N
- 1 行目には、ノーツの数を表す整数 N と、ボーナスタイムを適用する連続区間の長さを表す整数 K が、スペース区切りで与えられる。
- 2 行目には、各ノーツの基本スコアを表す整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
出力
獲得できる得点の最大値を 1 行で出力せよ。
入力例 1
5 2 1 3 2 4 1
出力例 1
17
入力例 2
7 3 10 20 5 100 100 100 15
出力例 2
650
入力例 3
10 4 500000000 1 1 1 1 1 1 1 1 500000000
出力例 3
1500000011
Score : 333 pts
Problem Statement
Takahashi is playing a rhythm game on his smartphone. In this game, N notes appear in sequence.
Each note i (1 \leq i \leq N) has a base score A_i.
This game has a special system called "Bonus Time." Before the game starts, Takahashi must select exactly one interval consisting of K consecutive notes and set it as the Bonus Time. Specifically, he chooses an integer s (1 \leq s \leq N - K + 1) and designates notes s, s+1, \ldots, s+K-1 as the Bonus Time targets.
The score earned from notes within the Bonus Time is doubled (i.e., 2 times the base score), while the score earned from all other notes remains equal to their base score. The final score is the sum of the scores earned from all notes.
Expressing the score when s is chosen as a formula:
\sum_{\substack{i=1 \\ i \notin [s, s+K-1]}}^{N} A_i + \sum_{i=s}^{s+K-1} 2A_i = \sum_{i=1}^{N} A_i + \sum_{i=s}^{s+K-1} A_i
In other words, the score equals the sum of base scores of all notes plus the sum of base scores of the notes in the Bonus Time interval.
Takahashi is aiming for a high score. Find the maximum score he can achieve by optimally choosing the interval for the Bonus Time.
Constraints
- 1 \leq K \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
- All input values are integers.
Input
N K A_1 A_2 \ldots A_N
- The first line contains an integer N representing the number of notes and an integer K representing the length of the consecutive interval to which the Bonus Time is applied, separated by a space.
- The second line contains integers A_1, A_2, \ldots, A_N representing the base score of each note, separated by spaces.
Output
Print the maximum score that can be achieved in a single line.
Sample Input 1
5 2 1 3 2 4 1
Sample Output 1
17
Sample Input 2
7 3 10 20 5 100 100 100 15
Sample Output 2
650
Sample Input 3
10 4 500000000 1 1 1 1 1 1 1 1 500000000
Sample Output 3
1500000011