Submission #798592

#TimeUsernameProblemLanguageResultExecution timeMemory
798592JohannDiversity (CEOI21_diversity)C++14
38 / 100
7039 ms12108 KiB
#include "bits/stdc++.h" using namespace std; typedef long long ll; typedef vector<ll> vi; #define sz(x) (int)(x).size() #define all(x) (x).begin(), (x).end() const ll INF = 1e18; int N, Q; vi A, AA; ll ans; vi P; vi answerPermutation; int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> N >> Q; AA.resize(N); for (int i = 0; i < N; ++i) cin >> AA[i]; while (Q--) { { int l, r; cin >> l >> r; --l; A = vi(AA.begin() + l, AA.begin() + r); } ll n = sz(A); vi heatMap(*max_element(all(A)) + 1, 0); for (int i = 0; i < sz(A); ++i) ++heatMap[A[i]]; map<ll, ll> cnts; for (int i = 0; i < sz(heatMap); ++i) if (heatMap[i]) ++cnts[heatMap[i]]; ll pref = 0; ll num = sz(cnts); vi dp[2]; for (int foo = 0; foo < 2; ++foo) dp[foo].reserve(N + 1), dp[foo].resize(N + 1); fill(all(dp[0]), INF); dp[0][0] = n * (n + 1) * (n + 1) / 2 - (2 * n + 1) * (n + 1) * n / 6; auto it = cnts.begin(); for (int j = 0; j < num; ++j) { int ii = j & 1; int ni = ii ^ 1; fill(all(dp[ni]), INF); ll x = it->first; // how much ll y = it->second; // how often ll subsure = 0; // either with left or right endpoint in set subsure += (n - x) * x * (x - 1) / 2; // if both are in set subsure += x * x * (x - 1) / 2 - (2 * x - 1) * x * (x - 1) / 6; // for every such set subsure *= y; for (ll left = 0; left < sz(dp[ii]); ++left) { ll tmp = dp[ii][left]; if (tmp == INF) continue; tmp -= subsure; vi L(y + 1, 0), R(y + 1, 0); ll l = left, r = pref - left; for (ll i = 1; i <= y; ++i) { L[i] = L[i - 1] + (x - 1) * l * (n - l - x); R[i] = R[i - 1] + (x - 1) * r * (n - r - x); l += x, r += x; } for (ll i = 0; i <= y; ++i) dp[ni][left + x * i] = min(dp[ni][left + x * i], tmp - L[i] - R[y - i]); } ++it; pref += x * y; } ans = *min_element(all(dp[num & 1])); cout << ans << "\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...