JOI 2015 - Growing Vegetables is Fun 2
Xem PDF
Điểm:
2400 (p)
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Khu vườn có \(N\) ô từ tây sang đông; cây IOI \(i\) cao \(H_i\), bán được \(P_i\) yên nếu ra quả. Vào mùa xuân, JOI có thể nhổ cây \(i\) với chi phí \(C_i\); cây bị nhổ sẽ chết.
Một cây còn lại ra quả khi và chỉ khi không có cây còn lại cao hơn nó ở phía tây, hoặc không có cây còn lại cao hơn nó ở phía đông. Lợi nhuận bằng tổng giá bán cây ra quả trừ tổng chi phí nhổ. Hãy tối đa hóa lợi nhuận.
Dữ liệu vào
Dòng đầu chứa \(N\). Mỗi trong \(N\) dòng sau chứa \(H_i,P_i,C_i\).
Dữ liệu ra
In lợi nhuận lớn nhất.
Ràng buộc
\[
3\le N\le100\,000,
\]
\[
1\le H_i,P_i,C_i\le10^9.
\]
Phân nhóm
- Nhóm 1 (10 điểm): \(N\le20\).
- Nhóm 2 (10 điểm): \(N\le300\).
- Nhóm 3 (10 điểm): \(N\le5000\).
- Nhóm 4 (50 điểm): mọi \(H_i\) đôi một khác nhau.
- Nhóm 5 (20 điểm): không có ràng buộc bổ sung.
Ví dụ
Ví dụ 1
Input
7
22 60 30
46 40 30
36 100 50
11 140 120
38 120 20
24 90 60
53 50 20Output
320Giải thích
Trong ví dụ 1, nhổ cây 2 và 7. Các cây còn lại là 1, 3, 4, 5, 6; cây 4 không ra quả, bốn cây kia ra quả. Lợi nhuận là \(60+100+120+90-30-20=320\).
Ví dụ 2
Input
5
18 150 180
18 380 250
18 140 170
17 180 900
14 150 520Output
1000Giải thích
Trong ví dụ 2, không cần nhổ cây nào và mọi cây đều ra quả.
Ví dụ 3
Input
8
52 156 59
15 166 185
16 122 115
24 161 154
44 252 678
32 225 557
44 155 254
59 57 253Output
854Kỳ thi:
- JOI 2015 Final Camp - Ngày 1 (3 Tháng 1., 2015)
Bình luận