Submission #601625

#	Time	Username	Problem	Language	Result	Execution time	Memory
601625		Valaki2	Diversity (CEOI21_diversity)	C++14	64 / 100	56 ms	6384 KiB

diversity

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

#define int long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second

const int maxn = 3e5;

int n, q;
int base_cnt[maxn + 1];
int ans;
vector<int> v;

void solve() {
    cin >> n >> q;
    for(int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        base_cnt[x]++;
    }
    for(int i = 1; i <= maxn; i++) {
        if(base_cnt[i] != 0) {
            int x = base_cnt[i];
            ans += (x * (x + 1)) / 2;
            v.pb(x);
        }
    }
    n = v.size();
    sort(v.rbegin(), v.rend());
    int lsum = 0, rsum = 0, sum = 0, cnt = 0;
    for(int cur : v) {
        cnt++;
        if(lsum < rsum) {
            ans += cur * lsum;
            lsum += sum;
            lsum += 2 * cur;
            rsum += (cnt + 1) * cur;
        } else {
            ans += cur * rsum;
            rsum += sum;
            rsum += 2 * cur;
            lsum += (cnt + 1) * cur;
        }
        sum += cur;
    }
    cout << ans << "\n";
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

/*
19 1
1 2 3 3 4 4 4 5 5 5 5 5 6 6 6 6 6 6 6
1 19
*/

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