Diferențe pentru problema/voodoo între reviziile #19 si #30

== 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~]$.

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 încât $1$ ≤ $i$ ≤ $X$ și $Y$ ≤ $j$ ≤ [$N$]. Costul poate fi calculat astfel:
!problema/voodoo?pseudocod2!

h2. Restricții
* $1$ ≤ $X$ < $Y$ ≤ $N$ ≤ $1.000.000$

* $0$ ≤ $a[~i~]$ ≤ $1.000.000$, pentru fiecare $i$ de la $1$ la $N$

* $0$ ≤ [$a$][~i~] ≤ $100.000$, pentru fiecare $i$ de la $1$ la $N$

* se garantează că răspunsul se incadrează pe tipul de date $long long$
* printr-un rearanjament al unui șir întelegem o reordonare a termenilor acestuia
* se acordă $50%$ din punctaj pentru afișarea costului minim corect

* pentru $30%$ din punctaj, se garantează că $N$ ≤ $1.000$
* pentru $60%$ din punctaj, se garantează că $N$ ≤ $10.000$
* *ATENȚIE!* Din cauza dimensiunii mari a datelor de intrare si de ieșire, se recomandă parsarea intrării și a ieșirii. Vă oferim o implementare suficientă pentru rezolvarea acestei probleme "aici":TODO.

* pentru $40%$ din punctaj, se garantează că $N$ ≤ $10.000$
* pentru $60%$ din punctaj, se garantează că $N$ ≤ $100.000$
* **ATENȚIE!** Din cauza dimensiunii mari a datelor de intrare si de ieșire, se recomandă parsarea intrării și a ieșirii. Vă oferim o implementare suficientă pentru rezolvarea acestei probleme "aici":parsare_io_c .

h2. Exemplu

table(example).

table(example).

|_. voodoo.in |_. voodoo.out |
|5 1 2
1 2 3 4 5
|34

1 2 3 5 2

2 1 3 4 5

|
|5 2 4
1 3 3 4 5
|46

5 1 4 3 3

5 3 1 3 4

|

| 8 2 6
1 2 6 2 10 9 3 5
|149
1 10 2 9 2 6 5 3

| 10 2 6
1 2 8 6 2 10 9 3 5 8
|322
8 2 3 5 1 2 6 8 9 10

|
h3. Explicație

$3 + 6 + 10 + 15 = 34$
Nu există nicio altă rearanjare cu cost mai mic.

Pentru al doilea exemplu, rearanjarea este $5 3 1 3 4$, costul acestei rearanjari este:

Pentru al doilea exemplu, rearanjarea este $5 3 1 3 4$, costul acestei rearanjări 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.
 
 

Din nou, nu există alte rearanjări ale șirului $a$ care au costul mai mic de 46.

== include(page="template/taskfooter" task_id="voodoo") ==