Getting Memory Limit Exceeded - Please help


#1


using ll = long long;
using vl = vector;
using vi = vector;
const ll inf = 1e18 + 7;
void optimal(vector<vector> &order,int i,int j,vector &result,vector &cuts){
if(i>=j-1)
return;
int k=order[i][j];
result.push_back(cuts[k]);
optimal(order,i,k,result,cuts);
optimal(order,k,j,result,cuts);
}
vector Solution::rodCut(int n, vector &cuts) {
if(cuts.size()<=1)
return cuts;
cuts.push_back(0);
cuts.push_back(n);
sort(cuts.begin(),cuts.end());
int s=cuts.size();
vector<vector> dp(s+1,vector(s+1,0));
vector<vector> order(s+1,vector(s+1,0));
vector result;
for(int l=3;l<=s;l++){
for(int i=0;i<=s-l;i++){
int j=i+l-1;
dp[i][j]=1e9;
for(int k=i;k<j;k++){
int cost=dp[i][k]+dp[k][j] + cuts[j] - cuts[i];
if(cost<dp[i][j]){
dp[i][j]=cost;
order[i][j]=k;
}
}
}
}
optimal(order,0,s-1,result,cuts);
return result;
}