/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
高橋君はあるチェーン店の売上データを分析するアルバイトをしています。
このチェーン店には N 日分の売上記録があり、i 日目 (1 \leq i \leq N) の売上は T_i 円でした。
高橋君は連続する K 日間の売上の平均値を計算し、その最大値を求めることで、最も売上が好調だった期間の成績を把握しようとしています。
具体的には、各整数 l (1 \leq l \leq N - K + 1) に対して、l 日目から l + K - 1 日目までの連続する K 日間の売上の平均値を
M_l = \frac{T_l + T_{l+1} + \cdots + T_{l+K-1}}{K}
と定めます。すべての l (1 \leq l \leq N - K + 1) に対する M_l の最大値を M とします。
\lfloor M \times 1000 \rfloor を求めてください。ここで \lfloor x \rfloor は x 以下の最大の整数（床関数）を表します。これは、M の小数第 4 位以下を切り捨てたものを 1000 倍した値に相当します。
ヒント： 連続する K 日間の売上の合計の最大値を S とすると、T_i はすべて整数であるため S も整数であり、\lfloor M \times 1000 \rfloor = \left\lfloor \frac{1000 \times S}{K} \right\rfloor が成り立ちます。したがって、答えは整数演算のみで求めることができます。
制約
- 1 \leq K \leq N \leq 2 \times 10^5
- 1 \leq T_i \leq 10^6
- 入力はすべて整数
入力
N K T_1 T_2 \cdots T_N
- 1 行目には、売上記録の日数を表す整数 N と、期間の長さを表す整数 K が、スペース区切りで与えられる。
- 2 行目には、各日の売上を表す整数 T_1, T_2, \ldots, T_N が、スペース区切りで与えられる。
出力
連続する K 日間の売上の平均値の最大値を M としたとき、\lfloor M \times 1000 \rfloor の値を 1 行で出力せよ。
入力例 1
5 3 10 20 30 25 15
出力例 1
25000
入力例 2
7 2 100 150 80 200 190 50 120
出力例 2
195000
入力例 3
10 4 1234 5678 9012 3456 7890 2345 6789 1357 2468 8024
出力例 3
6509000
Score : 300 pts
Problem Statement
Takahashi is working a part-time job analyzing sales data for a chain store.
This chain store has sales records for N days, and the sales on day i (1 \leq i \leq N) were T_i yen.
Takahashi wants to calculate the average sales over every consecutive K-day period and find the maximum value, in order to understand the performance of the period with the best sales.
Specifically, for each integer l (1 \leq l \leq N - K + 1), the average sales over the consecutive K days from day l to day l + K - 1 is defined as
M_l = \frac{T_l + T_{l+1} + \cdots + T_{l+K-1}}{K}
Let M be the maximum value of M_l over all l (1 \leq l \leq N - K + 1).
Find \lfloor M \times 1000 \rfloor, where \lfloor x \rfloor denotes the largest integer not exceeding x (the floor function). This corresponds to truncating M below the 4th decimal place and multiplying by 1000.
Hint: Let S be the maximum sum of sales over any consecutive K days. Since all T_i are integers, S is also an integer, and \lfloor M \times 1000 \rfloor = \left\lfloor \frac{1000 \times S}{K} \right\rfloor holds. Therefore, the answer can be computed using only integer arithmetic.
Constraints
- 1 \leq K \leq N \leq 2 \times 10^5
- 1 \leq T_i \leq 10^6
- All inputs are integers
Input
N K T_1 T_2 \cdots T_N
- The first line contains the integer N representing the number of days of sales records and the integer K representing the length of the period, separated by a space.
- The second line contains the integers T_1, T_2, \ldots, T_N representing the sales on each day, separated by spaces.
Output
Let M be the maximum average sales over any consecutive K-day period. Output the value of \lfloor M \times 1000 \rfloor on a single line.
Sample Input 1
5 3 10 20 30 25 15
Sample Output 1
25000
Sample Input 2
7 2 100 150 80 200 190 50 120
Sample Output 2
195000
Sample Input 3
10 4 1234 5678 9012 3456 7890 2345 6789 1357 2468 8024
Sample Output 3
6509000