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)$.
Формат выходного файла
Выведите одно целое число -- ответ на задачу.
Система оценки
Данная задача содержит шесть подзадач:
  1. $2 <= n <= 1000, 1 <= A_i, B_i <= 1$. Оценивается в $8$ баллов.
  2. $2 <= n <= 15, 1 <= A_i, B_i <= 10^9$. Оценивается в $9$ баллов.
  3. $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$ баллов.
  4. $2 <= n <= 1000$, $A_i=B_i$ для всех $i$, сумма всех $A_i$ не больше $10^5$. Оценивается в $18$ баллов.
  5. $2 <= n <= 100$, сумма всех $A_i$ не больше 300, сумма всех $B_i$ не больше 300. Оценивается в $15$ баллов.
  6. $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 )
посмотреть в олимпиаде

Комментарий/решение:

  0
2020-04-02 16:17:22.0 #

показать/скрыть код