A Rua das Flores é uma rua muito longa (tem N metros de comprimento!) e que há muito tempo está em terríveis condições. No entanto, e felizmente para os condutores que percorrem essa rua frequentemente, o presidente da freguesia prometeu fazer obras nessa rua para ela deixar de ser um problema no quotidiano dos seus transeuntes.
A rua pode ser vista como uma sequência S de N inteiros positivos, onde o i-ésimo, Si, corresponde ao custo de arranjar o i-ésimo metro da rua. Fazer obras em toda a rua pode exceder o orçamento da junta de freguesia, por isso estão a ser estudadas 3 opções distintas para a obra.
Uma das formas de cumprir o plano eleitoral é fazer obras de recuperação num segmento contíguo de S de comprimento exatamente K metros. Recordem que um segmento contíguo é um intervalo de elementos seguidos, por exemplo para a sequência [1, 2, 2, 3] a subsequência [1, 2, 2] é uma subsequência contígua (que contém os primeiros três elementos) mas [1, 2, 3] já não (contém o primeiro, segundo e quarto elementos). Entre todos os segmentos contíguos com K metros de comprimento, pretende-se descobrir aquele que tem o custo total mínimo de recuperação.
Vamos supor que N = 5 e S = [1, 6, 2, 2, 3], ou seja, o custo de arranjo do primeiro metro da rua é 1, do segundo é 6, etc.
Para este caso, se K = 1, então podemos reparar apenas o primeiro metro da rua (que tem custo 1), o que tem um custo total de 1.
Se K = 2, então podemos reparar o segmento composto pelo terceiro (2) e quarto (2) metros, o que tem um custo total de 4.
Se K = 3, então podemos reparar o segmento composto pelo terceiro (2), quarto (2) e quinto (3) metros, o que tem um custo total de 7.
São garantidos os seguintes limites em todos os casos de teste desta parte que irão ser colocados ao programa:
| 1 ≤ N ≤ 105 | Comprimento da rua | |
| 1 ≤ K ≤ N | Número de segmentos a considerar | |
| 1 ≤ Si ≤ 109 | Custo de um metro de rua |
Nota que a resposta pode ir até 2^62.
Os casos de teste desta parte do problema estão organizados num grupo com restrições adicionais diferentes:
| Grupo | Número de Pontos | Restrições adicionais |
|---|---|---|
| 1 | 25 |
A segunda alternativa considerada é de recuperar o segmento contíguo que, entre todos os segmentos contíguos, tem o K-ésimo menor custo. Como tal, pretende-se descobrir o custo de realizar uma obra segundo esse critério.
Vamos supor que N = 5 e S = [1, 6, 2, 2, 3]. Então, se ordenarmos as possíveis subsequências contíguas pela sua soma obtemos o seguinte:
Assim, se K = 1, então a resposta seria 1. Se K = 2, então a resposta seria 2. Para K = 3, seria 2 novamente. Para K = 4, seria 3. K = 5, seria 4 e para K = 6 seria 5.
São garantidos os seguintes limites em todos os casos de teste desta parte que irão ser colocados ao programa:
| 1 ≤ N ≤ 105 | Comprimento da rua | |
| 1 ≤ K ≤ N (N + 1) / 2 | Soma objetivo | |
| 1 ≤ Si ≤ 109 | Custo de um metro de rua |
Nota que N (N + 1) / 2 corresponde ao número total de subsequências contíguas.
Nota que a resposta pode ir até 2^62.
Os casos de teste desta parte do problema estão organizados em 2 grupos com restrições adicionais diferentes:
| Grupo | Número de Pontos | Restrições adicionais |
|---|---|---|
| 2 | 25 | N ≤ 1 000 |
| 3 | 25 |
A última alternativa correspondia a recuperar o segmento contíguo que, entre todos os segmentos contíguos, apresenta o K-ésimo menor custo por metro (arredondado para baixo, às unidades). Assim sendo, pretende-se descobrir esse mesmo custo por metro (na mesma arredondado para baixo, às unidades).
Vamos supor que N = 5 e S = [1, 6, 2, 2, 3]. Então, se ordenarmos as possíveis subsequências contíguas pelo seu custo por metro (arredondado para baixo) obtemos o seguinte:
Assim, se K = 1, então a resposta seria 1. Já se K estiver entre 2 e 8, então a resposta seria 2. Para K = 9, a resposta seria 3, ...
São garantidos os seguintes limites em todos os casos de teste desta parte que irão ser colocados ao programa:
| 1 ≤ N ≤ 105 | Comprimento da rua | |
| 1 ≤ K ≤ N (N + 1) / 2 | Custo por metro objetivo | |
| 1 ≤ Si ≤ 109 | Custo de um metro de rua |
Nota que N (N + 1) / 2 corresponde ao número total de subsequência contíguas.
Nota que a resposta pode ir até 2^62.
Os casos de teste desta parte do problema estão organizados num grupo com restrições adicionais diferentes:
| Grupo | Número de Pontos | Restrições adicionais |
|---|---|---|
| 4 | 25 |
Os casos de teste desta do problema estão organizados em 4 grupos com restrições adicionais diferentes:
| Grupo | Número de Pontos | Parte | Restrições adicionais |
|---|---|---|---|
| 1 | 25 | Parte I | |
| 2 | 25 | Parte II | N ≤ 1 000 |
| 3 | 25 | Parte II | |
| 4 | 25 | Parte III |
Nota: O formato de input é igual para todas as partes.
A primeira linha contém um inteiro P, que representa a parte que o caso de teste representa. Se for 1, então o caso de teste refere-se à Parte I, se for 2 então refere-se à Parte II, se for 3 então refere-se à Parte III.
Segue-se uma linha com os inteiros N e K, separados por espaços.
Segue-se uma linha com N inteiros, separados por espaços, onde o i-ésimo representa o valor de Si.
O output deve conter apenas uma linha, contendo um inteiro que representa:
1 5 1 1 6 2 2 3
1
1 5 3 1 6 2 2 3
7
2 5 5 1 6 2 2 3
4
3 5 9 1 6 2 2 3
3