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 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 , -109 ≤ V i ≤ 109. 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);
Date de intrare
Fişierul de intrare partition.in ...
Date de ieşire
În fişierul de ieşire partition.out ...
Restricţii
- ... ≤ ... ≤ ...
Exemplu
| partition.in | partition.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
