SEQ - Đề án cây xanh

View as PDF

Submit solution

Points: 1.00 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem types
Allowed languages
C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift

Đề án thay thế cây xanh Hà Nội được ban hành tháng 8/2013 với mục tiêu chặt hạ thay thế 6.700 cây xanh tại nhiều tuyến phố nội đô. Dự án đã thực hiện tại một số tuyến phố Huế, Hàng Bài, Kim Mã, Giảng Võ... Nhưng khi thành phố Hà Nội thực hiện chặt hạ thay thế 381 cây xanh trên phố Nguyễn Chí Thanh thì bị dư luận phản ứng dữ dội. Chủ tịch thành phố Nguyễn Thế Thảo đã yêu cầu tạm dừng đề án và tổ chức thanh tra.

seq.jpg

Trước kia, trên đường NT, có rất nhiều cây xanh. Tuy nhiên, để thực hiện việc xây đường sắt trên cao tuyến CL-HĐ, một số cây xanh trên đường cần được chặt bỏ.

Mỗi cây xanh có một giá trị khác nhau. Tuy nhiên, để giữ lại bóng mát cho người dân, chính quyền quyết định, không được chặt quá ~k~ cây liên tiếp. Nói cách khác, cứ mỗi ~k~ cây liên tiếp thì ít nhất phải còn lại một cây không bị chặt.

Số tiền lớn nhất có thể thu được sau khi chặt cây là bao nhiêu?

Input

  • Dòng đầu tiên chứa số nguyên dương ~n~ và ~k~, trong đó ~n~ là số cây xanh trên đường NT (~1 ≤ n ≤ 6700, 1 ≤ k ≤ 1000~).
  • Dòng tiếp theo chứa ~n~ số nguyên dương, là giá trị của các cây xanh dọc theo con đường. Giá trị của mỗi cây xanh không vượt quá 1000.

Output

  • In ra số tiền lớn nhất có thể thu được sau việc chặt cây.

Sample

Input #1
5 2
10 10 20 20 10
Output #1
40

Problem source: Kc97ble - Free Contest


Comments

Please read the guidelines before commenting.



  • 0
    nobita  commented on Feb. 12, 2024, 8:48 a.m.

    Cho mình hỏi là theo đề là ko được chặt quá k cây liên tiếp thì nếu xét input 5 2 10 10 20 20 10 thì mình chọn thế này có được không 10 10 20 20 10 thì tổng là 50. Mình chọn vậy có được không