/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
高橋君は気象観測所で働いており、毎日の平均気温を記録しています。気温は 1 から 9 までの 9 段階の整数値で簡易的に記録されています。
ある日、高橋君は過去の連続する N 日間の気温データを分析することにしました。高橋君は、連続する K 日間の気温の合計値に注目し、すべての連続 K 日間について合計値を計算したうえで、その中での最大値と最小値の差を求めたいと考えています。この差が大きいほど、期間内の気温変動が激しかったことを意味します。
具体的には、N 日間の気温の記録が A_1, A_2, \dots, A_N として与えられたとき、連続する K 日間の気温の合計値は N - K + 1 個存在します。すなわち、i = 1, 2, \dots, N - K + 1 に対して、
S_i = \sum_{j=0}^{K-1} A_{i+j}
を計算します。このとき、S_1, S_2, \dots, S_{N-K+1} の最大値と最小値の差を求めてください。
制約
- 1 \leq K \leq N \leq 10^5
- 1 \leq A_i \leq 9
- 入力はすべて整数である。
入力
N K A_1 A_2 \dots A_N
- 1 行目には、観測日数を表す整数 N と、注目する連続日数を表す整数 K が、スペース区切りで与えられる。
- 2 行目には、各日の気温を表す整数 A_1, A_2, \dots, A_N が、スペース区切りで与えられる。
出力
S_1, S_2, \dots, S_{N-K+1} の最大値と最小値の差を 1 行で出力せよ。
入力例 1
5 3 2 5 3 1 4
出力例 1
2
入力例 2
10 4 3 1 4 1 5 9 2 6 5 3
出力例 2
13
入力例 3
20 5 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 9
出力例 3
8
Score : 300 pts
Problem Statement
Takahashi works at a meteorological observatory and records the daily average temperature. Temperatures are recorded as simplified integer values ranging from 1 to 9 (9 levels).
One day, Takahashi decided to analyze temperature data from a consecutive N-day period in the past. Takahashi focuses on the total temperature over consecutive K-day windows, and wants to calculate the total for every consecutive K-day window, then find the difference between the maximum and minimum values among them. A larger difference indicates more intense temperature fluctuations during the period.
Specifically, given the temperature records for N days as A_1, A_2, \dots, A_N, there are N - K + 1 total values of consecutive K-day windows. That is, for i = 1, 2, \dots, N - K + 1, we compute:
S_i = \sum_{j=0}^{K-1} A_{i+j}
Find the difference between the maximum and minimum values among S_1, S_2, \dots, S_{N-K+1}.
Constraints
- 1 \leq K \leq N \leq 10^5
- 1 \leq A_i \leq 9
- All input values are integers.
Input
N K A_1 A_2 \dots A_N
- The first line contains an integer N representing the number of observation days and an integer K representing the number of consecutive days of interest, separated by a space.
- The second line contains integers A_1, A_2, \dots, A_N representing the temperature for each day, separated by spaces.
Output
Print the difference between the maximum and minimum values of S_1, S_2, \dots, S_{N-K+1} on a single line.
Sample Input 1
5 3 2 5 3 1 4
Sample Output 1
2
Sample Input 2
10 4 3 1 4 1 5 9 2 6 5 3
Sample Output 2
13
Sample Input 3
20 5 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 9 1 9
Sample Output 3
8