Educational Segment Tree Contest - ITMED

View as PDF

Submit solution

Points: 0.15
Time limit: 2.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem source:
Educational Segment Tree Contest - Anh Long
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Trò chơi này thật đơn giản: Bạn có ~n~ hộp được đánh số từ 1 đến ~n~ và một số ~k~. Trong mỗi hộp có một tấm séc ghi số ~a_i~. Nếu bạn chọn hộp ~i~ và ~a_i\ge0~ thì bạn sẽ nhận được ~a_i~ đồng còn ~a_i \le 0~ thì bạn sẽ phải "lộp" cho chương trình ~|a_i|~ đồng.

Bằng khả năng "see the future" khủng của mình, bạn đã biết được con số ghi trên tấm séc trong mỗi hộp. Nhiệm vụ của bạn bây giờ chỉ còn là kiếm nhiều tiền nhất. Nhưng, trò chơi này có 2 điều luật như sau:

  • Ví dụ bạn chọn hộp thứ ~i~, thì hộp tiếp theo bạn chọn phải có chỉ số ~\le i+k~. Với hộp đầu tiên thì bạn có thể chọn tùy ý.
  • Bạn chỉ được chọn các hộp từ trái qua phải. Nói cách khác, nếu bạn chọn hộp thứ ~i~ thì hộp tiếp theo bạn chọn phải có số thứ tự ~>i~.

Bạn hãy tìm cách chơi để đem về nhà được nhiều tiền nhất nhé.

Input

  • Dòng đầu tiên là 2 số ~n~ và ~k~ (~1\le n,k \le 10^5~)
  • Dòng thứ 2 là ~n~ số nguyên là số ghi trên tấm séc trong mỗi hộp (~|a_i|\le 10^9~)

Output

1 số duy nhất là số tiền nhiều nhất bạn có thể kiếm được

Sample Input

5 2
-1 -2 3 -4 5

Sample Output

8

Comments

Please read the guidelines before commenting.



  • -14
    phuoc2902   commented on 24, Dec, 2021, 16:06

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -12
    thanhchauns2   commented on 24, Dec, 2021, 12:05

    This comment is hidden due to too much negative feedback. Show it anyway.


  • 41
    YugiHackerKhongCopCode   commented on 20, Dec, 2021, 19:22

    Cmt này spoil thuật!

    Có thể không cần dùng IT

    Quy hoạch động

    Gọi f[i] là số tiền nhiều nhất có thể kiếm được khi chọn hộp thứ i là hộp bắt đầu

    => f[i] = max(f[j], 0) + a[i] với j từ i+1 đến i+k

    Cách tính max f[i+1] ... f[i+k]:

    C1: Dùng IT

    Code lấy max của đoạn như bình thường. (O(NlogN))

    C2: Dùng deque

    Tìm max trên đoạn tịnh tiến độ dài k, vừa cập nhật mảng f, vừa cập nhật deque. (O(N))