Con đường tơ lụa... với robot!
Đề bài
Mô tả
Một phần của con đường tơ lụa cổ xưa từng đi qua miền nam Kazakhstan. Bạn đang mơ mộng về một con đường tơ lụa hiện đại với những đặc điểm riêng. Dọc theo con đường tưởng tượng này có các robot và các cửa hàng cất giữ tiền tenge (đơn vị tiền tệ quốc gia của Kazakhstan). Nếu một robot di chuyển tới vị trí có cửa hàng, robot đó sẽ thu toàn bộ số tenge của cửa hàng ấy cho bạn.
Chi phí di chuyển một robot là tenge cho mỗi mét di chuyển. Vì vậy lợi nhuận khi đưa một robot tới một cửa hàng bằng số tenge mà cửa hàng đó đang giữ trừ đi số mét robot đã đi để tới được cửa hàng.
Xét kịch bản sau, kéo dài trong nhiều ngày. Ban đầu con đường trống, không có robot hay cửa hàng nào. Mỗi ngày, hoặc một robot mới, hoặc một cửa hàng mới được đặt tại một vị trí chưa có ai chiếm trên con đường. Ngay trước đó, mỗi cửa hàng đã có trên đường được bổ sung tenge để tổng số tiền của nó bằng đúng số tiền lúc nó mới được đặt lên đường, và mỗi robot được đưa về vị trí xuất phát ban đầu của nó.
Với mỗi ngày, hãy xác định lợi nhuận lớn nhất có thể thu được bằng cách di chuyển các robot để lấy tenge từ các cửa hàng. Lưu ý rằng không có hai robot nào xuất phát ở cùng một vị trí, nhưng chúng có thể ở cùng một vị trí trong khi di chuyển. Trong một ngày, mỗi cửa hàng chỉ có thể bị lấy hết tiền một lần.
Dữ liệu vào
Dòng đầu tiên chứa số nguyên (), số ngày.
Tiếp theo là dòng, dòng thứ bắt đầu bằng số nguyên : nếu ngày có một robot mới được thêm vào, nếu ngày đó có một cửa hàng mới được thêm vào. Tiếp theo là số nguyên (), vị trí của robot mới hoặc cửa hàng mới. Nếu , dòng đó còn chứa thêm số nguyên (), số tenge của cửa hàng. Mọi vị trí được cho đều đôi một khác nhau.
Dữ liệu ra
In ra số nguyên, số thứ là lợi nhuận lớn nhất có thể thu được sau ngày thứ , mỗi số trên một dòng.
Ràng buộc
- .
- , , .
- Các đôi một khác nhau.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 6 1 20 2 15 15 2 40 50 1 50 2 80 20 2 70 30 |
0 10 35 50 50 60 |
Ngày 2: robot ở đi tới , lời . Ngày 3: robot đi sang trái tới rồi quay lại sang phải tới , đi mét, thu , lời . Ngày 4: robot ở lấy cửa hàng ở (lời ), robot ở lấy cửa hàng ở (lời ). Ngày 6: robot ở đi sang trái tới rồi sang phải tới (đi mét, thu ), robot ở lấy cửa hàng ở , tổng lời . |
| 5 1 70000000 2 100000000 40000000 2 20000000 30000000 2 60000000 100000000 2 90000000 90000000 |
0 10000000 10000000 90000000 180000000 |
Ngày 5: robot đi sang trái tới rồi quay sang phải tới , đi mét và thu tenge. Cửa hàng ở ở quá xa nên không đáng lấy. |
Bình luận