Fişierul intrare/ieşire:	split.in, split.out	Sursă	ONI 2013, clasa a 9-a
Autor	Dan Pracsiu	Adăugată de	FMI Ciprian Olariu •scipianus
Timp execuţie pe test	0.1 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Split

Fie un şir a₁, a₂, ..., a_N de numere naturale. Se împarte şirul în patru secvenţe astfel încât orice element din şir să aparţină unei singure secvenţe şi fiecare secvenţă să conţină cel puţin două elemente. Mai exact, se identifică trei indici i < j < k astfel încât prima secvenţă este formată din elementele a₁, a₂, ..., a_i, a doua din elementele a_i+1, a_i+2, ..., a_j, a treia din elementele a_j+1, a_j+2, ..., a_k şi ultima din elementele a_k+1, a_k+2, ..., a_n. Pentru fiecare secvenţă se determină costul ei ca fiind diferenţa dintre valoarea maximă şi cea minimă din acea secvenţă.

Cerinţă

Să se determine o împărţire a şirului în patru secvenţe astfel încât suma costurilor celor patru secvenţe să fie maximă.

Date de intrare

Fişierul de intrare split.in conţine pe prima linie numărul natural N. Pe linia a doua se găsesc N numere naturale, separate prin câte un spaţiu, reprezentând elementele şirului a.

Date de ieşire

În fişierul de ieşire split.out conţine pe prima linie un singur număr natural reprezentând suma maximă a costurilor celor patru secvenţe. Pe linia a doua se află trei numere naturale i, j şi k, separate prin câte un spaţiu, cu semnificaţia din enunţ.

Restricţii

• 8 ≤ N ≤ 5 000
• 0 ≤ a_i ≤ 100 000 000, pentru orice i = 1..N
• O secvenţă poate avea costul 0 (valoarea maximă egală cu valoarea minimă)
• Dacă există mai multe soluţii cu aceeaşi sumă maximă, atunci se va alege soluţia cu i minim. Dacă există mai multe soluţii cu acelaşi i minim, se alege aceea cu j minim, iar dacă există mai multe soluţii cu acelaşi i şi j minim, se alege aceea cu k minim.

Exemplu

Explicaţie

Cele 4 secvenţe sunt:
9 7 3 0 (cost 9 – 0 = 9)
2 1 8 (cost 8 – 1 = 7)
6 0 (cost 6 – 0 = 6)
11 4 (cost 11 – 4 = 7)
O altă soluţie care obţine tot suma maximă 29 este 5 7 9, dar nu are i minim.

Cum se trimit solutii?