Revizia anterioară Revizia următoare
| Fișierul intrare/ieșire | voodoo.in, voodoo.out | Sursă | preONI 2023 6-7 |
|---|---|---|---|
| Autor | Luca Mureșan | Vlad Tutunaru | Adăugată de |
Muresan Luca
•
LucaLucaM
|
| Timp de execuție pe test | 0.1 sec | Limită de memorie | 65536 KB |
| Scorul tău | N/A | Dificultate |
   3.5
|
Poți vedea testele pentru această problemă accesând
atașamentele
.
Vezi soluțiile trimise | Statistici
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:
$ $
$ $
$ $
$ $
$ $
$ $
$ $
$ $
$ $
Aflați costul minim al unei rearanjări a șirului a cât și o rearanjare ce obține acest cost minim.
Date de intrare
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.
Date de ieșire
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.
Restricții
- 1 ≤ X < Y ≤ N ≤ 1.000.000
- 1 ≤ *a*~*i*~ ≤ 1.000.000, pentru fiecare i de la 1 la N
- Se garantează că răspunsul se incadreaza pe tipul de date long long
- 50% din punctaj se acordă pentru afișarea costului minim corect
- 30% din teste satisfac N ≤ 1.000
- 60% din teste satisfac N ≤ 10.000
Exemplu
| voodoo.in | voodoo.out |
|---|---|
| 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 |
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.
