28a Olimpíada Brasileira de Informática
Trio de Bonecas
Alice é a gerente de produção de uma fábrica de bonecas chinesas. Nessa fábrica, todas as bonecas possuem o mesmo formato, variando apenas de tamanho. As bonecas são vendidas sempre em trios.
- Configuração 1: trios (7, 8, 15) e (1, 5, 16).
- O primeiro trio possui balanceamento (8 - 7)^2 = 1.
- O segundo trio possui balanceamento (5 - 1)^2 = 16.
- O balanceamento total dessa configuração é 1 + 16 = 17.
- Configuração 2: trios (5, 7, 16) e (8, 11, 15).
- O primeiro trio possui balanceamento (7 - 5)^2 = 4.
- O segundo trio possui balanceamento (11 - 8)^2 = 9.
- O balanceamento total dessa configuração é 4 + 9 = 13.
Entrada
A primeira linha de entrada contém dois inteiros N e K, representando, respectivamente, o número de bonecas e a quantidade de trios solicitados pelo consulado Chinês. A segunda linha contém N números inteiros. O i-ésimo desses números será Ti, representando o tamanho da i-ésima boneca.Saída
Seu programa deverá imprimir uma única linha contendo um único inteiro, a menor soma de balanceamentos possível em uma caixa com K trios de bonecas.Restrições
- 3 ≤ N ≤ 10 000
- 1 ≤ K ≤ 3 000
- 3 K ≤ N
- 1 ≤ Ti ≤ 100 000 para todo 1 ≤ i ≤ N
Informações sobre a pontuação
A tarefa vale 100 pontos. Estes pontos estão distribuídos em subtarefas, cada uma com suas restrições adicionais às definidas acima:- Subtarefa 1 (13 pontos): 1 ≤ Ti ≤ 2 para todo 1 ≤ i ≤ N.
- Subtarefa 2 (28 pontos): N ≤ 30.
- Subtarefa 3 (33 pontos): N ≤ 1 000 e K ≤ 100.
- Subtarefa 4 (26 pontos): Nenhuma restrição adicional.
Exemplos
Entrada
7 2 11 1 7 5 16 8 15 |
Saída
13 |
Entrada
8 2 2 1 2 2 2 1 2 2 |
Saída
0 |