제출 #520458

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
520458		KoD	Diversity (CEOI21_diversity)	C++17	64 / 100	37 ms	2668 KiB

diversity

#include <bits/stdc++.h>
 
using std::vector;
using std::array;
using std::pair;
using std::tuple;
 
using i64 = std::int64_t;

constexpr int MAX = 300000;

constexpr i64 sum_k(const int n) {
    return (i64)n * (n + 1) / 2;
}

constexpr i64 sum_k2(const int n) {
    return (i64)n * (n + 1) * (2 * n + 1) / 6;
}
 
int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N, Q;
    std::cin >> N >> Q;
    vector<int> count(MAX);
    for (int i = 0; i < N; ++i) {
        int x;
        std::cin >> x;
        count[x - 1] += 1;
    }
    vector<int> block(N + 1);
    for (int i = 0; i < MAX; ++i) {
        block[count[i]] += 1;
    }
    int left = 0, right = 0;
    i64 ans = sum_k(N);
    const auto add_to = [&](const i64 s, const int a, const int n) {
        ans += (n * s + sum_k(n) * a) * N;
        ans -= n * s * s + 2 * s * sum_k(n) * a + sum_k2(n) * a * a;
    };
    for (int a = 1; a <= N; ++a) {
        const int b = block[a];
        if (b == 0) {
            continue;
        }
        if (left > right) {
            std::swap(left, right);
        }
        const int need = std::min(b, (right - left + a - 1) / a);
        const int to_left = need + (b - need) / 2;
        const int to_right = b - to_left;
        add_to(left, a, to_left);
        add_to(right, a, to_right);
        left += a * to_left;
        right += a * to_right;
    }
    ans -= (i64)left * (N - left);
    std::cout << ans << '\n';
    return 0;
}

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