HSG THPT Thanh Hóa 2022 - Mario
View as PDF
Trò chơi Mario bao gồm nhân vật hoạt hình Mario và các cây nấm được thiết kế trên một trục số nằm ngang. Có ~N~ cây nấm, cây thứ ~i~ đặt ở vị trí có tọa độ ~X_i~ và chứa ~W_i~ sức mạnh. Mario đang đứng ở vị trí ~X~, có thể di chuyển theo chiều dương hay âm của trục số tùy ý. Nếu đi qua cây nấm ~i~, nó sẽ ăn cây nấm đó và sẽ được tăng thêm ~W_i~ sức mạnh, đồng thời cây nấm ~i~ sẽ biến mất.
Yêu cầu: Thực hiện một lượt chơi để Mario ăn được nhiều sức mạnh nhất, biết rằng mỗi lượt chơi thì Mario chỉ có thể di chuyển quãng đường dài tối đa bằng ~K~.
Input
Từ tệp văn bản MARIO.INP gồm 2 dòng có cấu trúc như sau:
Dòng thứ nhất chứa ba số nguyên ~N~, ~X~ và ~K~ (~1 \leq N \leq 10^5, |X| \leq 10^6, 1 \leq K \leq 10^9~).
Dòng thứ ~i~ trong ~N~ dòng tiếp theo chứa ~2~ số nguyên ~X_i~ và ~W_i~ (~|X_i| \leq 10^6, 1 \leq W_i \leq 10^9~).
Output
Ghi ra tệp văn bản MARIO.OUT một số nguyên duy nhất là tổng sức mạnh tối đa Mario ăn được từ các cây nấm sau một lượt chơi.
Scoring
| Subtask | Điểm | Giới hạn |
|---|---|---|
| 1 | ~50~ | ~N \leq 10^4~ |
| 2 | ~50~ | Không có ràng buộc gì thêm |
Sample Input 1
4 3 7
0 9
4 1
5 5
7 8
Sample Output 1
15
Comments
Theo mình thì test mẫu không có bị sai. Mình đi từ 3->5 (mất 2); 5->0 (mất 5). Tổng cộng mất 7 (vừa đủ)
Theo mình thì bạn hiểu sai đề rồi nha OUTPUT đúng sẽ là 23
This comment is hidden due to too much negative feedback. Show it anyway.
This comment is hidden due to too much negative feedback. Show it anyway.
This comment is hidden due to too much negative feedback. Show it anyway.