Overview

This is a problem where you choose one stock from \(N\) stocks and double its value, performing this operation \(K\) times, to maximize the total sum of all stock values. You output the result modulo \(10^9 + 7\).

Analysis

Which stock should be doubled?

To maximize the total sum, we should maximize the “amount of increase” at each operation. When a stock has value \(X\), doubling it makes it \(2X\), increasing the total sum by \(X\).

Therefore, always choosing the stock with the highest current value to double is optimal.

What happens when we repeat the operation?

When values are positive, after doubling the maximum stock, it remains the “maximum stock.” For example, if the stock values are \(\{3, 5, 8\}\), the maximum is \(8\). 1. Double \(8\) \(\rightarrow \{3, 5, 16\}\) (maximum is \(16\)) 2. Double \(16\) \(\rightarrow \{3, 5, 32\}\) (maximum is \(32\))

In this way, once a stock is the maximum, it will never be overtaken by other stocks after being doubled. In other words, the optimal strategy is “from start to finish, continuously double the stock with the initial maximum value \(K\) times in a row.”

Handling large \(K\)

\(K\) can be as large as \(10^{18}\), so actually repeating the doubling operation \(K\) times would not finish in time (TLE). However, doubling a value \(M\) a total of \(K\) times is equivalent to computing \(M \times 2^K\). Using programming language features (such as Python’s pow function), \(2^K \pmod{10^9+7}\) can be computed in \(O(\log K)\), which is extremely fast.

Algorithm

1. Find the maximum value \(M\) among the input stocks \(L_1, L_2, \ldots, L_N\).
2. Compute the sum \(S_{others}\) of all stocks except the maximum.
3. Compute the value after doubling \(M\) a total of \(K\) times: \(M_{final} = M \times 2^K \pmod{10^9+7}\).
4. Output the final answer as \((S_{others} + M_{final}) \pmod{10^9+7}\).

Complexity

• Time complexity: \(O(N + \log K)\)
  • Finding the maximum and computing the sum takes \(O(N)\), and computing \(2^K\) via fast exponentiation takes \(O(\log K)\).
• Space complexity: \(O(N)\)
  • Memory is needed for the list holding the values of \(N\) stocks.

Implementation Notes

• Modular arithmetic with large numbers: Since values become extremely large during computation, it is necessary to properly take mod (\(10^9 + 7\)).

• Exponentiation: In Python, using pow(base, exp, mod) allows fast computation of exponentiation with huge exponents while taking the modulus.

• Multiple maximum values: Even if there are multiple stocks with the maximum value, you only need to double one of them \(K\) times, so the result remains the same.

  Source Code

import sys

def solve():
    # Read all input data at once for efficient processing
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N is the number of stocks, K is the number of investment chances
    n = int(input_data[0])
    k = int(input_data[1])
    
    # L is the list of current assessment values for the N stocks
    l = list(map(int, input_data[2:]))
    
    mod = 10**9 + 7
    
    # To maximize the total sum, the optimal strategy is to always double
    # the stock that currently has the highest assessment value.
    # Since all L_i >= 1, doubling the maximum value will always result 
    # in a value that remains the maximum. Thus, we pick the initial 
    # maximum value and double it exactly K times.
    
    max_val = max(l)
    total_sum = sum(l)
    
    # Calculate the sum of the other N-1 stocks modulo 10^9 + 7
    # These values remain unchanged throughout the operations.
    others_sum = (total_sum - max_val) % mod
    
    # Calculate the value of the chosen maximum stock after K doublings.
    # We use modular exponentiation (pow(base, exp, mod)) for efficiency.
    max_val_final = (max_val % mod * pow(2, k, mod)) % mod
    
    # The final total sum is the sum of the unchanged stocks and the doubled stock.
    ans = (others_sum + max_val_final) % mod
    
    # Output the result modulo 10^9 + 7
    print(ans)

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-thinking.