Chọn ĐTQG Tây Ninh 2026 - Chọn không kề nhau
Xem dạng PDF
Gửi bài giải
Điểm:
30,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
1G
Input:
stdin
Output:
stdout
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Output Only, Pascal, PyPy, Python, Scratch, TEXT
Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài
Có ~n~ món hàng xếp theo thứ tự. Món hàng thứ ~i~ có chi phí là ~c_i~ và giá trị là ~v_i~. Cho ngân sách ~B~. Mỗi món hàng chỉ có thể được chọn một lần, không được lấy hai món hàng kề nhau. Hãy tìm tổng giá trị lớn nhất của các món hàng được chọn sao cho tổng chi phí không vượt quá ngân sách ~B~.
Input
Dòng đầu chứa hai số nguyên ~n,B~;
Dòng thứ ~i~ trong ~n~ dòng tiếp theo chứa hai số nguyên ~c_i,v_i~.
Output
In tổng giá trị lớn nhất có thể đạt được.
Ràng buộc: ~1 \le n \le 500; 1 \le c_i,B \le 10^{18}; 1 \le v_i \le 100; 1 \le i \le n~.
Scoring
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| 1 | ~20\%~ | ~n \le 25~ |
| 2 | ~20\%~ | ~B \le 200000~ |
| 3 | ~20\%~ | ~c_i=1~ với mọi ~i~ |
| 4 | ~20\%~ | ~B \ge c_1+c_2+\dots+c_n~ |
| 5 | ~20\%~ | Không có ràng buộc nào thêm |
Sample Input 1
5 10
6 8
4 7
5 6
4 8
3 5
Sample Output 1
16
Notes
Chọn món ~1~ và món ~4~. Hai vị trí không kề nhau, tổng chi phí là ~6+4=10~ và tổng giá trị là ~8+8=16~.
Bình luận