C. Илья ба Матриц

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

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

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

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

Ильяа бол үнэхээр сайхан ааштай арслан юм. Тэр математикт дуртай ба математикийн тухай зүйлүүдээс матрицуудад хамгийн их дуртай. Одоо тэрээр нэгэн төвөгтэй матрицыг бодох хэрэгтэй болжээ.

Түүнд $2^{n} × 2^{n}$ хэмжээтэй квадрат хэлбэр бүхий матриц байгаа бөгөөд мөн $4^{n}$ ширхэг бүхэл тоо байгаа юм. Та эдгээр тоонуудыг матрицад байрлуулахдаа (тоо бүрийг нэг нүдэнд байрлуулна) үр дүнд үүсэх матрицын үзэмж нь хамгийн их байхаар байрлуулна.

$2^{n} × 2^{n}$ хэмжээтэй матрицын үзэмж нь бүхэл тоо байх ба доорх алгоритмаар олно:

  1. Матрицынхаа хамгийн их элементийг олох ба түүнийгээ $m$ гэж тэмдэглэе.
  2. Хэрэв $n = 0$ бол уг матрицын үзэмж нь $m$-тэй тэнцүү.Бусад тохиолдолд матрицаа $2^{n - 1} × 2^{n - 1}$ хэмжээтэй үл огтолцох дөрвөн ширхэг дэд матрицуудад хуваах ба уг матрицын үзэмж нь $m$ болон эдгээр дөрвөн дэд матрицуудын үзэмжүүдийн нийлбэр байх юм.

Уг алгоритм нь таны бодож байгаачлан рекурсив алгоритм тул Илья танаас уг асуудлыг шийдэхэд тусална уу гэж хүсчээ. Үзэмж нь хамгийн их байх матрицыг хэвлэнэ үү.

Оролт

Эхний мөрөнд бүхэл тоо $4^{n}$ $(1 ≤ 4^{n} ≤ 2 \cdot 10^{6})$ өгөгдөх ба дараачийн мөрөнд $2^{n} × 2^{n}$ хэмжээтэй матрицад байрлуулах $4^{n}$ ширхэг бүхэл тоонууд болох $a_{i}$ $(1 ≤ a_{i} ≤ 10^{9})$ өгөгдөнө.

Гаралт

Дан мөрөнд өгөгдсөн матрицын үзэмжийн хамгийн их утгыг хэвлэнэ.

С++ дээр өгөгдлийг уншихдаа %lld заагчыг хэрэглэхгүй мөн бичихгүй байхыг хүсье. cin, cout, %I64d заагчыг хэрэглэх нь илүү тохиромжтой.

Орчуулсан: Баатархүү

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

Оролт
1
13
Гаралт
13
Оролт
4
1 2 3 4
Гаралт
14

Тэмдэглэл

Хоёр дахь жишээнд тоонуудыг матрицад дараах дарааллаар байрлуулах ба

1 2  
3 4

Ингэснээр уг матрицын үзэмж нь $4 + 1 + 2 + 3 + 4 = 14$-тэй тэнцүү болох юм.

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