3971. Maximum Total Value
You are given two integer arrays value and decay, and an integer m.
value[i] represents the initial value at index i.decay[i] represents how much the value decreases after each selection of index i.
You may select any index multiple times. The total number of selections across all indices must not exceed m.
If you select index i for the t^th time, where t is 1-indexed, the value gained is value[i] - decay[i] * (t - 1).
Return the maximum total value you can obtain. Since the answer may be large, return it modulo 10^9 + 7.
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
|
class Solution {
long long mod = 1e9 + 7;
long long inv = modpow(2, mod - 2, mod);
long long modpow(long long n, long long x, long long mod) {
if(x<0){
return modpow(modpow(n,-x,mod),mod-2,mod);
}
n%=mod;
long long res=1;
while(x){if(x&1){res=res*n%mod;}n=n*n%mod;x>>=1;}return res;
}
array<long long, 3> calc(long long n, long long k, long long m) {
if (n <= m) return {0,n,0};
long long cnt = (n - m - 1) / k + 1;
return {((cnt * n % mod - k * cnt % mod * (cnt - 1) % mod * inv % mod) + mod) % mod, n - k * cnt, cnt};
}
bool helper(vector<int>& A, vector<int>& D, int op, int m) {
long long cnt = 0;
for(int i = 0; i < A.size(); i++) {
if(A[i] < m) continue;
long long diff = A[i] - m;
cnt += (diff / D[i]) + 1;
}
return cnt <= op;
}
public:
int maxTotalValue(vector<int>& value, vector<int>& decay, int op) {
int l = 0, r = *max_element(begin(value), end(value)), pick = r;
while(l <= r) {
int m = l + (r - l) / 2;
bool ok = helper(value,decay,op,m);
if(ok) {
pick = m;
r = m - 1;
} else l = m + 1;
}
priority_queue<pair<int,int>> q;
long long res = 0;
for(int i = 0; i < value.size(); i++) {
auto [sum,val,opp] = calc(value[i], decay[i], pick);
res = (res + sum) % mod;
if(val > 0) q.push({val,decay[i]});
op -= opp;
}
while(op-- and q.size()) {
auto [val, dec] = q.top(); q.pop();
res = (res + val) % mod;
if(val - dec > 0) q.push({val - dec, dec});
}
return res;
}
};
|
