Costel are de rezolvat o temă grea la matematică: având la dispoziţie $N$ numere naturale nenule trebuie să aşeze între acestea 2 operaţii de înmulţire şi $N-3$ operaţii de adunare, astfel încât rezultatul calculelor să fie cel mai mare posibil. Nu este permisă modificarea ordinii numerelor date.
De exemplu, dacă $N=5$ şi numerele sunt $4$, $7$, $1$, $5$, $3$, operaţiile pot fi aşezate $4 + 7 * 1 + 5 * 3, 4 * 7 *1 + 5 + 3$ etc.
h2. Cerinta
Scrieţi un program care să aşeze două operaţii de înmulţire şi $N-3$ operaţii de adunare între cele $N$ valori date astfel încât valoarea expresiei obţinute să fie maximă.
h2. Date de intrare
Fişierul de intrare $expresie.in$ ...
Fişierul de intrare $expresie.in$ va contine pe prima linie un număr natural $N$, reprezentând numărul elementelor date. Pe următoarele linii se află cele $N$ numere naturale date, fiecare pe câte o linie.
h2. Date de ieşire
În fişierul de ieşire $expresie.out$ ...
Fişierul de ieşire $expresie.out$ va conţine, pe prima linie, valoarea maximă obţinută prin evaluarea expresiei
h2. Restricţii
* $... ≤ ... ≤ ...$
* $$ ≤ N ≤ 1000$
* Numerele date sunt numere naturale între $1$ şi $10000$
h2. Exemplu
table(example). |_. expresie.in |_. expresie.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 5
4
7
1
5
3
| 44
|
h3. Explicaţie
...
Valoarea maximă se obţine prin aşezarea operaţiilor sub forma: $4 * 7 + 1 + 5 * 3$
== include(page="template/taskfooter" task_id="expresie") ==
