#274. Đoạn con trung bình lớn nhất (MAXMED)

Bộ nhớ: 512 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Trùm CUỐI

Đề bài

Cho một dãy số nguyên không âm A có độ dài n . Hãy tìm một đoạn con liên tiếp có độ dài không nhỏ hơn L sao cho trung bình cộng các phần tử của đoạn con đó là lớn nhất.

Dữ liệu:

  • Dòng đầu tiên chứa hai số nguyên cách nhau bởi dấu cách n L .
  • Dòng thứ hai chứa n số nguyên không âm cách nhau bởi dấu cách, biểu thị dãy A_i .

Kết quả:

  • Xuất ra một số nguyên, là giá trị trung bình cộng lớn nhất tìm được nhân với 1000 . Không làm tròn, lấy phần nguyên (cắt bỏ phần thập phân).

Ví dụ:

Dữ liệu:

10 6
6 4 2 10 3 8 5 9 4 1

Kết quả:

6500

Giới hạn: 1 \leq n \leq 10^5, 0 \leq A_i \leq 2000 .