sandwich

Sandwich

== include(page="template/taskheader" task_id="sandwich") ==

În Tărâmul Ooo, Jake vrea să pregătească sandwichul magic perfect. Pe o potecă sunt aliniate $N$ ingrediente numerotate de la $1$ la $N$, iar ingredientul $i$ are o valoare de „gust” $a{~i~}$. Magia sandwichului are o regulă ciudată: nu are voie să aleagă două ingrediente alăturate, altfel magia se risipeşte.

!>problema/sandwich?sandwichulperfect.jpg!

Pentru orice segment continuu de ingrediente $a{~l~} a{~l+1~} ... a{~r~}$, Jake poate alege un subşir de poziţii strict crescător (eventual gol) astfel încât să nu existe două poziţii adiacente alese. Gustului total acelui subşir este: $a{~i{~1~}~} + a{~i{~2~}~} + ... + a{~i{~k~}~}$, cu $l ≤ i{~1~} < i{~1~} < ... < i{~k~} ≤ r$ şi $i{~j~} + 1 < i{~j+1~}$ pentru orice $1 ≤ j < k$.

În Tărâmul Ooo, Jake vrea să pregătească sandwichul magic perfect. Pe o masă sunt aliniate $N$ ingrediente numerotate de la $1$ la $N$, iar ingredientul $i$ are o valoare de „gust” $a{~i~}$.

Definim <tex> f(a[l..r]) </tex> = gustul total maxim posibil pentru un astfel de subşir (se permite subşirul gol).

Pentru orice subsecvenţă de ingrediente $a{~l~} a{~l+1~} ... a{~r~}$, Jake poate alege un subşir de poziţii strict crescător (eventual gol) astfel încât să nu existe două poziţii adiacente alese. Gustul total acelui subşir este: $a{~i{~1~}~} + a{~i{~2~}~} + ... + a{~i{~k~}~}$, cu $l ≤ i{~1~} < i{~2~} < ... < i{~k~} ≤ r$ şi $i{~j~} + 1 < i{~j+1~}$ pentru orice $1 ≤ j < k$.

Jake vrea să ştie câtă magie totală poate aduna, dacă ia în calcul toate subsecvenţele posibile ale potecii. Cu alte cuvinte, calculaţi:

Definim <tex> f(a[l..r]) </tex> = gustul total maxim posibil pentru un astfel de subşir.

<tex> S = \sum_{1 \leq l \leq r \leq n} f(a[l..r]) </tex>

Jake vrea să ştie suma celor mai gustoase sandwichuri pe care le poate face, dacă ia în calcul toate subsecvenţele posibile ale mesei. Cu alte cuvinte, calculaţi:

!documentatie/textile?sandwichulperfect.jpg!

<tex> S = \sum_{1 \leq l \leq r \leq n} f(a[l..r]) </tex>

h2. Date de intrare

h2. Restricţii
* $1 ≤ N ≤ 5 000 000$

* $1 ≤ a{~i~} ≤ 1 000 000 000$

* $1 ≤ x, y ≤ 1 000 000 000$
* $0 ≤ a{~1~} < z ≤ 1 000 000 000$

|_. #  |_. Punctaj |_. Restricţii |

| 1 | 3 | $N ≤ 15$ |
| 2 | 16 | $N ≤ 500$ |
| 3 | 15 | $N ≤ 2000$ |
| 5 | 10 | $N ≤ 200 000$ şi $a{~i~} ≤ 1$|

| 1 | 4 | $N ≤ 15$ |
| 2 | 11 | $N ≤ 500$ |
| 3 | 13 | $N ≤ 2000$ |
| 5 | 9 | $N ≤ 200 000$ şi $z = 2$|

| 5 | 41 | $N ≤ 200 000$ |

| 6 | 15 | $N ≤ 5 000 000$ |

| 6 | 22 | $N ≤ 5 000 000$ |

h2. Exemplu
table(example). |_. sandwich.in |_. sandwich.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 4 3 1 6 5
| 50

|
h3. Explicaţie

...

$a = [5, 4, 1, 4]$
 
$f(a[1..1]) = 5$
$f(a[1..2]) = 5$
$f(a[1..3]) = 6$
$f(a[1..4]) = 9$
$f(a[2..2]) = 4$
$f(a[2..3]) = 4$
$f(a[2..4]) = 8$
$f(a[3..3]) = 1$
$f(a[3..4]) = 4$
$f(a[4..4]) = 4$
 
$S = 50$

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