Fişierul intrare/ieşire:minmax.in, minmax.outSursăConcurs de incalzire 2020
AutorBogdan PopAdăugată deBodo171Bogdan Pop Bodo171
Timp execuţie pe test0.9 secLimită de memorie524288 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Minmax

Ai un şir v de n numere naturale. Te gândeşti să îl împarţi în k subşiruri, astfel încât fiecare element al şirului să apară în exact un subşir iar suma valorilor acestor subşiruri să fie maximă. Valoarea unui subşir este reprezentată de diferenţa dintre valoarea maximă şi minimă a subşirului. Pentru că problema nu ţi se pare suficient de grea, vrei sa afli răspunsul pentru toate valorile lui k de la 1 la n.
Un subşir reprezintă un şir obţinut din şirul iniţial prin ştergerea a 0 sau mai multe elemente, nu neapărat consecutive.

Date de intrare

Fişierul de intrare minmax.in conţine pe prima linie un număr n, iar pe a doua linie n numere v[i].

Date de ieşire

În fişierul de ieşire minmax.out conţine n linii, a k-a linie conţinând răspunsul pentru o împărţire în k subşiruri.

Restricţii

  • 1 ≤ n ≤ 100.000 , 1 ≤ v[i] ≤ 1.000.000.000
  • Testele sunt grupate! Fiecare dintre următoarele seturi de teste reprezintă câte o grupă. Restul testelor (cele care nu respectă alte condiţii decât cele iniţiale) sunt, de asemenea, grupate.
  • Pentru primele 4 grupe, numerele din şirul v sunt distincte.
  • Pentru 10 puncte 1 ≤ n ≤ 5
  • Pentru alte 10 puncte, 1 ≤ n ≤ 10
  • Pentru alte 10 puncte 1 ≤ n ≤ 100
  • Pentru alte 10 puncte 1 ≤ n ≤ 1.000

Exemplu

minmax.inminmax.out
4
1 2 3 4
3
4
3
0
3
1 2 1
1
1
0

Explicaţie

În primul exemplu, vom avea pe rând următoarele partiţii (ca valori): { {1, 2, 3, 4} }, { {1, 4}, {2, 3} }, { {1, 4}, {2}, {3} }, { {1}, {2}, {3}, {4} }.
În al doilea exemplu, vom avea pe rând partiţiile (ca valori): { {1,2,1} }, { {1,2} , {1} }, { {1}, {2}, {1} }.

Nota

Limita de timp este diferita de cea din timpul concursului pentru a permite obtinerea scorului maxim si prin submisii in java

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?