Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2020-12-18 10:38:51.
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 orasului si dispui de N barci in sir indian (prima este cea mai apropiata de port, apoi a doua e in spatele primei si tot asa). Fiecare barca are puterea ei de atac specifica, dar aceasta putere scade in functie de distanta barcii fata de port.

Daca puterile barcilor sunt vazute ca un vector de numere intregi, 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. Asadar 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 incepe lupta in curand, dar realizeaza ca poate creste suma loviturilor reorganizand barcile, dar el din cauza ca este grabit poate doar sa permute circular vectorul cu barci, de exemplu [3, 4, 2, 1, 5] permutat circular la stanga de 2 ori va rezulta in [2, 1, 5, 4, 3]. Care este suma maxima a loviturilor daca poti permuta circular la stanga de ori de cate 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?