Fie un şir i < j < k
astfel încât prima secvenţă este formată din elementele
Cerința
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
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 și precizări
8 ≤ N ≤ 5.000
0 ≤
≤ 100.000.000
, pentru oricei = 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şii
minim, se alege aceea cuj
minim, iar dacă există mai multe soluții cu acelaşii
șij
minim, se alege aceea cuk
minim.
Exemplu:
split.in
11 9 7 3 0 2 1 8 6 0 11 4
split.out
29 4 7 9
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.