💻
Elearning
CodePath
Problems
Contests
Roadmap
🐱 Scratch
🔐 Login
Dãy con tăng có trọng số
DP4_02_wlis
## Bài 9. ### Đề bài Có `n` phần tử theo thứ tự, phần tử `i` có khóa `hi` và trọng số dương `wi`. Chọn một dãy con giữ nguyên thứ tự sao cho các khóa tăng nghiêm ngặt, tối đa hóa tổng trọng số. ### Dữ liệu vào Dòng 1: `n`; `n` dòng tiếp theo chứa `hi wi`. ### Kết quả Tổng trọng số lớn nhất. ### Ràng buộc `1 ≤ n ≤ 2·10^5`, `|hi|≤10^9`, `1≤wi≤10^9`. ### Phân chia subtask | Subtask | Điểm | Ràng buộc | |---:|---:|---| | 1 | 30% | n ≤ 25 | | 2 | 30% | n ≤ 3000 | | 3 | 40% | n ≤ 2·10^5 | ### Ví dụ **Input** ```text 5 3 5 1 4 2 7 4 6 5 10 ``` **Output** ```text 27 ``` **Giải thích:** Chọn các khóa `1,2,4,5` có trọng số `4+7+6+10=27`.
✅ Đã 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