2973 - Maratona de Pipoca

  • ID: 2973
  • IdBecrowd: 2973
  • Tags: programacao-dinamica
  • Nível: 9
  • Tempo Limite: 1 segundos
  • Memória: 200 MB
  • Categoria: Paradigmas
  • Autor: Maratona de Programação 2019, SBC Brazil

Descrição

A Maratona Brasileira de Comedores de pipocas é uma competição que ocorre anualmente com o intuito de descobrir qual a equipe mais organizada, preparada e bem-treinada na arte de comer pipoca.

Ela é organizada pela SBCp (Sociedade Brasileira de Comedores de pipocas), que periodicamente se reúne para discutir as regras e o formato da competição.

A competição consiste em N sacos de pipocas colocados lado a lado, onde cada saco possui uma quantidade arbitrária de pipoca. Para proporcionar uma maior diversão, a competição ocorre em equipes, cada uma composta por C competidores. Como a Maratona Brasileira de Comedores de pipocas é um evento sério que preza, além de tudo, pela saúde dos competidores, a comissão médica impôs que cada competidor poderá comer, no máximo, T pipocas por segundo, a fim de evitar um possı́vel mal-estar.

A SBCp, em sua última reunião, definiu duas novas regras para a edição de 2019:

Cada competidor da equipe deverá comer uma sequência contı́gua de sacos de pipoca. É perfei- tamente válido que um competidor não coma nenhuma pipoca.

Todas as pipocas de um mesmo saco devem ser comidas por um único competidor.

O objetivo da competição é comer todas as pipocas no menor tempo possı́vel, dado que os C competidores podem comer em paralelo e eles respeitarão todas as regras impostas pela SBCp.

Entrada

A primeira linha contém três inteiros N , C e T (1 ≤ N ≤ 10 5 , 1 ≤ C ≤ 10 5 e 1 ≤ T ≤ 50), representando a quantidade de sacos de pipoca, a quantidade de competidores de uma mesma equipe e quantidade máxima de pipoca por segundo que um competidor pode comer. A segunda linha conterá N inteiros P i (1 ≤ P i ≤ 10 4 ), sendo estes a quantidade de pipoca em cada um dos N sacos.

Saída

Seu programa deve produzir uma única linha com um inteiro representando a quantidade mı́nima de segundos necessária para a equipe comer todas as pipocas se ela se organizar da melhor maneira possı́vel.

Exemplos

Exemplo de Entrada

5 3 4

                                5 8 3 10 7

Exemplo de Saída

4
Back to top