Overview

Given \(N\) stocks, you can choose any stock and double its value, performing this operation \(K\) times, to maximize the total value. The key insight is that it is optimal to concentrate all operations on the stock with the maximum value.

Analysis

Key Insight: It is always optimal to double the maximum value

Consider the “increase” gained from one operation. If you double a stock with value \(x\), the increase is \(2x - x = x\). In other words, the larger the stock’s value, the greater the increase when doubled.

Therefore, to maximize the total, it is optimal to always select “the current maximum stock” each time.

Concrete Example

Consider the case \(N = 3\), \(K = 2\), \(L = [3, 5, 1]\).

• 1st operation: Double the maximum \(5\) → \([3, 10, 1]\) (total \(14\))
• 2nd operation: Double the maximum \(10\) → \([3, 20, 1]\) (total \(24\))

Once the maximum value is doubled, that stock remains the maximum, so all operations end up being concentrated on the stock that was maximum in the initial state.

Summary

Let \(M\) be the maximum of the initial values and \(S\) be the sum of all other values. The answer is:

\[\text{Answer} = S + M \times 2^K\]

Why Naive Simulation Doesn’t Work

Since \(K\) can be up to \(10^{18}\), simulating one operation at a time would be \(O(K)\), which is far too slow. By directly computing the formula above, we can obtain the answer in \(O(1)\) (excluding the exponentiation computation).

Algorithm

1. Find the maximum value \(M = \max(L)\) from the array \(L\).
2. Compute the sum of the remaining elements \(S = \sum L_i - M\).
3. Compute \(2^K \mod (10^9 + 7)\) efficiently using modular exponentiation (repeated squaring).
4. Output the answer as \((S + M \times 2^K) \mod (10^9 + 7)\).

What is Repeated Squaring?

Computing \(2^K\) by multiplying \(K\) times takes \(O(K)\), but using repeated squaring, it can be computed in \(O(\log K)\). For example, to compute \(2^{10}\):

• \(2^1 \to 2^2 \to 2^4 \to 2^8 \to 2^{10} = 2^8 \times 2^2\)

The exponent is decomposed into binary and computed accordingly. In Python, pow(2, K, MOD) automatically uses this method.

Complexity

• Time complexity: \(O(N + \log K)\)
  • \(O(N)\): Computing the maximum and the sum
  • \(O(\log K)\): Computing \(2^K \mod (10^9+7)\) (repeated squaring)
• Space complexity: \(O(N)\) (storing the input)

Implementation Notes

• Be careful not to forget taking mod: You need to take mod on \(S\) and \(M\) before performing multiplications and additions. In Python, arbitrary-precision integers prevent overflow, but don’t forget to take mod on the final result.

• Python’s pow(base, exp, mod) internally performs repeated squaring, so there is no need to implement it yourself.

• Even if there are multiple stocks with the maximum value, concentrating all operations on any one of them yields the same result.

  Source Code

import sys

def solve():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    K = int(input_data[1])
    L = [int(input_data[i + 2]) for i in range(N)]
    
    MOD = 10**9 + 7
    
    # To maximize the sum, we should always double the largest current value.
    # So we should apply all K doublings to the maximum element.
    # The maximum element gets multiplied by 2^K, and the rest stay the same.
    
    max_val = max(L)
    total_rest = sum(L) - max_val
    
    # Answer = total_rest + max_val * 2^K
    # All mod 10^9+7
    
    ans = (total_rest % MOD + (max_val % MOD) * pow(2, K, MOD)) % MOD
    print(ans)

solve()

---

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