Double Radars
Time limit1sMemory limit2048 MB
Pick a start house and move at speed v around a circle of k houses to collect the most coin value without meeting either of two bouncing radars.
- Level
Hard8 of 10
- Topics
- Simulation, Math, Two pointers
- Solved
- No attempts yet
Problem
Ali recently found a treasure and has arranged the coins from the treasure around a circle. There are houses around the circle with equal distances. Houses are numbered through consecutively in the clockwise direction. The treasure contains coins, where the th coin (for ) has the value and is located at the house . To protect the treasure, Ali has installed two radars stationed at the center of the circle, monitoring its circumference. Radar (for ) starts by monitoring house and moves houses per minute. More intuitively, every minutes, Radar goes one house forward. Initially, the first radar moves clockwise, and the second radar moves counterclockwise. Whenever the two radars meet, they both reverse their directions. Note that this can happen in the area between two adjacent houses. Gholi, who wants to steal as many coins as possible, plans to start at an arbitrary house on the circle and move at most houses per minute in either direction (clockwise or counterclockwise). He starts moving at time zero. He can reverse his direction anytime or stay still for a while. If Gholi crosses paths with one of the radars at any moment, he is caught and sent to jail. He cannot steal a coin if this happens at a house. Help Gholi maximize the total value of the coins he can steal before being detected by the radars.
Input
The first line contains three integers, () the number of coins, () the number of houses around the circle, and () the speed of Gholi. The second line contains the starting monitoring house and speed of the first radar (, ). The third line contains the starting monitoring house and speed of the second radar (, ). It is guaranteed that . The fourth line contains distinct integers , the houses where the coins are located (). The fifth line contains integers , the value of each coin ().
Output
Output the maximum total value of coins Gholi can steal before being detected by the radars.