Revizia anterioară Revizia următoare
| 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 sir de Q numere intregi. O subsecventa [X, Y] a sirului S , 0 ≤ X ≤ Y ≤ Q-1 , se defineste ca o secventa de elemente consecutive SX, SX+1,....,SY. Costul unei subsecvente se defineste ca fiind valoarea minima a unui element din aceasta. O partitie a sirului S se defineste ca o impartire a lui S in subsecvente astfel incat fiecare element al sirului apartine exact unei subsecvente. Daca partitia este formata din k subsecvente, scorul acesteia scorul acesteie 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! Desi valorile elementelor sirului V nu sunt generate aleator, ordinea acestora în sir este aleatoare.
Date de intrare
*linia 1: N M, reprezentand lungimea sirului V, respectiv numarul de intrebari
*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
| Intrare | Iesire |
|---|---|
| 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).
