Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2020-12-18 10:42:55.
Revizia anterioară   Revizia următoare  

 

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

Esti Stannis Baratheon si incerci sa cuceresti King's Landing. Ataci prin portul oraşului şi dispui 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ă inferioara numărului x. Aşadar, suma tuturor loviturilor date de barci 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 bprci, de exemplu [3, 4, 2, 1, 5] permutat circular la stânga de 2 ori va rezulta în [2, 1, 5, 4, 3]. 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 10% din punctajul problemei se asigura ca 1 ≤ n ≤ 5000
  • Pentru alte 10% din punctajul problemei se asigura ca 1 ≤ k ≤ 5000 unde k este numarul de elemente nenule
  • Pentru alte 15% din punctajul problemei se asigura ca valorile elementelor vor fi doar 0 sau 100 000

Exemplu

blackwater.inblackwater.out
5
3 4 2 1 5
7

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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?