[Help] Educational Round 93, Problem D (Colored Rectangles)

Revision en2, by yadv, 2020-08-14 20:08:07

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];

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English yadv 2020-08-14 20:08:47 48
en2 English yadv 2020-08-14 20:08:07 4 Tiny change: 'hem. (ar if for red, ag if for green' -> 'hem. (ar is for red, ag is for green'
en1 English yadv 2020-08-14 20:07:19 1494 Initial revision (published)