4-й этап Республиканской олимпиады по информатике 2019, 9 класс, *ДЕНЬ 1* Казахстан, Актобе

Есеп D. Айбардың таңдауы

Ограничение по времени:

1 секунда

Ограничение по памяти:

256 мегабайт

Айбардың ұзындықтары $n$ болатын $A$ және $B$ массивтары бар. Әр бір $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 <=q n <=q 1000, 1 <=q A_i, B_i <=q 1$. $8$ ұпайға есептеледі.
2. $2 <=q n <=q 15, 1 <=q A_i, B_i <=q 10^9$. $9$ ұпайға есептеледі.
3. $2 <=q n <=q 1000, 1 <=q A_i, B_i <=q 10^9$ и $A_1 <= A_2 <= ... <= A_n$, $B_1 \ge B_2 \ge ... \ge B_n$ . $10$ ұпайға есептеледі.
4. $2 <=q n <=q 1000$, $A_i=B_i$ барлық $i$ үшін, барлық $A_i$ соммасы $10^5$ аспайды. $18$ ұпайға есептеледі.
5. $2 <=q n <=q 100$, барлық $A_i$ соммасы 300 аспайды, барлық $B_i$ соммасы $300$ аспайды. $25$ ұпайға есептеледі.
6. $2 <=q n <=q 1000, 1 <=q A_i, B_i <=q 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;
}