TẦN SUẤT (10 ĐIỂM) CÔNG TY VIỄN THÔNG AZPHONE ĐANG ĐỐI MẶT VỚI TÌNH T...

Bài 1: Tần suất (10 điểm)

Công ty viễn thông AZPHONE đang đối mặt với tình trạng nghẽn mạng 4G tại một số thời điểm

trong năm. Hiện tại công ty đã ghi nhận được số lượng thuê bao truy cập trong từng giây của N giây

liên tiếp, là dãy số nguyên không âm a 1 , a 2 , …, a N (a i là số lượng thuê bao tại giây i, 1 ≤ i ≤ N).

Công ty muốn biết tần suất truy cập T(i, L) của L giây liên tiếp kể từ giây i, trong đó T(i, L) = (a i +

a i+1 + … + a i+L-1 )/L (1 ≤ i < N - L) với điều kiện L phải không nhỏ hơn một hằng số K cho trước

(1 ≤ K ≤ L ≤ N).

Yêu cầu: Cho biết K và dãy a 1 , a 2 , …, a N . Hãy giúp công ty xác định giá trị lớn nhất của T(i, L).

Dữ liệu vào: Được đọc từ file văn bản RATE.INP gồm:

 Dòng đầu tiên là hai số nguyên N và K (1 ≤ N ≤ 300000)

 Dòng thứ hai gồm dãy số nguyên không âm a 1 , a 2 , …, a N (0 ≤ a i ≤ 10 ⁶ ).

Các số trên cùng một dòng cách nhau một ký tự trống (dấu cách).

Kết quả: Ghi ra file văn bản RATE.OUT gồm duy nhất một dòng là giá trị lớn nhất của T(i, L), giá

trị bình quân gồm 6 chữ số sau dấu chấm thập phân.

Ví dụ:

RATE.INP RATE.OUT RATE.INP RATE.INP

4 1

2 4 3 4 1 3.666667

1 0 4 3 4.000000 5 2

Ràng buộc:

 60% số test ứng với 60% số điểm của bài có N ≤ 5000.

 Giới hạn thời gian cho mỗi test là 1 giây.