oj.uz

Submission #620776

# Submission time Handle Problem Language Result Execution time Memory
620776 2022-08-03T08:59:53 Z dozer Diversity (CEOI21_diversity) C++14
4 / 100
 1726 ms 3436 KB 
#include <bits/stdc++.h>
using namespace std;
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define sp " "
#define endl "\n"
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define N 300005
#define modulo 1000000007
#define int long long

int arr[N], cnt[N];


int f(int sz, int n, int mask, int ind)
{
	if (ind > sz) return 0;
	int ans = modulo;
	for (int i = 0; i < n; i++)
	{
		if (mask & (1<<i)) continue;
		int fin = ind + cnt[i + 1] - 1;
		int tmp = (sz * (sz + 1)) / 2 - (((ind - 1) * ind) / 2 + ((sz - fin) * (sz - fin + 1)) / 2);
		ans = min(ans, tmp + f(sz, n, mask | (1<<i), fin + 1));
	}
	return ans;
}

int32_t main()
{
	fastio();

	int n, q;
	cin>>n>>q;
	for (int i = 1; i <= n; i++)
		cin>>arr[i];

	while(q--)
	{
		memset(cnt, 0, sizeof(cnt));
		int l, r;
		cin>>l>>r;
		map<int, int> val;
		int counter = 1;
		for (int i = l; i <= r; i++)
		{
			cnt[arr[i]]++;
		}
		int res = f(r - l + 1, 11, 0, 1);
		cout<<res<<endl;
	}
}

Compilation message

diversity.cpp: In function 'int32_t main()':
diversity.cpp:46:7: warning: unused variable 'counter' [-Wunused-variable]
   46 |   int counter = 1;
      |       ^~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 261 ms 2764 KB Output is correct
2 Correct 498 ms 2656 KB Output is correct
3 Correct 688 ms 2752 KB Output is correct
4 Correct 937 ms 2656 KB Output is correct
5 Correct 1038 ms 2652 KB Output is correct
6 Correct 1388 ms 2660 KB Output is correct
7 Correct 1518 ms 2656 KB Output is correct
8 Correct 1658 ms 2652 KB Output is correct
9 Correct 1725 ms 2656 KB Output is correct
10 Correct 1726 ms 2652 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1261 ms 2660 KB Output is correct
2 Correct 1495 ms 2664 KB Output is correct
3 Correct 1587 ms 2736 KB Output is correct
4 Incorrect 1578 ms 3436 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1261 ms 2660 KB Output is correct
2 Correct 1495 ms 2664 KB Output is correct
3 Correct 1587 ms 2736 KB Output is correct
4 Incorrect 1578 ms 3436 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1261 ms 2660 KB Output is correct
2 Correct 1495 ms 2664 KB Output is correct
3 Correct 1587 ms 2736 KB Output is correct
4 Incorrect 1578 ms 3436 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 261 ms 2764 KB Output is correct
2 Correct 498 ms 2656 KB Output is correct
3 Correct 688 ms 2752 KB Output is correct
4 Correct 937 ms 2656 KB Output is correct
5 Correct 1038 ms 2652 KB Output is correct
6 Correct 1388 ms 2660 KB Output is correct
7 Correct 1518 ms 2656 KB Output is correct
8 Correct 1658 ms 2652 KB Output is correct
9 Correct 1725 ms 2656 KB Output is correct
10 Correct 1726 ms 2652 KB Output is correct
11 Correct 1261 ms 2660 KB Output is correct
12 Correct 1495 ms 2664 KB Output is correct
13 Correct 1587 ms 2736 KB Output is correct
14 Incorrect 1578 ms 3436 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 261 ms 2764 KB Output is correct
2 Correct 498 ms 2656 KB Output is correct
3 Correct 688 ms 2752 KB Output is correct
4 Correct 937 ms 2656 KB Output is correct
5 Correct 1038 ms 2652 KB Output is correct
6 Correct 1388 ms 2660 KB Output is correct
7 Correct 1518 ms 2656 KB Output is correct
8 Correct 1658 ms 2652 KB Output is correct
9 Correct 1725 ms 2656 KB Output is correct
10 Correct 1726 ms 2652 KB Output is correct
11 Correct 1261 ms 2660 KB Output is correct
12 Correct 1495 ms 2664 KB Output is correct
13 Correct 1587 ms 2736 KB Output is correct
14 Incorrect 1578 ms 3436 KB Output isn't correct
15 Halted 0 ms 0 KB -