Submission #798595

#	Time	Username	Problem	Language	Result	Execution time	Memory
798595		Johann	Diversity (CEOI21_diversity)	C++14	38 / 100	7049 ms	11724 KiB

diversity

#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<int, int> cnts;
        for (int i = 0; i < sz(heatMap); ++i)
            if (heatMap[i])
                ++cnts[heatMap[i]];

        vi L, R;
        {
            int maxi = 0;
            for (auto it = cnts.begin(); it != cnts.end(); ++it)
                maxi = max(maxi, it->second);
            L.resize(maxi + 1), R.resize(maxi + 1);
        }

        ll pref = 0;
        int 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;

                ll l = left, r = pref - left;

                L[0] = R[0] = 0;
                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;
}

• Subtask 1: 4 / 4
• Subtask 2: 10 / 10
• Subtask 3: 8 / 8
• Subtask 4: 16 / 16
• Subtask 5: 0 / 26
• Subtask 6: 0 / 36