/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
高橋君は N 日間にわたって開催される夏祭りに出店する計画を立てています。祭りの各日には 1 から N までの番号が付けられており、日 i（1 \leq i \leq N）の売上見込みは A_i です。
高橋君は、祭り期間中に 2つの出店期間 を選びます。それぞれの出店期間は ちょうど K 日間 の連続した日からなり、1つ目の出店期間は2つ目の出店期間よりも前の日程とします。さらに、食材の仕入れや機材の整備のため、1つ目の出店期間と2つ目の出店期間は重複してはならず、2つの出店期間の間には 少なくとも1日の空き（どちらの出店期間にも含まれない日が1日以上存在すること）を設ける必要があります。
具体的には、1つ目の出店期間を日 s から日 s+K-1 まで、2つ目の出店期間を日 t から日 t+K-1 までとするとき、以下の条件をすべて満たす必要があります。
- 1 \leq s かつ s + K - 1 \leq N（1つ目の出店期間が祭り期間内に収まる）
- 1 \leq t かつ t + K - 1 \leq N（2つ目の出店期間が祭り期間内に収まる）
- t \geq s + K + 1（1つ目の出店期間の最終日 s+K-1 と2つ目の出店期間の初日 t の間に、少なくとも1日の空きがある）
高橋君は、2つの出店期間に含まれる全日の売上見込みの合計、すなわち
\sum_{i=s}^{s+K-1} A_i + \sum_{i=t}^{t+K-1} A_i
をできるだけ大きくしたいと考えています。
この合計の最大値を求めてください。
制約
- 3 \leq N \leq 10^6
- 1 \leq K \leq \lfloor \frac{N-1}{2} \rfloor（すなわち 2K + 1 \leq N）
- 1 \leq A_i \leq 10^9（1 \leq i \leq N）
- 入力はすべて整数
K の制約により、条件を満たす2つの出店期間の選び方が必ず1つ以上存在することが保証されます。
入力
N K A_1 A_2 \ldots A_N
- 1 行目には、祭りの日数を表す整数 N と、各出店期間の長さを表す整数 K が、スペース区切りで与えられる。
- 2 行目には、各日の売上見込みを表す N 個の整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
出力
2つの出店期間に含まれる全日の売上見込みの合計の最大値を1行で出力せよ。
入力例 1
7 2 3 5 2 6 1 4 3
出力例 1
15
入力例 2
5 2 1 2 3 4 5
出力例 2
12
入力例 3
15 3 5 8 3 7 2 9 1 6 4 10 3 8 7 2 5
出力例 3
39
入力例 4
20 4 10 20 30 40 50 60 70 80 90 100 90 80 70 60 50 40 30 20 10 5
出力例 4
600
入力例 5
3 1 100 1 100
出力例 5
200
Score : 400 pts
Problem Statement
Takahashi is planning to set up a booth at a summer festival that runs for N days. Each day of the festival is numbered from 1 to N, and the expected sales for day i (1 \leq i \leq N) is A_i.
During the festival period, Takahashi will choose two booth periods. Each booth period consists of exactly K consecutive days, and the first booth period must be scheduled before the second booth period. Furthermore, due to ingredient procurement and equipment maintenance, the two booth periods must not overlap, and there must be at least one day of gap between them (at least one day that is not included in either booth period).
Specifically, if the first booth period runs from day s to day s+K-1, and the second booth period runs from day t to day t+K-1, then all of the following conditions must be satisfied:
- 1 \leq s and s + K - 1 \leq N (the first booth period fits within the festival period)
- 1 \leq t and t + K - 1 \leq N (the second booth period fits within the festival period)
- t \geq s + K + 1 (there is at least one day of gap between the last day s+K-1 of the first booth period and the first day t of the second booth period)
Takahashi wants to maximize the total expected sales over all days included in the two booth periods, that is,
\sum_{i=s}^{s+K-1} A_i + \sum_{i=t}^{t+K-1} A_i
Find the maximum value of this total.
Constraints
- 3 \leq N \leq 10^6
- 1 \leq K \leq \lfloor \frac{N-1}{2} \rfloor (i.e., 2K + 1 \leq N)
- 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
- All inputs are integers
The constraint on K guarantees that there always exists at least one valid way to choose the two booth periods.
Input
N K A_1 A_2 \ldots A_N
- The first line contains two integers separated by a space: N, the number of days of the festival, and K, the length of each booth period.
- The second line contains N integers separated by spaces: A_1, A_2, \ldots, A_N, representing the expected sales for each day.
Output
Print the maximum value of the total expected sales over all days included in the two booth periods, on a single line.
Sample Input 1
7 2 3 5 2 6 1 4 3
Sample Output 1
15
Sample Input 2
5 2 1 2 3 4 5
Sample Output 2
12
Sample Input 3
15 3 5 8 3 7 2 9 1 6 4 10 3 8 7 2 5
Sample Output 3
39
Sample Input 4
20 4 10 20 30 40 50 60 70 80 90 100 90 80 70 60 50 40 30 20 10 5
Sample Output 4
600
Sample Input 5
3 1 100 1 100
Sample Output 5
200