MyLeetcode/cpp_solutions/2818.cpp at main · Kaminyou/MyLeetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
class Solution {
public:
    long long getPower(long long n, long long p){
        long long mod = 1e9 + 7;
        long long res = 1;
        n = n % mod;
        while (p > 0){
            if(p & 1){
                res = (res * n) % mod;
                p--;
            }
            n = (n * n) % mod;
            p = p >> 1;
        }
        return res;
    }
    int scoring(int num) {
        int cnt = 0;
        for (int i = 2; i * i <= num; ++i) {
            if (num % i == 0) {
                while (num % i == 0) num /= i;
                cnt++;
            }
            if (num == 1) break;
        }
        if (num >= 2) cnt++;
        return cnt;
    }
    int maximumScore(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> primeScores(n, 0);
        for (int i = 0; i < n; ++i) {
            primeScores[i] = scoring(nums[i]);
        }
        stack<int> st;
        vector<int> left(n, 0);
        left[0] = 0;
        st.push(0);
        for (int i = 1; i < n; ++i) {
            int curr = i;
            while (!st.empty() && primeScores[i] > primeScores[st.top()]) {
                curr = min(curr, left[st.top()]);
                st.pop();
            }
            st.push(i);
            left[i] = curr;
        }
        while (!st.empty()) st.pop();
        vector<int> right(n, 0);
        right[n - 1] = n - 1;
        st.push(n - 1);
        for (int i = n - 2; i >= 0; --i) {
            int curr = i;
            while (!st.empty() && primeScores[i] >= primeScores[st.top()]) {
                curr = max(curr, right[st.top()]);
                st.pop();
            }
            st.push(i);
            right[i] = curr;
        }
        priority_queue<pair<long long, long long>> pq;
        for (int i = 0; i < n; ++i) {
            long long r = right[i] - i + 1;
            long long l = i - left[i];
            long long total = r * (1 + l);
            pq.push({nums[i], total});
        }
        long long res = 1;
        long long mod = 1e9 + 7;
        long long kk = k;
        while (kk > 0) {
            auto [x, total] = pq.top();
            pq.pop();
            res = res * getPower(x, min(kk, total)) % mod;
            kk = kk - min(kk, total);
        }
        return res;
    }
};