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

October LeetCoding Challenge 11

Description

Maximum Total Damage With Spell Casting

A magician has various spells.

You are given an array power, where each element represents the damage of a spell. Multiple spells can have the same damage value.

It is a known fact that if a magician decides to cast a spell with a damage of power[i], they cannot cast any spell with a damage of power[i] - 2, power[i] - 1, power[i] + 1, or power[i] + 2.

Each spell can be cast only once.

Return the maximum possible total damage that a magician can cast.

Example 1:

Example 2:

Constraints:

• 1 <= power.length <= 105
• 1 <= power[i] <= 109

Solution

class Solution {
  void rotate(vector<pair<int, long long>> &arr) {
    arr[0] = arr[1];
    arr[1] = arr[2];
  }
public:
  long long maximumTotalDamage(vector<int>& power) {
    map<int, long long> dp;
    vector<pair<int, long long>> prevs(4);
    for(auto s : power) {
      dp[s] += s;
    }

    for(auto [p, s] : dp) {
      pair<int, long long> newP = {p, prevs[0].second + s};
      if(p > prevs[1].first + 2) {
        newP.second = max(prevs[1].second + s, newP.second);
      } else {
        newP.second = max(prevs[1].second, newP.second);
      }
      if(p > prevs[2].first + 2) {
        newP.second = max(prevs[2].second + s, newP.second);
      } else {
        newP.second = max(prevs[2].second, newP.second);
      }
      rotate(prevs);
      prevs[2] = newP;
    }
    return max({prevs[0].second, prevs[1].second, prevs[2].second});
  }
};

// Accepted
// 554/554 cases passed (396 ms)
// Your runtime beats 37.39 % of cpp submissions
// Your memory usage beats 77.04 % of cpp submissions (189.5 MB)