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ả:
bedao
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

Hãy đọc nội quy trước khi bình luận.


  • 0
    chaudiensdk5  đã bình luận lúc 20, Tháng 4, 2025, 9:35

    testcase 11 là gì v mn


  • -3
    saimondragonvn  đã bình luận lúc 13, Tháng 3, 2025, 4:15

    clm may nguu vcl tk chó gia Huy


  • 0
    nb_truonghansieu_legiabao  đã bình luận lúc 20, Tháng 2, 2025, 17:42 ← chỉnh sửa

    hello


  • 12
    YougiTuber  đã bình luận lúc 8, Tháng 11, 2024, 1:30

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

    Chú ý case ~k = 1~

    2 1
1 10

    • 12
      LA_NHVKhang  đã bình luận lúc 8, Tháng 11, 2024, 7:44

      Cảm ơn anh 🤩


  • 1
    vudinhlong  đã bình luận lúc 16, Tháng 5, 2024, 3:57

    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