Problema A - Regar as plantas

Se é a primeira vez que participas, consulta a página de instruções para informações detalhadas sobre o formato deste problema.

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.

Parte I

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.

Exemplo

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:

Restrições:

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
-

Parte II

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.

Exemplo

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:

Restrições:

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
-

Sumário de subtarefas

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
-

Input

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).

Parte I

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.

Parte II

Nesta parte adicionalmente segue-se uma linha contendo N inteiros separados por espaços, representando as alturas Ai das flores

Output

Parte I

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).

Parte II

O output deve conter uma única linha com um inteiro, representando a maior soma de alturas.

Input do Exemplo 1

1
4 3
3 4 3 1
1 1 2 3

Output do Exemplo 1

6 7 9 10

Explicação do Exemplo 1

Este exemplo corresponde ao exemplo da Parte I mencionado no enunciado.

Input do Exemplo 2

2
10 2
1 2 1 3 1 1 4 2 2 1

Output do Exemplo 2

13

Explicação do Exemplo 2

Este exemplo corresponde ao exemplo da Parte II mencionado no enunciado.


Qualificação para a final das ONI'2021
(30/04 a 02/05 de 2021)