Submission #1097436

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097436		alexander707070	Diversity (CEOI21_diversity)	C++17	38 / 100	7049 ms	4948 KiB

diversity

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

int n,a[MAXN],q;

int br[MAXN],maxs,l,r,p[MAXN],len;
long long ans;

int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        br[a[i]]++;

        maxs=max(maxs,a[i]);
    }

    sort(br+1,br+maxs+1);
    for(int i=1;i<=maxs;i++){
        if(br[i]>0)r++;
    }
    r++;
    len=r-1;

    for(int i=1;i<=maxs;i++){
        if(br[i]==0)continue;

        if(i%2==0){
            l++; p[l]=br[i];
        }else{
            r--; p[r]=br[i];
        }
    }

    for(int i=1;i<=len;i++){
        ans+=(long long) (p[i])*(p[i]-1)/2+p[i];
    }

    for(int i=1;i<=len;i++){
        for(int f=i+1;f<=len;f++){
            ans+=(long long) p[i]*p[f]*(f-i+1);
        }
    }

    cout<<ans<<"\n";
    
    return 0;
}

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