[AtCoder] Q - Flowers

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : Q - Flowers
Source            : AtCoder Educational DP Contest
Category          : Dynamic Programing
Algorithm         : solving Insert-Query Problems Offline, LIS
Verdict           : Accepted

#include "bits/stdc++.h"
 
using namespace std;
 
#define ll         long long int
#define eb         emplace_back
 
static const int maxn = 2e5 + 5;
 
struct information
{
      ll h, d;
      information(ll h = 0, ll d = 0) : h(h), d(d) {}
      inline bool operator < (const information &p) const
      {
            return h < p.h;
      }
};
 
int N;
ll height[maxn];
ll score[maxn];
ll dp[maxn];
 
inline void divideConquer(int l, int r)
{
      if (l >= r) return;
      int mid = (l + r) / 2;
      divideConquer(l, mid);
      vector <information> vec;
      for (int i = l; i <= mid; i++)  vec.eb(height[i], dp[i]);
      sort(vec.begin(), vec.end());
      int n = vec.size();
      vector <ll> prefixMax(n);
      ll maxi = -1;
      for (int i = 0; i < n; i++)
      {
            if (vec[i].d > maxi) maxi = vec[i].d;
            prefixMax[i] = maxi;
      }
      for (int i = mid+1; i <= r; i++)
      {
            ll h = height[i];
            auto it = lower_bound(vec.begin(), vec.end(), h) - vec.begin();
            --it;
            if (it >= 0 && it < n)
            {
                  dp[i] = max(dp[i], score[i] + prefixMax[it]);
            }
      }
      divideConquer(mid+1, r);
}
 
int main()
{
      scanf("%d", &N);
      for (int i = 1; i <= N; i++) scanf("%lld", height + i);
      for (int i = 1; i <= N; i++) scanf("%lld", score + i);
      for (int i = 1; i <= N; i++) dp[i] = score[i];
      divideConquer(1, N);
      ll maxi = -1;
      for (int i = 1; i <= N; i++) if (dp[i] > maxi) maxi = dp[i];
      printf("%lld", maxi);
}