USACO 2022 US Open Contest, Gold, Apple Catching
Xem PDFTrời ơi!!! Một cơn mưa táo!! Đến một lúc nào đó, các quả táo này sẽ rơi xuống trục số. Và cũng đến một lúc nào đó, các chú bò của nông dân John sẽ đến trục số và bắt đầu hứng táo.
Nếu như một quả táo chạm vào trục số mà không được hứng, nó sẽ biến mất mãi mãi. Ngược lại, nếu như một chú bò đến kịp lúc quả táo chạm đất, chú ta sẽ hứng được quả táo đó. Biết rằng mỗi chú bò chỉ có thể di chuyển một đơn vị khoảng cách mỗi giây và một khi đã hứng được một quả táo, chú ta sẽ đi ra khỏi trục số ngay lập tức.
Hãy cho biết số táo nhiều nhất hứng được là bao nhiêu nếu như các chú bò hứng một cách tối ưu!
Input
- Dòng đầu tiên là số \(N\) \((1 \le N \le 2 \times 10^5)\) là số lần một quả táo rơi trúng trục số hoặc một chú bò xuất hiện ở trục số.
- \(N\) dòng tiếp theo, mỗi dòng là bộ bốn số nguyên \(q_i, t_i, x_i, n_i\) \((q_i \in \{1, 2\}, 0 \le t_i \le 10^9, 0 \le x_i \le 10^9, 1 \le n_i \le 10^3)\):
- Nếu \(q_i = 1\), \(n_i\) chú bò của bác John sẽ xuất hiện tại vị trí \(x_i\) vào thời điểm \(t_i\).
- Nếu \(q_i = 1\), \(n_i\) quả táo sẽ rơi trúng trục số tại vị trí \(x_i\) vào thời điểm \(t_i\).
- Dữ liệu đảm bảo mọi cặp \((t_i, x_i)\) là đôi một khác nhau.
Output
- Số lượng táo lớn nhất mà đàn bò của John thu hoạch được.
Scoring
- \(100\%\) số test không có điều kiện ràng buộc.
Test 1
Input
5
2 5 10 100
2 6 0 3
2 8 10 7
1 2 4 5
1 4 7 6
Output
10
Note
Trong ví dụ này, không có quả táo nào được hứng trong \(100\) quả táo rơi trúng trục số tại thời điểm \(t_i = 5\). Đây là một cách để có thể thu hoạch được \(10\) quả táo:
- Cả sáu chú bò của bác John xuất hiện tại trục số ở thời điểm \(t = 4\) di chuyển đến từ vị trí \(x = 7\) đến vị trí \(x = 10\) và thu hoạch được \(6\) quả táo xuất hiện ở vị trí đó lúc \(t = 8\).
- Một chú bò xuất hiện tại thời điểm \(t = 2\) di chuyển từ vị trí \(x = 4\) đến vị trí \(x = 10\) và thu hoạch được \(1\) quả táo xuất hiện tại vị trí đó lúc \(t = 8\).
- Ba chú bò xuất hiện tại thời điểm \(t = 2\) di chuyển từ vị trí \(x = 4\) đến vị trí \(x = 0\) và thu hoạch được \(3\) quả táo xuất hiện tại vị trí đó lúc \(t = 6\).
Test 2
Input
5
2 5 10 100
2 6 0 3
2 8 11 7
1 2 4 5
1 4 7 6
Output
9
Note
Trong ví dụ này, cũng không quả táo nào được hứng trong \(100\) quả táo xuất hiện vào thời điểm \(t = 5\). Thêm nữa, không một chú bò nào xuất hiện tại thời điểm \(t = 2\) hứng được táo xuất hiện tại thời điểm \(t = 8\). Đây là một cách để thu hoạch được \(9\) quả táo:
- Cả sáu chú bò của bác John xuất hiện tại trục số ở thời điểm \(t = 4\) di chuyển đến từ vị trí \(x = 7\) đến vị trí \(x = 10\) và thu hoạch được \(6\) quả táo xuất hiện ở vị trí đó lúc \(t = 8\).
- Ba chú bò xuất hiện tại thời điểm \(t = 2\) di chuyển từ vị trí \(x = 4\) đến vị trí \(x = 0\) và thu hoạch được \(3\) quả táo xuất hiện tại vị trí đó lúc \(t = 6\).
Bình luận