URI Online Judge | 2837

Sequência

Por OBI-Olimpíada Brasileira de Informatica BR Brazil

Timelimit: 1

O professor da importante disciplina de Indução Matemática está tentando resolver uma versão generalizada de um problema muito tradicional: encontrar o valor máximo possível para a soma dos elementos de uma subsequência contígua de uma sequência de números inteiros quaisquer. Mais rigorosamente, dado uma sequência S = [s1, s2, . . . , sN ], onde si é um número inteiro qualquer, para 1 ≤ iN, maximizar soma(i, j) = si + si+1 + · · · + sj entre todos os possíveis pares (i, j), onde 1 ≤ i ≤ j ≤ N.

Na versão do professor, entretanto, alguns elementos da sequência são especiais e estão marcados. Além da sequência marcada, são dadas como entrada duas cotas: L e H, com LH. O objetivo agora é encontrar o valor máximo possível para a soma dos elementos de uma subsequência contígua, que contenha pelo menos L e no máximo H elementos marcados. 

Por definição, uma subsequência vazia (de zero elementos) tem soma igual a zero. Mas note que, como podemos ter uma cota inferior para o número de elementos marcados, a subsequência contígua de soma máxima pode ter soma negativa!

Entrada

A primeira linha da entrada contém três inteiros N (1 ≤ N ≤ 105), L e H (0 ≤ LH ≤ 20), indicando respectivamente o número de elementos na sequência, a cota inferior L e a cota superior H. A segunda linha contém N inteiros si (−103si ≤ 103 , para 1 ≤ i N), para 1 ≤ i N, definindo os elementos da sequência. A terceira linha contém N inteiros mi , para 1 ≤ iN, indicando as marcas. Se o i-ésimo elemento está marcado, o valor é mi = 1. Se não estiver marcado, mi = 0. O número de elementos  marcados na sequência é maior ou igual a L; portanto sempre existe solução.

Saída

Imprima um inteiro, representando o valor máximo possível para a soma dos elementos de uma subsequência contígua, que contenha pelo menos L e no máximo H elementos marcados.

Exemplos de Entrada Exemplos de Saída

14 3 4

9 0 -23 -12 7 1 -13 2 -1 9 -16 -1 14 12

1 0 0 1 0 1 0 0 1 1 0 0 1 1

19

14 7 20

9 0 -23 -12 7 1 -13 2 -1 9 -16 -1 14 12

1 0 0 1 0 1 0 0 1 1 0 0 1 1

-12

14 5 5

9 0 -23 -12 7 1 -13 2 -1 9 -16 -1 14 12

1 0 0 1 0 1 0 0 1 1 0 0 1 1

14

14 0 20

9 0 -23 -12 7 1 -13 2 -1 9 -16 -1 14 12

1 0 0 1 0 1 0 0 1 1 0 0 1 1

26