[Codeforces] Codeforces Round #670 (Div. 2) B. Maximum Product

2020年9月13日2020年12月13日

問題

方針

\( n \) 個の整数 \( a \) が与えられ、

\[ a_i a_j a_k a_l a_t \ (i < j < k < l < t)\]

の最大値を答えます。添え字に制約がありますが、この問題は \( a \) から任意に \( 5 \) 個の整数を選ぶことができます。したがって、以下のパターンを考えればよいです。

1. \( a \) の最大値 \( 5 \) つ
2. \( a \) の最小値 \( 5 \) つ
3. \( a \) の最小値 \( 2 \) つと最大値 \( 3 \) つ
4. \( a \) の最小値 \( 4 \) つと最大値 \( 1 \) つ

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n;
ll a[100000];

ll solve(int n) {
    sort(a, a + n);
    ll best = LLONG_MIN;
    ll v1 = 1;
    vector<ll> p, q;
    for (int i = 0; i < n; i++) {
        if (a[i] < 0) {
            p.push_back(a[i]);
        }
        if (a[i] > 0) {
            q.push_back(a[i]);
        }
    }
    for (int i = 0; i < 5; i++) {
        v1 *= a[i];
    }
    best = max(best, v1);
    v1 = 1;
    for (int i = n - 1; i >= n - 5; i--) {
        v1 *= a[i];
    }
    best = max(best, v1);

    int idx = q.size() - 1;
    if (p.size() >= 2 && q.size() >= 3) {
        best = max(best, p[0] * p[1] * q[idx] * q[idx - 1] * q[idx - 2]);
    }
    if (p.size() >= 4 && q.size() >= 1) {
        best = max(best, p[0] * p[1] * p[2] * p[3] * q[idx]);
    }
    return best;
}

int main() {
    int t;
    cin >> t;
    ll ans[t];
    for (int i = 0; i < t; i++) {
        cin >> n;
        for (int j = 0; j < n; j++) {
            cin >> a[j];
        }
        ans[i] = solve(n);
    }
    for (ll i : ans) {
        cout << i << "\n";
    }
    return 0;
}