Failing for larger testcases - Please Help


#1

typedef int ll;

void find(vector&ans,vector<vector>&q,ll x,ll y,vector &a)
{

if(x>y)
return ;
ll temp=q[x][y];
if(temp==-1)
return ;
ans.push_back(a[temp]);
find(ans,q,x,temp-1,a);
find(ans,q,temp+1,y,a);

}
ll solv(ll x,ll y,ll lx,ll ly,vector&a,vector<vector>&dp,vector<vector>&q)
{

if(x>y)
return 0;

if(dp[x][y]!=-1)
return dp[x][y];

int ans=-1;
for(ll i=x;i<=y;i++)
{
    if(a[i]<=lx||a[i]>=ly)
    continue;
    
    if(ans==-1)
    {
      ans=ly-lx+solv(x,i-1,lx,a[i],a,dp,q)+solv(i+1,y,a[i],ly,a,dp,q);
      q[x][y]=i;
    }
    else
    {
     ll temp=ly-lx+solv(x,i-1,lx,a[i],a,dp,q)+solv(i+1,y,a[i],ly,a,dp,q);
     if(ans>temp)
     {
         ans=temp;
         q[x][y]=i;
     }
    }
}
if(ans==-1)
 ans=0;
 return dp[x][y]=ans;

}
vector Solution::rodCut(int l, vector &a) {

ll n=a.size(),i=0,j;
vector<vector<ll>>dp(n,vector<ll>(n,-1));
 vector<vector<ll>>q(n,vector<ll>(n,-1));

sort(a.begin(),a.end());
solv(0,n-1,0,l,a,dp,q);
vector<ll>ans;
find(ans,q,0,n-1,a);

return ans;

}