시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 35 | 10 | 9 | 30.000% |
There are M (1 ≤ M ≤ 1, 000) planets each with vi (1 ≤ vi ≤ 10, 000) units of resources and radius ri (1 ≤ ri ≤ 100).
Starting from (0, 0, 0), you travel in straight lines through N (1 ≤ N ≤ 1, 000) waypoints in a specific order.
Whenever you travel within D + ri (1 ≤ D ≤ 50) units from a planet’s center, you can mine the planet using your tractor beam retrieving vi units of resources. Note that if you are exactly D units from the surface of the planet, you can mine the planet. If your path takes you through a planet, do not worry, since your spaceship can drill through planets, which makes mining even easier. Also note that you cannot mine the same planet on a subsequent visit.
Give the number of minerals that can be mined on your journey.
Hint: you should do all calculations with 64-bit integers.
On the first line of input is the number M, the number of planets. On the next M lines are five integers describing each of the M planets. These integers are xi yi zi vi ri, where the planet i is at position (xi, yi, zi), (where −1, 000 ≤ xi, yi, zi ≤ 1, 000) and this planet has vi resources and radius ri. On the next line is the number N, the number of waypoints to pass through. Each of the next N lines contains the position of these waypoints, as three integers xi yi zi (−1, 000 ≤ xi, yi, zi ≤ 1, 000). The last line of input is the number D, the maximum distance from a planet’s surface that your ship can be and still mine a planet.
On one line, output the amount of minerals that you can mine on your journey.
3 10 0 0 1 1 0 10 0 2 1 0 0 10 4 1 3 8 0 0 0 7 0 0 0 9 1
5