Dầu mỏ
Đề bài
Mô tả
Một phần lớn nền kinh tế thế giới phụ thuộc vào dầu mỏ, vì vậy việc nghiên cứu các phương pháp mới để tìm kiếm và khai thác dầu vẫn đang rất sôi động. Lợi nhuận của các công ty dầu khí phụ thuộc một phần vào việc họ khoan dầu hiệu quả đến đâu. Tập đoàn Dầu thô Quốc tế (ICPC) hy vọng rằng các mô phỏng máy tính quy mô lớn sẽ giúp xác định cách khoan giếng dầu tốt nhất dễ dàng hơn.
Khoan giếng dầu tối ưu ngày càng khó: các mỏ dầu mới phát hiện thường không tạo thành một khối duy nhất mà bị chia thành nhiều phần. ICPC hiện quan tâm tới các mỏ dạng phân tầng, như minh họa ở hình dưới.

Hình: các lớp dầu nằm dưới mặt đất (Surface là mặt đất, trục hướng xuống theo độ sâu). Hình ứng với ví dụ thứ nhất.
Để đơn giản, ICPC chỉ xét trường hợp hai chiều, trong đó các mỏ dầu được mô hình hóa thành các đoạn thẳng nằm ngang, song song với mặt đất. ICPC muốn biết nên đặt một giếng dầu duy nhất như thế nào để khai thác được nhiều dầu nhất. Giếng dầu được khoan từ mặt đất theo một đường thẳng và khai thác dầu từ mọi mỏ mà nó cắt trên đường đi xuống, kể cả khi giao điểm là một đầu mút của mỏ. Hình trên vẽ một giếng như vậy bằng nét đứt, đi qua ba mỏ. Trong mô hình đơn giản này, lượng dầu trong một mỏ bằng chiều rộng của mỏ đó. Hãy giúp ICPC xác định lượng dầu lớn nhất có thể khai thác bằng một giếng dầu duy nhất.
Dữ liệu vào
Dòng đầu tiên chứa một số nguyên , số mỏ dầu.
Mỗi dòng trong dòng tiếp theo mô tả một mỏ gồm ba số nguyên , và : mỏ là đoạn thẳng có hai đầu mút và .
Dữ liệu ra
In ra lượng dầu lớn nhất có thể khai thác bằng một giếng dầu duy nhất.
Ràng buộc
- .
- , .
- Không có hai mỏ nào giao nhau, kể cả tại một điểm.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 5 100 180 20 30 60 30 70 110 40 10 40 50 0 80 70 |
200 | Đây là hình trên. Giếng nét đứt đi qua các mỏ ở độ sâu , và , khai thác . |
| 3 50 60 10 -42 -42 20 25 0 10 |
25 | Mỏ thứ ba có , chiều rộng . Hai mỏ ở cùng độ sâu không thể cùng bị một giếng cắt, mỏ ở độ sâu có chiều rộng . |
Bình luận