Submission #959263

#	Time	Username	Problem	Language	Result	Execution time	Memory
959263		Dan4Life	Diversity (CEOI21_diversity)	C++17	64 / 100	102 ms	11460 KiB

diversity

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define int long long
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
const int mxN = (int)3e5+10;
int n, q, a[mxN], d[mxN], pr[mxN];
vector<int> v;
 
int f(){
	d[0] = a[0]*(a[0]+1)/2;
	int tot = d[0], SZ = a[0]; 
	pr[0]=(d[0]-a[0]*(a[0]-1)/2)/a[0];
	for(int i = 1; i < n; i++){
		d[i] = pr[i-1]+a[i-1]-1+SZ+1;
		pr[i] = d[i]; d[i] *= a[i];
		d[i] += a[i]*(a[i]-1)/2;
		tot+=d[i]; SZ+=a[i];
	}
	return tot;
}
 
int32_t main() {
	cin >> n >> q;
	int ans = mxN*mxN*mxN;
	for(int i = 0; i < n; i++) cin >> a[i];
	cin >> q >> q; sort(a,a+n);
	for(int i = 0; i < n; i++){
	    int j = i;
	    while(i<n-1 and a[i]==a[i+1]) i++;
	    v.pb(i-j+1);
	} 
	n = sz(v); sort(all(v));
 
	int l = 0, r = n-1;
	for(int i = 0; i < n; i++){
		if(i%2==0) a[l++]=v[i];
		else a[r--] = v[i];
	}
	cout << f() << "\n";
}

Compilation message (stderr)

diversity.cpp: In function 'int32_t main()':
diversity.cpp:26:6: warning: unused variable 'ans' [-Wunused-variable]
   26 |  int ans = mxN*mxN*mxN;
      |      ^~~

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