Submission #798561

#	Time	Username	Problem	Language	Result	Execution time	Memory
798561		Johann	Diversity (CEOI21_diversity)	C++14	38 / 100	7072 ms	13896 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;
        ll n = r - l;

        A = vi(AA.begin() + l, AA.begin() + r);

        vi heatMap(*max_element(all(A)) + 1, 0);
        for (int i = 0; i < sz(A); ++i)
            ++heatMap[A[i]];
        vi cnts;
        for (int i = 0; i < sz(heatMap); ++i)
            if (heatMap[i])
                cnts.push_back(heatMap[i]);
        sort(all(cnts));

        vi pref(sz(cnts));
        partial_sum(all(cnts), pref.begin());

        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;

        for (int j = 0; j < num; ++j)
        {
            int ii = j & 1;
            int ni = ii ^ 1;
            fill(all(dp[ni]), INF);

            ll x = cnts[j];
            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 (ll left = 0; left < sz(dp[ii]); ++left)
            {
                ll tmp = dp[ii][left];
                if (tmp == INF)
                    continue;
                tmp -= subsure;
                // left
                dp[ni][left + x] = min(dp[ni][left + x], tmp - (x - 1) * left * (n - left - x));
                // right
                ll right = pref[j] - x - left;
                dp[ni][left] = min(dp[ni][left], tmp - (x - 1) * right * (n - right - x));
            }
        }
        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