Таягийн Ялгаа

2s

512MB

2579

0%

Additional Problems II

Уртууд нь $a_1,a_2,\dots,a_n$ байх $n$ таяг өгөгдөнө. Таягуудад яг $k$ удаа огтолж, таягийн тоог $n + k$ болгох ёстой.

Огтолсоны дараа хамгийн урт ба хамгийн богино таягийн уртын ялгаа хамгийн бага байвал сайн. $k=1,2,\dots,m$ бүрийн хувьд боломжит хамгийн бага ялгааг ол.

Огтолсоны дараах таягийн уртууд эерэг бүхэл тоо байх ёстой. Таягуудыг $m$ удаа огтлож болно гэж үзнэ.

https://cses.fi/problemset/task/3401

Оролтын формат

Эхний мөрөнд хоёр бүхэл тоо $n,m$ байна: таягийн тоо ба огтлолтын дээд хязгаар.

Хоёр дахь мөрөнд $n$ бүхэл тоо $a_1,a_2,\dots,a_n$ байна: таягийн уртууд.

Гаралтын формат

$m$ бүхэл тоо бүхий нэг мөр хэвлэ: яг $k=1,2,\dots,m$ удаа огтолсон үеийн боломжит хамгийн бага ялгаа.

Хязгаарлалт

$1 \le n \le 10^5$
$1 \le m \le 2 \cdot 10^5$
$1 \le a_i \le 10^9$

Жишээ

Оролт1

3 3
7 3 2

Гаралт1

2 1 2

0.1 / 64 KiB

Редактор уншиж байна...