хэлпаните нет идей
прошерстить список разок, найти кол-во людей с ростом равным одному из чисел в m, запомнить их позиции.
Потом зная длину списка и координаты челиков с равным ростом можно проверить какая позиция будет максимизировать произведение. Тут вроде можно аналитически формулу даже проверить
Если для каждого х из m находить это разве не O(n*m)?
Да, если держать memory \in O(k), где k количество людей с тем же ростом. А можно за один проход находить позиции всех m-ов, но memory \in O(km) что на практике должно быть \in O(m)
Назовем изначальный массив - a.
Для решения за O(n) нам понадобятся 3 массива. pref, suf, ans. В pref и suf мы будем хранить количество людей с ростом i на префиксе/суффиксе. В массиве ans будет находиться ответ для i-того роста.
Изначально все значения в массиве pref[i] = 0, suf[i] = количество людей с ростом i
Будем проходить по массиву a(i = 1 ... n) и для каждого a[i] выполнять следующие действия:
pref[a[i]]++, suf[a[i]]--;. Встретив рост a[i], мы на префиксе увеличиваем количество людей с ростом a[i], а в массиве suf понижаем.
После чего, мы будем “нынешний” ответ, сравнивать с другими ответами, хранимые в массиве ans.
int cur = pref[a[i]] * (n - i - suf[a[i]]);
ans[a[i]] = max(ans[a[i]], cur);
“нынешний” ответ - это просто количество на префиксе людей с тем же ростом(pref[a[i]]) умноженное на количество людей(n - i), которое отнимаем от количество людей с ростом a[i] на суффиксе(suf[a[i]])
P.S. вероятнее всего код имеет ошибки, надеюсь ты понял мое решение и сможешь его реализовать 
2 лайка
э, а разве тут не надо знать максимальный рост, чтобы инициализировать этот массив?
Ну, изначально пройдемся по массиву a и будем делать так:
for(int i = 1; i <= n; i++){
suf[a[i]]++;
}
Возможно вы неправильно поняли задачу
я может не совсем понимаю как работают массивы в С. Это же dynamic array? Если да, то нам же нужно знать его размеры, чтобы инициализировать пустой массив нужных размеров?
Вот допустим в начале pref = пустой массив. Каким образом C отреагирует на запрос “сделай позицию 205 равной 1”?
Сделаем массивы pref и suf глобальными. Это означает, что pref и suf будут за какими-либо функциями. У таких массивов обязательно должно быть константное значение, а так как тут значения a[i] <= 1e5, то соответственно сделаем размер этих массивов равным 1е5(и навсякий следует прибавить небольшое число, дабы избежать выхода за границы массива). Также одним из свойств глобальных массивов - они автоматический заполняются нулями.
а точно)
Да ну, шайтанисто как-то такие пустые массивы инициализировать))))
P.S. Это кстати \in O(10^5) занимает по времени.
Это норм
Ну, если тестировать на n \in \Omega(10^5), то да, а так нет))
хотя может Си настолько шустро инициирует массивы, что на практике разницы не заметить.
Зачем создавать костыль, когда С++ дает готовый велосипед)
А вообще это полезно, на олимпиаде можно не париться на счет того, что массив без каких-либо значений, а то произойдет какая-либо операция с пустым значением и тогда наступит настоящее шайтанство)
Если значения были бы <= 1e9, то мы бы просто заменили массивы на структуру данных map, работающую за log n. Решение бы перешло из O(n) к O(n log n).