概要

食材の下ごしらえ時間の合計に、必ず取ることになる休憩時間 \(M \times R\) を足したものが、そのまま最小（というより常に同じ）合計時間になります。

考察

この問題のポイントは「順番を変えても、合計時間が変わらない」ことです。

• 食材の下ごしらえは必ず全て行うので、下ごしらえにかかる総時間は順番に関係なく常に \(\sum_{i=1}^{N} T_i\) です。
• 休憩は「ちょうど \(M\) 回」「1回 \(R\) 秒」なので、休憩にかかる総時間も常に \(M \times R\) です。
• 休憩は「食材を終えた直後」にしか取れず、「最初の前」「最後の後」には取れませんが、制約で \(M \le N-1\) が保証されています。
  つまり、食材と食材の間（間は全部で \(N-1\) 箇所）に休憩を入れれば必ず \(M\) 回入れられます。

よって、どの食材を先にやるか・どこで休憩を挟むかを工夫して短くする余地がありません。最小値は常に [ \sum_{i=1}^{N} T_i + M R ] です。

具体例:
\(N=3, M=1, R=10, (T_1,T_2,T_3)=(3,100,5)\) のとき、
どんな順番でも下ごしらえ合計は \(3+100+5=108\)、休憩は1回で \(10\)。
合計は常に \(118\) 秒になります（休憩を入れる場所を変えても同じ）。

素朴に「順番を全探索」「休憩位置をDP」などを考えると、\(N\) が最大 \(2 \times 10^5\) なので到底間に合いません。しかし上の観察により計算は単なる加算だけで済みます。

アルゴリズム

1. 入力を受け取る。
2. \(\text{ans} = \left(\sum T_i\right) + M \times R\) を計算する。
3. \(\text{ans}\) を出力する。

計算量

• 時間計算量: \(O(N)\)（\(T_i\) の総和を取るだけ）
• 空間計算量: \(O(N)\)（入力配列を保持する分。保持せず逐次加算なら \(O(1)\) でも可能）

実装のポイント

• 答えは最大で \(\sum T_i \le 2\times10^5 \times 10^9 = 2\times10^{14}\)、さらに \(M R\) も加わるため、\(64\) bit 整数相当が必要です（Python の int なら問題なし）。

• 入力が大きいので、sys.stdin.buffer.read() による高速入力にしておくと安全です。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, M, R = data[0], data[1], data[2]
    T = data[3:3+N]
    ans = sum(T) + M * R
    print(ans)

if __name__ == "__main__":
    main()

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