Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

### ajraj27's blog

By ajraj27, history, 4 weeks ago, ,

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.

• +6

 » 4 weeks ago, # |   0 Auto comment: topic has been updated by ajraj27 (previous revision, new revision, compare).
 » 4 weeks ago, # |   0 Dp
•  » » 4 weeks ago, # ^ |   0 Why you removed the code?
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 You asked for the approach and i thought pasting code wasn't a good idea so i removed it. Spoiler#include "bits/stdc++.h" using namespace std; const int N = 5000 + 5; #define ll long long int ll pet[N]; ll val[N]; ll n, d, p, k; ll dp[N][N]; ll go(int pos, ll petrol){ if(pos == d) return 0; ll &ans = dp[pos][petrol]; if(ans != -1) return ans; ans = numeric_limits::max(); ans = min(ans, go(pos + 1, max(0LL, petrol - 1)) + ((petrol == 0) ? 5 : 1)); if(pet[pos]){ ans = min(ans, go(pos + 1, max(0LL, petrol) + pet[pos] - 1) + 1 + k); } return ans; } int main(){ cin >> n >> d >> p >> k; for(int i = 0; i < n; i++){ int x; cin >> x; pet[x] = 1; } for(int i = 0; i < n; i++){ int x; cin >> x; val[i] = x; } int pt = 0; for(int i = 0; i < 5001; i++){ if(pet[i]){ pet[i] = val[pt++]; } } memset(dp, -1, sizeof dp); cout << go(0, p); }