| 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 diamante, fiecare diamant i având asociat un număr de carate Vi. Puterea magică oferită de un colier 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 să fie respectate următoarele condiţii:
- 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
- suma puterilor oferite de colierele noi să fie maximă
Deoarece Tassadar nu este un bijutier prea iscusit, vă roagă pe voi să-i spuneţi care este puterea 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 numărul de carate pentru fiecare diamant.
Date de ieşire
În fişierul de ieşire collar.out veţi afişa un singur număr, reprezentând suma maximă a puterilor 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
- Vă recomandăm să folosiţi numere întregi pe 64 de biţi cu semn
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).
