Задача E. Конференция
Задачу добавил: alef
Успешно сдано решений: 189
В один из дней почти все сотрудники компании, где проходит стажировку Кеша, отправились на конференцию. Кеше показались наиболее интересными программы двух секций. Сделать между ними выбор Кеша так и не смог, поэтому решил, что попробует послушать доклады и там, и там.
В каждой секции запланировано по n докладов, причём регламент секций совершенно одинаков. Это значит, что доклад #i первой секции и доклад #i второй секции начнутся и закончатся одновременно (с учётом вопросов, обсуждений и т.п.).
Кеша определил интересность f1, f2, ..., fn для докладов первой секции и s1, s2, ..., sn для докладов второй секции. К огорчению Кеши, аудитории, где проводятся секции, расположены далеко друг от друга. Поэтому, чтобы перейти из одной аудитории в другую, ему придётся пропустить доклад.
Кеша хочет составить для себя расписание таким образом, чтобы суммарная интересность прослушанных им докладов была максимальной. Ваша задача — определить, какие доклады каких секций Кеша будет слушать.
В первой строке содержится целое число n (1 ≤ n ≤ 2·105) — количество докладов каждой секции.
Во второй строке содержится n целых чисел f1, f2, ..., fn (1 ≤ fi ≤ 105), fi — интересность доклада #i первой секции.
В третьей строке содержится n целых чисел s1, s2, ..., sn (1 ≤ si ≤ 105), si — интересность доклада #i второй секции.
В первой строке выведите максимально возможную суммарную интересность прослушанных Кешей докладов.
Во второй строке выведите число m — количество докладов, которые прослушает Кеша.
В третьей строке выведите m символов A и B, где символ A означает, что Кеша слушал доклад на первой секции, а символ B — что Кеша слушал доклад на второй секции.
Если существует несколько решений, выведите любое.
Подзадача 1 (до 30 баллов)
1 ≤ n ≤ 1000.
Баллы начисляются в случае прохождения всех тестов подзадачи.
Подзадача 2 (до 70 баллов)
1 ≤ n ≤ 200000.
Баллы начисляются в случае прохождения всех тестов подзадачи.
По запросу сообщается результат проверки на каждом тесте.
5
3 4 16 2 5
8 6 4 6 7
31
3
BAB
Приведённый в примере ответ не является единственно верным. Также правильными ответами будут, например, строки BAAA и BBBBB (конечно, при этом во второй строке следует выводить 4 и 5 соответственно).