Today I have done leetcode's March LeetCoding Challenge with cpp.

March LeetCoding Challenge 29

Description

Apply Operations to Maximize Score

You are given an array nums of n positive integers and an integer k.

Initially, you start with a score of 1. You have to maximize your score by applying the following operation at most k times:

• Choose any non-empty subarray nums[l, ..., r] that you haven't chosen previously.
• Choose an element x of nums[l, ..., r] with the highest prime score. If multiple such elements exist, choose the one with the smallest index.
• Multiply your score by x.

Here, nums[l, ..., r] denotes the subarray of nums starting at index l and ending at the index r, both ends being inclusive.

The prime score of an integer x is equal to the number of distinct prime factors of x. For example, the prime score of 300 is 3 since 300 = 2 * 2 * 3 * 5 * 5.

Return the maximum possible score after applying at most k operations.

Since the answer may be large, return it modulo 109 + 7.

Example 1:

Input: nums = [8,3,9,3,8], k = 2
Output: 81
Explanation: To get a score of 81, we can apply the following operations:
- Choose subarray nums[2, ..., 2]. nums[2] is the only element in this subarray. Hence, we multiply the score by nums[2]. The score becomes 1 * 9 = 9.
- Choose subarray nums[2, ..., 3]. Both nums[2] and nums[3] have a prime score of 1, but nums[2] has the smaller index. Hence, we multiply the score by nums[2]. The score becomes 9 * 9 = 81.
It can be proven that 81 is the highest score one can obtain.

Example 2:

Input: nums = [19,12,14,6,10,18], k = 3
Output: 4788
Explanation: To get a score of 4788, we can apply the following operations: 
- Choose subarray nums[0, ..., 0]. nums[0] is the only element in this subarray. Hence, we multiply the score by nums[0]. The score becomes 1 * 19 = 19.
- Choose subarray nums[5, ..., 5]. nums[5] is the only element in this subarray. Hence, we multiply the score by nums[5]. The score becomes 19 * 18 = 342.
- Choose subarray nums[2, ..., 3]. Both nums[2] and nums[3] have a prime score of 2, but nums[2] has the smaller index. Hence, we multipy the score by nums[2]. The score becomes 342 * 14 = 4788.
It can be proven that 4788 is the highest score one can obtain.

Constraints:

• 1 <= nums.length == n <= 105
• 1 <= nums[i] <= 105
• 1 <= k <= min(n * (n + 1) / 2, 109)

Solution

inline long long qpow(long long base, long long exp, long long mod) {
  long long result = 1;
  while(exp) {
    if(exp & 1) {
      result *= base;
      result %= mod;
    }
    base *= base;
    base %= mod;
    exp >>= 1;
  }
  return result;
}
class Solution {
  const int MOD = 1e9 + 7;
  static vector<int> primeScores;
public:
  int maximumScore(vector<int>& nums, int k) {
    int len = nums.size();
    vector<int> scores(len);
    for(int i = 0; i < len; ++i) {
      scores[i] = primeScores[nums[i]];
    }
    vector<int> left(len, -1);
    vector<int> right(len, len);
    vector<int> mono;
    for(int i = 0; i < len; ++i) {
      while(mono.size() && scores[mono.back()] < scores[i]) {
        mono.pop_back();
      }
      if(mono.size()) left[i] = mono.back();
      mono.push_back(i);
    }
    mono.clear();
    for(int i = len - 1; i >= 0; --i) {
      while(mono.size() && scores[mono.back()] <= scores[i]) {
        mono.pop_back();
      }
      if(mono.size()) right[i] = mono.back();
      mono.push_back(i);
    }
  
    vector<long long> count(len);
    for(int i = 0; i < len; ++i) {
      count[i] = 1LL * (i - left[i]) * (right[i] - i);
    }
    map<int, long long> ops;
    for(int i = 0; i < len; ++i) {
      ops[-nums[i]] += count[i];
    }

    long long answer = 1;
    for(auto [num, count] : ops) {
      if(k > count) {
        answer *= qpow(-num, count, MOD);
        answer %= MOD;
        k -= count;
      } else {
        answer *= qpow(-num, k, MOD);
        answer %= MOD;
        break;
      }
    }
    return answer;
  }
};

vector<int> Solution::primeScores = []() {
  vector<int> result(100001, 0);
  result[1] = 0;
  for(int i = 2; i < 50001; ++i) {
    if(result[i]) continue;
    for(int j = i * 2; j < 100001; j += i) {
      result[j] += 1;
    }
  }
  for(int i = 2; i < 100001; ++i) {
    result[i] += !result[i];
  }
  return result;
}();

// Accepted
// 870/870 cases passed (167 ms)
// Your runtime beats 86.06 % of cpp submissions
// Your memory usage beats 59.39 % of cpp submissions (147.3 MB)