4-й этап Республиканской олимпиады по информатике 2019, 9 класс, *ДЕНЬ 2* Казахстан, Актобе
Задача D. Выбор Айбара
Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт
У Айбара есть два массива $A$ и $B$, что размер каждого равен $n$. Для каждого $i$, что $(1 <= i <= n)$, Айбар должен выбрать либо $A_i$, либо $B_i$. Он хочет максимизировать произведение суммы выбранных $A_i$ и суммы выбранных $B_j$. Помогите Айбару найти максимальное значение. Гарантируется, что максимальное значение не превосходит $10^9$.
Формат входного файла
Первая строка содержит одно целое число $n$ $(2 <= n <= 1000)$.
Вторая строка содержит $n$ целых чисел $A_1, A_2, A_3,...A_n$ $(1 <= A_i <= 10^9)$.
Третья строка содержит $n$ целых чисел $B_1, B_2, B_3,...B_n$ $(1 <= B_i <= 10^9)$.
Формат выходного файла
Выведите одно целое число -- ответ на задачу.
Система оценки
Данная задача содержит шесть подзадач:
- $2 <= n <= 1000, 1 <= A_i, B_i <= 1$. Оценивается в $8$ баллов.
- $2 <= n <= 15, 1 <= A_i, B_i <= 10^9$. Оценивается в $9$ баллов.
- $2 <= n <= 1000, 1 <= A_i, B_i <= 10^9$ и $A_1 <= A_2 <= ... <= A_n$, $B_1 \ge B_2 \ge ... \ge B_n$ . Оценивается в $10$ баллов.
- $2 <= n <= 1000$, $A_i=B_i$ для всех $i$, сумма всех $A_i$ не больше $10^5$. Оценивается в $18$ баллов.
- $2 <= n <= 100$, сумма всех $A_i$ не больше 300, сумма всех $B_i$ не больше 300. Оценивается в $15$ баллов.
- $2 <= n <= 1000, 1 <= A_i, B_i <= 10^9$. Оценивается в $30$ баллов.
Примеры:
Вход 5 1 4 3 2 5 5 2 2 4 1Ответ
108Вход
2 5 7 3 5Ответ
25Вход
7 1 1 1 1 1 1 1 1 1 1 1 1 1 1Ответ
12
Замечание
В первом сэмпле Айбар выбирает в массиве $A$ позиции 2, 3, 5, а в массиве $B$ позиции 1 и 4. Тогда ответ $(4 + 3 + 5) * (5 + 4)=108$.
(
Aibar Kuanyshbay
)
Комментарий/решение:
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.