Закордонна подорож
Обмеження: 2 сек., 256 МіБ
Усе більше країн знову відкривають свої кордони після пандемії реп’яховірусу. Марічка та Зеник вирішили поїхати зі своїми друзями в подорож. Для цього їм усім потрібно вакцинуватися.
Друзі пішли до поліклініки, відстояли в гігантській черзі та придбали великий ящик з вакцинами — \(x\) доз першого типу та \(y\) доз другого типу. Тепер кожному з \(n\) учасників поїздки треба визначитися, яким типом вакцини він буде щеплюватися. Відомо, що користь від вакцинації \(i\)-го учасника групи вакциною першого типу дорівнює \(a_i\), а вакциною другого типу — \(b_i\).
Друзі хочуть розподілити вакцини між учасниками так, щоб кожен учасник отримав рівно по одній дозі вакцини та сумарна користь була максимальною. Допоможете їм?
Вхідні дані
У першому рядку задано три цілі числа \(n\), \(x\) та \(y\) — кількість учасників поїздки, кількість доз першого типу та кількість доз другого типу.
У кожному з наступних \(n\) рядків задано по два цілих числа \(a_i\) та \(b_i\) — користь від вакцинації відповідного учасника кожним з типів вакцини.
Вихідні дані
Виведіть один рядок з \(n\)
символів. \(i\)-й символ рівний
A, якщо \(i\)-тому
учаснику слід прийняти вакцину першого типу, B — другу.
Якщо способів досягнути максимальної користі кілька, то виведіть
довільний з них.
Обмеження
\(1 \le n \le 10^5\),
\(0 \le x, y \le 2 \cdot 10^5\),
\(x+y \ge n\),
\(0 \le a_i, b_i \le 10^9\).
Приклади
| Вхідні дані (stdin) | Вихідні дані (stdout) |
|---|---|
| 4 2 2 1 3 7 4 9 2 3 3 | BAAB |
Примітки
Сумарна користь складе 22. Більшого значення досягнути не можна.
Надіслати розв'язок
| Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
|---|
Закордонна подорож - Розбір
Припустимо, що в нас є необмежений запас вакцини першого типу, але лише одна вакцина другого типу. Якщо ми всім дамо вакцину першого типу, то сумарна користь становитиме \(A_1 + A_2 + ... + A_n\). Якщо \(i\)-тій людині ми дамо вакцину другого типу, замість першого, то ця користь зміниться на \(B_i - A_i\). Отже, вакцину другого типу є зміст давати лише учаснику в якого \(B_i - A_i\) максимальне і лише в випадку, коли \(B_i - A_i\) додатне для нього.
Аналогічно, якщо в нас є лише дві дози другої вакцини, то їх може бути зміст давати лише двом учасниками з найбільшими значеннями \(B_i - A_i\).
Узагальнюючи ці міркування, отримуємо повний розв’язок. Впорядкуємо всіх учасників за незростанням \(B_i - A_i\). Другу вакцину отримає деяка група людей, що стоїть на початку в цьому посортованому списку. Треба лише визначити скільком людям на початку списку вигідно дати другу вакцину. Очевидно, що ідеально було б дати вакцину другого типу усім в кого значення \(B_i - A_i\) додатне, а решті дати вакцину першого типу. Але у цьому випадку нам може не вистачити вакцин одного з типів. А тому треба також врахувати, що другу вакцину ми маємо дати не менше ніж \(n - x\) учасникам та не більше ніж \(y\) учасникам.
Складність розв’язку — \(O(n \log(n))\).
| Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
|---|