in this problem, in an array S we need to find three indices (i<j<k) such that 1<=(i,j,k)<=n && Si < Sj < Sk... there is another array C.. && the sum of (Ci,Cj,Ck) should be minimum...
my implementation is below..
define N 1000000007
vector a(3000),c(3000); vector<vector> dp(3001,vector (4,-1));
ll f(int i,int p,int mx){ if(p==0) return 0; if(i==0){ if(p==1 && a[0]<mx) return c[0]; return N; } if(dp[i][p]!=-1) return dp[i][p];
ll pick=N; if(a[i]<mx){ pick=0ll+c[i]+f(i-1,p-1,a[i]); } ll no_pick=f(i-1,p,mx); return dp[i][p]=min(no_pick,pick);
}
int main(){ ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int n; cin>>n; for(int i=0;i<n;i++) cin>>a[i]; for(int i=0;i<n;i++) cin>>c[i]; int ans=f(n-1,3,N); cout<<(ans==N?-1:ans)<<nl; return 0;
}
for the test case , 5 2 4 5 4 10 40 30 20 10 40 the answer is: 90 but my output is: 70
why is my code is not giving the right output.. where should I make a change??