Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | collar.in, collar.out | Sursă | Algoritmiada 2014, Runda 2 |
| Autor | Andrei Heidelbacher | Adăugată de |  Heidelbacher Andrei •a_h1926 |
| Timp execuţie pe test | 0.6 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Collar
Tassadar a descoperit un colier Xel’Naga format din N perle, fiecare perlă i având asociat un coeficient Vi, iar frumuseţea colierului este max(Vi, 1 ≤ i ≤ N) – min(Vi, 1 ≤ i ≤ N). El vrea să împartă colierul în mai multe coliere de lungimi egale, astfel încat fiecare colier nou să reprezinte o subsecvenţă a colierului iniţial, fiecare perlă din colierul iniţial să facă parte din exact un colier nou, iar suma frumuseţilor colierelor noi să fie maximă.
Tassadar nu este un bijutier prea iscusit şi vă roagă pe voi să-i spuneţi care este suma frumuseţilor maximă pe care o poate obţine printr-o împărţire a colierului.
Date de intrare
Fişierul de intrare collar.in conţine pe prima linie numărul natural N cu semnificaţia din enunţ. Pe linia următoare se află N numere întregi Vi reprezentând coeficienţii perlelor.
Date de ieşire
În fişierul de ieşire collar.out veţi afişa un singur număr, reprezentând frumuseţea maximă pe care o poate obţine Tassadar prin împărţirea colierului.
Restricţii
- 1 ≤ N ≤ 65.536
- -1.000.000.000 ≤ Vi ≤ 1.000.000.000
- colierul iniţial este circular
Exemplu
| collar.in | collar.out |
|---|---|
| 6 4 2 3 1 2 1 | 5 |
Explicaţie
Împărţim şirul în subsecvenţele [1, 4, 2] şi [3, 1, 2]. O altă împărţire validă este [1, 4] [2, 3] [1, 2] (putem considera aceste îmărţiri, deoarece colierul iniţial este circular).
