Магічна функція#28

Магічна функція (Розбір)

Прямий перебір усіх пар дав би \mathcal{O}(n^2), що при n = 10^5 надто повільно. Скористаємось нерівномірністю обмежень: a_i сягає 10^6, а от b_i — лише 10^3.

Різних значень не більше , тому згрупуємо індекси за значенням b_i. Помітимо, що всередині групи важливе лише найбільше : якщо два індекси мають однакове , то більше ніколи не гірше — функція

f(i, j) = a_i b_j + b_i a_j

зростає за кожним із a_i, a_j при невід'ємних .

Тому для кожного значення достатньо зберігати два найбільші серед індексів з b_i = v: найбільше — щоб брати пари з іншими групами, і друге за величиною — щоб коректно обробити пару всередині однієї групи (адже потрібні різні індекси).

Далі переберемо всі пари значень , u \le v. Для u \ne v беремо найбільші з кожної групи і рахуємо . Для u = v беремо два найбільші цієї групи; тут f = v \cdot (a_1 + a_2).

Пар значень щонайбільше близько 5 \cdot 10^5, тому загальна складність — \mathcal{O}(n + B^2), де B = 1001.

Відповідь сягає 2 \cdot 10^6 \cdot 10^3 = 2 \cdot 10^9, тому обов'язково беріть 64-бітний тип.