### MJSaif's blog

By MJSaif, history, 5 weeks ago,

987C - Three displays

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

• 0

 » 5 weeks ago, # |   0 Auto comment: topic has been updated by MJSaif (previous revision, new revision, compare).