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
|
# 2818. 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 maxmise your score by
applying the following operation at most 'k' times: chose any non-empty
element 'x' of 'nums[l .. r]' with the highest prime score. if multiple such
elements exist, choose the one with the smallest index. multiple your score
'x'. return the maximum possible score after applying at most 'k' operations.
since the answer may be very large, return it module '10e9+7'
"""
class Solution(object):
mod = 10**9 + 7
def mod_pow(self, x, n):
res = 1
while n > 0:
if n % 2 == 1:
res = (res * x) % self.mod
x = (x * x) % self.mod
n //= 2
return res
def maximumScore(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
n = len(nums)
upper = max(nums) + 1
prime = [True] * upper
prime[0] = prime[1] = False
score = [0] * upper
for i in range(2, upper):
if prime[i]:
for j in range(i, upper, i):
score[j] += 1
prime[j] = False
next, stk = [n] * n, []
for i in range(n - 1, -1, -1):
while stk and score[nums[i]] >= score[nums[stk[-1]]]:
stk.pop()
next[i] = stk[-1] if stk else n
stk.append(i)
prev, stk = [-1] * n, []
for i in range(n):
while stk and score[nums[i]] > score[nums[stk[-1]]]:
stk.pop()
prev[i] = stk[-1] if stk else -1
stk.append(i)
ans = 1
tuples = [[nums[i], i] for i in range(n)]
tuples.sort(reverse=True)
for num, idx in tuples:
operations = min(
(idx - prev[idx]) * (next[idx] - idx),
k,
)
ans = (ans * self.mod_pow(num, operations)) % self.mod
k -= operations
if k == 0:
return ans
return ans
if __name__ == "__main__":
obj = Solution()
print(obj.maximumScore(nums=[8, 3, 9, 3, 8], k=2))
print(obj.maximumScore(nums=[19, 12, 14, 6, 10, 18], k=3))
|