Codeforces Round #804 (Div. 2)
5 өдрийн дараа |
C. Васяа ба гоё массив
хугацааны хязгаарлалт 1 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Васяа-ийн төрсөн өдөр болох гэж байгаа ба түүний ээж түүнд $n$ урттай эерэг бүхэл $a$ массив өгөхөөр шийдсэн.
Васяа хамгийн их ерөнхий хуваагчтай массивийг гоё массив гэж бодсон. Түүний ээж мэдээж хэрэг түүнд аль болох гоё массив өгөхыг хүссэн. Харамсалтай нь дэлгүүрт зөвхөн $a$ массив л үлдсэн байсан. Худалдагч нь массивийн зарим элементийг бууруулж болно гэж хэлсэн ($k$-аас ихээр буруулж болохгүй).
Худалдагч $a$ матрицаас $b$ матрицийг олж авхад дараах дүрмийг дагаж авах боломжтой. Үүнд: $b_{i} > 0; 0 ≤ a_{i} - b_{i} ≤ k$; $1 ≤ i ≤ n$.
Васяа-аад өгөх гоё массивд хамгийн боломжтой массивийг олоход нь түүний ээжид туслаарай.
Оролт
Эхнй мөрөнд хоёр бүхэл $n$ ба $k$ $(1 ≤ n ≤ 3*10^{5}; 1 ≤ k ≤ 10^{6})$ тоонууд оруулна. Хоёр дахь мөрөнд $n$ ширхэг $a$ массивийн $a_{i}$ $(1 ≤ a_{i} ≤ 10^{6})$ элементүүдийг оруулна.
Гаралт
Ганц мөрөнд нэг тоо хэвлэнэ. Энэ тоо нь гоё массивийн хамгийн их ерөнхий хуваагч юм.
Орчуулсан: Даариймаа
Жишээ тэстүүд
Оролт
6 1 3 6 10 12 13 16
Гаралт
3
Оролт
5 3 8 21 52 15 77
Гаралт
7
Тэмдэглэл
Эхний жишээнд бид энэ массивийг авч чадна:
$3 6 9 12 12 15$
Хоёр дахь жишээнд бид энэ дараагийн массивийг авна:
$7 21 49 14 77$