Chó săn
Đề bài
Mô tả
Một anh nông dân trẻ nghèo có con chó săn. Mỗi con chó săn có ba thuộc tính: cân nặng, trí thông minh và giá trị thị trường. Một ngày nọ, anh cần bán một số con chó săn để lấy tiền cưới vợ. Anh đã tìm được một tỷ phú đủ tiền mua chó. Tuy nhiên, vị tỷ phú muốn chọn các con chó thỏa mãn điều kiện sau: hai con chó và có thể cùng được chọn nếu khi cân nặng của lớn hơn hoặc bằng cân nặng của thì trí thông minh của cũng phải lớn hơn hoặc bằng trí thông minh của , và ngược lại (khi trí thông minh của lớn hơn hoặc bằng trí thông minh của thì cân nặng của cũng phải lớn hơn hoặc bằng cân nặng của ). Điều kiện này phải đúng với mọi cặp con chó được chọn.
Hãy giúp anh nông dân chọn các con chó để bán sao cho tổng số tiền thu được là lớn nhất.
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên dương ().
- Dòng thứ đến dòng thứ : mỗi dòng chứa số nguyên cách nhau bởi dấu cách, lần lượt là cân nặng, trí thông minh và giá trị thị trường của một con chó săn. Các số nguyên đều nằm trong đoạn .
Dữ liệu ra
In ra một số nguyên dương là tổng giá trị thị trường lớn nhất của các con chó được chọn.
Ràng buộc
- Cân nặng, trí thông minh, giá trị thị trường đều thuộc .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 7 2300 7 10 2000 13 40 2800 13 40 2100 11 50 2500 6 20 2600 9 15 2000 17 50 |
90 | Ví dụ của đề gốc. Chọn con thứ (2100, 11, 50) và con thứ (2800, 13, 40). |
| 4 1 1 5 2 1 5 1 2 5 1 1 3 |
8 | Ví dụ bổ sung, tính bằng lời giải mẫu. Chọn con thứ và con thứ (giống hệt nhau về cân nặng và trí thông minh). Không thể chọn thêm con thứ : trí thông minh của con lớn hơn hoặc bằng của con nhưng cân nặng thì nhỏ hơn. |
Bình luận