Максимальное произведение показаний
По каналу связи передаётся последовательность натуральных чисел — показания прибора. В течение $N$ минут прибор ежеминутно регистрирует значение напряжения в электрической сети и передаёт его на сервер. Определите три таких переданных числа, чтобы между моментами передачи любых двух из них прошло не менее $K$ минут, а произведение этих трёх чисел было максимально возможным. Даны два входных файла: файл $A$ и файл $B$. В первой строке каждого файла содержится натуральное число $K$, во второй — количество переданных показаний $N$ ($1 \leq N \leq 10\,000\,000$, $N>K$). В следующих $N$ строках записаны натуральные числа, не превышающие $10\,000\,000$. Запишите сначала значение искомой величины для файла $A$, затем для файла $B$. Для обработки файла $B$ нельзя использовать перебор всех возможных троек.
Условие как в банке ФИПИ — открыть и сверить
| ||||||
| | ||||||
Формат: өлшем бірліктері жоқ сан немесе сөз; бөлшек бөлігін үтірмен бөліңіз.
1Мягкая — с чего смотретьдеңгей 1 из 3
Как организовать выбор трёх элементов, если между соседними выбранными позициями должно быть не менее $K$ минут?
2Жетекші — қандай сандарды есептеудеңгей 2 из 3
Для каждого текущего показания храните лучшие произведения для выбора одного, двух и трёх элементов, а также учитывайте максимум среди уже доступных позиций.
3Тікелей — іс жүзінде шешімдеңгей 3 из 3
При обработке позиции $i$ обновляйте состояния через позицию $i-K$: $dp_1[i]=\max(dp_1[i-1],a_i)$, $dp_2[i]=\max(dp_2[i-1],dp_1[i-K]\cdot a_i)$, $dp_3[i]=\max(dp_3[i-1],dp_2[i-K]\cdot a_i)$. В ответе берите итоговое значение $dp_3[N]$.