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

Î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~}$. Magia sandwichului are o regulă ciudată: nu are voie să aleagă două ingrediente alăturate, altfel magia se risipeşte.

Î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.

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

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

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:

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