Language: C++

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using uint = unsigned int;
using pcc = pair<char, char>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<double, double>;
using tuplis = array<ll, 3>;
template<class T> using pq = priority_queue<T, vector<T>, greater<T>>;
const ll LINF=0x1fffffffffffffff;
const ll MINF=0x7fffffffffff;
const int INF=0x3fffffff;
const int MOD=1000000007;
const int MODD=998244353;
const ld DINF=numeric_limits<ld>::infinity();
const ld EPS=1e-9;
const ld PI=3.1415926535897932;
const ll four[] = {0, 1, 0, -1, 0};
const ll eight[] = {0, 1, 1, 0, -1, -1, 1, -1, 0};
#define overload4(_1,_2,_3,_4,name,...) name
#define overload3(_1,_2,_3,name,...) name
#define rep1(n) for(ll i=0;i<n;++i)
#define rep2(i,n) for(ll i=0;i<n;++i)
#define rep3(i,a,b) for(ll i=a;i<b;++i)
#define rep4(i,a,b,c) for(ll i=a;i<b;i+=c)
#define rep(...) overload4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__)
#define rrep1(n) for(ll i=(n)-1;i>=0;i--)
#define rrep2(i,n) for(ll i=(n)-1;i>=0;i--)
#define rrep3(i,a,b) for(ll i=(b)-1;i>=(a);i--)
#define rrep4(i,a,b,c) for(ll i=a+(b-a-1)/c*c;i>=a;i-=c)
#define rrep(...) overload4(__VA_ARGS__,rrep4,rrep3,rrep2,rrep1)(__VA_ARGS__)
#define each(i,a) for(auto&& i:a)
#define all1(i) begin(i),end(i)
#define all2(i,a) begin(i),begin(i)+a
#define all3(i,a,b) begin(i)+a,begin(i)+b
#define all(...) overload3(__VA_ARGS__,all3,all2,all1)(__VA_ARGS__)
#define rall1(i) (i).rbegin(),(i).rend()
#define rall2(i,k) (i).rbegin(),(i).rbegin()+k
#define rall3(i,a,b) (i).rbegin()+a,(i).rbegin()+b
#define rall(...) overload3(__VA_ARGS__,rall3,rall2,rall1)(__VA_ARGS__)
#define sum(...) accumulate(all(__VA_ARGS__),0LL)
#define dsum(...) accumulate(all(__VA_ARGS__),0.0L)
#define elif else if
#define unless(a) if(!(a))
#define mp make_pair
#define mt make_tuple
#define INT(...) int __VA_ARGS__;in(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__;in(__VA_ARGS__)
#define ULL(...) ull __VA_ARGS__;in(__VA_ARGS__)
#define STR(...) string __VA_ARGS__;in(__VA_ARGS__)
#define CHR(...) char __VA_ARGS__;in(__VA_ARGS__)
#define DBL(...) double __VA_ARGS__;in(__VA_ARGS__)
#define LD(...) ld __VA_ARGS__;in(__VA_ARGS__)
#define vec(type,name,...) vector<type> name(__VA_ARGS__)
#define VEC(type,name,size) vector<type> name(size);in(name)
#define vv(type,name,h,...) vector<vector<type>>name(h,vector<type>(__VA_ARGS__))
#define VV(type,name,h,w) vector<vector<type>>name(h,vector<type>(w));in(name)
#define vvv(type,name,h,w,...) vector<vector<vector<type>>>name(h,vector<vector<type>>(w,vector<type>(__VA_ARGS__)))
template<class T> auto max(const T& a){ return *max_element(all(a)); }
template<class T> auto min(const T& a){ return *min_element(all(a)); }
ll gcd(ll a, ll b){ while(b){ ll c = b; b = a % b; a = c; } return a; }
ll lcm(ll a, ll b){ if(!a || !b) return 0; return a * b / gcd(a, b); }
ll intpow(ll a, ll b){ ll ans = 1; while(b){ if(b & 1) ans *= a; a *= a; b /= 2; } return ans; }
ll modpow(ll a, ll b, ll p){ ll ans = 1; while(b){ if(b & 1) (ans *= a) %= p; (a *= a) %= p; b /= 2; } return ans; }
template<class T> bool chmin(T& a, const T& b){ if(a > b){ a = b; return 1; } return 0; }
template<class T> bool chmax(T& a, const T& b){ if(a < b){ a = b; return 1; } return 0; }
vector<pll> factor(ull x){ vector<pll> ans; for(ll i = 2; i * i <= x; i++) if(x % i == 0){ ans.push_back({i, 1}); while((x /= i) % i == 0) ans.back().second++; } if(x != 1) ans.push_back({x, 1}); return ans; }
vector<ll> divisor(ull x){ vector<ll> ans; for(ll i = 1; i * i <= x; i++) if(x % i == 0) ans.push_back(i); rrep(ans.size() - (ans.back() * ans.back() == x)) ans.push_back(x / ans[i]); return ans; }
template<class T> unordered_map<T, ll> press(vector<T>& a){ auto b = a; sort(all(b)); b.erase(unique(all(b)), b.end()); unordered_map<T,ll> ans; rep(b.size()) ans[b[i]] = i; each(i, a) i = ans[i]; return ans; }
template<class T> map<T, ll> press_map(vector<T>& a){ auto b = a; sort(all(b)); b.erase(unique(all(b)), b.end()); map<T,ll> ans; rep(b.size()) ans[b[i]] = i; each(i, a) i = ans[i]; return ans; }
int scan(){ return getchar(); }
void scan(int& a){ scanf("%d", &a); }
void scan(unsigned& a){ scanf("%u", &a); }
void scan(long& a){ scanf("%ld", &a); }
void scan(long long& a){ scanf("%lld", &a); }
void scan(unsigned long long& a){ scanf("%llu", &a); }
void scan(char& a){ do{ a = getchar(); }while(a == ' ' || a == '\n'); }
void scan(float& a){ scanf("%f", &a); }
void scan(double& a){ scanf("%lf", &a); }
void scan(long double& a){ scanf("%Lf", &a); }
void scan(vector<bool>& a){ for(unsigned i = 0; i < a.size(); i++) { int b; scan(b); a[i] = b; } }
void scan(char a[]){ scanf("%s", a); }
void scan(string& a){ cin >> a; }
template<class T> void scan(vector<T>&);
template<class T, size_t size> void scan(array<T, size>&);
template<class T, class L> void scan(pair<T, L>&);
template<class T, size_t size> void scan(T(&)[size]);
template<class T> void scan(vector<T>& a){ for(auto& i : a) scan(i); }
template<class T> void scan(deque<T>& a){ for(auto& i : a) scan(i); }
template<class T, size_t size> void scan(array<T, size>& a){ for(auto& i : a) scan(i); }
template<class T, class L> void scan(pair<T, L>& p){ scan(p.first); scan(p.second); }
template<class T, size_t size> void scan(T (&a)[size]){ for(auto& i : a) scan(i); }
template<class T> void scan(T& a){ cin >> a; }
void in(){}
template <class Head, class... Tail> void in(Head& head, Tail&... tail){ scan(head); in(tail...); }
void print(){ putchar(' '); }
void print(bool a){ printf("%d", a); }
void print(int a){ printf("%d", a); }
void print(unsigned a){ printf("%u", a); }
void print(long a){ printf("%ld", a); }
void print(long long a){ printf("%lld", a); }
void print(unsigned long long a){ printf("%llu", a); }
void print(char a){ printf("%c", a); }
void print(char a[]){ printf("%s", a); }
void print(const char a[]){ printf("%s", a); }
void print(float a){ printf("%.15f", a); }
void print(double a){ printf("%.15f", a); }
void print(long double a){ printf("%.15Lf", a); }
void print(const string& a){ for(auto&& i : a) print(i); }
template<class T> void print(const vector<T>&);
template<class T, size_t size> void print(const array<T, size>&);
template<class T, class L> void print(const pair<T, L>& p);
template<class T, size_t size> void print(const T (&)[size]);
template<class T> void print(const vector<T>& a){ if(a.empty()) return; print(a[0]); for(auto i = a.begin(); ++i != a.end(); ){ putchar(' '); print(*i); } }
template<class T> void print(const deque<T>& a){ if(a.empty()) return; print(a[0]); for(auto i = a.begin(); ++i != a.end(); ){ putchar(' '); print(*i); } }
template<class T, size_t size> void print(const array<T, size>& a){ print(a[0]); for(auto i = a.begin(); ++i != a.end(); ){ putchar(' '); print(*i); } }
template<class T, class L> void print(const pair<T, L>& p){ print(p.first); putchar(' '); print(p.second); }
template<class T, size_t size> void print(const T (&a)[size]){ print(a[0]); for(auto i = a; ++i != end(a); ){ putchar(' '); print(*i); } }
template<class T> void print(const T& a){ cout << a; }
int out(){ putchar('\n'); return 0; }
template<class T> int out(const T& t){ print(t); putchar('\n'); return 0; }
template<class Head, class... Tail> int out(const Head& head, const Tail&... tail){ print(head); putchar(' '); out(tail...); return 0; }
#ifdef DEBUG
void err(){ putchar('\n'); }
template<class T> void err(const T& t){ print(t); putchar('\n'); }
template<class Head, class... Tail> void err(const Head& head, const Tail&... tail){ print(head); putchar(' '); out(tail...); }
#else
template<class... T> void err(const T&...){}
#endif
int first(bool i = true){ return out(i?"first":"second"); }
int yes(bool i = true){ return out(i?"yes":"no"); }
int Yes(bool i = true){ return out(i?"Yes":"No"); }
int No(){ return out("No"); }
int YES(bool i = true){ return out(i?"YES":"NO"); }
int NO(){ return out("NO"); }
int Yay(bool i = true){ return out(i?"Yay!":":("); }
int possible(bool i = true){ return out(i?"possible":"impossible"); }
int Possible(bool i = true){ return out(i?"Possible":"Impossible"); }
int POSSIBLE(bool i = true){ return out(i?"POSSIBLE":"IMPOSSIBLE"); }
void Case(ll i){ printf("Case #%lld: ", i); }


#define int ll
#define ll __int128_t
namespace ntt{
    typedef pair<int, int> Pii;
    
#define FOR(i,n) for(int i = 0; i < (n); i++)
#define sz(c) ((int)(c).size())
#define ten(x) ((int)1e##x)
    
    template<class T> T extgcd(T a, T b, T& x, T& y) { for (T u = y = 1, v = x = 0; a;) { T q = b / a; swap(x -= q * u, u); swap(y -= q * v, v); swap(b -= q * a, a); } return b; }
    template<class T> T mod_inv(T a, T m) { T x, y; extgcd(a, m, x, y); return (m + x % m) % m; }
    ll mod_pow(ll a, ll n, ll mod) { ll ret = 1; ll p = a % mod; while (n) { if (n & 1) ret = ret * p % mod; p = p * p % mod; n >>= 1; } return ret; }
    
    template<int mod, int primitive_root>
    class NTT {
    public:
        int get_mod() const { return mod; }
        void _ntt(vector<ll>& a, int sign) {
            const int n = sz(a);
            assert((n ^ (n&-n)) == 0); //n = 2^k
            
            const int g = 3; //g is primitive root of mod
            int h = (int)mod_pow(g, (mod - 1) / n, mod); // h^n = 1
            if (sign == -1) h = (int)mod_inv(h, mod); //h = h^-1 % mod
            
            //bit reverse
            int i = 0;
            for (int j = 1; j < n - 1; ++j) {
                for (int k = n >> 1; k >(i ^= k); k >>= 1);
                if (j < i) swap(a[i], a[j]);
            }
            
            for (int m = 1; m < n; m *= 2) {
                const int m2 = 2 * m;
                const ll base = mod_pow(h, n / m2, mod);
                ll w = 1;
                FOR(x, m) {
                    for (int s = x; s < n; s += m2) {
                        ll u = a[s];
                        ll d = a[s + m] * w % mod;
                        a[s] = u + d;
                        if (a[s] >= mod) a[s] -= mod;
                        a[s + m] = u - d;
                        if (a[s + m] < 0) a[s + m] += mod;
                    }
                    w = w * base % mod;
                }
            }
            
            for (auto& x : a) if (x < 0) x += mod;
        }
        void ntt(vector<ll>& input) {
            _ntt(input, 1);
        }
        void intt(vector<ll>& input) {
            _ntt(input, -1);
            const int n_inv = mod_inv(sz(input), mod);
            for (auto& x : input) x = x * n_inv % mod;
        }
        
        // 畳み込み演算を行う
        vector<ll> convolution(const vector<ll>& a, const vector<ll>& b){
            int ntt_size = 1;
            while (ntt_size < sz(a) + sz(b)) ntt_size *= 2;
            
            vector<ll> _a = a, _b = b;
            _a.resize(ntt_size); _b.resize(ntt_size);
            
            ntt(_a);
            ntt(_b);
            
            FOR(i, ntt_size){
                (_a[i] *= _b[i]) %= mod;
            }
            
            intt(_a);
            return _a;
        }
    };
    
    ll garner(vector<Pii> mr, int mod){
        mr.emplace_back(mod, 0);
        
        vector<ll> coffs(sz(mr), 1);
        vector<ll> constants(sz(mr), 0);
        FOR(i, sz(mr) - 1){
            // coffs[i] * v + constants[i] == mr[i].second (mod mr[i].first) を解く
            ll v = (mr[i].second - constants[i]) * mod_inv<ll>(coffs[i], mr[i].first) % mr[i].first;
            if (v < 0) v += mr[i].first;
            
            for (int j = i + 1; j < sz(mr); j++) {
                (constants[j] += coffs[j] * v) %= mr[j].first;
                (coffs[j] *= mr[i].first) %= mr[j].first;
            }
        }
        
        return constants[sz(mr) - 1];
    }
    
    typedef NTT<167772161, 3> NTT_1;
    typedef NTT<469762049, 3> NTT_2;
    typedef NTT<1224736769, 3> NTT_3;
    
    //任意のmodで畳み込み演算 O(n log n)
    vector<ll> int32mod_convolution(vector<ll> a, vector<ll> b,int mod){
        for (auto& x : a) x %= mod;
        for (auto& x : b) x %= mod;
        NTT_1 ntt1; NTT_2 ntt2; NTT_3 ntt3;
        auto x = ntt1.convolution(a, b);
        auto y = ntt2.convolution(a, b);
        auto z = ntt3.convolution(a, b);
        
        vector<ll> ret(sz(x));
        vector<Pii> mr(3);
        FOR(i, sz(x)){
            mr[0].first = ntt1.get_mod(), mr[0].second = (int)x[i];
            mr[1].first = ntt2.get_mod(), mr[1].second = (int)y[i];
            mr[2].first = ntt3.get_mod(), mr[2].second = (int)z[i];
            ret[i] = garner(mr, mod);
        }
        
        return ret;
    }
    
    // garnerのアルゴリズムを直書きしたversion，速い
    vector<ll> fast_int32mod_convolution(vector<ll> a, vector<ll> b,int mod){
        for (auto& x : a) x %= mod;
        for (auto& x : b) x %= mod;
        
        NTT_1 ntt1; NTT_2 ntt2; NTT_3 ntt3;
        assert(ntt1.get_mod() < ntt2.get_mod() && ntt2.get_mod() < ntt3.get_mod());
        auto x = ntt1.convolution(a, b);
        auto y = ntt2.convolution(a, b);
        auto z = ntt3.convolution(a, b);
        
        // garnerのアルゴリズムを極力高速化した
        const ll m1 = ntt1.get_mod(), m2 = ntt2.get_mod(), m3 = ntt3.get_mod();
        const ll m1_inv_m2 = mod_inv<ll>(m1, m2);
        const ll m12_inv_m3 = mod_inv<ll>(m1 * m2, m3);
        const ll m12_mod = m1 * m2 % mod;
        vector<ll> ret(sz(x));
        FOR(i, sz(x)){
            ll v1 = (y[i] - x[i]) *  m1_inv_m2 % m2;
            if (v1 < 0) v1 += m2;
            ll v2 = (z[i] - (x[i] + m1 * v1) % m3) * m12_inv_m3 % m3;
            if (v2 < 0) v2 += m3;
            ll constants3 = (x[i] + m1 * v1 + m12_mod * v2) % mod;
            if (constants3 < 0) constants3 += mod;
            ret[i] = constants3;
        }
        
        return ret;
    }
}
signed main(){
    uint64_t n,m;
    in(n,m);
    VEC(uint64_t,a,n);
    vec(ll,b,100001);
    each(i,a)b[i]++;
    auto c=ntt::fast_int32mod_convolution(b,b,10000000001);
    uint64_t ans=0;
    rrep(c.size()){
        if(ll(c[i])>m){
            ans+=i*m;
            return out(ans);
        }
        ans+=i*c[i];
        m-=c[i];
    }
    out(ans);
}


Compiler output:
a.cc: In instantiation of 'void scan(std::vector<_Tp>&) [with T = long unsigned int]':
a.cc:98:78:   required from 'void in(Head&, Tail& ...) [with Head = std::vector<long unsigned int>; Tail = {}]'
   98 | template <class Head, class... Tail> void in(Head& head, Tail&... tail){ scan(head); in(tail...); }
      |                                                                          ~~~~^~~~~~
a.cc:303:5:   required from here
   58 | #define VEC(type,name,size) vector<type> name(size);in(name)
      |                                                     ~~^~~~~~
a.cc:91:65: error: no matching function for call to 'scan(long unsigned int&)'
   91 | template<class T> void scan(vector<T>& a){ for(auto& i : a) scan(i); }
      |                                                             ~~~~^~~
a.cc:75:6: note: candidate: 'void scan(int&)' (near match)
   75 | void scan(int& a){ scanf("%d", &a); }
      |      ^~~~
a.cc:75:6: note:   conversion of argument 1 would be ill-formed:
a.cc:75:6: error: cannot bind non-const lvalue reference of type 'int&' to a value of type 'long unsigned int'
a.cc:76:6: note: candidate: 'void scan(unsigned int&)' (near match)
   76 | void scan(unsigned& a){ scanf("%u", &a); }
      |      ^~~~
a.cc:76:6: note:   conversion of argument 1 would be ill-formed:
a.cc:76:6: error: cannot bind non-const lvalue reference of type 'unsigned int&' to a value of type 'long unsigned int'
a.cc:77:6: note: candidate: 'void scan(long int&)' (near match)
   77 | void scan(long& a){ scanf("%ld", &a); }
      |      ^~~~
a.cc:77:6: note:   conversion of argument 1 would be ill-formed:
a.cc:77:6: error: cannot bind non-const lvalue reference of type 'long int&' to a value of type 'long unsigned int'
a.cc:78:6: note: candidate: 'void scan(long long int&)' (near match)
   78 | void scan(long long& a){ scanf("%lld", &a); }
      |      ^~~~
a.cc:78:6: note:   conversion of argument 1 would be ill-formed:
a.cc:78:6: error: cannot bind non-const lvalue reference of type 'long long int&' to a value of type 'long unsigned int'
a.cc:79:6: note: candidate: 'void scan(long long unsigned int&)' (near match)
   79 | void scan(unsigned long long& a){ scanf("%llu", &a); }
      |      ^~~~
a.cc:79:6: note:   conversion of argument 1 would be ill-formed:
a.cc:79:6: error: cannot bind non-const lvalue reference of type 'long long unsigned int&' to a value of type 'long unsigned int'
a.cc:80:6: note: candidate: 'void scan(char&)' (near match)
   80 | void scan(char& a){ do{ a = getchar(); }while(a == ' ' || a == '\n'); }
      |      ^~~~
a.cc:80:6: note:   conversion of argument 1 would be ill-formed:
a.cc:80:6: error: cannot bind non-const lvalue reference of type 'char&' to a value of type 'long unsigned int'
a.cc:81:6: note: candidate: 'void scan(float&)' (near match)
   81 | void scan(float& a){ scanf("%f", &a); }
      |      ^~~~
a.cc:81:6: note:   conversion of argument 1 would be ill-formed:
a.cc:81:6: error: cannot bind non-const lvalue reference of type 'float&' to a value of type 'long unsigned int'
a.cc:82:6: note: candidate: 'void scan(double&)' (near match)
   82 | void scan(double& a){ scanf("%lf", &a); }
      |      ^~~~
a.cc:82:6: note:   conversion of argument 1 would be ill-formed:
a.cc:82:6: error: cannot bind non-const lvalue reference of type 'double&' to a value of type 'long unsigned int'
a.cc:83:6: note: candidate: 'void scan(long double&)' (near match)
   83 | void scan(long double& a){ scanf("%Lf", &a); }
      |      ^~~~
a.cc:83:6: note:   conversion of argument 1 would be ill-formed:
a.cc:83:6: error: cannot bind non-const lvalue reference of type 'long double&' to a value of type 'long unsigned int'
a.cc:85:6: note: candidate: 'void scan(char*)' (near match)
   85 | void scan(char a[]){ scanf("%s", a); }
      |      ^~~~
a.cc:85:6: note:   conversion of argument 1 would be ill-formed:
a.cc:85:6: error: invalid conversion from 'long unsigned int' to 'char*' [-fpermissive]
   85 | void scan(char a[]){ scanf("%s", a); }
      |      ^~~~
      |      |
      |      long unsigned int
a.cc:84:6: note: candidate: 'void scan(std::vector<bool>&)'
   84 | void scan(vector<bool>& a){ for(unsigned i = 0; i < a.size(); i++) { int b; scan(b); a[i] = b; } }
      |      ^~~~
a.cc:84:25: note:   no known conversion for argument 1 from 'long unsigned int' to 'std::vector<bool>&'
   84 | void scan(vector<bool>& a){ for(unsigned i = 0; i < a.size(); i++) { int b; scan(b); a[i] = b; } }
      |           ~~~~~~~~~~~~~~^
a.cc:86:6: note: candidate: 'void scan(std::string&)'
   86 | void scan(string& a){ cin >> a; }
      |      ^~~~
a.cc:86:19: note:   no known conversion for argument 1 from 'long unsigned int' to 'std::string&' {aka 'std::__cxx11::basic_string<char>&'}
   86 | void scan(string& a){ cin >> a; }
      |           ~~~~~~~~^
a.cc:91:24: note: candidate: 'template<class T> void scan(std::vector<_Tp>&)'
   91 | template<class T> void scan(vector<T>& a){ for(auto& i : a) scan(i); }
      |                        ^~~~
a.cc:91:24: note:   template argument deduction/substitution failed:
a.cc:91:65: note:   mismatched types 'std::vector<_Tp>' and 'long unsigned int'
   91 | template<class T> void scan(vector<T>& a){ for(auto& i : a) scan(i); }
      |                                                             ~~~~^~~
a.cc:93:37: note: candidate: 'template<class T, long unsigned int size> void scan(std::array<_Tp, _Nm>&)'
   93 | template<class T, size_t size> void scan(array<T, size>& a){ for(auto& i : a) scan(i); }
      |                                     ^~~~
a.cc:93:37: note:   template argument deduction/substitution failed:
a.cc:91:65: note:   mismatched types 'std::array<_Tp, _Nm>' and 'long unsigned int'
   91 | template<class T> void scan(vector<T>& a){ for(auto& i : a) scan(i); }
      |                                                             ~~~~^~~
a.cc:94:33: note: candidate: 'template<class T, class L> void scan(std::pair<_T1, _T2>&)'
   94 | template<class T, class L> void scan(pair<T, L>& p){ scan(p.first); scan(p.second); }
      |                                 ^~~~
a.cc:94:33: note:   template argument deduction/substitution failed:
a.cc:91:65: note:   mismatched types 'std::pair<_T1, _T2>' and 'long unsigned int'
   91 | template<class T> void scan(vector<T>& a){ for(auto& i : a) scan(i); }
      |                                                             ~~~~^~~
a.cc:95:37: note: candidate: 'template<class T, long unsigned int size> void scan(T (&)[size])'
   95 | template<class T, size_t size> void scan(T (&a)[size]){ for(auto& i : a) scan(i); }
      |                                     ^~~~
a.cc:95:37: note:   template argument deduction/substitution failed:
a.cc:91:65: note:   mismatched types 'T [size]' and 'long unsigned int'
   91 | template<class T> void scan(vector<T>& a){ for(auto& i : a) scan(i); }
      |                                                             ~~~~^~~
a.cc:74:5: note: candidate: 'int scan()'
   74 | int scan(){ return getchar(); }
      |     ^~~~
a.cc:74:5: note:   candidate expects 0 arguments, 1 provided