Gfrktyl

I am trying to solve a question given on Codeforces involving Dynamic Programming with 3D arrays.

Here is my code:

#include<iostream>

#include<vector>

using namespace std;



int mat[403][403][403];

//mat[current_location][final_location][refuel_count_left] 

vector<int> city;

int fun(int s,int f, int r){

    if(s==f){

        return mat[s][f][r]  = 0;

    }

    if(mat[s][f][r]!=0){

        return mat[s][f][r];

    }

    if(s+1==f || r==0){

        return mat[s][f][r] = city[f]-city[s];

    }



    int opt = city[s]  + (city[f]-city[s])/(r+1);





    int pos  = lower_bound(city.begin()+s,city.begin()+f+1,opt) - city.begin();



    mat[s][f][r] = max(fun(pos,f,r-1), city[pos] - city[s]);



    //cout<<"s=" <<s<<" f="<<f<<" r="<<r<<" mat"<<mat[s][f][r]<<endl;



    return mat[s][f][r];

}

int main(){



    long long ans=0;

    int no_cities,no_vehicle;

    cin>>no_cities>>no_vehicle;



    city.push_back(0);

    for(int i=1;i<=no_cities;++i){

        int b;cin>>b;

        city.push_back(b);

    }

    for(int i=0;i<no_vehicle;++i){

        int start,finish,costperkm,refuel_count;

        cin>>start>>finish>>costperkm>>refuel_count;

        long long  vol_curr_vehicle = (long long)fun(start,finish,refuel_count)* (long long)costperkm;

        //cout<<jj<<" ";

        ans = max(ans,vol_curr_vehicle);

    }

    printf("%lld",ans);

    return 0;

}

I've used a 3D array named mat which stores the different DP states.

1st Dimension - index of starting location
2nd Dimension - index of final location to reach
3rd Dimestion - No. of refuelling left

The ith element in the city array represents that the 𝑖-th city is situated at the distance of ai kilometers from the origin.

Explanation for the code :

fun(s,f,r) function takes in 3 arguments representing the current position as s, finish postion as f and refuel_count_left as r.

The problem can be understood as dividing the array city into r+1 segments with the starting index as s and ending index as f.

That is, dividing city[s...f] into r+1 segments. This division should be in such a manner that from all segment max( city[ending index of current segment] - city[starting index of current segment] ) is minimised.

Inside the function fun(s,f,r) which computes and returns mat[s][f][r], the base cases are when :

s==f then return 0; because dividing city[s...f] into r+1 segments is just no segment.

mat[s][f][r]!=0 when mat[s][f][r] has already been computed then return it.

s+1==f || r==0 then return city[f] - city[s]. which mean that either we have no refulling left then we have to reach the final position from the starting position. Or when we are just before the final position then we just directly reach the final postion without refuelling.

If none of the above match then we have to find the position of a element opt which is equal to city[s] + (city[f]-city[s])/(r+1). ie - There will be one segment present to the left opt(a[s...p]) and r segments to the right of opt (a[p....f]).

So, a[s...p] is the first segment out of the r+1 segments and a[p...f] contain the rest r segments out of the r+1 segments

pos is the first position that I've described.

mat[s][f][r] is maximum of fun(pos,f,r-1) and city[pos] - city[s]. where fun(pos,f,r-1) mean that city[s...pos] is the first of the r segments and city[pos...f] are the rest r-1 segments and so now we are going to compute for city[pos...f] with r=r-1 refuellings left.

So, I'm finding the maximum of the difference between the last and first elements of the segments and equating that to mat[s][f][r].

Here is the right answer.

I realized the my code took 1481 ms of time for execution.

What is way that I can use to reduce the time complexity or the time taken by code during execution?