← Все вопросы
ЕГЭ 27: программа не укладывается в тайм-лимит на больших данных
7
Решение 27 задания работает на маленьком файле, но на большом — таймаут. Читаю файл и гоняю вложенные циклы. Как ускорить, чтобы прошло по времени?
2 ответа
12
✓ Принятый ответ — помог автору
Главные ускорения для 27-й:
- Один проход вместо вложенных циклов. O(n²) почти всегда заменяется на O(n) с накоплением (бегущие максимумы/суммы, остатки по модулю в словаре).
- Читай файл потоково, не держи всё в памяти, если не нужно.
- Используй массивы/словари для предподсчёта вместо повторного перебора.
Типовой приём: вместо «для каждой пары (i,j)…» считаем нужное за один проход, держа в переменных/словаре промежуточные лучшие значения. Покажи кусок — подскажу конкретику.
Максим Николаев убрал вложенный цикл, накапливаю максимум на лету — прошло! · 4 месяца назад
Вера Новикова спасибо, O(n²)→O(n) это прям мой случай был · 4 месяца назад
3
ещё: input() через sys.stdin читает быстрее, на больших объёмах заметно.
Ваш ответ
Войдите, чтобы ответить на вопрос.
