제출 #528187

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
528187		Rafi22	Diversity (CEOI21_diversity)	C++14	64 / 100	40 ms	6884 KiB

diversity

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define ll long long
ll mod=1000000007;
int inf=1000000007;
ll infl=1000000000000000007;
#define int long long

ll cnt[300007];
ll x[300007];

signed main()
{
    srand(time(NULL));
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
   /* vector<int>P(10),p(10),best;
    for(int i=0;i<10;i++)
    {
        P[i]=(i+1)*(i+1)*(i+1)*(i+1);
        p[i]=i;
    }
    sort(all(P));
    int ans=inf;
    while(true)
    {
        int act=0;
        for(int i=0;i<10;i++)
        {
            for(int j=i+1;j<10;j++)
            {
                act+=P[p[i]]*P[p[j]]*(j-i+1);
            }
        }
        if(act<ans)
        {
            cout<<act<<endl;
            ans=act;
            best=p;
        }
        else if(act==ans) cout<<"XD"<<endl;
        if(!next_permutation(all(p))) break;
    }
    for(int i=0;i<10;i++) cout<<best[i]<<" ";
    cout<<endl;
    cout<<ans<<endl;
    for(int i=0;i<10;i++) cout<<P[best[i]]<<" ";*/
    int n,a,q;
    cin>>n>>q;
    for(int i=1;i<=n;i++)
    {
        cin>>a;
        cnt[a]++;
    }
    int mx=300000;
    sort(cnt+1,cnt+mx+1);
    int it=0,it1=mx+1;
    for(int i=1;i<=mx;i++)
    {
        if(i%2) x[++it]=cnt[i];
        else x[--it1]=cnt[i];
    }
    ll ans=0;
    ll sum=0,sum1=0;
    for(int i=1;i<=mx;i++)
    {
        ans+=x[i]*(x[i]+1)/2;
        ans+=x[i]*(i+1)*sum;
        ans+=x[i]*sum1;
        sum+=x[i];
        sum1-=i*x[i];
    }
    cout<<ans;

    return 0;
}

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