== include(page="template/taskheader" task_id="secv7") ==
Poveste si cerinta...
Se dă un şir de $N$ numere întregi {$A{~1~}$}, {$A{~2~}$}, ..., {$A{~N~}$}. Asupra acestui şir se poate efectua următoarea operaţie: se împarte şirul în $3$ secvenţe nevide, se calculează valoarea maximă din fiecare secvenţă şi apoi se face suma acestor valori. Cu alte cuvinte se aleg doi indici $0 < i < j < N$ şi se calculează valorile
{$X = max { A{~k~} | 1 ≤ k ≤ i }$},
{$Y = max { A{~k~} | i+1 ≤ k ≤ j }$},
{$Z = max { A{~k~} | j+1 ≤ k ≤ N }$}
ÅŸi suma {$S = X + Y + Z$}.
h2. Cerinţă
Calculaţi valoarea minimă a lui $S$ care se poate obţine în urma unei astfel de operaţii şi determinaţi cei doi indici care separă secvenţele pentru a obţine această valoare.
h2. Date de intrare
...
Prima linie a fişierului de intrare $secv7.in$ conţine un număr natural $N$ reprezentând numărul de elemente al şirului de intrare, iar a doua linie conţine numerele întregi {$A{~1~}$}, {$A{~2~}$}, ..., {$A{~N~}$} separate prin câte un spaţiu.
h2. Date de iesire
...
Fişierul de ieşire secv7.out va conţine:
* pe prima linie: valoarea minimă a sumei;
* pe a doua linie: două numere naturale $i,j$ separate printr-un spaţiu, reprezentând indicii pentru care se obţine valoarea minimă pentru $S$ prin aplicarea operaţiei descrise mai sus.
h2. Restrictii
* $... ≤ ... ≤ ...$
* $3 ≤ N ≤ 30000$
* {$A{~1~}$}, {$A{~2~}$}, ..., {$A{~N~}$} sunt numere întregi din intervalul [{$-10000,10000$}]
* În cazul în care există mai multe soluţii se poate afişa oricare dintre ele.
h2. Exemplu
table(example). |_. secv7.in |_. secv7.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 7
3 2 1 5 6 3 2
| 10
2 3
|
h3. Explicatie
...
Prima secvenţă : $3 2$ – maximul este $3$
A doua secvenţă : $1$ – maximul este $1$
A treia secvenţă : $5 6 3 2$ – maximul este $6$
Suma: $10$
== include(page="template/taskfooter" task_id="secv7") ==
