# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
989492 | yoav_s | Diversity (CEOI21_diversity) | C++17 | 1 ms | 2652 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>
using namespace std;
typedef long long ll;
typedef vector<ll> v;
typedef vector<v> vv;
typedef vector<vv> vvv;
typedef pair<ll,ll> p;
typedef vector<p> vp;
typedef vector<vp> vvp;
typedef vector<vvp> vvvp;
typedef pair<ll, p> tri;
typedef vector<tri> vtri;
typedef vector<vtri> vvtri;
typedef vector<vvtri> vvvtri;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<vvb> vvvb;
#define f first
#define s second
#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(),(v).end()
const ll INF = 1e18;
const ll mod = 1e9 + 7;
const ll maxValue = 3e5;
ll evaluate(v &segments)
{
ll N = 0;
for (ll x : segments) N += x;
ll l = 0;
ll res = 0;
for (ll x : segments)
{
ll r = l + x - 1;
res += ((r - l + 1) * (r - l + 2)) / 2 + l * (N - r - 1) + (r - l + 1) * l + (r - l + 1) * (N - r - 1);
l += x;
}
return res;
}
int main()
{
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
ll N, Q;
cin >> N >> Q;
v a(N);
for (ll i = 0; i < N; i++) cin >> a[i];
sort(all(a));
v histogram(maxValue + 1, 0);
for (ll x : a) histogram[x]++;
v segments;
for (ll i = 0; i <= maxValue; i++) if (histogram[i] > 0) segments.pb(histogram[i]);
sort(all(segments));
v segOrder;
for (ll i = 0; i < segments.size() / 2; i++)
{
segOrder.pb(segments[i]);
segOrder.pb(segments[segments.size() - 1 - i]);
}
if (N % 2 == 1) segOrder.pb(segments[segments.size() / 2]);
ll mini = evaluate(segOrder);
/*while (next_permutation(all(segments)))
{
mini = min(mini, evaluate(segments));
}*/
cout << mini << "\n";
return 0;
}
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... |