Problem:
 Score : 500 points    Problem Statement Takahashi has come to a party as a special guest.
There are N ordinary guests at the party. The i -th ordinary guest has a power of A_i .  Takahashi has decided to perform M  handshakes to increase the happiness of the party (let the current happiness be 0 ).
A handshake will be performed as follows:   Takahashi chooses one (ordinary) guest x for his left hand and another guest y for his right hand ( x and y can be the same).  Then, he shakes the left hand of Guest x and the right hand of Guest y simultaneously to increase the happiness by A_x+A_y .   However, Takahashi should not perform the same handshake more than once. Formally, the following condition must hold:   Assume that, in the k -th handshake, Takahashi shakes the left hand of Guest x_k and the right hand of Guest y_k . Then, there is no pair p, q  (1 \leq p < q \leq M) such that (x_p,y_p)=(x_q,y_q) .   What is the maximum possible happiness after M handshakes?      Constraints  1 \leq N \leq 10^5  1 \leq M \leq N^2  1 \leq A_i \leq 10^5  All values in input are integers.         Input Input is given from Standard Input in the following format:  N  M  A_1  A_2  ...  A_N       Output Print the maximum possible happiness after M handshakes.        Sample Input 1 5 3
10 14 19 34 33      Sample Output 1 202  Let us say that Takahashi performs the following handshakes:   In the first handshake, Takahashi shakes the left hand of Guest 4 and the right hand of Guest 4 .  In the second handshake, Takahashi shakes the left hand of Guest 4 and the right hand of Guest 5 .  In the third handshake, Takahashi shakes the left hand of Guest 5 and the right hand of Guest 4 .   Then, we will have the happiness of (34+34)+(34+33)+(33+34)=202 .  We cannot achieve the happiness of 203 or greater, so the answer is 202 .       Sample Input 2 9 14
1 3 5 110 24 21 34 5 3      Sample Output 2 1837       Sample Input 3 9 73
67597 52981 5828 66249 75177 64141 40773 79105 16076      Sample Output 3 8128170

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def f(n):
    r = 2
    ret = 1
    for i in range(n, n-r, -1):
        ret *= i
    for i in range(1, r+1):
        ret //= i
    return ret * 2 + n


class Bisect:
    def __init__(self, func):
        self.__func = func

    def bisect_left(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if self.__func(mid) < x:
                lo = mid+1
            else:
                hi = mid
        return lo

    def bisect_right(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if x < self.__func(mid):
                hi = mid
            else:
                lo = mid+1
        return lo

@mt
def slv(N, M, A):
    A.sort(reverse=True)
    print(A)
    b = Bisect(f)

    i = b.bisect_left(M, 1, N)
    if f(i) != M:
        i -= 1
    l = f(i)

    ans = 0
    for j in range(i):
        ans += A[j] * 2
        ans += A[j] * (i-1)

    rem = M - l
    print(i, l, rem)
    j = 0
    while rem != 0:
        ans += A[j] + A[i]
        rem -= 1
        if rem == 0:
            break
        ans += A[j] + A[i]
        rem -= 1
        if rem == 0:
            break
        j += 1


    return ans

import numpy as np
@mt
def slv2(N, M, A):
    C = Counter(A)
    L = 1 << (max(A).bit_length() + 1)
    B = [C[i] for i in range(L)]
    D = np.fft.rfft(B)
    D *= D
    E = list(map(int, np.round(np.fft.irfft(D).real)))
    ans = 0
    c = 0
    i = L - 1
    while c != M:
        n = E[i]
        if c + n > M:
            n = M-c
        c += n
        ans += i * n
        i -= 1
        assert i != -1

    return ans

def main():
    N, M = read_int_n()
    A = read_int_n()
    print(slv2(N, M,A))

    
    
    
    


if __name__ == '__main__':
    main()

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def f(n):
    r = 2
    ret = 1
    for i in range(n, n-r, -1):
        ret *= i
    for i in range(1, r+1):
        ret //= i
    return ret * 2 + n


class Bisect:
    def __init__(self, func):
        self.__func = func

    def bisect_left(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if self.__func(mid) < x:
                lo = mid+1
            else:
                hi = mid
        return lo

    def bisect_right(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if x < self.__func(mid):
                hi = mid
            else:
                lo = mid+1
        return lo

@mt
def slv(N, M, A):
    A.sort(reverse=True)
    print(A)
    b = Bisect(f)

    i = b.bisect_left(M, 1, N)
    if f(i) != M:
        i -= 1
    l = f(i)

    ans = 0
    for j in range(i):
        ans += A[j] * 2
        ans += A[j] * (i-1)

    rem = M - l
    print(i, l, rem)
    j = 0
    while rem != 0:
        ans += A[j] + A[i]
        rem -= 1
        if rem == 0:
            break
        ans += A[j] + A[i]
        rem -= 1
        if rem == 0:
            break
        j += 1


    return ans

import numpy as np
@mt
def slv2(N, M, A):
    C = Counter(A)
    L = 1 << ((max(A)).bit_length() + 1)
    B = [C[i] for i in range(L)]
    D = np.fft.rfft(B)
    D *= D
    E = list(np.fft.irfft(D).real)
    ans = 0
    c = 0
    i = L - 1
    while c != M:
        n = int(round(E[i]))
        if c + n > M:
            n = M-c
        c += n
        ans += i * n
        i -= 1
        assert i != -1

    return ans

def main():
    N, M = read_int_n()
    A = read_int_n()
    print(slv2(N, M,A))

    
    
    
    


if __name__ == '__main__':
    main()

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def f(n):
    r = 2
    ret = 1
    for i in range(n, n-r, -1):
        ret *= i
    for i in range(1, r+1):
        ret //= i
    return ret * 2 + n


class Bisect:
    def __init__(self, func):
        self.__func = func

    def bisect_left(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if self.__func(mid) < x:
                lo = mid+1
            else:
                hi = mid
        return lo

    def bisect_right(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if x < self.__func(mid):
                hi = mid
            else:
                lo = mid+1
        return lo

@mt
def slv(N, M, A):
    A.sort(reverse=True)
    print(A)
    b = Bisect(f)

    i = b.bisect_left(M, 1, N)
    if f(i) != M:
        i -= 1
    l = f(i)

    ans = 0
    for j in range(i):
        ans += A[j] * 2
        ans += A[j] * (i-1)

    rem = M - l
    print(i, l, rem)
    j = 0
    while rem != 0:
        ans += A[j] + A[i]
        rem -= 1
        if rem == 0:
            break
        ans += A[j] + A[i]
        rem -= 1
        if rem == 0:
            break
        j += 1


    return ans

import numpy as np
def slv2(N, M, A):
    C = Counter(A)
    L = 1 << ((max(A)*2).bit_length() + 1)
    B = [C[i] for i in range(L)]
    D = np.fft.rfft(B)
    D *= D
    E = list(np.fft.irfft(D).real)
    ans = 0
    c = 0
    i = L - 1
    while c != M:
        n = int(round(E[i]))
        if c + n > M:
            n = M-c
        c += n
        ans += i * n
        i -= 1
        assert i != -1

    return ans

def main():
    N, M = read_int_n()
    A = read_int_n()
    print(slv2(N, M,A))

    
    
    
    


if __name__ == '__main__':
    main()

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def f(n):
    r = 2
    ret = 1
    for i in range(n, n-r, -1):
        ret *= i
    for i in range(1, r+1):
        ret //= i
    return ret * 2 + n


class Bisect:
    def __init__(self, func):
        self.__func = func

    def bisect_left(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if self.__func(mid) < x:
                lo = mid+1
            else:
                hi = mid
        return lo

    def bisect_right(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if x < self.__func(mid):
                hi = mid
            else:
                lo = mid+1
        return lo

@mt
def slv(N, M, A):
    A.sort(reverse=True)
    print(A)
    b = Bisect(f)

    i = b.bisect_left(M, 1, N)
    if f(i) != M:
        i -= 1
    l = f(i)

    ans = 0
    for j in range(i):
        ans += A[j] * 2
        ans += A[j] * (i-1)

    rem = M - l
    print(i, l, rem)
    j = 0
    while rem != 0:
        ans += A[j] + A[i]
        rem -= 1
        if rem == 0:
            break
        ans += A[j] + A[i]
        rem -= 1
        if rem == 0:
            break
        j += 1


    return ans

import numpy as np
def slv2(N, M, A):
    C = Counter(A)
    L = 2 ** ((max(A)*2).bit_length() + 1)
    B = [C[i] for i in range(L)]
    D = np.fft.rfft(B)
    D *= D
    E = list(np.fft.irfft(D).real)
    ans = 0
    c = 0
    i = L - 1
    while c != M:
        n = int(round(E[i]))
        if c + n > M:
            n = M-c
        c += n
        ans += i * n
        i -= 1
        assert i != -1

    return ans

def main():
    N, M = read_int_n()
    A = read_int_n()
    print(slv2(N, M,A))

    
    
    
    


if __name__ == '__main__':
    main()

Solution (Python):
from itertools import accumulate

MAX = 2 * 10 ** 5 + 5

N, M, *A = map(int, open(0).read().split())

B = [0] * MAX
for a in A:
    B[a] += 1

C = list(accumulate(reversed(B)))[::-1]

ng, ok = 1, MAX
while abs(ok - ng) > 1:
    m = (ok + ng) // 2
    if sum(C[max(0, m - a)] for a in A) >= M:
        ng = m
    else:
        ok = m

D = list(accumulate(reversed(list(i * b for i, b in enumerate(B)))))[::-1]
print(sum(D[max(0, ng - a)] - (ng - a) * C[max(0, ng - a)] for a in A) + ng * M)

Solution (Python):


import sys
from bisect import bisect_left
from itertools import accumulate

import numpy as np

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def bisearch_max(mn, mx, func):
    """ 条件を満たす最大値を見つける二分探索 """

    ok = mn
    ng = mx
    while ok+1 < ng:
        mid = (ok+ng) // 2
        if func(mid):
            
            ok = mid
        else:
            
            ng = mid
    return ok


def calc(x):
    
    res = N - np.searchsorted(A, x - A)
    return res.sum() >= M

N, M = MAP()
A = np.array(LIST(), dtype=np.int64)

A.sort()
res = bisearch_max(0, 10**10 + 1, calc)

ans = m = 0
acc = [0] + list(A.cumsum())
for a in A:
    idx = bisect_left(A, res - a)
    cnt = N - idx
    
    ans += a * cnt + (acc[N] - acc[idx])
    
    m += cnt


ans -= res * (m - M)
print(ans)

Solution (Python):


import sys
from bisect import bisect_left
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def bisearch_max(mn, mx, func):
    """ 条件を満たす最大値を見つける二分探索 """

    ok = mn
    ng = mx
    while ok+1 < ng:
        mid = (ok+ng) // 2
        if func(mid):
            
            ok = mid
        else:
            
            ng = mid
    return ok


def calc(x):
    
    ans = 0
    for a in A:
        
        ans += N - bisect_left(A, x - a)
    return ans >= M

N, M = MAP()
A = LIST()

A.sort()
res = bisearch_max(0, 10**10+1, calc)

ans = m = 0
acc = [0] + list(accumulate(A))
for a in A:
    idx = bisect_left(A, res - a)
    cnt = N - idx
    
    ans += a * cnt + (acc[N] - acc[idx])
    
    m += cnt


ans -= res * (m - M)
print(ans)

Solution (Python):
import sys
from itertools import accumulate
 
read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines

import bisect

n,m=map(int,input().split())
A=list(map(int,input().split()))
A.sort()

def hand(x):
  cnt=0
  for i in range(n):
    k=n-bisect.bisect_left(A,x-A[-i-1])
    if k==0:
      break
    cnt+=k
    if cnt>=m:
      break
  return cnt

def main():
  l=0
  h=2*10**5+1
  mid=(l+h)//2
  
  while l+1<h:
    mid=(l+h)//2
    if hand(mid)<m:
      h=mid
    else:
      l=mid
  
  B = list(accumulate(A[::-1]))[::-1]

  ans=0
  cnt=0
  
  
  for i in range(n):
    index=bisect.bisect_left(A,l-A[-i-1]+1)
    if n==index:
      break
    else:
      ans+=(n-index)*A[-i-1]+B[index]
      cnt+=(n-index)
  
  ans+=(m-cnt)*l
  print(ans)

if __name__ == "__main__":
	main()

Solution (Python):

import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,m=map(int,input().split())
A=sorted(map(int,input().split()))
B=[0]+A[:]
for i in range(n):
    B[i+1]+=B[i]

def solve_binary(mid):
    tmp=0
    for i,ai in enumerate(A):
        tmp+=n-bisect.bisect_left(A,mid-ai)
    return tmp>=m

def binary_search(n):
    ok=0
    ng=n
    while abs(ok-ng)>1:
        mid=(ok+ng)//2
        if solve_binary(mid):
            ok=mid
        else:
            ng=mid
    return ok

binresult=binary_search(2*10**5+1)
for i ,ai in enumerate(A):
    ans+=ai*(n-bisect.bisect_left(A,binresult-ai))+B[n]-B[bisect.bisect_left(A,binresult-ai)]
    count+=n-bisect.bisect_left(A,binresult-ai)
    
ans-=binresult*(count-m)
print(ans)

Solution (Python):

import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,m=map(int,input().split())
A=sorted(map(int,input().split()))
B=[0]+A[:]
for i in range(n):
    B[i+1]+=B[i]

def solve_binary(mid):
    tmp=0
    for i,ai in enumerate(A):
        tmp+=n-bisect.bisect_left(A,mid-ai)
    return tmp>=m

def binary_search(n):
    ok=0
    ng=n
    while abs(ok-ng)>1:
        mid=(ok+ng)//2
        if solve_binary(mid):
            ok=mid
        else:
            ng=mid
    return ok

binresult=binary_search(2*10**5+1)
for i ,ai in enumerate(A):
    ans+=ai*(n-bisect.bisect_left(A,binresult-ai))+B[n]-B[bisect.bisect_left(A,binresult-ai)]
    count+=n-bisect.bisect_left(A,binresult-ai)
    
ans-=binresult*(count-m)
print(ans)

Solution (Python):
import sys
from itertools import accumulate
 
read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines

import bisect

n,m=map(int,input().split())
A=list(map(int,input().split()))
A.sort()

def hand(x):
  cnt=0
  for i in range(n):
    p=x-A[-i-1]
    k=n-bisect.bisect_left(A,p)
    if k==0:
      break
    cnt+=k
    if cnt>=m:
      break
  return cnt

def main():
  l=0
  h=2*10**5+1
  mid=(l+h)//2
  
  while l+1<h:
    mid=(l+h)//2
    if hand(mid)<m:
      h=mid
    else:
      l=mid
  
  B = list(accumulate(A[::-1]))[::-1]

  ans=0
  cnt=0
  
  
  for i in range(n):
    y=l-A[i]+1
    index=bisect.bisect_left(A,y)
    if n==index:
      continue
    else:
      ans+=(n-index)*A[i]+B[index]
      cnt+=(n-index)
  
  ans+=(m-cnt)*l
  print(ans)

if __name__ == "__main__":
	main()

Solution (Python):
import sys
from itertools import accumulate
 
read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines

import bisect

n,m=map(int,input().split())
A=list(map(int,input().split()))
A.sort()

def hand(x):
  cnt=0
  for i in range(n):
    p=x-A[-i-1]
    k=n-bisect.bisect_left(A,p)
    if k==0:
      break
    cnt+=k
  return cnt

def main():
  l=0
  h=2*10**5+1
  mid=(l+h)//2
  
  while l+1<h:
    mid=(l+h)//2
    if hand(mid)<m:
      h=mid
    else:
      l=mid
  
  B = list(accumulate(A[::-1]))[::-1]

  ans=0
  cnt=0
  
  
  for i in range(n):
    y=l-A[i]+1
    index=bisect.bisect_left(A,y)
    if n==index:
      continue
    else:
      ans+=(n-index)*A[i]+B[index]
      cnt+=(n-index)
  
  ans+=(m-cnt)*l
  print(ans)

if __name__ == "__main__":
	main()

Solution (Python):
import sys
from itertools import accumulate
 
read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines

import bisect

n,m=map(int,input().split())
A=list(map(int,input().split()))
A.sort()

def hand(x):
  cnt=0
  for i in range(n):
    p=x-A[i]
    cnt+=n-bisect.bisect_left(A,p)
  return cnt

def main():
  l=0
  h=2*10**5+1
  mid=(l+h)//2
  
  while l+1<h:
    mid=(l+h)//2
    if hand(mid)<m:
      h=mid
    else:
      l=mid
  
  B = list(accumulate(A[::-1]))[::-1]

  ans=0
  cnt=0
  
  
  for i in range(n):
    y=l-A[i]+1
    index=bisect.bisect_left(A,y)
    if n==index:
      continue
    else:
      ans+=(n-index)*A[i]+B[index]
      cnt+=(n-index)
  
  ans+=(m-cnt)*l
  print(ans)

if __name__ == "__main__":
	main()

Solution (Python):

def nmx(x):
    r = 0
    for a in As:
        r += d2[max(0, x-a)]
    return -r
def bsearch(target, min_i, max_i, func):
    
    if func(max_i) <= target:
        return max_i
    if target < func(min_i):
        return None
    index = (max_i + min_i)//2
    while True:
        if func(index) <= target:
            if target < func(index+1):
                return index
            index, min_i = (index+1 + max_i)//2, index+1
            continue
        index, max_i = (index-1 + min_i)//2, index-1
N, M = map(int, input().split())
As = sorted(list(map(int, input().split())))
mn, mx = As[0], As[-1]

j = 0
n = N
d2 = []
for i in range(mx*2):
    while True:
        if j>=N:
            break
        if i <= As[j]:
            break
        j += 1
        n -= 1
    d2.append(n)


r = bsearch(-M, 1, mx*2, nmx)
r += 1
from itertools import accumulate
aas = list(accumulate([0]+As[::-1]))
rr = 0
c = 0
for a in As[::-1]:
    idx = min(mx*2-1, max(0, r-a))
    rr += a*d2[idx] + aas[d2[idx]]
    c += d2[idx]
rr += (r-1)*(M-c)
print(rr)

Solution (Python):
import sys
 
read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines

import bisect

n,m=map(int,input().split())
A=list(map(int,input().split()))
A.sort()

def hand(x):
  cnt=0
  for i in range(n):
    p=x-A[i]
    cnt+=n-bisect.bisect_left(A,p)
  return cnt

def main():
  l=0
  h=2*10**5+1
  mid=(l+h)//2
  
  while l+1<h:
    mid=(l+h)//2
    if hand(mid)<m:
      h=mid
    else:
      l=mid
  
  B=A[::-1]
  
  for i in range(n-1):
    B[i+1]+=B[i]
  
  B=B[::-1]
  
  ans=0
  cnt=0
  
  
  for i in range(n):
    y=l-A[i]+1
    index=bisect.bisect_left(A,y)
    if n==index:
      continue
    else:
      ans+=(n-index)*A[i]+B[index]
      cnt+=(n-index)
  
  ans+=(m-cnt)*l
  print(ans)

if __name__ == "__main__":
	main()

Solution (Python):
N,M = map(int,input().split())
A = list(map(int,input().split()))
A.sort(reverse=True)





inf = 2*10**5+1
X_top = inf
X_bot = 0 


while X_top - X_bot !=1:  
    X=(X_top+X_bot)//2
    num=0
    
    for i in range(N):
        ok=-1
        ng=N
        h1=A[i]
        
        
        while ng-ok!=1:
            med=(ok+ng)//2
            h2=A[med]
            if h1+h2>=X:
                ok=med
            else:
                ng=med
        num+=ok+1
    
    if num>=M:
        X_bot = X
    else:
        X_top = X
        
ok_list=[0]*N

for i in range(N):
        ok=-1
        ng=N
        h1=A[i]
        X = X_bot
        
        while ng-ok!=1:
            med=(ok+ng)//2
            h2=A[med]
            if h1+h2>=X:
                ok=med
            else:
                ng=med
        ok_list[i]=ok

S=[0]*(N+1)
for i in range(N):
    S[i+1]=S[i]+A[i]

ans=0
for i in range(N):
    ans += A[i]*(ok_list[i]+1)+S[ok_list[i]+1]

if sum(ok_list)+N>M:
    ans-=(sum(ok_list)+N-M)*X
print(ans)

Solution (Python):
import sys
 
read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines

import bisect

n,m=map(int,input().split())
A=list(map(int,input().split()))
A.sort()

def hand(x):
  cnt=0
  for i in range(n):
    p=x-A[i]
    cnt+=n-bisect.bisect_left(A,p)
  return cnt

def main():
  l=0
  h=10**15+3
  mid=(l+h)//2
  
  while l+1<h:
    mid=(l+h)//2
    if hand(mid)<m:
      h=mid
    else:
      l=mid
  
  B=A[::-1]
  
  for i in range(n-1):
    B[i+1]+=B[i]
  
  B=B[::-1]
  
  ans=0
  cnt=0
  
  
  for i in range(n):
    y=l-A[i]+1
    index=bisect.bisect_left(A,y)
    if n==index:
      continue
    else:
      ans+=(n-index)*A[i]+B[index]
      cnt+=(n-index)
  
  ans+=(m-cnt)*l
  print(ans)

if __name__ == "__main__":
	main()

Solution (Python):

"""
方針：

幸福度が一定以上のつなぎ方の数→NlogNで二分探索可能
採用するうち最小の幸福度を NlogNlogNで探索

累積和を用いて合計を算出

2 3
5 2

10 + 7 + 7 = 24

"""

import bisect

def wantover(n): 

    ret = 0

    for i in range(N):

        serchnum = n - A[i]

        ret += (N - bisect.bisect_left(A,serchnum))

    

    if ret >= M:
        return True
    else:
        return False


N,M = map(int,input().split())

A = list(map(int,input().split()))
A.sort()



hpl = 0
hpr = A[-1] * 2 + 1

while hpr - hpl != 1:

    mid = (hpr + hpl) // 2

    if wantover(mid):

        hpl = mid

    else:

        hpr = mid




B = [0] 

for i in range(N):

    B.append(B[-1] + A[-1 - i])




ans = 0
plnum = 0 
for i in range(N):

    i = N-i-1

    ind = bisect.bisect_left(A,hpl - A[i])

    
    
    plnum += N - ind
    
    ans += B[N - ind] + A[i] * (N-ind)


print (ans - hpl * (plnum - M))

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def f(n):
    r = 2
    ret = 1
    for i in range(n, n-r, -1):
        ret *= i
    for i in range(1, r+1):
        ret //= i
    return ret * 2 + n


class Bisect:
    def __init__(self, func):
        self.__func = func

    def bisect_left(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if self.__func(mid) < x:
                lo = mid+1
            else:
                hi = mid
        return lo

    def bisect_right(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if x < self.__func(mid):
                hi = mid
            else:
                lo = mid+1
        return lo

@mt
def slv(N, M, A):
    A.sort(reverse=True)
    print(A)
    b = Bisect(f)

    i = b.bisect_left(M, 1, N)
    if f(i) != M:
        i -= 1
    l = f(i)

    ans = 0
    for j in range(i):
        ans += A[j] * 2
        ans += A[j] * (i-1)

    rem = M - l
    print(i, l, rem)
    j = 0
    while rem != 0:
        ans += A[j] + A[i]
        rem -= 1
        if rem == 0:
            break
        ans += A[j] + A[i]
        rem -= 1
        if rem == 0:
            break
        j += 1


    return ans

import numpy as np
def slv2(N, M, A):
    C = Counter(A)
    B = [C[i] for i in range(2**18)]
    D = np.fft.rfft(B)
    D *= D
    E = list(np.fft.irfft(D).real)
    ans = 0
    c = 0
    i = 2**18 - 1
    while c != M:
        n = int(round(E[i]))
        if n != 0:
            if c + n > M:
                n = M-c
            c += n
            ans += i * n
        i -= 1
        assert i != -1

    return ans

def main():
    N, M = read_int_n()
    A = read_int_n()
    print(slv2(N, M,A))

    
    
    
    


if __name__ == '__main__':
    main()

Solution (Python):
def run(N, M, A):
    '''
    Aiが10^5なので、searchを以下に変えられる
    サイズ10**5のリストで、その満足度を持つ数の件数を事前計算しておけばO(1)で求められる
    '''
    A = sorted(A, reverse=True)
    cnt_A = [len(A)]
    pre_a = 0
    cnt_dict_A = {}
    for a in sorted(A):
        cnt_dict_A[a] = cnt_dict_A.get(a, 0) + 1
    next_cnt = cnt_A[-1]
    for a in sorted(cnt_dict_A.keys()):
        cnt_A.extend([next_cnt]*(a-pre_a))
        pre_a = a
        next_cnt = cnt_A[-1]-cnt_dict_A[a]
    right = A[0] * 2
    left = 0
    while left <= right:
        X = (left + right) // 2
        
        cnt = 0
        for a in A:
            
            if X - a <= A[0]:
                if X - a >= 0:
                    cnt += cnt_A[X - a]
                else:
                    cnt += cnt_A[0]
        if cnt >= M:
            res = X
            left = X + 1
        else:
            right = X - 1
    X = res
    
    sum_A = [0]
    for a in sorted(A):
        sum_A.append(sum_A[-1] + a)
    sum_cnt = 0
    ans = 0
    for a in A:
        cnt = search(A, X - a)
        sum_cnt += cnt
        if cnt > 0:
            ans += cnt * a + sum_A[-1] - sum_A[-cnt-1]
    if sum_cnt > M:
        ans -= X * (sum_cnt - M)
    return ans


def search(A, X):
    '''
    AのリストからX以上となる数値がいくつか探す
    Aはソート済み(降順)
    二分探索で実装O(logN)
    leftとrightはチェック未
    middleはループ終了後チェック済み
    '''
    left = 0
    right = len(A) - 1
    res = 0
    while left <= right:
        middle = (left + right) // 2
        if A[middle] >= X:
            res = middle + 1
            left = middle + 1
        else:
            right = middle - 1
    return res


def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    print(run(N, M, A))


if __name__ == '__main__':
    main()

Solution (Python):
def run(N, M, A):
    A = sorted(A, reverse=True)
    right = A[0] * 2
    left = 0
    while left <= right:
        X = (left + right) // 2
        
        cnt = 0
        for a in A:
            cnt += search(A, X - a)
        if cnt >= M:
            res = X
            left = X + 1
        else:
            right = X - 1
    X = res
    
    sum_A = [0]
    for a in sorted(A):
        sum_A.append(sum_A[-1] + a)
    sum_cnt = 0
    ans = 0
    for a in A:
        cnt = search(A, X - a)
        sum_cnt += cnt
        if cnt > 0:
            ans += cnt * a + sum_A[-1] - sum_A[-cnt-1]
    if sum_cnt > M:
        ans -= X * (sum_cnt - M)
    return ans


def search(A, X):
    '''
    AのリストからX以上となる数値がいくつか探す
    Aはソート済み(降順)
    二分探索で実装O(logN)
    leftとrightはチェック未
    middleはループ終了後チェック済み
    '''
    left = 0
    right = len(A) - 1
    res = 0
    while left <= right:
        middle = (left + right) // 2
        if A[middle] >= X:
            res = middle + 1
            left = middle + 1
        else:
            right = middle - 1
    return res


def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    print(run(N, M, A))


if __name__ == '__main__':
    main()