Тоже писал эту задачу. Поддерживал минимум на префиксе. Стресс-тест дома программа прошла, правда в бланке из-за того, что писал на Pascal, а не на C++ написал for i := 1 to n по привычке, а надо было условие i < n, то есть до n-1;
Итак, если мы находимся в элементе с номером i, то minpref - минимум на отрезке от 1 до i-6, который мы поддерживаем (в каждой итерации смотрим на элемент, который был 6 итераций назад и если a[i-6] < minpref то minpref = a[i-6]), и если a[i] * minpref < minout, то minout = a[i] * minpref. Как сделать это с памятью O(n) очевидно, у меня написан костыль, который работает с константной памятью(массив a), можно было использовать стандартную очередь, но за нее бы не поставили максимум баллов по критериям.
Время работы - O(n).
Кусок с считыванием от 0 до 5 можно запихать и в основной цикл, если предварительно всё заполнено +inf.
Если не понятно, то могу какие-то моменты разъяснить.
Собственно код:
#include <stdio.h>
#include <iostream>
using namespace std;
double a[6];
int main(void){
int i,n;
double minpref = 1000000, minout = 1000000, xcur, a[5];
cin >> n;
for (int i = 0; i <= 5; i++)
cin >> a[i];
for (int i = 6; i < n; i++){
cin >> xcur;
minpref = min(minpref, a[i % 6]);
a[i % 6] = xcur;
minout = min(minout, xcur * minpref);
}
cout << minout << "\n";
return 0;
}
Простой
