Overview

Given \(N\) stocks, you perform exactly \(K\) operations of “double the value of a chosen stock” to maximize the total asset value. The optimal strategy is to concentrate all operations on the stock with the maximum value, and we use fast exponentiation to compute the result efficiently.

Analysis

Key Insight: It is always optimal to double the largest stock

Let’s focus on the increase gained from a single operation. When you double a stock with asset value \(X\), the increase is \(2X - X = X\).

In other words, doubling the stock with the currently largest asset value maximizes the increase per operation.

Let’s consider a concrete example. For \(S = [3, 5]\), \(K = 2\):

• Choose 5 twice: \(3 + 5 \times 2^2 = 3 + 20 = 23\)
• Choose 5 once, choose 3 once: \((3 \times 2) + (5 \times 2) = 6 + 10 = 16\)
• Choose 3 twice: \(3 \times 4 + 5 = 12 + 5 = 17\)

Choosing 5 twice gives the maximum.

In general, when you choose the maximum-value stock for the first operation, that stock becomes \(2 \times \max(S)\), which remains larger than any other stock (since it was already the largest). Therefore, it is optimal to keep choosing the same stock for all subsequent operations.

Conclusion

It is optimal to apply all \(K\) operations to the stock with the initial maximum value \(S_{\max}\).

The final total is:

\[\text{answer} = \left(\sum_{i=1}^{N} S_i - S_{\max}\right) + S_{\max} \times 2^K\]

Problem with the Naive Approach

Since \(K\) can be as large as \(10^{18}\), a method that loops \(K\) times to double the value is far too slow. We need to compute \(2^K\) efficiently.

Algorithm

1. Find the maximum value \(S_{\max}\) and the sum \(\text{total}\) of \(S\).
2. Compute \(2^K \mod (10^9 + 7)\) using fast exponentiation (binary method).
   • In Python, pow(2, K, MOD) computes this in \(O(\log K)\).
3. Compute the answer using the following formula:

\[\text{ans} = \left((\text{total} - S_{\max}) + S_{\max} \times 2^K\right) \mod (10^9 + 7)\]

Complexity

• Time complexity: \(O(N + \log K)\)
  • \(O(N)\): Computing the maximum and sum
  • \(O(\log K)\): Computing \(2^K \mod (10^9+7)\) via fast exponentiation
• Space complexity: \(O(N)\)
  • For storing the input array

Implementation Notes

• Fast exponentiation: Using Python’s built-in function pow(base, exp, mod), modular exponentiation in \(O(\log K)\) can be written easily.

• Taking MOD: Compute \(\text{total} - S_{\max}\) and \(S_{\max} \times 2^K\) each modulo \((10^9 + 7)\), then add them together. Since \(\text{total} - S_{\max}\) is non-negative, there is no concern about negative values when taking the modulus.

• When there are multiple maximum values: You can concentrate all operations on any one of them, and the result is the same.

  Source Code

import sys

def solve():
    input_data = sys.stdin.read().split()
    N = int(input_data[0])
    K = int(input_data[1])
    S = [int(input_data[i + 2]) for i in range(N)]
    
    MOD = 10**9 + 7
    
    # To maximize the total sum, we should always double the largest current value.
    # So we find the maximum value and apply all K doublings to it.
    max_val = max(S)
    total = sum(S)
    
    # The answer is (total - max_val) + max_val * 2^K
    # = (total - max_val) + max_val * 2^K
    
    rest = (total - max_val) % MOD
    contribution = (max_val % MOD) * pow(2, K, MOD) % MOD
    
    ans = (rest + contribution) % MOD
    print(ans)

solve()

---

This editorial was generated by claude4.6opus-thinking.