Codeforces Round #803 (Div. 2)
2 өдрийн дараа |
Codeforces Round #804 (Div. 2)
8 өдрийн дараа |
B. Ур чадварууд
хугацааны хязгаарлалт 2 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Леша домогт тоглоом Хакнет-ийн саяхан гарсан загварыг тоглодог. Тус загварт баатруудын ур чадварыг танилцуулжээ. Одоо баатар болгон яг $n$ ширхэг ур чадвартай байх юм. Ур чадвар болгон нь уг чадварын одоо байгаа төвшин болох сөрөг биш бүхэл тоо $a_{i}$-аар илэрхийлэгдэнэ. Бүх ур чадварууд нь хамгийн ихдээ ижилхэн $A$ төвшинтэй байж болно.
Ур чадварын дагуу бүх тоглогчдын дэлхийн чансаа мөн нэмэгджээ. Тоглогчид нь ХҮЧ-ын дагуу тус чансаанд эрэмбэлэгдэнэ. Тоглогчийн ХҮЧ гэдэг нь дараах утгуудын нийлбэр байна:
- Тоглогчийн баатрын төгс болгосон чадварын тоог (ө.х., $a_{i} = A$ байх чадварын тоо) $c_{f}$ коэффициентээр үржүүлнэ.
- Бүх чадвар дундах хамгийн бага төвшинтэй ($min a_{i}$) чадварыг $c_{m}$ коэффициентээр үржүүлнэ.
Одоо Леша-д $m$ ширхэг Хакнетиан валютын нэгж байгаа ба тэрээр эдгээрийг үрэх сонирхолтой байгаа юм. Валютын нэгж бүр нь ямар ч чадварын одоогийн төвшинг (хэрэв энэ нь хараахан $A$ болоогүй бол) $1$-ээр ихэсгэж чадна. Түүний баатар нь боломжит хамгийн их ХҮЧ-ын утгатай байхаар мөнгийг нь үрж өгнө үү.
Оролт
Эхний мөрөнд зайгаар тусгаарлагдсан 5 бүхэл тоо $n$, $A$, $c_{f}$, $c_{m}$ болон $m$ ($1 ≤ n ≤ 100 000$, $1 ≤ A ≤ 10^{9}$, $0 ≤ c_{f}, c_{m} ≤ 1000$, $0 ≤ m ≤ 10^{15}$) өгөгдөнө.
2-дахь мөрөнд чадваруудын одоогийн төвшин болох зайгаар тусгаарлагдсан яг $n$ ширхэг бүхэл тоо $a_{i}$ ($0 ≤ a_{i} ≤ A$) өгөгдөнө.
Гаралт
Эхний мөрөнд $m$-ээс ихгүй валютын нэгж ашиглан үүсгэж болох баатрын ХҮЧ-ын хамгийн их утгыг хэвлэнэ.
2-дахь мөрөнд $n$ ширхэг бүхэл тоо $a'_{i}$ ($a_{i} ≤ a'_{i} ≤ A$)-г хэвлэнэ. Эдгээр нь $m$-ээс ихгүй валютын нэгж ашиглан ХҮЧ нь хамгийн их байхаар үүсгэсэн баатрын шинэчлэгдсэн чадваруудын төвшинүүд юм. Тоонууд нь зайгаар тусгаарлагдсан байна.
Орчуулсан: Баатархүү
Жишээ тэстүүд
Оролт
3 5 10 1 5 1 3 1
Гаралт
12 2 5 2
Оролт
3 5 10 1 339 1 3 1
Гаралт
35 5 5 5
Тэмдэглэл
Эхний жишээнд оновчтой арга нь 2-дахь чадварыг хамгийн их төвшинд хүргэх ба бусад 2 чадварыг нь $1$-ээр ихэсгэх юм.
2-дахь жишээнд Леша бүх чадварыг хамгийн их төвшинд хүргэх юм.