Bedao Regular Contest 18 - Hai dãy con
Xem dạng PDF
Gửi bài giải
Điểm:
0,15 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Cho dãy ~A~ gồm ~N~ phần tử nguyên dương và một số nguyên dương ~K~. Tìm hai dãy liên tiếp của dãy ~A~ gồm đúng ~K~ phần tử (hai dãy không được phép giao nhau), sao cho chênh lệch tổng các phần tử của hai dãy là lớn nhất.
Input
Dòng đầu tiên gồm hai số nguyên dương ~N~, ~K~ ~(2 \le N \le 10^6, 1 \le K \le N / 2)~.
Dòng thứ hai gồm ~N~ số nguyên dương có giá trị không quá ~10^9~ mô tả dãy số ~A~.
Output
- In ra một số nguyên dương là giá trị chênh lệch lớn nhất tìm được.
Scoring
| Subtask | Điểm | Giới hạn |
|---|---|---|
| 1 | ~20~ | ~N \le 100~ |
| 2 | ~30~ | ~N \le 10^3~ |
| 3 | ~50~ | Không có ràng buộc nào. |
Sample Input 1
5 2
1 3 2 1 8
Sample Output 1
5
Notes
Đáp án lớn nhất có thể đạt được là chọn 2 đoạn ~[1, 2]~ và đoạn ~[3, 4]~. ~|(1 + 3) - (1 + 8)|~ = 5
Bình luận