Сортируй типа есть пары ai,bi и aj,bj тогда первую лучше раньше брать если aibj+bi<ajbi+ai

Там ожидается сортировка с предикатом (a_i - 1) / b_i > (a_j - 1) / b_j.

Честно говоря, я сам был бы очень признателен, если бы кто-нибудь объяснил, как и почему это работает.

Предположим, что a_i = 1 нет, вернемся к ним позже.

Посмотрим, при каком условии будет выгодно поменять соседние элементы (a₁, b₁) и (a₂, b₂). Для этого нужно сравнить b₁·a₂ + b₂ с b₂·a₁ + b₁, то есть b₁·(a₂ - 1) с b₂·(a₁ - 1). Если a по разные стороны от единицы, то раньше должна идти та, что больше единицы. Другими словами, в оптимальном решении сначала идут все пары с a_i больше единицы. Если a по одному сторону от единицы, то можно все разнести по разные стороны неравенства и получить валидный компаратор.

Теперь выясняется, что нам повезло, и наибольший префиксный максимум по произведению a_i-х образуется всеми a_i-ми большими единицы. Поэтому элементы с a_i можно засунуть после них в любом порядке.

    const auto comp = [&](int i, int j) -> bool {
        const int Ai = (a[i] < 1) - (a[i] > 1);
        const int Aj = (a[j] < 1) - (a[j] > 1);
        if (Ai != Aj) {
            return Ai < Aj;
        }
        if (Ai == 0 && Aj == 0) {
            return 0;
        }
        return b[i] / (a[i] - 1) < b[j] / (a[j] - 1);
    };