室温(Room Temperature)

K 理事長は,役員がいる部屋の室温を調節する役割を担っており,役員ができるだけ快適に過ごせるよう
にしたいと考えている.
今,部屋にN 人の役員がいる.それぞれの役員には1 からN までの番号が付けられており,上着を着て
いない状態での役員i (1 ≦i ≦N) の適温はAi 度である.また,それぞれの役員について,上着を1 枚着る
ごとに適温がT 度下がる.すなわち,役員i が上着をk 枚着ると,役員i の適温はAi −kT 度になる.
室温をx 度,ある役員の適温をy 度とすると,その役員の不快度は|x −y| で表される.ただし,|t| はt の
絶対値を表す.各役員は室温に応じて,不快度が最小となるよう0 枚以上の適切な枚数の上着を着る.
ここでK 理事長は,役員の不快度の最大値を部屋の不快度と呼ぶことにし,部屋の不快度が最小となる
ように室温を設定することにした.ただし,設定する室温は整数でなければならない.
役員と適温に関する情報が与えられたとき,部屋の不快度としてありうる最小値を求めるプログラムを作
成せよ.

• 2 ≦N ≦500 000.
• 1 ≦T ≦109.
• 1 ≦Ai ≦109 (1 ≦i ≦N).
• 入力される値はすべて整数である.

1. (15 点) N = 2.
2. (5 点) N ≦3 000,T = 1.
3. (30 点) N ≦3 000,T ≦2.
4. (35 点) N ≦3 000,T ≦3 000.
5. (15 点) 追加の制約はない.

入力は以下の形式で標準入力から与えられる.
N T
A1 A2 · · · AN

標準出力に,部屋の不快度としてありうる最小値を1 行で出力せよ.

第23 回日本情報オリンピック(JOI 2023/2024) 本選
2024 年2 月4 日(オンライン開催)

생성자가 기록되지 않았습니다.

출처 JOI 2024 Final