aboutsummaryrefslogtreecommitdiff
path: root/apply_operations_max_score.c
blob: 166c756223bd7d242b33f32b7124a0a39e28b6c5 (plain)
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
80
81
82
83
84
85
86
87
88
89
90
91
92
// 2818. Apply Operations to Maximize Score
#include "leetcode.h"

/*
 * 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'
 */

static int mod = 1e9 + 7, *vals;

void prime_score(int *score, int upper) {
  memset(score, 0, upper * sizeof(int));
  for (int i = 2; i < upper; i++)
    if (!score[i])
      for (int j = i; j < upper; j += i)
        score[j] += 1;
}

long long mod_pow(long long base, long long exp, long long mod) {
  long long res = 1;
  while (exp) {
    if (exp % 2 == 1)
      res = (res * base) % mod;
    base = (base * base) % mod;
    exp /= 2;
  }
  return res;
}

int cmp(const void *a, const void *b) {
  return vals[*(int *)b] - vals[*(int *)a];
}

int maximumScore(int *nums, int n, int k) {
  int upper = 0;
  for (int i = 0; i < n; i++) {
    if (nums[i] > upper)
      upper = nums[i];
  }
  upper++;
  int *score = (int *)malloc(upper * sizeof(int));
  int *next = (int *)malloc(n * sizeof(int));
  int *prev = (int *)malloc(n * sizeof(int));
  int *stack = (int *)malloc(n * sizeof(int));
  prime_score(score, upper);
  int top = -1, ans = 1;
  for (int i = 0; i < n; i++) {
    while (top >= 0 && score[nums[i]] > score[nums[stack[top]]])
      top--;
    prev[i] = (top >= 0) ? stack[top] : -1;
    stack[++top] = i;
  }
  top = -1;
  for (int i = n - 1; i >= 0; i--) {
    while (top >= 0 && score[nums[i]] >= score[nums[stack[top]]])
      top--;
    next[i] = (top >= 0) ? stack[top] : n;
    stack[++top] = i;
  }
  int *indices = (int *)malloc(n * sizeof(int));
  for (int i = 0; i < n; i++)
    indices[i] = i;
  vals = nums;
  qsort(indices, n, sizeof(int), cmp);
  for (int i = 0; i < n && k > 0; i++) {
    int idx = indices[i], num = nums[idx];
    long long operations = (long long)(idx - prev[idx]) * (next[idx] - idx);
    if (operations > k)
      operations = k;
    ans = (ans * mod_pow(num, operations, mod)) % mod;
    k -= operations;
    if (!k)
      break;
  }
  free(score);
  free(next);
  free(prev);
  free(stack);
  free(indices);
  return ans;
}

int main() {
  int n1[] = {8, 3, 9, 3, 8}, n2[] = {19, 12, 14, 6, 10, 18};
  printf("%d\n", maximumScore(n1, ARRAY_SIZE(n1), 2)); // expect: 81
  printf("%d\n", maximumScore(n2, ARRAY_SIZE(n2), 3)); // expect: 4788
}