Getting wrong answer

#22

pls wait … … …

#23

Yaa… Sorry :slight_smile:

#24

try this->
store this things in ur pair
pair.first = maximum positive product
par.second= maximum negative product

dont use map for memoisation it will give tle.

use 2 d dp .
pair< int, int> dp[n+1][6];

#25

in this code…
https://codeforces.com/contest/1406/submission/95727061
i think i have done the same this…
only thing is that i have used map…
what do you say…

#26

yeah i saw that, it is correct.

use long long in place of int.

add this as well

#27

Hii…
Look at this code…
https://codeforces.com/contest/1406/submission/95729126
Here i have used ll int alltime… But have used Map… But instead of TLE… It is showing wrong answer…

#28

I know… It is taking time… But i want to find the mistake in my approch… So that i couldn’t repeat this mistake…

#29

image

ur code is giving same result for multiple test cases probably map might be creating some issue.
once try that i suggested above

#30

Okay… One doubt…
Here in pair<int,int> dp[n+1][6]…
How will check that if it is previously calculated or not…
Like in arr[n][d] first with the help of memset we make all to -1. and then check arr[i][j]!=-1…then return…
Here how do we use memset…
Hope you got what i am asking…
It is first time i am using this… So this kind of doubt i am asking…

#31

initialise dp[i][j] ={-1,-1}

also ur base case needs some correction.
u r always returning 1,1 which is not correct. u should return 1,1 only in case of le==0

#32

What should i return when i>=n…
Does it INT_MIN,INT_MAX…??

#33 

#include <bits/stdc++.h> 
#define ll long long
using namespace std;

pair<ll int,ll int> solve(ll int arr[],ll int le,ll int i,ll int n,unordered_map<string,pair<ll int,ll int>>&mp){
	string s = "";
	s+=to_string(i)+"0";
	s.push_back('-');
	s+=to_string(le)+"0";
	s.push_back('-');
	if(i>=n){
		ll int yy = 1;
		ll int yyy = 1;
		pair<ll int,ll int> pa(yy,yy);
		return pa;
	}
	if(le==0){
		ll int yy = 1;
		ll int yyy = 1;
		pair<ll int,ll int> pa(yy,yy);
		return pa;
	}
	if(i+le==n){
		ll int kk = 1;
		for(ll int j=i;j<n;j++){
			kk = kk*arr[j];
		}
		pair<ll int,ll int> pa(kk,kk);
		return pa;
	}
	if(mp.count(s)){
		return mp[s];
	}
	ll int a1 = 1;
	ll int a2 = 1;
	ll int b1 = 1;
	ll int b2 = 1;
	a1 = arr[i]*solve(arr,le-1,i+1,n,mp).first;
	a2 = arr[i]*solve(arr,le-1,i+1,n,mp).second;
	b1 = solve(arr,le,i+1,n,mp).first;
	b2 = solve(arr,le,i+1,n,mp).second;
	//cout<<a<<" "<<b<<"\n";
	ll int aa = max(max(max(a1,a2),b1),b2);
	ll int bb = min(min(min(a1,a2),b1),b2);
	pair<ll int,ll int> pa(aa,bb);
	return mp[s] = pa;
}


int main(){
#ifndef ONLINE_JUDGE
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);	
#endif	
	int t;
	cin >> t;
	while(t--){
		ll int n;
		cin >> n;
		ll int arr[n];
		for(ll int i=0;i<n;i++){
			cin >> arr[i];
		}
		unordered_map<string,pair<ll int,ll int>> mp;
		cout<<solve(arr,5,0,n,mp).first<<"\n";
	}
}

check now

#34

It got accepted… Now…:slight_smile:
What changes have you done…

#35

these changes…
a)
u cannot append number to string. first u need to convert int to string and then u can add.
b)
also u can use pushback on string only when u want to add single char to string.
if it has multiple char then u cant use pushback

#36

Thank You… Very…Very much… :slight_smile:
I got this… Thanks again for your patience…