D. Мөсөн хөшөөнүүд

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

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

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

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

Бэрландын Их Сургууль $256$ жилийн ойгоо тэмдэглэхээр зэхэж байна. Дэд захирал их сургуулийн хотхоныг чимэглэхээр шийдэж, хотхоны төв хэсэгт $n$ ширхэг мөсөн хөшөөг босгожээ. Хөшөөнүүд нь бие биенээсээ ижил хэмжээтэй байхаар тойрог хэлбэрээр байрласан бөгөөд эдгээр нь нийлээд $n$ өнцөгт үүсгэж байв. Мөн хөшөөнүүдийг цагийн зүүний дагуу $1$-ээс $n$ хүртэл дугаарлажээ.

Хөшөө болгоныг сэтгэл татам байдлаар нь үнэлсэн бөгөөд хөшөө тус бүр $t_{i}$ үнэлгээ авчээ. $t_{i}$ нь эерэг, сөрөг, эсвэл $0$ байх боломжтой.

Их сургуулийн захирал чимэглэлтийг шалгахаар ирээд "Хараахан төгс болоогүй байна. Зарим хөшөөг хайлуулах хэрэгтэй" гэжээ. Дараах дүрмээр хөшөөг хайлуулна:

  • Үлдэж буй хөшөө зөв олон өнцөгт үүсгэх ($3$-аас $n$ хүртэл олон өнцөгт байх боломжтой).
  • Үлдсэн хөшөөний үнэлгээнүүдийн $t_{i}$ нийлбэр хамгийн их байх.

Дэд захиралд энэ даалгаварыг биелүүлэхэд туслана уу. Нэг ч хөшөөг хайлуулахгүй байж болно. Хөшөө байрнаасаа хөдлөхгүй.

Оролт

Эхний мөрөнд анхны хөшөөнүүдийн тоо бүхэл тоо $n$ ($3 ≤ n ≤ 20000$). Хоёр дахь мөрөнд $n$ ширхэг бүхэл тоо $t_{1}, t_{2}, ..., t_{n}$ ($-1000 ≤ t_{i} ≤ 1000$) хоосон зайгаар тусгаарлагдан өгөгдөнө. Үүнд $t_{i}$ нь $i$ дэхь хөшөөний үнэлгээ.

Гаралт

Гарч болох хамгийн их үнэлгээний нийлбэрийг хэвлэнэ.

Орчуулсан: Энхлут

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

Оролт
8
1 2 -3 4 -5 5 2 3
Гаралт
14
Оролт
6
1 -2 3 -4 5 -6
Гаралт
9
Оролт
6
1 2 3 4 5 6
Гаралт
21

Тэмдэглэл

Эхний жишээн дээр хоёр дахь хөшөө болгоныг үлдээж бусдыг нь хайлуулна. Өөрөөр хэлвэл $2$, $4$, $5$, $3$ гэсэн үнэлгээтэй хөшөөнүүдийг үлдээнэ.

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