Контест Senior Стек и монотонный стек обновлено
Сумма минимумов всех подотрезков
Условие
Дан массив из n положительных чисел. Для каждого из n·(n+1)/2 непустых подотрезков возьмите минимум и сложите все эти минимумы.
Ввод: в первой строке n (1 ≤ n ≤ 2500), во второй n чисел (1 ≤ aᵢ ≤ 10⁴).
Вывод: сумма минимумов (точное значение, не превышает 4·10¹⁰).
Пример 1
Ввод:
4
3 1 2 4
Вывод:
17
Пример 2
Ввод:
3
2 2 2
Вывод:
12
Как подойти
Подсказки: 2
- Посчитайте вклад каждого элемента: в скольких подотрезках он минимум.
- Осторожно с равными: с одной стороны строгое сравнение, с другой нестрогое.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.