Bedao Regular Contest 18 - Hai dãy con

View as PDF
Submit solution
Points: 0.15 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout
Author:
bedao
Problem type
Allowed languages
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

Comments

Please read the guidelines before commenting.


  • 6
    YougiTuber  commented on Nov. 8, 2024, 1:30 a.m.

    Spoil dành cho các bạn được ~99~ điểm:

    Chú ý case ~k = 1~

    2 1
1 10

    • 11
      LA_NHVKhang  commented on Nov. 8, 2024, 7:44 a.m.

      Cảm ơn anh 🤩


  • 1
    vudinhlong  commented on May 16, 2024, 3:57 a.m.

    Cách khác so với lời giải của tác giá các bạn nhé:

    https://ideone.com/9wHlnD