Overview

Under the constraint that “you cannot use the same machine consecutively,” we maximize the total exercise effect over \(K\) selections. The conclusion is that it is optimal to alternately use the machine with the highest effect and the machine with the second highest effect.

Analysis

Key Insight

• The consecutive prohibition only applies to “the same machine as the one used immediately before.” In other words, it is possible to use the same machine every other turn.
• Since we want to maximize the total, the strategy is to “use the largest \(A_i\) as many times as possible.”

Let \(m_1\) be the maximum exercise effect value and \(m_2\) be the second largest (\(m_1 \ge m_2\)).

Why can’t we use \(m_1\) every time?

Since we cannot use the same machine consecutively, the turn after using \(m_1\) must always use a different machine.
Therefore, to increase the number of times \(m_1\) is used, we need to insert a different machine in between.

What is the optimal “filler” machine?

The “filler” needed to use \(m_1\) on turn \(k\) is added to the total regardless. Therefore, the filler should also be as large as possible, and the optimal choice is to always use \(m_2\).

Example: When \(K=5\)
The optimal arrangement is
\(m_1, m_2, m_1, m_2, m_1\)
which uses \(m_1\) three times and \(m_2\) twice.

How many times can each be used?

By alternating, - Odd turns (1, 3, 5, …) use \(m_1\) - Even turns (2, 4, 6, …) use \(m_2\)

which gives the maximum.

Therefore: - Number of times \(m_1\) is used: \(x=\left\lceil \dfrac{K}{2} \right\rceil = \dfrac{K+1}{2}\) (integer division: \((K+1)//2\)) - Number of times \(m_2\) is used: \(y=\left\lfloor \dfrac{K}{2} \right\rfloor = \dfrac{K}{2}\) (integer division: \(K//2\))

The maximum total is \(x \cdot m_1 + y \cdot m_2\).

Why a naive approach doesn’t work

Since \(K\) can be up to \(10^9\), actually simulating \(K\) selections (\(O(K)\)) is too slow.
However, based on the above observation, we can compute the answer in one shot using just the “count formula.”

Algorithm

1. Sort the array \(A\) in descending order.
2. Extract the maximum \(m_1=A[0]\) and the second largest \(m_2=A[1]\).
3. Compute \(x=(K+1)//2\) and \(y=K//2\).
4. Output the answer \(x \cdot m_1 + y \cdot m_2\).

Complexity

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

Implementation Notes

• Since \(K\) is large, there is no need to “construct the arrangement”; we simply compute the counts \(x, y\) using a formula.

• Since \(N \ge 2\) is guaranteed, we can safely access \(A[0]\) and \(A[1]\).

• Python integers can handle large values (on the order of \(10^9 \times 10^9\)), so there is no concern about overflow.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort(reverse=True)
    m1, m2 = A[0], A[1]
    x = (K + 1) // 2
    y = K // 2
    print(x * m1 + y * m2)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.