제출 #556004

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
556004		Stickfish	Diversity (CEOI21_diversity)	C++17	22 / 100	2431 ms	2344 KiB

diversity

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
using ll = long long;

const int MAXN = 3e5 + 123;
int a[MAXN];

signed main() {
    int n, q;
    cin >> n >> q;
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    for (int t = 0; t < q; ++t) {
        int l, r;
        cin >> l >> r;
        --l;
        map<int, int> mp;
        for (int i = l; i < r; ++i)
            ++mp[a[i]];
        vector<int> cnts;
        for (auto [vl, cnt] : mp)
            cnts.push_back(cnt);
        sort(cnts.begin(), cnts.end());
        int m = cnts.size();
        ll ans = 1ll * n * n * n;
        for (int msk = 0; msk < (1 << (m - 1)); ++msk) {
            vector<int> arr;
            for (int i = 0; i < m; ++i) {
                if (msk & (1 << i))
                    arr.push_back(cnts[i]);
            }
            for (int i = m - 1; i >= 0; --i) {
                if ((msk & (1 << i)) == 0)
                    arr.push_back(cnts[i]);
            }
            ll ans0 = 0;
            for (int i = 0; i < m; ++i) {
                ans0 += 1ll * arr[i] * (arr[i] + 1) / 2;
                for (int j = i + 1; j < m; ++j) {
                    ans0 += 1ll * (j - i + 1) * arr[i] * arr[j];
                }
            }
            ans = min(ans, ans0);
        }
        cout << ans << '\n';
    }
}

• Subtask 1: 4 / 4
• Subtask 2: 10 / 10
• Subtask 3: 8 / 8
• Subtask 4: 0 / 16
• Subtask 5: 0 / 26
• Subtask 6: 0 / 36