XXVI Olimpíada Brasileira de Informática
Submeta sua solução

Nome do arquivo: etiquetas.x, onde x deve ser c, cpp, java, js ou py

Etiquetas

Uma fita esticada horizontalmente é composta de N quadrados de dimensão 1 x 1, cada um deles contendo um número inteiro anotado. Temos também K etiquetas retangulares idênticas, de dimensão 1 x C, onde C é um inteiro. Nosso objetivo é colar todas as etiquetas sobre a fita de modo que a soma dos inteiros que não estiverem cobertos por nenhuma etiqueta ao final seja a máxima possível. Cada etiqueta deve ser colada na horizontal, ao longo da fita. Duas etiquetas não podem estar sobrepostas e cada quadrado da fita deve estar ou totalmente coberto por uma etiqueta, ou totalmente descoberto.

Entrada

A primeira linha da entrada contém três inteiros N, K e C, representando, respectivamente, o comprimento da fita, o número de etiquetas e o comprimento das etiquetas. A segunda linha da entrada contém N inteiros A indicando a sequência de números anotados nos quadrados da fita.

Saída

Seu programa deve imprimir uma linha contendo um inteiro indicando a soma máxima possível de inteiros descobertos na fita depois que todas as etiquetas sejam coladas seguindo as condições do enunciado.

Restrições

  • 1 ≤ N ≤ 10000
  • -10000 ≤ A ≤ 10000
  • 1 ≤ K ≤ 10000
  • 1 ≤ C ≤ 10000
  • K\times C ≤ N

Informações sobre a pontuação

  • Para um conjunto de casos de testes valendo 10 pontos, os números no vetor estão ordenados crescentemente.
  • Para um conjunto de casos de testes valendo outros 10 pontos, C=1.
  • Para um conjunto de casos de testes valendo outros 20 pontos, K=1.
  • Para um conjunto de casos de testes valendo outros 20 pontos, K,N ≤ 100.

Exemplos

Entrada
12 2 3
1 22 4 -8 9 2 10 -1 5 5 32 -11
Saída
58
	

 

Entrada
1 1 1
10000
Saída
0
	

 

Tarefas Programação Nível 2
Promoção
logo sbc
Patrocínio
Apoio
Coordenação