💻
Elearning
CodePath
Problems
Contests
Roadmap
🐱 Scratch
🔐 Login
Trạm sạc cách nhau
DP2_01_gapselect
### Đề bài Có `n` vị trí trên một đường thẳng theo thứ tự. Chọn một số vị trí để nhận giá trị `ai`. Giữa hai vị trí được chọn liên tiếp phải có ít nhất `G` vị trí không được chọn. Tìm tổng giá trị lớn nhất. ### Dữ liệu vào Dòng 1: `n G`; dòng 2: `a1..an`. ### Kết quả Tổng lớn nhất. ### Ràng buộc `1 ≤ n ≤ 2·10^5`, `0 ≤ G < n`, `0 ≤ ai ≤ 10^9`. ### Phân chia subtask | Subtask | Điểm | Ràng buộc | |---:|---:|---| | 1 | 30% | n ≤ 25 | | 2 | 30% | n ≤ 5000 | | 3 | 40% | n ≤ 2·10^5 | ### Ví dụ **Input** ```text 6 1 5 1 4 9 2 8 ``` **Output** ```text 22 ``` **Giải thích:** Với `G=1`, hai vị trí được chọn phải cách nhau ít nhất 2 chỉ số. Chọn các vị trí `1,4,6` được tổng `5+9+8=22`.
✅ Đã AC: 1 / 1 submissions
⬅ Contest
🚀 Nộp bài
💡 Gợi ý AI
📌 Bài kế
📋 Copy đề
⚙️
⬅ Contest
🚀 Nộp bài
💡 Gợi ý
📌 Bài kế
📋 Copy
📖 Hướng dẫn học tập
Học trò tri ân
☕ Một ly cà phê sẻ chia
Bạn bè ủng hộ
🍜 Một bát phở ấm lòng
💳 Quét mã ủng hộ tuỳ tâm nhé!
💬 Liên hệ Zalo!
Đóng