B. ХИЕХ-ын массив

хугацааны хязгаарлалт 3 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Танд $n$ урттай $a_{i}$ массив өгөгдсөн. Та уг массивд дараалласан хоёр үйлдэл хийж болно:

  • $m < n$ урттай зарим дэд хэсгийг(үргэлжилсэн дэд дараалал) устгах ба үүний оронд $m*a$ ширхэг зоос төлөх
  • массивийн зарим элементийг хамгийн ихдээ $1$-ээр өөрчлөх ба өөрчлөлт бүрт $b$ ширхэг зоос төлөх

Үйлдэл бүрийг хамгийн ихдээ нэг удаа хийж болох ба (хийхгүй ч байж болно) та зөвхөн нэг хэсгийг л устгаж болох ба тоо бүр хамгийн ихдээ $1$-ээр өөрчлөгдөж (ихсэнэ эсвэл буурна) болно гэдгийг сана. Мөн та массивийг бүхэлд нь устгаж болохгүй.

Таны зорилго бол үүссэн массивын элементүүдийн хувьд ХИЕХ нь $1$-ээс их болгохын тулд зарцуулах зоосны хамгийн бага тоог тооцоолох явдал юм.

Оролт

Оролтын эхний мөрөнд бүхэл тоон утгууд $n$, $a$ ба $b$ ($1 ≤ n ≤ 1 000 000, 0 ≤ a, b ≤ 10^{9}$) байх ба харгалзан массивийн урт, эхний үйлдэлд нэг элементийг устгахад шаардагдах өртөг ба нэг элементийг өөрчлөх өртөг юм.

Хоёр дахь мөрөнд $n$ ширхэг бүхэл тоон утгууд $a_{i}$ ($2 ≤ a_{i} ≤ 10^{9}$) байх ба массивийн элементүүд юм.

Гаралт

Массивын элементүүдийн хувьд ХИЕХ нь $1$-ээс их байх массивийг олж авахын тулд хэрэгтэй өөрчлөлтүүдийн хамгийн бага өртгийг илэрхийлэх ганц тоог хэвлэ.

Орчуулсан: Г.Мэндбаяр

Жишээ тэстүүд

Оролт
3 1 4
4 2 3
Гаралт
1
Оролт
5 3 2
5 17 13 5 6
Гаралт
8
Оролт
8 3 4
3 7 5 4 3 12 9 4
Гаралт
13

Тэмдэглэл

Эхний жишээн дээр хамгийн тохиромжтой зам бол $3$ тоог устгаж оронд нь $1$ зоос зарцуулах юм.

Хоёр дахь жишээн дээр та $[17, 13]$ хэсгийг устгаж $6$ тоог бууруулах хэрэгтэй. Эдгээр өөрчлөлтүүдийн өртөг нь $2*3 + 2 = 8$ зоостой тэнцэнэ.

Сэтгэгдлүүдийг ачааллаж байна...