| Fişierul intrare/ieşire: | tabara2.in, tabara2.out | Sursă | .com 2009, Runda 1 |
| Autor | Radu Zernoveanu | Adăugată de |  Radu Zernoveanu •raduzer |
| Timp execuţie pe test | 0.075 sec | Limită de memorie | 80192 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Tabara2
Alexandra isi petrece vacanta de vara intr-o tabara, in care participantii au fost impartiti in echipe, iar ea a fost aleasa lider al uneia dintre ele. Echipele trec prin diferite probe in urma carora acumuleaza puncte, echipa cu cele mai multe puncte castigand trofeul taberei.
Pentru prima proba, fiecare echipa a primit o harta a taberei pe care sunt marcate N locatii, numerotate de la 1 la N si o lista de sarcini numerotate de la 1 la S, fiecare sarcina valorand un anumit numar de puncte. Sarcinile vor fi realizate tinand cont de instructiunile primite de la organizatori pe tot parcursul probei. Instructiunile sunt de 2 tipuri:
1) Realizarea sarcinii i permite realizarea sarcinii j si invers (realizarea sarcinii j permite realizarea sarcinii i).
2) La locatia i poate fi realizata sarcina j (dupa care pot fi realizate sarcinile permise de instructiunea 1).
Cerinta
Ajutati-o pe Alexandra ca pentru locatiile i si j date sa realizeze sarcina cu punctaj maxim pe care o poate indeplini plecand din orice locatie din intervalul [i, j].
Date de intrare
Pe prima linie a fisierului de intrare tabara.in se gasesc 3 numere N, S si M reprezentand numarul de locatii, numarul de sarcini si, respectiv, numarul de instructiuni si cerinte. Pe a doua linie se afla S numere semnificand punctajul sarcinilor in ordine, de la 1 la S. Pe urmatoarele M linii vor fi date instructiunile si cerintele. O linie va fi de forma:
1) U 1 i j -> Realizarea sarcinii i permite realizarea sarcinii j si invers (realizarea sarcinii j permite realizarea sarcinii i).
2) U 2 i j -> La locatia i poate fi realizata sarcina j (dupa care pot fi realizate sarcinile permise de instructiunea 1).
3) Q i j -> Sa se afiseze in fiesierul de iesire sarcina cu punctaj maxim pe care o poate realiza dintr-o locatie k, i ≤ k ≤ j.
Date de ieşire
In fisierul de iesire tabara.out, pentru fiecare cerinta 'Q' se va afisa numarul cerut pe cate o linie.
Restricţii si precizari
- 1 ≤ N, S, M ≤ 50 000
- Pentru 30% din teste 1 ≤ N, S, M ≤ 1 000
- Atentie! Se garanteaza ca o sarcina poate fi indeplinita numai dintr-o locatie (direct sau indirect).
- Punctajul unei sarcini este ≤ 1 000 000 000.
Exemplu
| tabara2.in | tabara2.out |
|---|---|
| 2 4 6 3 2 4 1 U 1 2 4 U 2 1 1 U 2 2 2 Q 1 2 U 1 3 4 Q 1 2 | 3 4 |
