/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 333 点
問題文
高橋君は、庭に一列に並んだ N 個の花壇を管理しています。花壇には左から順に 1 から N の番号がついており、花壇 i には「美しさ」A_i が定められています。
高橋君は、N 個の花壇それぞれについて、手入れするかしないかを選びます。ただし、手入れする花壇の選び方は以下の条件を満たさなければなりません。
- ある整数 l（1 \leq l \leq N - K + 1）が存在して、花壇 l, l+1, \ldots, l+K-1 がすべて手入れする花壇に含まれる。
すなわち、連続する K 個の花壇がすべて手入れされるような区間が少なくとも 1 つ存在しなければなりません。この条件さえ満たしていれば、それ以外の花壇については手入れしてもしなくても構いません。
手入れする花壇として選んだものの美しさの合計としてありえる最大値を求めてください。
制約
- 1 \leq K \leq N \leq 5 \times 10^5
- -10^9 \leq A_i \leq 10^9
- 入力はすべて整数
入力
N K A_1 A_2 \cdots A_N
- 1 行目には、花壇の総数 N と、連続して手入れしなければならない花壇の個数 K が、スペース区切りで与えられる。
- 2 行目には、各花壇の美しさ A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
出力
条件を満たすように手入れする花壇を選んだとき、美しさの合計の最大値を一行に出力してください。
入力例 1
5 2 3 -5 4 2 -1
出力例 1
9
入力例 2
4 3 -2 -7 -1 -3
出力例 2
-10
入力例 3
10 4 5 -2 3 -1 6 -7 4 2 -3 8
出力例 3
25
入力例 4
20 6 4 -5 7 0 -2 9 -8 3 1 -4 6 -1 5 -7 2 8 -3 4 -6 10
出力例 4
54
入力例 5
1 1 -1000000000
出力例 5
-1000000000
Score : 333 pts
Problem Statement
Takahashi manages N flower beds arranged in a row in his garden. The flower beds are numbered 1 to N from left to right, and flower bed i has a defined "beauty" value A_i.
For each of the N flower beds, Takahashi chooses whether or not to maintain it. However, the selection of flower beds to maintain must satisfy the following condition:
- There exists an integer l (1 \leq l \leq N - K + 1) such that flower beds l, l+1, \ldots, l+K-1 are all included in the maintained flower beds.
In other words, there must exist at least one interval where K consecutive flower beds are all maintained. As long as this condition is satisfied, any other flower bed may or may not be maintained.
Find the maximum possible sum of beauty values of the flower beds chosen for maintenance.
Constraints
- 1 \leq K \leq N \leq 5 \times 10^5
- -10^9 \leq A_i \leq 10^9
- All inputs are integers
Input
N K A_1 A_2 \cdots A_N
- The first line contains the total number of flower beds N and the number of consecutive flower beds that must be maintained K, separated by a space.
- The second line contains the beauty values of each flower bed A_1, A_2, \ldots, A_N, separated by spaces.
Output
Print on one line the maximum sum of beauty values when choosing flower beds to maintain while satisfying the condition.
Sample Input 1
5 2 3 -5 4 2 -1
Sample Output 1
9
Sample Input 2
4 3 -2 -7 -1 -3
Sample Output 2
-10
Sample Input 3
10 4 5 -2 3 -1 6 -7 4 2 -3 8
Sample Output 3
25
Sample Input 4
20 6 4 -5 7 0 -2 9 -8 3 1 -4 6 -1 5 -7 2 8 -3 4 -6 10
Sample Output 4
54
Sample Input 5
1 1 -1000000000
Sample Output 5
-1000000000