提出 #10325022

---

ソースコード 拡げる

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx")
#include <bits/stdc++.h>

namespace {
    template<int n, typename T>
    void mult(const T *__restrict a, const T *__restrict b, T *__restrict res) {
        if (n <= 64) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    res[i + j] += a[i] * b[j];
                }
            }
        } else {
            const int mid = n / 2;
            alignas(64) T btmp[n], E[n] = {};
            auto atmp = btmp + mid;
            for (int i = 0; i < mid; i++) {
                atmp[i] = a[i] + a[i + mid];
                btmp[i] = b[i] + b[i + mid];
            }
            mult<mid>(atmp, btmp, E);
            mult<mid>(a + 0, b + 0, res);
            mult<mid>(a + mid, b + mid, res + n);
            for (int i = 0; i < mid; i++) {
                const auto tmp = res[i + mid];
                res[i + mid] += E[i] - res[i] - res[i + 2 * mid];
                res[i + 2 * mid] += E[i + mid] - tmp - res[i + 3 * mid];
            }
        }
    }
}

using ll = long long;

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(0);
    const int NMAX = (1 << 11)*49;
    alignas(64) static ll a[NMAX], b[NMAX * 2];
    int n; ll k; std::cin >> n >> k;
    for (int i = 0, val; i < n; i++) {
        std::cin >> val;
        a[val]++;
    }
    mult<NMAX>(a,a,b);
    ll answ(0);
    for (int i = 2 * NMAX - 1; k > 0 && i >= 0; i--) {
        answ += std::min(k, b[i]) * i;
        k -= b[i];
    }
    std::cout << answ << std::endl;
    return 0;
}

提出情報

ジャッジ結果