eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Оптимальне бінарне дерево пошуку

Оптимальне бінарне дерево пошуку

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

Розглянемо множину S = \{e_1, e_2, ..., e_n\}, яка містить n різних елементів таких що e_1 < e_2 < ... < e_n. Розглянемо бінарне дерево пошуку, що складається з елементів S. Чим частіше відбувається запит до елементу, тим ближче він має розташовуватися до кореня.

Вартістю cost доступу до елементу e_i з S у дереві будемо називати значення cost(e_i), яке дорівнює кількості ребер на шляху, що сполучає корінь з вершиною, яка містить елемент. Маючи частоту запитів до елементів із S, (f(e_1), f(e_2), ..., f(e_n)), визначимо загальну вартість дерева наступним чином:

f(e_1) \cdot cost(e_1) + f(e_2) \cdot cost(e_2) + ... + f(e_n) \cdot cost(e_n)

Дерево, яке має найменшу вартість, вважається найкращим для пошуку елементів із S. Тому воно називається Оптимальним Бінарним Деревом Пошуку.

Вхідні дані

Складається з декількох тестів, кожний з яких розташований в окремому рядку. Перше число в рядку n~(1 \le n \le 250) вказує на розмір множини S. Наступні n невід'ємних цілих чисел описують частоти запитів елементів з S: f(e_1), f(e_2), ..., f(e_n)~(0 \le f(e_i) \le 100).

Вихідні дані

Для кожного тесту в окремому рядку вивести вартість Оптимального Бінарного Дерева Пошуку.

Приклад

Вхідні дані #1
1 5
3 3 1 7
7 4 10 6 2 3 5 7
6 1 3 5 10 20 30
Вихідні дані #1
0
5
49
63