== include(page="template/taskheader" task_id="palsubsecv") ==
Poveste şi cerinţă...
Se da un sir de caractere $S$ de lungime $N$. Trebuie sa gasim subsirul palindromic al lui $S$ de lungime maxima, cu lungime para. De asemenea avem un buget de $B$ dolarei. Odata ce alegem o solutie, va trebui sa tinem cont de $R$ restrictii care ne vor scadea din buget.
O restrictie de forma $(a, b, c)$ inseamna ca daca este luata subsecventa dintre $a$ si $b$ in palindrom, trebuie sa platim $c$ dolarei. Asta inseamna ca, fiind alese *toate* pozitiile dintre $a$ si $b$ in palindromul solutie, trebuie sa platim $c$ dolarei.
Care este palindromul par de lungime maxima astfel incat la final sa ramanem cu un numar nenegativ de dolarei?
h2. Date de intrare
Fişierul de intrare $palsubsecv.in$ ...
Fişierul de intrare $palsubsecv.in$ va contine pe prima linie $T$, numarul de teste. Pe prima linie a fiecarui test se vor afla trei numere intregi $N$, $R$ si $B$, separate prin cate un spatiu. A doua linie va contine sirul $S$. Urmatoarele $R$ linii ale unui test vor contine fiecare cate trei numere intregi $a$, $b$ si $c$, separate prin cate un spatiu, cu semnificatia din enunt.
h2. Date de ieşire
În fişierul de ieşire $palsubsecv.out$ ...
În fişierul de ieşire $palsubsecv.out$ se vor afla $T$ linii, pe fiecare cate un numar natural care va reprezenta raspunsul la cerinta.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ T ≤ 20$
* $1 ≤ N ≤ 33$
* $1 ≤ R ≤ 5.000$
* $1 ≤ B ≤ 10^9^$
* $1 ≤ a ≤ b ≤ N$
* $1 ≤ c ≤ 10^5^$
* $S$ contine doar litere mici ale alfabetului englez
* $x$ e nenegativ daca $x ≥ 0$
* *Atentie!* Trebuie sa alegeti un subsir al sirului, nu o subsecventa! Doar costul este calculat in functie de subsecvente
* Va recomandam ca daca tineti in mana stanga dolarei, in mana dreapta sa aveti leii grei.
h2. Exemplu
table(example). |_. palsubsecv.in |_. palsubsecv.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
|2
5 2 9
acbba
1 2 10
4 5 11
4 2 5
xyyx
3 4 2
2 3 3
|2
4
|
h3. Explicaţie
...
In primul exemplu, ori luam subsirul $aa$ ori $bb$. Nu putem sa le luam pe ambele, deoarece ar trebui sa platim $11$ dolarei din cauza ca luam toate caracterele din intervalul $[4, 5]$.
In al doilea exemplu, luam intregul sir $S$ si platim $2 + 3 = 5$ dolarei.
== include(page="template/taskfooter" task_id="palsubsecv") ==
