Що саме шукаємо. Позначимо через c_1, c_2, c_3 кількості елементів, узятих із початків масивів. Тоді -й елемент об'єднання дорівнює
де a[0] = -\infty. Отже треба знайти оптимальний «розріз», а не сам масив.
Два правила обміну. Триматимемо для кожного масиву відрізок [L_t, R_t], у якому напевно лежить оптимальне c_t. Візьмемо будь-які m_t \in [L_t, R_t] і запитаємо значення a_t[m_t]. Далі:
якщо \sum m_t \ge k, то серед перших m_t елементів уже назбиралось чисел, і всі вони не перевищують V = \max_t a_t[m_t]; отже відповідь , і для масиву , на якому цей максимум досягається, існує оптимум із c_Y \le m_Y. Опускаємо R_Y = m_Y;
якщо \sum m_t < k, то навпаки: для масиву з найменшим a_X[m_X] існує оптимум із c_X \ge m_X. Піднімаємо L_X = m_X.
Обидва твердження доводяться однаково — обміном: переносимо одиницю з «дорогого» масиву в «дешевий» і перевіряємо, що максимум не зростає.
Чому запитів мало. Правила дозволяють будь-які m_t всередині відрізків, тож беремо середини. Кожен крок скорочує вдвічі один відрізок, а решта масивів залишаються з тими самими серединами — їхні значення вже в кеші. Тому крок коштує один новий запит, а кроків усього \sum_t \log_2 |t| \approx 3\log_2 10^6 = 60.
Дрібниця, на якій легко застрягти: при округленні вниз завжди прогресує лише перше правило, при округленні вгору — лише друге. Тому спершу пробуємо «підлоги» (якщо сума ), потім «стелі» (якщо сума ), а в рідкісному проміжному випадку добираємо решту до рівно , віддаючи надлишок найширшому відрізку. Наприкінці, коли всі відрізки стиснуті до кількох варіантів, перебираємо їх напряму й беремо мінімум максимумів.
Технічно. Обов'язково кешуйте відповіді: повторний запит — це змарнована квота. Не забувайте fflush після кожного рядка й негайно завершуйте роботу, отримавши . Разом виходить близько запитів навіть на найбільших тестах, що вкладається в найсуворіше обмеження Q = 65.