Как ускорить код?

Не знаю, насколько это поможет, но есть такие мысли:
- распределить числа на чётные и нечётные. При выборе пар будет гарантировано, что одно число чётное, другое нечётное. Будет меньше итераций цикла.
- нет смысла хранить все найденные пары, поскольку важно только их количество и максимум. Обе величины можно считать походу нахождения пар.
- для проверки, есть ли число в списке, надо использовать множество (set). Поиск по множеству выполняется гораздо быстрее, чем по списку.
Я не понял, зачем список отсортирован.

Никак. От кода это никак не зависит

В ЕГЭ заданиях нет ограничений по времени. Хочешь ускорить, используй Паскаль. Для 5К чисел вполне понятное время. Реально же даётся не более 10и чисел
Любое усложнение кода в условиях отсутствия времени для отладки тупо украдёт его у остальных заданий. Правильный результат - самый простой

очень легко ускорить до 4-х секунд (на моей машине), сделав сет из списка и делая in по нему, а не по списку

Убрать in из цикла. А дальше разные варианты. Я бы добавлял в список все суммы, преобразовал списки в множества и вывел пересечение.
И сортировку можно убрать, она в твоем коде ничего не делает

Подсчет длины и максимума вместо того чтобы заносить все в список тоже хорошая идея.

Либо можно все делать так как ты делал, но преобразовать изначально a в множество - они быстрее.

На c++ пиши