ZOJ Problem Set - 3288
Nevermore the Shadow Fiend is among the most powerful heroes in the game Defense of the Ancients. Indeed, Zhejiang University is famous for one especially good Shadow Fiend player. However, to master this hero is not so easy, for starters, it's enlightening to learn how to maximize the damage output of Shadow Fiend when chasing down enemies. Shadow Fiend has three powerful skills.
Now, suppose an enemy's distance is initially K from Shadow Fiend and Shadow Fiend wants to kill the enemy. The enemy is trying to escape at speed V, and for simplicity we suppose this Shadow Fiend will not move but just use his techniques to kill the enemy. Alas, there are restrictions to Shadow Fiends skills, they cannot be used instantaneously. For each of the N ShadowRaze skills, there is T1 time to prepare and after which the skill can be used. For Requiem of Souls the time to prepare is T2. The techniques must be used right after the preparation time, you can not prepare then wait some time to use it.
You are to determine the maximum damage Shadow Fiend can do to the enemy.
Since the skills have rather long Cooldowns, each of the N ShadowRaze attack can be used only once, and Requiem of Souls can be used once. Also, for the N ShadowRaze attacks, it would make no sense if one attack's range covers another, which would render imbalance in the game. Thus, there is no i and j that xi < xj and yi > yj.
The first line is the number T(1 <= T <= 100), the number of test cases. T test cases follow and are of the following format: The first line contains integers: N(1 <= N <= 1000), D(1 <= D <= 100), M(1 <= M <= 100), P(0 <= P <= 100), K(0 <= K <= 100), V(0 < V <= 10), T1(0 < T1 <= 10), T2(0 < T2 <= 10). Then follows N lines, each containing two integers xi and yi,1 <= i <= N,both numbers are within 10000.
For each test case output one integer, the maximum damage Shadow Fiend can do to the enemy. For Requiem of Souls, use the expression M*P/(X*X) to compute the integer value of the damage, where X is the distance when Requiem of the souls is used.
2 1 100 100 100 0 10 1 1 10 15 1 100 100 100 0 10 1 1 20 30
Author: SONG, Yu
Source: ZOJ Monthly, January 2010