aimin

Aimin

== include(page="template/taskheader" task_id="aimin") ==

Poveste si cerinta...

Sa consideram cele $N$ frunze ale unui arbore binar strict (fiecare nod intern al arborelui are exact $2$ fii, fiul stanga si fiul dreapta), numerotate de la $1$ la $N$ (in ordinea in care apar ele de la stanga la dreapta intr-o parcurgere $stanga-radacina-dreapta$ a arborelui). De fiecare frunza $i$ a fost agatata o panglica de lungime $L{~i~}$. Nivelul fiecarui nod al arborelui este egal cu lungimea drumului de la radacina arborelui la nodul respectiv (nivelul radacinii este $0$). Inaltimea unei frunze $i$ este egala cu nivelul acesteia plus $L{~i~}$. Inaltimea intregului arbore este egala cu maximul dintre inaltimile celor $N$ frunze ale sale. Determinati inaltimea minima posibila a arborelui.

h2. Date de intrare

...

Pe prima linie a fisierului de intrare $aimin.in$ se afla numarul intreg $N$. Pe a doua linie se afla $N$ numere intregi, separate prin spatii, reprezentand valorile $L{~i~}$, in ordine, de la $1$ la $N$.

h2. Date de iesire

...

In fisierul de iesire $aimin.out$ veti afisa inaltimea minima posibila a arborelui.

h2. Restrictii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 100 000$
* $1 ≤ L{~i~} ≤ 100 000 000$

h2. Exemplu
table(example). |_. aimin.in |_. aimin.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|5
3 1 2 4 2
|6

|

h3. Explicatie
 
...
 

== include(page="template/taskfooter" task_id="aimin") ==

2368