DP or Greedy Approach

Revision en2, by ajraj27, 2020-01-19 23:26:35

Hari is a Food Delivery guy and he has to pick food from restaurant R and deliver it to home H. Distance of H from R is D.When Hari reached at the restaurant R , he checked and found that his motorbike has P units of petrol left. Now, there are N fuel stations on the path from R to H and he may use these fuel stations to get petrol for his motorbike if any need arises. These N fuel stations are at distance D1, D2, D3,…, DN units from the restaurant R and these N fuel stations have P1, P2, P3,…, P N units of petrol. Hari’s motorbike tank is large enough to store any quantity of petrol. if Hari stops at any fuel station to get petrol, it takes K minutes. If at any point of time, there is no petrol in Hari’s motorbike, he will have to drag his motorbike on foot to nearest fuel station or his delivery location. If Hari drags his motorbike on foot, he takes 5 minutes to cover 1 unit distance and if he drives the motorbike, he takes 1 minute to cover 1 unit distance. Hari may drag his motorbike on foot even if there is petrol in motorbike to minimise the delivery time. Now, Hari has to deliver this order in minimum amount of time. Find the minimum possible time required to deliver the order.

Input: First line will contain 4 integers denoting N, D, P and K. Next line will contain integers denoting D1 , D2, D 3 ,…, DN . Next line will contain N integers denoting P1, P 2, P3,…, PN.

Testcase : 3 10 1 3

3 5 9

6 1 2

Ans — 24

Please someone explain the logic.


  Rev. Lang. By When Δ Comment
en2 English ajraj27 2020-01-19 23:26:35 4 Tiny change: ' 2\n\nAns — 24\n\nPle' -> ' 2\n\nAns - 24\n\nPle'
en1 English ajraj27 2020-01-19 23:25:26 1520 Initial revision (published)