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 dă un ÅŸir de N numere întregi A₁, A₂, ..., 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.

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.

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₁, A₂, ..., A_N separate prin câte un spaÅ£iu.

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.

Restrictii

• 3 ≤ N ≤ 30000
• A₁, A₂, ..., 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.

Exemplu

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

Cum se trimit solutii?