Codeforces Round #803 (Div. 2)
04:22:59 |
Codeforces Round #804 (Div. 2)
6 өдрийн дараа |
C. Таамгаар үүссэн гайхамшигт нийлбэр
хугацааны хязгаарлалт 2 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
"Сур сур, бас дахин сур" — Энэ бол Валерагийн өдөр бүр хийх ёстой зүйл. Тэр математикийг гол чиглэлээ болгосон математикийн сургуульд сурдаг. Математикийн багш нь өөрийн мэргэжилдээ маш хайртай ба үүнийгээ өөрийн сурагчдад түгээхийг хүсдэг. Тийм ч учраас тэр сурагчиддаа хүнд ба их даалгавар өгдөг. Хэдийгээр Валера хамгийн шилдэг сурагчдын нэг ч гэсэн тэрбээр гэрийн даалгавраа сайн зохицуулж чадаагүй. Тийм учраас Валера танаас дараах даалгаврууд дээрээ тусламж хүсчээ.
$n$ ширхэг элемэнттэй тоон дараалал өгөгдсөн. Дарааллын префикс гэдэг нь дарааллын эхлэлээс сонгогдсон хэсэг юм (хоосон байж болно). Дарааллын саффикс гэдэг нь дарааллын төгсгөлөөс сонгогдсон хэсэг (хоосон байж болно). Дараалалд 2 үйлдлийг дэс дараатайгаар хийх боломжтой. Эхний үйлдэл нь ямар нэгэн префикс сонгож аваад бүх тоог нь $-1$-ээр үржүүлэх. Хоёр дахь үйлдэл нь ямар нэгэн саффикс сонгож аваад бүх тоог нь $-1$-ээр үржүүлэх. Сонгогдсон префикс болон саффикс нь огтлолцож болно. Өмнө дурдсан үйлдлүүдийг хийсний дараа үүсэх дарааллын боломжит хамгийн их нийлбэр хэд вэ?
Оролт
Эхний мөр дарааллын элемэнтийн тоог илэрхийлэх $n$ ($1 ≤ n ≤ 10^5$) тоог агуулна. Дараагийн мөрөнд дарааллыг илэрхийлэх $n$ ширхэг $a_i$ ($-10^4 ≤ a_i ≤ 10^4$) тоонууд зайгаар тусгаарлагдан өгөгдөнө.
Гаралт
Нэг мөрөнд бодлогын хариуг хэвлэ.
Орчуулсан: Хонгор
Жишээ тэстүүд
Оролт
3 -1 -2 -3
Гаралт
6
Оролт
5 -4 2 0 5 0
Гаралт
11
Оролт
5 -1 10 -5 10 -2
Гаралт
18