[Codeforces] C. Choosing Balls

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : C. Choosing Balls
Source            : Codeforces
Category          : Dynamic Programing, STL
Algorithm         : DP, Hash Tables with PBDS
Verdict           : Accepted

Hash Tables with Policy Based Data Structure Tutorial : https://codeforces.com/blog/entry/60737

Without Hash Tables : 2214 ms

#include "bits/stdc++.h"  
  
using namespace std;  
  
#define pll              pair <ll, ll>  
  
typedef long long int        ll;  
  
static const int maxn = 1e5 + 5;  
static const ll  inf  = 1e18;  
  
int n, q;  
ll value[maxn], color[maxn], dp[maxn], curMax[maxn];  
  
int main()  
{  
      ios_base::sync_with_stdio(false);  
      cin.tie(nullptr);  
      cout << fixed << setprecision(15);  
      #ifndef ONLINE_JUDGE  
            freopen("in.txt", "r", stdin);  
      #endif // ONLINE_JUDGE  
  
      cin >> n >> q;  
      for (int i = 1; i <= n; i++) cin >> value[i];  
      for (int i = 1; i <= n; i++) cin >> color[i];  
      while (q--)  
      {  
            ll a, b;  
            cin >> a >> b;  
            for (int i = 1; i <= n; i++)  
            {  
                  dp[i] = -inf;  
                  curMax[ color[i] ] = -inf;  
            }  
            pll mx1 = pll(0LL, 1e5 + 5);  
            pll mx2 = pll(0LL, 1e5 + 4);  
            /** 
            dp[j] = Maximum value we can obtain from position 1 to j (Subsequence) 
            curMax[j] = Latest Maximum value using color j 
            mx1 = {Maximum value, color} 
            mx2 = {Maximum value, color} 
            mx1.color != mx2.color 
            **/  
            for (int j = 1; j <= n; j++)  
            {  
                  if (curMax[ color[j] ] != -inf) // previous color == current color  
                  {  
                        dp[j] = max(dp[j], curMax[ color[j] ] + a * value[j]);  
                  }  
                  if (color[j] != mx1.second) // previous color != current color  
                  {  
                        dp[j] = max(dp[j], mx1.first + b * value[j]);  
                  }  
                  else  
                  {  
                        dp[j] = max(dp[j], mx2.first + b * value[j]);  
                  }  
                  if (dp[j] > mx1.first) // update mx1 and mx2  
                  {  
                        if (color[j] == mx1.second)  
                        {  
                              mx1 = pll(dp[j], color[j]);  
                        }  
                        else  
                        {  
                              mx2 = mx1;  
                              mx1 = pll(dp[j], color[j]);  
                        }  
                  }  
                  else if (dp[j] > mx2.first && color[j] != mx1.second)  
                  {  
                        mx2 = pll(dp[j], color[j]);  
                  }  
                  curMax[ color[j] ] = max(curMax[ color[j] ], dp[j]);  
            }  
            cout << mx1.first << '\n';  
      }  
}  

With Hash Tables : 3026 ms

#include "bits/stdc++.h"  
#include "ext/pb_ds/assoc_container.hpp"  
#include "ext/pb_ds/tree_policy.hpp"  
  
using namespace std;  
using namespace __gnu_pbds;  
  
#define pll              pair <ll, ll>  
  
typedef long long int        ll;  
template <typename T> using HashTable = cc_hash_table <T, T, hash <T> >;  
  
static const int maxn = 1e5 + 5;  
static const ll  inf  = 1e18;  
  
  
int n, q;  
ll value[maxn], color[maxn], dp[maxn];  
  
int main()  
{  
      ios_base::sync_with_stdio(false);  
      cin.tie(nullptr);  
      cout << fixed << setprecision(15);  
      #ifndef ONLINE_JUDGE  
            freopen("in.txt", "r", stdin);  
      #endif // ONLINE_JUDGE  
  
      cin >> n >> q;  
      for (int i = 1; i <= n; i++) cin >> value[i];  
      for (int i = 1; i <= n; i++) cin >> color[i];  
      HashTable <ll> curMax;  
      for (int i = 1; i <= n; i++) curMax[ color[i] ] = -inf;  
      while (q--)  
      {  
            ll a, b;  
            cin >> a >> b;  
            for (int i = 1; i <= n; i++)  
            {  
                  dp[i] = -inf;  
                  curMax[ color[i] ] = -inf;  
            }  
            pll mx1 = pll(0LL, 1e5 + 5);  
            pll mx2 = pll(0LL, 1e5 + 4);  
            /** 
            dp[j] = Maximum value we can obtain from position 1 to j (Subsequence) 
            curMax[j] = Latest Maximum value using color j 
            mx1 = {Maximum value, color} 
            mx2 = {Maximum value, color} 
            mx1.color != mx2.color 
            **/  
            for (int j = 1; j <= n; j++)  
            {  
                  if (curMax[ color[j] ] != -inf) // previous color == current color  
                  {  
                        dp[j] = max(dp[j], curMax[ color[j] ] + a * value[j]);  
                  }  
                  if (color[j] != mx1.second) // previous color != current color  
                  {  
                        dp[j] = max(dp[j], mx1.first + b * value[j]);  
                  }  
                  else  
                  {  
                        dp[j] = max(dp[j], mx2.first + b * value[j]);  
                  }  
                  if (dp[j] > mx1.first) // update mx1 and mx2  
                  {  
                        if (color[j] == mx1.second)  
                        {  
                              mx1 = pll(dp[j], color[j]);  
                        }  
                        else  
                        {  
                              mx2 = mx1;  
                              mx1 = pll(dp[j], color[j]);  
                        }  
                  }  
                  else if (dp[j] > mx2.first && color[j] != mx1.second)  
                  {  
                        mx2 = pll(dp[j], color[j]);  
                  }  
                  curMax[ color[j] ] = max(curMax[ color[j] ], dp[j]);  
            }  
            cout << mx1.first << '\n';  
      }  
}