Overview

This is a problem about maximizing the total exercise effect from \(K\) training sessions, under the constraint that you cannot use the same machine consecutively.

Analysis

Key Insight

To maximize the exercise effect, we want to use the machines with the highest effects as much as possible. However, there’s a constraint that “you cannot use the same machine consecutively.”

Here’s an important observation: - We want to use the machine with the maximum value as much as possible - To avoid consecutive use, we need to insert a different machine in between - For the machine in between, the second highest effect machine is optimal

In other words, we only need to consider the top two machines (\(\text{max1}\), \(\text{max2}\)).

Problem with the Naive Approach

A simulation that “loops \(K\) times and makes the optimal choice each time” will obviously result in TLE since \(K\) can be up to \(10^9\).

Solution

Analyze the pattern and calculate directly using formulas.

Case 1: When \(\text{max1} = \text{max2}\) - There are multiple machines with the maximum effect, so we can use them alternately - We get the effect of \(\text{max1}\) every time - Total = \(\text{max1} \times K\)

Case 2: When \(\text{max1} > \text{max2}\) - We use them alternately: \(\text{max1}\), \(\text{max2}\), \(\text{max1}\), \(\text{max2}\), … - Out of \(K\) times, we can use \(\text{max1}\) \(\lceil K/2 \rceil\) times and \(\text{max2}\) \(\lfloor K/2 \rfloor\) times

Concrete Example

For \(N=3\), \(K=5\), \(A = [10, 7, 3]\): - \(\text{max1} = 10\), \(\text{max2} = 7\) - Pattern: \(10 \to 7 \to 10 \to 7 \to 10\) - \(\text{max1}\) is used \(\lceil 5/2 \rceil = 3\) times, \(\text{max2}\) is used \(\lfloor 5/2 \rfloor = 2\) times - Total = \(10 \times 3 + 7 \times 2 = 44\)

Algorithm

1. Sort array \(A\) in descending order
2. Get the maximum value \(\text{max1} = A[0]\) and second maximum \(\text{max2} = A[1]\)
3. If \(\text{max1} = \text{max2}\), the answer is \(\text{max1} \times K\)
4. Otherwise, the answer is \(\text{max1} \times \lceil K/2 \rceil + \text{max2} \times \lfloor K/2 \rfloor\)

Complexity

• Time complexity: \(O(N \log N)\) (dominated by sorting)
• Space complexity: \(O(N)\) (for storing the array)

Implementation Notes

• \(\lceil K/2 \rceil\) can be calculated as (K + 1) // 2

• \(\lfloor K/2 \rfloor\) can be calculated as K // 2

• Since \(K\) and \(A_i\) can be up to \(10^9\), the answer can be as large as \(10^{18}\). In Python, there’s no need to worry about integer overflow, but caution is required in other languages

• Due to the constraint \(N \geq 2\), \(\text{max2}\) is guaranteed to always exist

  Source Code

def solve():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    
    # Sort in descending order
    A.sort(reverse=True)
    
    # Get the two largest values
    max1 = A[0]  # Largest
    max2 = A[1]  # Second largest
    
    # Strategy:
    # - If max1 == max2, we can use them alternately for all K rounds
    #   Total = K * max1
    # - If max1 > max2, we want to use max1 as much as possible
    #   We alternate between max1 and max2
    #   In K rounds, we can use max1 ceil(K/2) times and max2 floor(K/2) times
    #   But we need to be careful: we use max1, max2, max1, max2, ...
    #   If K is odd: (K+1)/2 times max1, K/2 times max2
    #   If K is even: K/2 times max1, K/2 times max2
    
    if max1 == max2:
        # All top values are the same, can use any of them every round
        result = max1 * K
    else:
        # Alternate between max1 and max2
        # Pattern: max1, max2, max1, max2, ...
        # Number of max1 uses: ceil(K/2) = (K+1)//2
        # Number of max2 uses: floor(K/2) = K//2
        times_max1 = (K + 1) // 2
        times_max2 = K // 2
        result = max1 * times_max1 + max2 * times_max2
    
    print(result)

solve()

---

This editorial was generated by claude4.5opus.