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 S _X, S _X+1,....,S _Y. 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 , -10⁹ ≤ V _i ≤ 10⁹. Se cere să se răspundă, pentru M întrebări de forma X _i , Y _i , care este maximul dintre scorurile tuturor partitiilor subsecventei [X _i , Y _i]

Important! Desi valorile elementelor sirului V nu sunt generate aleator, ordinea acestora în sir este aleatoare.

Detalii de implementare

Trebuie sa implementati urmatoarea functie :
std::vector<long long> find_partitions(std::vector<int> V, std::vector<int> X, std::vector<int> Y);

Punctare

Model de grader

Vi se pune la dispozit, ie un grader pentru a vă putea compila s, i testa codul local. Acesta va citi de la
consolă datele de intrare în următorul format:

• linia 1: N M , reprezentand lungimea sirului V ,respectiv numarul de intrebari
• linia 2: V ₀ V ₁ .... V _N-1 , cele N elemente ale sirului V
• linia 3: 3+i (0 ≤ i ≤ M-1): X _i Y _i reprezentand cele M intrebari

Exemplu

Explicaţie

...

Cum se trimit solutii?