/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 333 点
問題文
高橋君は果樹園を経営しています。果樹園には N 本の果物の木が一列に並んでおり、左から順に 1 番目、 2 番目、…、 N 番目と番号がついています。
i 番目の木には A_i 個の果物が実っています。
今年は人手不足のため、高橋君はすべての木を収穫することができず、連続するちょうど K 本の木を選んで収穫作業を行うことにしました。すなわち、ある整数 l（1 \leq l \leq N - K + 1）を選び、l 番目から l + K - 1 番目までの K 本の木から果物を収穫します。選んだ 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 が、スペース区切りで与えられる。
出力
連続する K 本の木を適切に選んだときの、収穫する果物の個数の合計の最小値を 1 行で出力せよ。
入力例 1
5 3 4 2 1 3 5
出力例 1
6
入力例 2
8 4 10 5 8 3 2 7 4 6
出力例 2
16
入力例 3
10 5 100 200 50 80 120 30 60 90 150 70
出力例 3
340
Score : 333 pts
Problem Statement
Takahashi runs an orchard. The orchard has N fruit trees lined up in a row, numbered 1, 2, \ldots, N from left to right.
The i-th tree bears A_i fruits.
Due to a labor shortage this year, Takahashi cannot harvest all the trees, so he has decided to select exactly K consecutive trees to harvest. Specifically, he chooses an integer l (1 \leq l \leq N - K + 1) and harvests fruits from the K trees numbered l through l + K - 1. He must harvest all fruits from each of the K chosen trees (he cannot partially harvest a tree), and he does not harvest any fruits from the trees he did not choose.
Takahashi wants to minimize his workload, so he wants to minimize the total number of fruits harvested.
Find the minimum possible total number of fruits 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 the integer N representing the number of trees in the orchard and the integer K representing the number of consecutive trees to harvest, separated by a space.
The second line contains the integers A_1, A_2, \ldots, A_N representing the number of fruits on each tree, separated by spaces.
Output
Print in one line the minimum total number of fruits harvested when the K consecutive trees are chosen optimally.
Sample Input 1
5 3 4 2 1 3 5
Sample Output 1
6
Sample Input 2
8 4 10 5 8 3 2 7 4 6
Sample Output 2
16
Sample Input 3
10 5 100 200 50 80 120 30 60 90 150 70
Sample Output 3
340