| Fişierul intrare/ieşire: | partition.in, partition.out | Sursă | Lot Seniori Dorohoi 2019 - Baraj 2 |
| Autor | Andrei Constantinescu, Costin Oncescu | Adăugată de |  brebenel mihnea stefan •tryharderul |
| Timp execuţie pe test | 0.4 sec | Limită de memorie | 16384 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Partition
Error 404: Poveste not found
Fie S un şir de Q numere întregi. O subsecvenţa [X, Y] a şirului S , 0 ≤ X ≤ Y ≤ Q-1 , se defineşte ca o secvenţă de elemente consecutive SX, SX+1,....,SY. Costul unei subsecvenţe se defineşte ca fiind valoarea minimă a unui element din aceasta. O partitie a şirului S se defineste ca o împarţire a lui S in subsecvenţe astfel încât fiecare element al şirului aparţine exact unei subsecvente. Daca partitia este formată din k subsecvente, scorul acesteia se defineste ca fiind suma costurilor celor k subsecvente.
Se da un sir V de N (1 ≤ N ≤ 200 000) numere intregi , -109 ≤ Vi ≤ 109. Se cere să se răspundă, pentru M întrebări de forma Xi , Yi , care este maximul dintre scorurile tuturor partitiilor subsecventei [Xi, Y i]
Important! Deşi valorile elementelor şirului V nu sunt generate aleator, ordinea acestora în sir este aleatoare.
Date de intrare
- linia 1: N M, reprezentând lungimea sirului V, respectiv numarul de intrebări
- linia 2: V0 V1 ... VN-1, cele N elemente ale sirului V.
- linia 3 + i (0 ≤ i ≤ M-1): Xi Yi reprezentand cele M intrebari.
Punctare
| Subtask | Punctaj | Constrangeri |
|---|---|---|
| 1 | 6 puncte | 1 ≤ N ≤ 50 , 1 ≤ M ≤ 50 |
| 2 | 7 puncte | 1 ≤ N ≤ 400 , 1 ≤ M ≤ 16000 |
| 3 | 38 puncte | 1 ≤ N ≤ 2000 , 1 ≤ M ≤ 200 000 |
| 4 | 49 puncte | 1 ≤ N ≤ 200 000 , 1 ≤ M ≤ 200 000 |
Exemplu
| Ppartition.in | partition.out |
|---|---|
| 7 3 3 -2 5 -2 -4 1 -2 0 6 2 4 4 6 | 2 1 -4 |
Explicaţie
Pentru primul exemplu, avem un sir format din N = 7 elemente si M = 3 întrebări.
O partitie optimă a subsecventei [0, 6] este următoarea: (3),(−2),(5),(−2, −4, 1, −2), iar scorul acesteia este 2, dat de suma costurilor subsecventelor (elementele afisate îngrosat).
O partitie optimă a subsecventei [2, 4] este următoarea: (5),(−2, −4), iar scorul acesteia este 1, dat de suma costurilor subsecventelor (elementele afisate îngrosat).
O partitie optimă a subsecventei [4, 6] este următoarea: (−4, 1, −2), iar scorul acesteia este −4, dat de suma costurilor subsecventelor (elementele afisate îngrosat).
