Submission #830782

#	Time	Username	Problem	Language	Result	Execution time	Memory
830782		lovrot	Diversity (CEOI21_diversity)	C++17	4 / 100	18 ms	1748 KiB

diversity

#include <cstdio>
#include <vector>
#include <algorithm>

#define EB emplace_back

using namespace std;

typedef long long ll;

const int N = 3e5 + 10;

int n, m, CNT[N];
vector<int> C, S;

ll count() {
	ll cnt = 0;
	for(int i = 0; i < S.size(); ++i) {
		cnt += S[i] * (S[i] - 1) / 2 + S[i];
		for(int j = i - 1; j >= 0; --j) cnt += S[i] * S[j] * (i - j + 1);
	}
	return cnt; 
}

int main() {
	//int t; scanf("%d", &t); 

	scanf("%d%d", &n, &m);
	for(int i = 0; i < n; ++i) {
		int x; 
		scanf("%d", &x);
		++CNT[x];
	}
	scanf("%d%d", &m, &m);
	sort(CNT, CNT + N, [](int a, int b) { return a > b; } );
	for(int i = 0; i < N && CNT[i]; ++i) C.EB(CNT[i]), S.EB(0);
	int l = (C.size() - 1) / 2;
	int r = l + 1, flag = 0; 
	for(int x : C) {
		if(!flag) {
			S[l] = x;
			--l;
		} else {
			S[r] = x;
			++r;
		}
		flag ^= 1;
	}
	printf("%lld\n", count());

	//if(t) for(int i = 0; i < S.size(); ++i) printf("%d%c", S[i], " \n"[i == S.size() - 1]);
	return 0;
}

Compilation message (stderr)

diversity.cpp: In function 'll count()':
diversity.cpp:18:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |  for(int i = 0; i < S.size(); ++i) {
      |                 ~~^~~~~~~~~~
diversity.cpp: In function 'int main()':
diversity.cpp:28:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
diversity.cpp:31:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |   scanf("%d", &x);
      |   ~~~~~^~~~~~~~~~
diversity.cpp:34:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |  scanf("%d%d", &m, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~

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