Overview

When each operation allows you to “double the value of a certain stock,” maximize the total value after \(K\) operations and find the result modulo \(10^9+7\).

Analysis

Focus on the increase in total value (the increment) from each operation.

• If a stock’s current value is \(x\), doubling it increases the total by \(x\) (\(x \to 2x\), so the increment is \(2x - x = x\)).
• This means “which stock to choose” is answered by always choosing the stock with the current maximum value, as it yields the greatest gain.

Furthermore, once you choose the maximum stock and double it, that stock becomes even larger, and the increment from the next operation becomes even greater.
Let \(m = \max(L_i)\). Then:

• Choosing the maximum stock gives an increment of \(m\), and subsequent increments grow as \(2m, 4m, \dots\).
• On the other hand, choosing any non-maximum stock gives an increment of at most that stock’s current value, which is at most \(m\) even initially, and can never catch up with the increments from growing the maximum stock.

Therefore, the optimal strategy is to always double the stock with the initial maximum value for all \(K\) operations (this can be justified by an exchange argument: if any operation targets a different stock, replacing it with an operation on the maximum stock does not decrease — and generally increases — the total).

The final total is then: - The sum of all non-maximum stocks remains unchanged. - The maximum stock \(m\) becomes \(m \cdot 2^K\).

So: [ \text{answer} = \left(\sum_{i=1}^N Li - m\right) + m \cdot 2^K = \sum{i=1}^N L_i + m(2^K - 1) ]

Naively simulating \(K\) operations is impossible when \(K \le 10^{18}\) (TLE), so we compute \(2^K\) efficiently using fast exponentiation (e.g., Python’s pow(2, K, MOD)).

Algorithm

1. Find the maximum value \(m = \max(L)\).
2. Compute \(\text{sum} = \sum L_i\).
3. Compute \(p = 2^K \bmod MOD\) using pow(2, K, MOD).
4. Calculate the formula [ \text{ans} = \text{sum} + m(2^K - 1) ] under MOD and output the result. Specifically: [ \text{ans} = (\text{sum} \bmod MOD + (m \bmod MOD) \cdot ((p - 1) \bmod MOD)) \bmod MOD ]

(Example) \(L = [3, 5, 2], K = 2\)
The maximum is \(m = 5\). Doubling the maximum stock twice: \(5 \to 10 \to 20\), total is \(3 + 20 + 2 = 25\).
Using the formula: \(\sum L = 10\), \(10 + 5(4 - 1) = 25\).

Complexity

• Time complexity: \(O(N)\) (computing maximum and sum) + \(O(\log K)\) (exponentiation), dominated by \(O(N)\).
• Space complexity: \(O(1)\) (excluding the input array).

Implementation Notes

• Since \(K\) can be very large, \(2^K\) must be computed using modular fast exponentiation such as pow(2, K, MOD).

• The answer is [ \sum L_i + m(2^K - 1) ] so it is safe to take the mod in a non-negative form like (pow2 - 1) % MOD (in this case pow2 is always at least \(1\), but this is a good habit in general).

  Source Code

import sys

MOD = 10**9 + 7

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    L = list(map(int, input().split()))
    m = max(L)
    sum_mod = sum(L) % MOD
    pow2 = pow(2, K, MOD)
    ans = (sum_mod + (m % MOD) * ((pow2 - 1) % MOD)) % MOD
    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.