Fişierul intrare/ieşire:blackwater.in, blackwater.outSursăWinter Challenge 2020
AutorBogdan Pop, Craciun Ioan-FlaviuAdăugată dewinterchallenge2020Comisia •winterchallenge2020
Timp execuţie pe test2 secLimită de memorie256000 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Battle of the Blackwater

Stannis Baratheon incearcă să cucerească King's Landing. El atacă prin portul oraşului şi dispune de N bărci in şir indian (prima este cea mai apropiată de port, apoi a doua e in spatele primei şi tot aşa). Fiecare barcă are puterea ei de atac specifică, dar aceasta putere scade în funcţie de distanţa bărcii faţă de port.

Dacă puterile bărcilor sunt vazute ca un vector de numere întregi, de exemplu V = [3, 4, 2, 1, 5] atunci prima va lovi cu putere [3/1], a doua cu putere [4/2] = 2, a treia cu putere [2/3] = 0, a patra cu putere [1/4] = 0 si a cincea cu putere [5/5] = 1, unde [x] este partea întreagă inferioară numărului x. Aşadar, suma tuturor loviturilor date de bărci este \lfloor{$V_{1}/1}\rfloor + \lfloor{V_{2}/2}\rfloor + \lfloor{V_{3}/3}\rfloor + .. + \lfloor{V_{N}/N$}\rfloor .

Stannis începe lupta în curând, dar realizează că poate creşte suma loviturilor reorganizand bărcile, dar el, din cauza că este grabit, poate doar să permute circular vectorul cu bărci, de exemplu [3, 4, 2, 1, 5] permutat circular la stânga de 2 ori va rezulta în [2, 1, 5, 3, 4]. Care este suma maximă a loviturilor daca poti permuta circular la stânga de ori de câte ori vrei (eventual 0 ori)?

Date de intrare

Fişierul de intrare blackwater.in va contine pe prima linie un numar natural N.
A doua linie va contine cele n numere intregi ce formeaza vectorul V.

Date de ieşire

În fişierul de ieşire blackwater.out se va afisa pe prima linie un singur numar natural, suma maxima a puterilor barcilor dupa permutari.

Restricţii

  • 1 ≤ n ≤ 80 000
  • 0 ≤ v[i] ≤ 100 000
  • Pentru 11 puncte se asigura ca 1 ≤ n ≤ 5000
  • Pentru 10 puncte se asigura ca 1 ≤ k ≤ 5000 unde k este numarul de elemente nenule
  • Pentru alte 16 puncte se asigura ca valorile elementelor vor fi doar 0 sau 100 000

Exemplu

blackwater.inblackwater.out
5
3 4 2 1 5
7
3
100000 0 100000
150000

Explicaţie

[3, 4, 2, 1, 5] permutat la stanga de 4 ori va rezulta [5, 3, 4, 2, 1] -> [5/1] + [3/2] + [4/3] + [2/4] + [1/5] = 5 + 1 + 1 + 0 + 0 = 7
[100000, 0, 100000] permutat la stanga de 2 ori va rezulta [100000, 100000, 0] -> [100000/1] + [100000/2] + [0/3] = 100000 + 50000 + 0 = 150000

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?