Задачу можно решать последовательными улучшениями.

\(O(n^3)\) — 20 баллов

Переберем все тройки натуральных чисел \(a,b,c\le n\). Рассмотрим прямоугольный параллелепипед со сторонами \((a,b,c)\). Площадь поверхности этого параллелепипеда есть \(2ab+2ac+2bc=S\). Среди всех таких, что \(S\le n\), найдём тот, объём которого максимален.

\(O(n^2)\) — 30 баллов

Зафиксируем две стороны \(a\) и \(b\). Зададимся вопросом, какой может быть третья сторона. Из неравенства \(2ab+2ac+2bc\le n\) получаем, что \(c\le\frac{n-2ab}{2a+2b}\). Таким образом, достаточно рассмотреть только \(c=\left\lfloor\frac{n-2ab}{2a+2b}\right\rfloor\). Перебирая все пары \(a,b\le n\), получаем решение за \(O(n^2)\).

\(O(n\log n)\) — 60 баллов

Для того, чтобы ещё сильнее ускорить решение, заметим, что имеет смысл перебирать только такие стороны \(a\) и \(b\), что \(ab\le n\). Количество таких пар есть \(\)\sum^n_{a=1}\frac na=n\sum^n_{a=1}\frac1a=O(n\log n).\(\) Аналогичная идея применяется при оценке времени работы алгоритма Эратосфена.

\(O(n)\) — 70 баллов

Описанное выше рассуждение можно ещё улучшить. Предположим, что \(a\le b\le c\) — стороны параллелепипеда. Тогда \(a,b\le\sqrt{n/2}\). Действительно, если предположить обратное, то \(b,c>\sqrt{n/2}\Rightarrow2bc>n\). Исходя из этого наблюдения, достаточно перебрать \(O(n)\) пар значений \((a,b)\).

\(O(\sqrt n)\) — 100 баллов

Основная идея решения заключается в исследовании границ, в которых лежит оптимальный ответ. Кратко опишем ключевые моменты:

Cреди всех прямоугольных параллелепипедов с натуральными длинами сторон и площадью поверхности не более \(n\) найти тот, объём которого максимален.