Help needed regarding today's contest. Problem D (Colored Rectangles).
I tried to solve this problem using a 3-dimensional dp array but I'm not able to figure out where I went wrong. My code is written below with comments, and it won't take much of your time. Thank you.
int r,g,b; cin>>r>>g>>b; // number of red, green and blue pair
vi ar(r),ag(g),ab(b); // vector to store each of them. (ar is for red, ag is for green, ab for blue)
for (ll i = 0; i < r; ++i)
cin>>ar[i];
for (ll i = 0; i < g; ++i)
cin>>ag[i];
for (ll i = 0; i < b; ++i)
cin>>ab[i];
// declaring a 3d vector to store all the possible choices for red,green and blue
//dp vector is 1-based index
vector<vector<vector<int>>> dp (r+1,vector<vector<int> >(g+1,vector <int>(b+1,0)));
for (ll i = 1; i < r+1; ++i)
{
for (ll j = 1; j < g+1; ++j)
{
for (ll k = 1; k < b+1; ++k)
{
// exclude
dp[i][j][k]=dp[i-1][j-1][k-1];
// red & green include
dp[i][j][k]=max(dp[i][j][k], ((ar[i-1]*ag[j-1])+dp[i-1][j-1][k]));
// red & blue include
dp[i][j][k]=max(dp[i][j][k], ((ar[i-1]*ab[k-1])+dp[i-1][j][k-1]));
// green & blue
dp[i][j][k]=max(dp[i][j][k], ((ab[k-1]*ag[j-1])+dp[i][j-1][k-1]));
}
}
}
cout<<dp[r][g][b];
First sort the and then continue extracting elements from the back.
You shouldn't exclude all 3 at once, only one at a time. Also sort before you do dp.
Can you please elaborate why sorting is necessary?
You have missed the cases where i+j+k=2, (for e.g. i=1, j=1, k=0), check my solution (https://mirror.codeforces.com/contest/1398/submission/89931563) if you're still not sure.
Edit: Also sort as everyone else has recommended.
Can someone please explain why sorting is necessary? We will be visiting all elements before and after so how will sorting help?
This
dpdoes not skip elements but takes some elements at the beginning. So imaging you got the input like this:If $$$a{\geq}b{\geq}c{\geq}d$$$ (all greater than 0) then it can be proven that $$$a*b+c*d {\geq} a*c+b*d$$$ and $$$a*b+c*d{\geq}a*d+b*c$$$. That means that for every subset of four elements it is always more convenient to add the product of the larger elements to the product of the smaller ones. That's why the numbers are sorted in descending order. So that we can maximize the number of subsets of four mentioned above. Hope it helps.
On dry run you shall find you missed to include conditions
This gets your code going 89962238
Can someone please help me with this. I have done sorting and still I am not able to get the correct output. I have used 1 based indexing so the user baranwalm's comment regarding two cases won't be required (I think so).
Here is a sample test(the incorrect one produced by my code): INPUT: 10 1 1 11 7 20 15 19 14 2 4 13 14 8 11
OUTPUT: 220
Please help if you have some time.
Are you sorting in descending order? If not, you should be. Can you post the code in a spoiler tag so we can see it?