Informática - Nível Avançado - Semana 5

Bolinhos de Queijo

Laurêncio adora bolinhos de queijo. Ele possui n bolinhos de queijo em um prato, cada um com um valor a_i. Antes de comê-los, deseja juntá-los até que virem um bolinho só. Para juntar bolinhos de queijo, Laurêncio pode realizar a seguinte operação:

  • Escolher dois bolinhos de queijo consecutivos e juntá-los, formando um novo bolinho de queijo que ocupa a posição dos dois bolinhos anteriores. O novo bolinho possuirá valor x+y, onde x e y são os valores dos bolinhos originais. Além disso, a operação possui custo de x+y.

Laurêncio deseja descobrir o menor custo possível para juntar os n bolinhos em só. Ajude-o nesta missão!

Entrada

A primeira linha consiste de um inteiro n.
A segunda linha de entrada possui os valores a_i (1 \leq i \leq n) dos bolinhos.

Saída

Imprima apenas um inteiro: A menor soma de custos de operações para juntar todos os bolinhos em um só.

Restrições

  • 1 \leq N \leq 400
  • 1 \leq a_i \leq 10^9

Exemplos:

ENTRADA

SAÍDA

 
4
10 20 30 40
 
190

Explicação do caso: Laurêncio pode juntar os bolinhos da seguinte forma:

(10 20 30 40) \implies (30 30 40)
(30 30 40) \implies (60 40)
(60 40) \implies (100)

Para submeter sua solução use esse link.