Tiền từ hư không
Đề bài
Mô tả
Trong bài này, bạn sẽ giải một trong những thử thách sâu sắc nhất của loài người trên khắp thế giới từ thuở khai thiên lập địa: làm thế nào để kiếm thật nhiều tiền.
Bạn là người trung gian trên thị trường widget. Công việc của bạn là mua widget từ các công ty sản xuất widget và bán chúng cho các công ty tiêu thụ widget. Mỗi công ty tiêu thụ có một yêu cầu mở là mua một widget mỗi ngày cho đến một ngày kết thúc nào đó, với một mức giá mà công ty sẵn sàng trả cho mỗi widget. Mặt khác, mỗi công ty sản xuất có một ngày bắt đầu, từ đó công ty có thể giao widget, và một mức giá cho mỗi widget giao đi.
Do luật cạnh tranh công bằng, bạn chỉ được ký hợp đồng với đúng một công ty sản xuất và đúng một công ty tiêu thụ. Bạn sẽ mua widget từ công ty sản xuất, mỗi ngày một chiếc, bắt đầu từ ngày công ty đó có thể bắt đầu giao hàng và kết thúc vào ngày do công ty tiêu thụ quy định. Vào mỗi ngày trong khoảng đó, bạn kiếm được phần chênh lệch giữa giá bán của công ty sản xuất và giá mua của công ty tiêu thụ.
Mục tiêu của bạn là chọn công ty tiêu thụ và công ty sản xuất sao cho lợi nhuận lớn nhất.
Dữ liệu vào
Dòng đầu tiên chứa hai số nguyên và (), lần lượt là số công ty sản xuất và số công ty tiêu thụ trên thị trường.
Tiếp theo là dòng, dòng thứ chứa hai số nguyên và (): giá (tính bằng đô la) mà công ty sản xuất thứ bán một widget và ngày mà widget đầu tiên của công ty này sẵn sàng.
Sau đó là dòng, dòng thứ chứa hai số nguyên và (): giá (tính bằng đô la) mà công ty tiêu thụ thứ sẵn sàng trả cho một widget và ngày ngay sau ngày cuối cùng phải giao widget cho công ty này.
Dữ liệu ra
In ra tổng số đô la lớn nhất bạn có thể kiếm được. Nếu không có cách ký hợp đồng nào mang lại lợi nhuận dương, in ra .
Ràng buộc
- .
- với mọi .
- với mọi .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 2 1 3 2 1 3 5 7 2 |
5 | Chọn công ty sản xuất thứ hai (giá , từ ngày ) và công ty tiêu thụ thứ hai (giá , ngày kết thúc ): giao widget vào ngày , lãi . |
| 1 2 10 10 9 11 11 9 |
0 | Công ty tiêu thụ thứ nhất trả giá thấp hơn giá bán , công ty tiêu thụ thứ hai kết thúc ở ngày trước ngày bắt đầu : không có hợp đồng nào có lãi. |
Bình luận