#1289. SUBSEQ - Đoạn con

Bộ nhớ: 256 MiB Thời gian: 500 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

Hải Phòng - Ngày 06 tháng 11 năm 2020 (pm)

Cho dãy số nguyên 𝑎_1, 𝑎_2, … , 𝑎_𝑛 và số nguyên dương 𝑘 .

Yêu cầu: Tìm đoạn con liên tiếp gồm không ít hơn 𝑘 số nguyên trong dãy sao cho tổng các số nguyên thuộc đoạn là lớn nhất.

Dữ liệu vào:

  • Dòng đầu ghi hai số nguyên dương 𝑛, 𝑘\ (1 ≤ 𝑘 ≤ 𝑛 ≤ 10^6) ;
  • 𝑛 dòng tiếp theo, dòng thứ 𝑖 chứa số nguyên 𝑎_𝑖\ (|𝑎_𝑖| ≤ 1000) .

Dữ liệu ra:

  • Một số nguyên là tổng các giá trị đoạn con theo yêu cầu.

Ví dụ:

Dữ liệu vào:
8 3
-20
90
-30
-20
80
-70
-60
125
Dữ liệu ra:
120