Submission #1186756

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186756		Unforgettablepl	Diversity (CEOI21_diversity)	C++20	22 / 100	1709 ms	2632 KiB

diversity

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

#define int long long

const int modulo = 1e9+7;


int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N,Q;
    cin >> N >> Q;
    vector<int> arr(N);
    for(int&i:arr)cin>>i;
    vector<int> newarr;
    {
        int c=0;
        map<int,int> comp;
        for(int&i:arr){
            if(!comp.count(i)){
                comp[i]=c++;
                newarr.emplace_back(0);
            }
            newarr[comp[i]]++;
        }
    }
    sort(newarr.rbegin(),newarr.rend());
    list<int> newarrr;
    auto test = [&](){
        int ans = 0;
        int curr = 0;
        for(int&i:newarrr){
            int L = curr+1;
            int R = curr+i;
            curr = R;
            ans+=R*(N+1ll) - L*L + ((L+1ll)*L - R*(R+1ll))/2ll;
        }
        return ans;
    };
    int minima = 1e17;
    swap(arr,newarr);
    int n = arr.size();
    for(int mask=0;mask<(1<<(n-1));mask++){
        newarrr.clear();
        newarrr.emplace_back(arr[0]);
        for(int bit=0;bit<n-1;bit++){
            if(mask&(1<<bit))newarrr.emplace_back(arr[bit+1]);
            else newarrr.emplace_front(arr[bit+1]);
        }
        minima = min(minima,test());
    }
    cout << minima << '\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