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), greater<ll>());
ll mini = evaluate(segments);
/*while (next_permutation(all(segments)))
{
mini = min(mini, evaluate(segments));
}*/
cout << mini << "\n";
return 0;
}
# | 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... |