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 )

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

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

#include <bits/stdc++.h>
#define speed                   \
  ios_base::sync_with_stdio(0); \
  cin.tie(0);                   \
  cout.tie(0);
#define oprecision    \
  cout.precision(30); \
  cerr.precision(7);
#define ll long long
#define ld long double
#define ss string
#define pii pair<int, int>
#define pll pair<ll, ll>
#define forn(n) for (int i = 1; i <= n; i++)
#define forlr(l, r) \
  for (int i = l; (l > r ? i >= r : i <= r); (l > r ? i-- : i++))
#define pb push_back
#define pc __builtin_popcount
#define pcll __builtin_popcountll
#define mp make_pair
#define mt make_tuple
#define F first
#define S second
#define int ll
using namespace std;
const int inf = 1000000000;
const int m = 32000;
int n, x, y, ans, a[1005], b[1005], dp[m + 5], pd[m + 5];
main() {
  speed;
  oprecision;
  // code
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> a[i], x += a[i];
  for (int i = 1; i <= n; i++) cin >> b[i], y += b[i];
  for (int i = 1; i <= m; i++) dp[i] = pd[i] = inf;
  for (int i = 1; i <= n; i++) {
    for (int j = m - a[i]; j >= 0; j--) {
      dp[a[i] + j] = min(dp[a[i] + j], dp[j] + b[i]);
    }
  }
  for (int i = 1; i <= n; i++) {
    for (int j = m - b[i]; j >= 0; j--) {
      pd[b[i] + j] = min(pd[b[i] + j], pd[j] + a[i]);
    }
  }
  for (int i = 1; i <= m; i++)
    ans = max({ans, (y - dp[i]) * i, (x - pd[i]) * i});
  cout << ans;
  // endl
#ifndef ONLINE_JUDGE
  cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
  return 0;
}