Nsryjdtyk

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

F. Trucks and Cities

There are $n$ cities along the road, which can be represented as a straight line. The $i$-th city is situated at the distance of $a_i$ kilometers from the origin. All cities are situated in the same direction from the origin. There are $m$ trucks travelling from one city to another.

Each truck can be described by $4$ integers: starting city $s_i$, finishing city $f_i$, fuel consumption $c_i$ and number of possible refuelings $r_i$. The $i$-th truck will spend $c_i$ litres of fuel per one kilometer.

When a truck arrives in some city, it can be refueled (but refueling is impossible in the middle of nowhere). The $i$-th truck can be refueled at most $r_i$ times. Each refueling makes truck's gas-tank full. All trucks start with full gas-tank.

All trucks will have gas-tanks of the same size $V$ litres. You should find minimum possible $V$ such that all trucks can reach their destinations without refueling more times than allowed.

Input

First line contains two integers $n$ and $m$ ($2 ≤ n
≤ 400$, $1 ≤ m ≤ 250000$) — the number of cities and trucks.

The second line contains $n$ integers $a_1,a_2,…,a_n$ ($1 ≤ a_i ≤ 10^9$, $a_i < a_i + 1$) — positions of cities in the ascending order.

Next $m$ lines contains $4$ integers each. The $i$-th line contains integers $s_i, f_i, c_i, r_i$ ($1 ≤ s_i < f_i ≤ n$, $1 ≤ c_i ≤ 10^9$, $0 ≤ r_i ≤ n$) — the description of the $i$-th truck.

Output

Print the only integer — minimum possible size of gas-tanks $V$ such that all trucks can reach their destinations.

Requirements

time limit per test — 2 seconds
memory limit per test — 256 megabytes
input — standard input
output — standard output

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 Dimension - No. of refueling left

The 𝑖th 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:

The fun(s,f,r) function takes in 3 arguments representing the current position as s, finish position 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 refuling 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 position without refueling.

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). i.e. - There will be one segment present to the left opt(a[s...p]) and r segments to the right of opt (a[p....f]).

• 
  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 refuelings 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?