Overview

Given \(N\) types of training machines, find the maximum total exercise effect obtainable by selecting \(K\) machines such that no machine is used consecutively.

Analysis

In this problem, the same machine cannot be used consecutively. Therefore, when considering the optimal selection, it is important to use machines with the highest exercise effects as much as possible.

First, as the simplest case, when \(K = 1\), it is optimal to simply choose the maximum exercise effect.

Next, consider the case \(K \geq 2\).

Key Observation

• If the machine with the maximum exercise effect exists in 2 or more copies:

  • By alternating between them, we can obtain the maximum value every time.
  • That is, the total is \(K \times \text{maximum value}\).

• If the maximum value is unique:

  • Since it cannot be used consecutively, after using the machine with the maximum value, we need to use the machine with the next highest exercise effect.
  • The optimal pattern in this case is:
    [max value, second max value, max value, second max value, ...]
    alternating like this.
  • The total in this case is: $\( \left\lfloor \frac{K}{2} \right\rfloor \times (\text{maximum value} + \text{second maximum value}) + (K \bmod 2) \times \text{maximum value} \)$

In this way, the problem can be solved by simply finding the maximum and second maximum values, without needing exhaustive search or DP.

Algorithm

1. Read the input and find the maximum value and the second maximum value.
2. Determine whether the maximum value appears multiple times.
   • If so, the answer is \(K \times \text{maximum value}\).
3. If the maximum value appears only once, calculate the total using the alternating pattern of maximum and second maximum values.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(1)\) (excluding input)

Implementation Notes

• Correctly find the maximum and second maximum values.
• Do not forget to handle the case \(K = 1\).
• Whether the maximum value appears multiple times can be determined using count() or similar.

## Source Code

```python
import sys
import heapq

def main():
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    K = int(data[1])
    A = list(map(int, data[2:]))

    # 最大値とそのインデックスを取得
    max_val = max(A)
    max_idx = A.index(max_val)

    # 最大値以外の最大値（異なるインデックス）
    second_max = 0
    for i in range(N):
        if i != max_idx:
            second_max = max(second_max, A[i])

    # もしK=1なら、単純に最大値を返す
    if K == 1:
        print(max_val)
        return

    # 最大値が複数あるかどうかを確認
    max_count = A.count(max_val)

    if max_count >= 2:
        # 同じ最大値を交互に使えるので、K * max_val
        print(K * max_val)
    else:
        # 最大値が1つだけの場合
        # 最初に最大値を使って、その後はsecond_maxと交互に使うのが最適
        # パターン: [max_val, second_max, max_val, second_max, ...]
        # 合計 = (K // 2) * (max_val + second_max) + (K % 2) * max_val
        res = (K // 2) * (max_val + second_max)
        if K % 2 == 1:
            res += max_val
        print(res)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.