Fişierul intrare/ieşire:collar.in, collar.outSursăAlgoritmiada 2014, Runda 2
AutorAndrei HeidelbacherAdăugată dea_h1926Heidelbacher Andrei a_h1926
Timp execuţie pe test1.2 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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.incollar.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).

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content