Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | minmax.in, minmax.out | Sursă | Concurs de incalzire 2020 |
| Autor | Bogdan Pop | Adăugată de |  Bogdan Pop •Bodo171 |
| Timp execuţie pe test | 0.45 sec | Limită de memorie | 524288 kbytes |
| Scorul tău | N/A | Dificultate | N/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 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 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.in | minmax.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} }.
