/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 333 点
問題文
高橋君は果樹園でアルバイトをしています。この果樹園には N 本の果物の木が一列に並んでおり、左から i 番目の木には A_i 個の果物がなっています。
高橋君はこれから収穫作業を行います。収穫には専用のカートを使いますが、このカートは一列に並んだ木に沿って連続した区間しか移動できないため、連続して並んだちょうど K 本の木を選び、その K 本の木になっている果物をすべて収穫します。より正確には、ある整数 l（1 \leq l \leq N - K + 1）を選び、左から l 番目の木から l + K - 1 番目の木までの K 本の木になっている果物をすべて収穫します。
高橋君は収穫できる果物の個数を最大化したいと考えています。連続する K 本の木を最適に選んだとき、収穫できる果物の個数の最大値を求めてください。
制約
- 1 \leq K \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- 入力はすべて整数
入力
N K A_1 A_2 \ldots A_N
- 1 行目には、木の本数を表す整数 N と、選択する連続した木の本数を表す整数 K が、スペース区切りで与えられる。
- 2 行目には、各木になっている果物の個数を表す整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
- A_i は左から i 番目の木になっている果物の個数を表す。
出力
連続する K 本の木を最適に選んだとき、収穫できる果物の個数の最大値を 1 行で出力せよ。
入力例 1
5 3 2 5 3 8 1
出力例 1
16
入力例 2
7 2 10 4 8 6 15 3 9
出力例 2
21
入力例 3
10 4 100 250 180 320 90 410 275 150 380 200
出力例 3
1215
Score : 333 pts
Problem Statement
Takahashi works part-time at an orchard. In this orchard, N fruit trees are lined up in a row, and the i-th tree from the left has A_i fruits.
Takahashi is about to perform the harvest. He uses a special cart for harvesting, but since this cart can only move along a contiguous section of the row of trees, he must choose exactly K consecutive trees and harvest all the fruits from those K trees. More precisely, he chooses an integer l (1 \leq l \leq N - K + 1) and harvests all the fruits from the K trees starting from the l-th tree to the (l + K - 1)-th tree from the left.
Takahashi wants to maximize the number of fruits he can harvest. Find the maximum number of fruits that can be harvested when the K consecutive trees are chosen optimally.
Constraints
- 1 \leq K \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- All inputs are integers
Input
N K A_1 A_2 \ldots A_N
- The first line contains an integer N representing the number of trees and an integer K representing the number of consecutive trees to select, separated by a space.
- The second line contains integers A_1, A_2, \ldots, A_N representing the number of fruits on each tree, separated by spaces.
- A_i represents the number of fruits on the i-th tree from the left.
Output
Print in one line the maximum number of fruits that can be harvested when the K consecutive trees are chosen optimally.
Sample Input 1
5 3 2 5 3 8 1
Sample Output 1
16
Sample Input 2
7 2 10 4 8 6 15 3 9
Sample Output 2
21
Sample Input 3
10 4 100 250 180 320 90 410 275 150 380 200
Sample Output 3
1215