| Fişierul intrare/ieşire: | secv7.in, secv7.out | Sursă | ONI 2007, clasa 9 |
| Autor | Adrian Diaconu | Adăugată de |  Adrian Diaconu •DITzoneC |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Secv7
Se da un sir de N numere intregi A1, A2, ..., AN. 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 { Ak | 1 ≤ k ≤ i },
Y = max { Ak | i+1 ≤ k ≤ j },
Z = max { Ak | j+1 ≤ k ≤ N }
si suma S = X + Y + Z.
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.
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 A1, A2, ..., AN separate prin cate un spatiu.
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.
Restrictii
- 3 ≤ N ≤ 30000
- A1, A2, ..., AN sunt numere intregi din intervalul [-10000,10000]
- In cazul in care exista mai multe solutii se poate afisa oricare dintre ele.
Exemplu
| secv7.in | secv7.out |
|---|---|
| 7 3 2 1 5 6 3 2 | 10 2 3 |
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
