# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
857993 | danikoynov | Diversity (CEOI21_diversity) | C++14 | 1 ms | 6492 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
void speed()
{
ios_base::sync_with_stdio(NULL);
cin.tie(NULL);
cout.tie(NULL);
}
const int maxn = 3e5 + 10;
int n, q, a[maxn], cnt[maxn], m, val[maxn], used[maxn];
vector < ll > groups;
ll ans;
ll bef[maxn], aft[maxn];
void check()
{
ll tot = 0;
/**for (int i = 0; i < m; i ++)
cout << val[i] << " ";
cout << endl;*/
ll bf = 0;
for (int i = 0; i < m; i ++)
{
bef[i] = bf;
bf += groups[val[i]];
}
ll af = 0;
for (int i = m - 1; i >= 0; i --)
{
aft[i] = af;
af += groups[val[i]];
}
for (ll i = 0; i < m; i ++)
{
tot = tot + i * groups[val[i]] * (bef[i] - aft[i]);
}
/**for (int i = 0; i < m; i ++)
cout << groups[val[i]] << " ";
cout << endl;
cout << tot << endl;
cout << "-----------" << endl;*/
ll sf = 0;
for (int i = 0; i < m; i ++)
{
ll cur = groups[i];
tot = tot + cur * (cur + 1) / 2;
tot = tot + groups[i] * sf;
sf += groups[i];
}
ans = min(ans, tot);
}
void perm(int pos)
{
if (pos == m)
check();
else
{
for (int i = 0; i < m; i ++)
{
if (!used[i])
{
val[pos] = i;
used[i] = 1;
perm(pos + 1);
used[i] = 0;
val[pos] = 0;
}
}
}
}
void solve()
{
cin >> n >> q;
for (int i = 1; i <= n; i ++)
cin >> a[i];
int l, r;
cin >> l >> r;
for (int i = 1; i <= n; i ++)
cnt[a[i]] ++;
for (int i = 1; i <= n; i ++)
if (cnt[i] > 0)
groups.push_back((ll)(cnt[i]));
ans = 1e18;
m = groups.size();
for (int j = 0; j < m; j ++)
{
int pos = 0;
for (int d = j; d < m; d ++)
{
val[pos] = d;
pos ++;
}
for (int d = j - 1; d >= 0; d --)
{
val[pos] = d;
pos ++;
}
check();
}
cout << ans << endl;
}
int main()
{
solve();
return 0;
}
/**
4 1
1 1 1 1
1 2
2 4
4 1
2 1 3 2
1 4
*/
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |