Submission #1169535

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169535		Troll321	Diversity (CEOI21_diversity)	C++20	14 / 100	7093 ms	436 KiB

diversity

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll MAXN = 3e5 + 5;
const ll MAXQ = 5e4 + 5;
const ll MAX = 1e18;

// 4 1
// 1 1 1 1
// 1 2

ll n, q, k = 0, ans = MAX;
//								Compressed Cnt
ll cnt[MAXN], compressed[MAXN], ccnt[MAXN];
vector<ll> vec; 
set<ll> st;

ll calc() {
	ll out = n*k*(n+1) - n*(k-1);
	ll sqSum = 0, bef = 0;
	for (int i = 0; i < vec.size(); ++i) {
		ll now = vec[i];
		ll after = (n-ccnt[now]-bef);
		sqSum += bef*bef + after*after;
		bef += ccnt[now];
	}
	
	out = (out - sqSum) / 2;
	return out;
}

void compress() {
	for (auto it = st.begin(); it != st.end(); it++) {
		k++;
		compressed[(*it)] = k;
		ccnt[k] = cnt[(*it)];
	}
}

int main() {
	cin >> n >> q;
	for (int i = 1; i <= n; ++i) {
		ll tmp; cin >> tmp;
		st.insert(tmp);
		cnt[tmp]++;
	}

	compress();

	ll _tmp;
	cin >> _tmp >> _tmp;

	for (int i = 1; i <= k; ++i) {
		vec.push_back(i);
	}

	sort(vec.begin(), vec.end());
	do {
		ans = min(ans, calc());
	} while (next_permutation(vec.begin(), vec.end()));

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

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