Fişierul intrare/ieşire:secv7.in, secv7.outSursăONI 2007, clasa 9
AutorAdrian DiaconuAdăugată deDITzoneCAdrian Diaconu DITzoneC
Timp execuţie pe test0.1 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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.insecv7.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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content