Secv7

secv7

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

Se da un sir de $N$ numere intregi {$A{~1~}$}, {$A{~2~}$}, ..., {$A{~N~}$}. Asupra acestui sir se poate efectua urmatoarea operatie: se imparte sirul in $3$ secvente nevide, se calculeaza valoarea maxima din fiecare secventa si apoi se face suma acestor valori. Cu alte cuvinte se aleg doi indici $0 < i < j < N$ si se calculeaza valorile
{$X = max { A{~k~} | 1 &le; k &le; i }$},
{$Y = max { A{~k~} | i+1 &le; k &le; j }$},
{$Z = max { A{~k~} | j+1 &le; k &le; N }$}
si suma {$S = X + Y + Z$}.
 
h2. Cerinta
 
Calculati valoarea minima a lui $S$ care se poate obtine in urma unei astfel de operatii si determinati cei doi indici care separa secventele pentru a obtine aceasta valoare.

Poveste si cerinta...

h2. Date de intrare

Prima linie a fisierului de intrare $secv7.in$ contine un numar natural $N$ reprezentand  numarul de elemente al sirului de intrare, iar a doua linie contine numerele intregi {$A{~1~}$}, {$A{~2~}$}, ..., {$A{~N~}$} separate prin cate un spatiu.

...

h2. Date de iesire

Fisierul de iesire $secv7.out$ va contine:
 
* pe prima linie: valoarea minima a sumei;
* pe a doua linie: doua numere naturale $i,j$ separate printr-un spatiu, reprezentand indicii pentru care se obtine valoarea minima pentru $S$ prin aplicarea operatiei descrise mai sus.

...

h2. Restrictii

* $3 ≤ N ≤ 30000$
* {$A{~1~}$}, {$A{~2~}$}, ..., {$A{~N~}$} sunt numere intregi din intervalul [{$-10000,10000$}]
* In cazul in care exista mai multe solutii se poate afisa oricare dintre ele.
 

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

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

| 7
3 2 1 5 6 3 2
| 10
2 3

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

|
h3. Explicatie

Prima secventa : $3 2$ - maximul este $3$
A doua secventa : $1$ - maximul este $1$
A treia secventa : $5 6 3 2$ - maximul este $6$
Suma: $10$

...

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

== SmfTopic(topic_id="...") ==

1827