概要

「同じマシンを連続で使えない」という制約のもとで、\(K\) 回の選択による運動効果の合計を最大化します。結論として、効果が最大のマシンと2番目のマシンを交互に使うのが最適です。

考察

重要な気づき

• 連続禁止なのは「直前と同じマシンだけ」です。つまり、同じマシンを 1回おき に使うのは可能です。
• 合計を最大化したいので、「できるだけ大きい \(A_i\) を多く使う」方針になります。

ここで、運動効果が最大の値を \(m_1\)、2番目を \(m_2\) とします（\(m_1 \ge m_2\)）。

なぜ \(m_1\) を毎回使えないか

同じマシンを連続では使えないため、\(m_1\) を使った次の回は必ず別のマシンにする必要があります。
したがって、\(m_1\) の使用回数を増やすには、間に別マシンを挟む必要があります。

「挟むマシン」は何が最適か

\(k\) 回目に \(m_1\) を使うために必要な「つなぎ」は、どれも合計に加算されます。ならば、その「つなぎ」もできるだけ大きい方がよく、最適なのは常に \(m_2\) を使うことです。

例：\(K=5\) のとき
最適な並べ方は
\(m_1, m_2, m_1, m_2, m_1\)
となり、\(m_1\) を 3 回、\(m_2\) を 2 回使えます。

何回ずつ使えるか

交互に置くと、 - 奇数回目（1,3,5,…）に \(m_1\) - 偶数回目（2,4,6,…）に \(m_2\)

となるのが最大です。

よって - \(m_1\) の回数：\(x=\left\lceil \dfrac{K}{2} \right\rceil = \dfrac{K+1}{2}\)（整数除算で \((K+1)//2\)） - \(m_2\) の回数：\(y=\left\lfloor \dfrac{K}{2} \right\rfloor = \dfrac{K}{2}\)（整数除算で \(K//2\)）

合計最大値は \(x \cdot m_1 + y \cdot m_2\) です。

素朴な方法がダメな理由

\(K\) は最大で \(10^9\) なので、実際に \(K\) 回シミュレーションして選ぶ（\(O(K)\)）のは時間的に不可能です。
一方で、上の観察により「回数の式」だけで一発計算できます。

アルゴリズム

1. 配列 \(A\) を降順にソートする。
2. 最大値 \(m_1=A[0]\)、2番目 \(m_2=A[1]\) を取り出す。
3. \(x=(K+1)//2\)、\(y=K//2\) を計算する。
4. 答え \(x \cdot m_1 + y \cdot m_2\) を出力する。

計算量

• 時間計算量: \(O(N \log N)\)（ソート）
• 空間計算量: \(O(N)\)（配列保持）

実装のポイント

• \(K\) が大きいので「並べ方の構築」は不要で、回数 \(x,y\) を式で求めます。

• \(N \ge 2\) が保証されているため、\(A[0], A[1]\) を安全に参照できます。

• Python の整数は大きな値（最大で \(10^9 \times 10^9\) 規模）でも扱えるのでオーバーフローの心配はありません。

  ソースコード

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()

---

この解説は gpt-5.2-high によって生成されました。