[problem:987C]↵
↵
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..↵
↵
#include<bits/stdc++.h>↵
using namespace std;↵
↵
#define ll long long↵
#define nl '\n'↵
#define N 1000000007 ↵
↵
define N 1000000007 ↵
↵
vector<int> a(3000),c(3000);↵
vector<vector<int>> dp(3001,vector<int> (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??↵
↵
↵
↵
↵
↵
↵
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..↵
↵
using namespace std;↵
↵
#define ll long long↵
#define nl '\n'↵
#define N 1000000007 ↵
↵
↵
vector<int> a(3000),c(3000);↵
vector<vector<int>> dp(3001,vector<int> (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??↵
↵
↵
↵
↵
↵
