oj.uz

Submission #830782

# Submission time Handle Problem Language Result Execution time Memory
830782 2023-08-19T10:32:37 Z lovrot Diversity (CEOI21_diversity) C++17
4 / 100
 18 ms 1748 KB 
#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

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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1364 KB Output is correct
2 Correct 4 ms 1444 KB Output is correct
3 Correct 4 ms 1364 KB Output is correct
4 Correct 5 ms 1364 KB Output is correct
5 Correct 5 ms 1444 KB Output is correct
6 Correct 4 ms 1448 KB Output is correct
7 Correct 5 ms 1448 KB Output is correct
8 Correct 4 ms 1444 KB Output is correct
9 Correct 4 ms 1364 KB Output is correct
10 Correct 4 ms 1364 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1364 KB Output is correct
2 Correct 4 ms 1440 KB Output is correct
3 Correct 5 ms 1476 KB Output is correct
4 Correct 13 ms 1584 KB Output is correct
5 Incorrect 18 ms 1748 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1364 KB Output is correct
2 Correct 4 ms 1440 KB Output is correct
3 Correct 5 ms 1476 KB Output is correct
4 Correct 13 ms 1584 KB Output is correct
5 Incorrect 18 ms 1748 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1364 KB Output is correct
2 Correct 4 ms 1440 KB Output is correct
3 Correct 5 ms 1476 KB Output is correct
4 Correct 13 ms 1584 KB Output is correct
5 Incorrect 18 ms 1748 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1364 KB Output is correct
2 Correct 4 ms 1444 KB Output is correct
3 Correct 4 ms 1364 KB Output is correct
4 Correct 5 ms 1364 KB Output is correct
5 Correct 5 ms 1444 KB Output is correct
6 Correct 4 ms 1448 KB Output is correct
7 Correct 5 ms 1448 KB Output is correct
8 Correct 4 ms 1444 KB Output is correct
9 Correct 4 ms 1364 KB Output is correct
10 Correct 4 ms 1364 KB Output is correct
11 Correct 4 ms 1364 KB Output is correct
12 Correct 4 ms 1440 KB Output is correct
13 Correct 5 ms 1476 KB Output is correct
14 Correct 13 ms 1584 KB Output is correct
15 Incorrect 18 ms 1748 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #6
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1364 KB Output is correct
2 Correct 4 ms 1444 KB Output is correct
3 Correct 4 ms 1364 KB Output is correct
4 Correct 5 ms 1364 KB Output is correct
5 Correct 5 ms 1444 KB Output is correct
6 Correct 4 ms 1448 KB Output is correct
7 Correct 5 ms 1448 KB Output is correct
8 Correct 4 ms 1444 KB Output is correct
9 Correct 4 ms 1364 KB Output is correct
10 Correct 4 ms 1364 KB Output is correct
11 Correct 4 ms 1364 KB Output is correct
12 Correct 4 ms 1440 KB Output is correct
13 Correct 5 ms 1476 KB Output is correct
14 Correct 13 ms 1584 KB Output is correct
15 Incorrect 18 ms 1748 KB Output isn't correct
16 Halted 0 ms 0 KB -