Submission #1154975

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154975		ace5	Diversity (CEOI21_diversity)	C++20	4 / 100	13 ms	6844 KiB

diversity

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 300005;

vector<int> vs(maxn);

vector<int> reorder(vector<int> a)
{
    sort(a.rbegin(),a.rend());
    deque<int> ans;
    ll lv = 0,rv = 0;
    ll sum = 0;
    for(int i = 0;i < a.size();++i)
    {
        if(lv < rv)
        {
            ans.push_front(a[i]);
            lv += a[i] * 2;
            lv += sum;
            rv += a[i] * (ans.size()+1);
            sum += a[i];
        }
        else
        {
            ans.push_back(a[i]);
            rv += a[i] * 2;
            rv += sum;
            lv += a[i] * (ans.size()+1);
            sum += a[i];
        }
    }
    vector<int> h;
    for(int i = 0;i < ans.size();++i)
        h.push_back(ans[i]);
    return h;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,q;
    cin >> n >> q;
    vector<int> a(n);
    for(int i = 0;i < n;++i)
    {
        cin >> a[i];
        vs[a[i]]++;
    }
    vs = reorder(vs);
    ll res = 0,tsum = 0,tres = 0;
    for(int i = maxn-1;i >= 0;--i)
    {
        res += vs[i] * (vs[i]+1) / 2;
        res += tres * vs[i];
        tres += 2*vs[i];
        tres += tsum;
        tsum += vs[i];
    }
    cout << res;
    return 0;
}

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