 pranay_teja
9/26/2018 - 11:17 AM

## HE Journey

``````#include<bits/stdc++.h>
using namespace std;

// #DynamicProgramming
// https://www.hackerearth.com/problem/algorithm/journey-1-0418ba3e/

int minCost(int n, vector<int> li, vector<int> ci, vector<int> pi, int x);
int solve(vector<int> li, vector<int> ci, vector<int> pi, int x, int start, int end, int cost);

int main(){
int n,m;
cin>>n>>m;
vector<int> li(n-1);
vector<int> ci(n-1);
vector<int> pi(n-1);
for(int i=0;i<n-1;i++){
cin>>li[i];
}
for(int i=0;i<n-1;i++){
cin>>ci[i];
}
for(int i=0;i<n-1;i++){
cin>>pi[i];
}
while(m--){
int x;
cin>>x;
cout<<minCost(n,li,ci,pi,x)<<endl;
}
return 0;
}

int solve(vector<int> li, vector<int> ci, vector<int> pi, int charge, int start, int end, int cost){
if(charge<0){
return -1;  // if charge is depleted even before reaching the city
}
if(charge<li[start]){
if(ci[start]<li[start]){   // if both charge & battery at shop are not enough to go to next city
return -1;
}
}
if(start==(end-1)){ // at last-but-one city
if(charge<li[start]){   // if current charge is less than that is req to travel to last city
//charge=ci[start]-li[start]; // replace battery
return cost+pi[start];  // buy the battery and move forward
}else{
//charge-=li[start];
return cost;    // journey possible without buying battery
}
}
int with,without;
without=solve(li,ci,pi,charge-li[start],start+1,end,cost);
with=solve(li,ci,pi,ci[start]-li[start],start+1,end,cost+pi[start]);
if(without!=-1){   // if journey can be completed without buying battery at current city
return min(with,without);
}else{
if(with!=-1){
return with;    // if journey can be completed only if battery is bought at current city
}else{
return -1;    // if journey can't be completed even after buying
}
}
}
int minCost(int n,vector<int> li,vector<int> ci,vector<int> pi,int x){
return solve(li,ci,pi,x,0,n-1,0);
}``````