== include(page="template/taskheader" task_id="voodoo") ==
Se dă $*N*$, $*X*$, $*Y*$ și un șir de $*N*$ numere naturale $*a*[~1~]$, $*a*[~2~]$, ..., $*a*~*N*~$.
Definim costul unui rearajament $*p*$ al șirului $*a*$ ca fiind suma tuturor subsecvențelor (i, j) astfel încat 1 ≤ i ≤ X și Y ≤ j ≤ N. Costul poate fi calculat astfel:
Definim costul unui rearajament $*p*$ al șirului $*a*$ ca fiind suma tuturor subsecvențelor (i, j) astfel încat $1$ ≤ i ≤ $*X*$ și $*Y*$ ≤ j ≤ $*N*$. Costul poate fi calculat astfel:
!pseudocod_.png!
Aflați costul minim al unei rearanjări a șirului $*a*$ cât și o rearanjare ce obține acest cost minim.
h2. Date de intrare
Fișierul de intrare $voodoo.in$ ...
Fișierul de intrare $voodoo.in$ conține pe prima linie, în aceast ordine numerele naturale $*N*$, $*X*$, $*Y*$, separate prin spațiu. Pe cea de-a doua linie se află $*N*$ numere naturale separate prin spațiu, reprezentând șirul $*a*$.
h2. Date de ieșire
În fișierul de ieșire $voodoo.out$ ...
Pe prima linie a fișierul de ieșire $voodoo.out$ se află costul minim al unei rearanjări a șirului $*a*$, iar pe a doua linie se afla $*N*$ numere naturale care reprezintă o rearanjare a șirului $*a*$ ce obține cost minim.
h2. Restricții
* $... ≤ ... ≤ ...$
* $1$ ≤ $*X*$ < $*Y*$ ≤ $*N*$ ≤ $1.000.000$
* Se garantează că răspunsul se incadreaza pe tipul de date $long long$
h2. Exemplu
table(example).
|_. voodoo.in |_. voodoo.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|5 1 2
1 2 3 4 5
|34
2 1 3 4 5
|
|5 2 4
1 3 3 4 5
|46
5 3 1 3 4
|
| 8 2 6
1 2 6 2 10 9 3 5
|202
6 2 1 2 3 5 9 10
|
h3. Explicație
...
Pentru primul exemplu, rearanjarea este $2 1 3 4 5$, costul acestei rearanjari este:
$(2 + 1) + (2 + 1 + 3) + (2 + 1 + 3 + 4) + (2 + 1 + 3 + 4 + 5) =$
$3 + 6 + 10 + 15 = 34$
Se poate demonstra ca nu exista alta rearanjare cu costul mai mic.
Pentru al doilea exemplu, rearanjarea este $5 3 1 3 4$, costul acestei rearanjari este:
$(5 + 3 + 1 + 3) + (5 + 3 + 1 + 3 + 4) + (3 + 1 + 3) + (3 + 1 + 3 + 4) =$
$12 + 16 + 7 + 11 = 46$
Din nou, se poate demonstra ca nu exista alte rearanjări ale șirului $*a*$ care au costul mai mic decât 46.
== include(page="template/taskfooter" task_id="voodoo") ==
