| Submit | All submissions | Best solutions | Back to list |
TTBRM - To the Bird-planet |
"Weddings are basically funerals with cake Morty"
Birdperson has invited Rick and Morty to attend his marriage party. Rick doesn't like to go to marriage parties but Morty wants to go, as Birdperson is a very close friend. Also, Birdperson is king of Bird-planet and wants to compensate for the travel expenses for Rick's family. Bird-planet is many light years away from the earth but that is not the problem as Rick has Space Cruiser with hyperspeed.
Space cruiser needs 1 unit of fuel to travel 1 light year but it has a limited capacity 'C' so they may need to refuel in-between. There are many planets between Birdplanet and Earth and the fuel pricing is different on each planet.
Let Earth is numbered as '1' and bird-planet as 'N+1' then they can fuel at n planets (including earth). Distance between any two consecutive planets is 'D' light-years.
Evil Rick wants to maximize the expense of fueling and Birdperson knows this so he put a condition that on arrival there should be zero fuel in the tank.
Your task is to maximize the expense and it is obvious that they can't fuel at bird-planet. Initially, there is zero fuel in the tank.
Input
The first line contains T, the number of test cases. Then the test cases follow.
The first line of each test case contains N, C and D, Number of planets for fueling (including Earth), Capacity of the fuel tank and distance between two consecutive planets
Second-line contains A1 A2 A3… AN, where Ai denotes the price of 1 unit of fuel on ith planet.
Output
For each test case print the maximum possible expense.
Constraints
1 ≤ T ≤ 10
1 ≤ N ≤ 105
1 ≤ D ≤ 105
D ≤ C ≤ 105
1 ≤ Ai ≤ 109
Example
Input: 1 3 5 3 1 5 2 Output: 30
Explanation
- As N=3 so Birdplanet will be 4th planet and hence they will need to travel 3*3=9 light year.
- First they will buy 3 unit fuel from 1st planet to go to 2nd planet, expense: 3*1=3
- They will buy 5 unit of fuel (up to full capacity) at 2nd planet, expense: 5*5=25
- There will be 2 unit of fuel remaining on reaching 3rd planet so the need to buy only 1 more unit of fuel to reach Birdplanet, expense: 1*2=2
- Total expense 3+25+2=30
| Added by: | 17 Sonu Verma |
| Date: | 2019-11-25 |
| Time limit: | 1s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All |
hide comments
|
2021-09-11 06:01:25 Waseem Ahmed
A great problem to learn greedy algorithms from. Thanks @pavansss91 for the test cases |
|
|
2020-03-16 03:06:52 pavansss91
Sample tricky test cases are given below: Input: 2 4 7 3 3 2 1 1 4 7 3 3 1 2 1 Output: 29 31 @sonuverma If this gives too much info, you can delete this. |
|
|
2020-01-31 07:32:48 Vipul Srivastava
Can you please see my latest solution, and just let me know if many cases are getting WA? No other hints needed Nevermind, I got it at last Last edit: 2020-02-04 15:59:08 |
|
|
2020-01-30 21:16:04
Thanks for pointing out @devilwolverine but there are no such cases. The answer will always fit in long long range |
|
|
2020-01-28 16:36:14 Vipul Srivastava
what if N is 10^5 and D is 10^5 and Ai is 10^9 for all i, I think answer won't fit in long long, are there any such cases? |
|
|
2019-12-07 12:48:20
Thanks for the compliment :D :) |
|
|
2019-12-01 00:27:55 :D
Very nice problem. Description is also fun. This must be the only problem where maximizing cost makes sense :) |
RSS