Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | sandwich.in, sandwich.out | Sursă | Junior Challenge 2025 |
| Autor | Muresan Luca Valentin | Adăugată de |  Vlad Tutunaru •vlad2009 |
| Timp execuţie pe test | 0.7 sec | Limită de memorie | 262144 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
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” ai. 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 al al+1 ... ar, Jake poate alege un subşir de poziţii strict crescător (eventual gol) astfel încât nu există două poziţii adiacente alese. Suma gustului acelui subşir este: ai1 + ai2 + ... + aik, cu l ≤ i1 < i1 < ... < ik ≤ r şi ij + 1 < ij+1
Definim ![f(a[l..r])](http://www.infoarena.ro/static/images/latex/0a8fdf965192cca6fac3a38efd64aaa7_3.5pt.gif "f(a[l..r])")
= suma 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 segmentele posibile ale potecii. Cu alte cuvinte, calculaţi:
![S = \sum_{1 \leq l \leq r \leq n} f(a[l..r])](http://www.infoarena.ro/static/images/latex/c46cd91ebe71755ba75989923ca3113d_5.29832pt.gif "S = \sum_{1 \leq l \leq r \leq n} f(a[l..r])")
Date de intrare
Fişierul de intrare sandwich.in ...
Date de ieşire
În fişierul de ieşire sandwich.out ...
Restricţii
- ... ≤ ... ≤ ...
Exemplu
| sandwich.in | sandwich.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
