Um jardim tem N flores, dispostas numa linha comprida. Cada flor tem uma certa altura em centímetros que é um inteiro positivo. A altura da i-ésima flor é representada pelo valor Ai.
Todas as flores são regadas uma vez por dia, mas a sua taxa de crescimento varia. A i-ésima flor cresce Bi centímetros por dia, ou seja, após um dia a sua altura passa a ser Ai + Bi, após dois dias passa a ser Ai + 2Bi, etc.
Queremos saber como estará o jardim ao fim de alguns dias. Determina as alturas de cada flor ao fim de K dias.
Se N = 4, K = 3 e tivermos as seguintes alturas:
E as seguintes taxas de crescimento:
Ao fim de 3 dias as alturas serão as seguintes:
A seguinte figura ilustra este caso:
São garantidos os seguintes limites em todos os casos de teste desta parte que irão ser colocados ao programa:
1 ≤ N ≤ 200 | Número de flores | |
1 ≤ K ≤ 1 000 | Número de dias | |
1 ≤ Ai, Bi ≤ 106 | Alturas/Taxas de crescimento |
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 | 50 |
Queremos agora tirar algumas fotografias para ilustrar o quão bonito o jardim se tornou. Vamos tirar exatamente 3 fotografias. Cada fotografia pode apanhar um conjunto de até K flores consecutivas e as fotografias não se podem intersetar, ou seja, cada flor pode aparecer numa fotografia no máximo.
Para enaltecer o jardim, queremos tirar as 3 fotografias que maximizam a soma das alturas das flores que capturam. Determina este valor.
Se N = 10, K = 2 e tivermos as seguintes alturas:
Podemos tirar as fotografias que apanham os seguintes intervalos: [1, 2] (de alturas 1 e 2, ou seja, 3 no total), [4, 5] (de alturas 3 e 1, ou seja, 4 no total) e finalmente [7, 8] (de alturas 4 e 2, ou seja, 6 no total). A altura total das 3 fotografias é 13 e este é o melhor que conseguimos fazer, logo é a resposta.
A seguinte figura ilustra este caso:
São garantidos os seguintes limites em todos os casos de teste desta parte que irão ser colocados ao programa:
1 ≤ K ≤ N ≤ 200 | Número de flores / Comprimento máximo de uma fotografia | |
1 ≤ Ai ≤ 106 | Alturas das flores |
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 |
---|---|---|
2 | 50 |
Os casos de teste do problema estão organizados em 2 grupos com restrições adicionais diferentes:
Grupo | Número de Pontos | Parte | Restrições adicionais |
---|---|---|---|
1 | 50 | Parte I | |
2 | 50 | Parte II |
Nota: O formato de input é diferentes nas duas 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.
Segue-se uma linha com dois inteiros separados por espaços, primeiro N, representando o número de flores, seguido de K, o número de dias (na Parte I) ou o comprimento máximo de uma fotografia (na Parte II).
Nesta parte adicionalmente seguem-se duas linhas, cada uma contendo N inteiros separados por espaços. A primeira contém as alturas Ai das flores. A segunda contém as taxas de crescimento Bi das flores.
Nesta parte adicionalmente segue-se uma linha contendo N inteiros separados por espaços, representando as alturas Ai das flores
O output deve conter uma única linha com N inteiros separados por espaços, representando as alturas finais das flores.
Nota: deve existir exatamente um único espaço entre cada inteiro e não deve haver nenhum espaço no final da linha (ou seja, após o último inteiro deve aparecer apenas uma mudança de linha). Se não respeitares este formato o resultado de uma submissão será Presentation Error (consulta as instruções para mais informações).
O output deve conter uma única linha com um inteiro, representando a maior soma de alturas.
1 4 3 3 4 3 1 1 1 2 3
6 7 9 10
Este exemplo corresponde ao exemplo da Parte I mencionado no enunciado.
2 10 2 1 2 1 3 1 1 4 2 2 1
13
Este exemplo corresponde ao exemplo da Parte II mencionado no enunciado.