Задача на цепочки ромашек, с++

Информатика
1

Цепочки ромашек
Лимит времени 1 секунда
Лимит использования памяти 128 MiB
Каждый день, прогуливаясь по ферме, корова Бесси посещает свое любимое пастбище, на котором растут
n цветков (все разноцветные ромашки), пронумерованные от 1 до
n и выстроенные в ряд. Цветок
i имеет
p^i лепестков.
Будучи начинающим фотографом, Бесси решила сделать несколько снимков этих цветков. В частности, для каждой пары цветков
(i,j), удовлетворяющих 1≤i≤j≤n, Бесси делает снимок всех цветков от i до j (включая i и j).
Позже Бесси смотрит на эти фотографии и замечает, что на некоторых из них присутствует “средний цветок” — цветок с
p лепестками, где p — среднее количество лепестков среди всех цветков на фотографии.
На скольких фотографиях Бесси присутствует средний цветок?
Входные данные
Первая строка содержит число n(1≤n≤100). Вторая строка содержит
n целых чисел p1,…,pn(1≤p^i≤1000).

Выходные данные
Выведите количество фотографий, на которых изображен средний цветок.

Пример
Входные данные #1
4
1 1 2 3
Выходные данные #1
6
Примечание
Каждая фотография, содержащая в точности один цветок, участвует в подсчете (в примере их четыре). Кроме того, отрезки
(1,2) и (2,4) соответствуют фотографиям, которые содержат средний цветок.

Вот условие задачи, я не имею даже представления как решить данную задачу,кто может - пожалуйста,помогите

1 лайк
2

Попробуй пробежаться по отрезкам, найти среднее на отрезке и если на отрезке есть число равное среднему то увеличиваем ответ на 1. Еще прибавляем кол-во цветков и должен получиться ответ. Может можно оптимизировать(наверняка можно), но я не знаю как.

3

А оптимизировать и не нужно, ограничения не кусаются n <= 100.
Так что можно смело писать ваше решение, его асимптотика O(n^3)

4 лайка