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



Sample input:
5 3
10 14 19 34 33


Sample output:
202

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

import bisect
from itertools import accumulate

N, M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
A.sort()

left = -1
right = 1 + 2 * 10 ** 5

def shake(x):
    cnt = 0
    for i in A:
        cnt += N - bisect.bisect_left(A, x - i)
    if cnt >= M:
        return 1
    else:
        return 0

while True:
    mid = (left + right) // 2
    if shake(mid):
        if not shake(mid + 1):
            X = mid
            break
        else:
            left = mid
    else:
        if shake(mid - 1):
            X = mid - 1
            break
        else:
            right = mid

happy = 0
cumsum_A = [0] + list(accumulate(A))

for j in A:
    idx = bisect.bisect_right(A, X - j)
    cnt = N - idx
    happy += cumsum_A[-1] - cumsum_A[idx] + cnt * j
    M -= cnt

happy += M * X

print(happy)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

import bisect
from itertools import accumulate

N, M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
A.sort()

left = -1
right = 1 + 2 * 10 ** 5

def shake(x):
    cnt = 0
    for i in A:
        cnt += N - bisect.bisect_left(A, x - i)
    if cnt >= M:
        return 1
    else:
        return 0

while True:
    mid = (left + right) // 2
    if shake(mid):
        if not shake(mid + 1):
            X = mid
            break
        else:
            left = mid
    else:
        if shake(mid - 1):
            X = mid - 1
            break
        else:
            right = mid

happy = 0
cumsum_A = list(accumulate(A))

for j in A:
    idx = bisect.bisect_right(A, X - j)
    cnt = N - idx
    if cnt == N:
        happy += cumsum_A[-1] + cnt * j
    else:
        happy += cumsum_A[-1] - cumsum_A[idx - 1] + cnt * j
    M -= cnt

happy += M * X

print(happy)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

import bisect
from itertools import accumulate

N, M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
A.sort()

left = -1
right = 10 ** 6

def shake(x):
    cnt = 0
    for i in A:
        cnt += N - bisect.bisect_left(A, x - i)
    if cnt >= M:
        return 1
    else:
        return 0

while True:
    mid = (left + right) // 2
    if shake(mid):
        if not shake(mid + 1):
            X = mid
            break
        else:
            left = mid
    else:
        if shake(mid - 1):
            X = mid - 1
            break
        else:
            right = mid

happy = 0
cumsum_A = list(accumulate(A))

for j in A:
    idx = bisect.bisect_right(A, X - j)
    cnt = N - idx
    if cnt == N:
        happy += cumsum_A[-1] + cnt * j
    else:
        happy += cumsum_A[-1] - cumsum_A[idx - 1] + cnt * j
    M -= cnt

happy += M * X

print(happy)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
# sys.setrecursionlimit(10000000)
INF = 1<<32


from bisect import bisect_left, bisect_right

def solve(N: int, M: int, A: "List[int]"):
        
    def binary_search(left: int, right: int):
        s = 0
        c = 0
        mi = INF

        while right-left > 1 or c < M:
            # print("test: ", left, " ", right)
            mid = (left+right)//2
            # print("mid: ", mid)
            # mid以上の価値の握手の個数を求める
            # s = []
            s = 0
            c = 0
            mi = INF
            for i in range(N):
                p = bisect_left(A, mid-A[i])
                if p != N:
                    mi = min(mi, A[i]+A[p])
                # print(A[i], A[p:], aq[N]-aq[p],  A[i]*(N-p))
                s += aq[N]-aq[p]
                s += A[i]*(N-p)
                c += N-p
                
            # mid以上の握手の個数がM以上か否か
            if c > M:
                left = mid

            else:
                right = mid
        
        if c > M:
            s -= (c-M)*mi

        return s

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

    print(binary_search(1, A[-1]*2))
    
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, M, A)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
import sys
input = sys.stdin.readline


def main():
    N,M = map(int, input().split())
    A = np.array(sorted([int(i) for i in input().split()]))

    left = 0
    right = A[-1] * 2 + 5
    while right - left > 1:
        x = (left + right) // 2

        count = N**2 - np.searchsorted(A, x-A).sum()

        if count >= M:
            left = x
        else:
            right = x

    bound = np.searchsorted(A, left-A)
    count = N**2 - bound.sum()
    diff = count - M
    ans = ((N - bound) * A * 2).sum() - diff * left

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
######################
# AC: ms(PyPy)
# AC: ms(Python3)
######################

from bisect import bisect_left
import sys
input = sys.stdin.readline


def main():
    N,M = map(int, input().split())
    A = [int(i) for i in input().split()]

    A.sort()

    left = 0
    right = A[-1] * 2 + 5
    while right - left > 1:
        X = (left + right) // 2

        count = 0
        for a in A:
            i = bisect_left(A, X-a)
            count += (N - i)

        if count >= M:
            left = X
        else:
            right = X

    count = 0
    num = []
    append = num.append
    for a in A:
        i = bisect_left(A, left-a)
        count += (N - i)
        append(N - i)

    diff = count - M
    ans = 0
    for i, a in zip(num, A):
        ans += i * a

    print(ans * 2 - diff * left)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    import numpy as np
    n,m=map(int,input().split())
    A=list(map(int,input().split()))
    A.sort()
    A=np.array(A)

    def cnt_shake(x): #握手の組であって合計パワーがx以上となる組みの数
        return n**2-np.searchsorted(A,x-A).sum()
  
    right=2*(10**5)+1
    left=-1
    while right-left>1:
        mid=(left+right)//2
        if cnt_shake(mid)<m:
            right=mid
        else:
            left=mid
    
    C=n-np.searchsorted(A,right-A)
    B=np.cumsum(A[::-1])
    cnt=C.sum()
    print(np.sum(A*C)+left*(m-cnt)+B[C[np.where(C>0)]-1].sum())
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import numpy as np
    n,m=map(int,input().split())
    A=list(map(int,input().split()))
    A.sort()
    A=np.array(A)

    def cnt_shake(x): #握手の組であって合計パワーがx以上となる組みの数
        return n**2-np.searchsorted(A,x-A).sum()
  
    right=2*10**5+1
    left=-1
    while right-left>1:
        mid=(left+right)//2
        if cnt_shake(mid)<m:
            right=mid
        else:
            left=mid
    
    border=left  #border以上の握手をする
    C=n-np.searchsorted(A,border+1-A)
    B=np.cumsum(A[::-1])
    cnt=C.sum()
    s=np.sum(A*C)+border*(m-cnt)+B[C[np.where(C>0)]-1].sum()
    print(s)
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import numpy as np
    n,m=map(int,input().split())
    A=list(map(int,input().split()))
    A.sort()
    A=np.array(A)

    def cnt_shake(x): #握手の組であって合計パワーがx以上となる組みの数
        return n**2-np.searchsorted(A,x-A).sum()
  
    right=10**10*1
    left=-10**10-1
    while right-left>1:
        mid=(left+right)//2
        if cnt_shake(mid)<m:
            right=mid
        else:
            left=mid
    
    border=left  #border以上の握手をする
    C=n-np.searchsorted(A,border+1-A)
    B=np.cumsum(A[::-1])
    #print(border,A,B,C)

    s,cnt=0,0
    for i in range(n):
        if C[i]>0:
          cnt+=C[i]
          s+=B[C[i]-1]+A[i]*C[i]
    s+=border*(m-cnt)

    print(s)
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    N, M = map(int, input().split())
    A = sorted(list(map(int, input().split())), reverse=True)
    def helper(x):
        p = len(A) - 1
        t = 0
        for a in A:
            while p >= 0 and A[p] + a < x:
                p -= 1
            t += p + 1
        return t
    l, r = 0, A[0] * 2 + 1
    while r - l > 1:
        m = (l + r) // 2
        if helper(m) > M:
            l = m
        else:
            r = m
    k = sum(A)
    p = len(A) - 1
    t = (M - helper(l)) * l
    for a in A:
        while p >= 0 and A[p] + a < l:
            k -= A[p]
            p -= 1
        t += a * (p + 1) + k
    print(t)

main()

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,m = inpl()
a = sorted(inpl())
ng = 10**9+1
ok = -1
def sol(x):
    cnt = 0
    for i,t in enumerate(a):
        tmp = x - t
        c = bisect.bisect_left(a,tmp)
        cnt += n-c
    return True if cnt >= m else False

while ng-ok > 1:
    mid = (ng+ok)//2
    if sol(mid):
        ok = mid
    else: ng = mid
    # print(ok,ng)
# print(ok)
res = 0
cnt = 0
revc = [0]
for i in range(n)[::-1]:
    revc.append(revc[-1] + a[i])
# print(revc)
for i in range(n):
    j = n-bisect.bisect_left(a,ok-a[i])
    res += j*a[i] + revc[j]
    cnt += j
res -= (cnt-m) * ok
print(res)

Submission status: Accepted

Solution code:
from bisect import bisect_left
n, m = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
maxA = max(A)
cnt = [0] * (maxA * 2 + 2)
rui = [n] * (maxA * 2 + 2)

for a in A:
  cnt[a] += 1

accum = 0  
for i in range(maxA * 2 + 1):
  accum += cnt[i]
  rui[i + 1] -= accum 
  
# 左手を決めた時(left)に、幸福度がx 以上となる組み合わせの数を返す
def f(x):
  ret = 0
  for left in A:
    ret += rui[max(x - left, 0)]
  return ret
  
lo = 0
hi = maxA * 2 + 1
while hi - lo > 1:
  md = (lo + hi) // 2
  if f(md) >= m:
    lo = md
  else:
    hi = md 
# もとまる lo が m 通り以上握手ができる最小の数。
    
ruiA = [0] * (n + 1)
for i in range(n):
  ruiA[i + 1] = ruiA[i] + A[i]

ans = 0
cnt = 0
for i in range(n):
  pos = bisect_left(A, lo - A[i])
  cnt += n - pos
  ans += ruiA[-1] - ruiA[pos] + A[i] * (n - pos)
if cnt == m:
  print(ans)
else: # m個よりも多い分を引く
  rem = cnt - m
  print(ans - rem * lo)

Submission status: Accepted

Solution code:
import bisect
from itertools import accumulate
N,M = map(int,input().split())
A = sorted(list(map(int,input().split())))
A2 = [0]+list(accumulate(A))
def judge(mid):
    count = 0
    for i in range(N):
        border = mid - A[i]
        ind = bisect.bisect_left(A,border)
        count += N-ind
    if count < M:
        return True
    else:
        return False
mina = 0
maxa = 2*(10**5) + 1
while maxa-mina > 1:
    mid = (maxa+mina)//2
    if judge(mid):
        maxa = mid
    else:
        mina = mid
count = 0
ans = 0
for i in range(N):
    border = maxa - A[i]
    ind = bisect.bisect_left(A,border)
    count += N-ind
    ans += A[i]*(N-ind) + A2[N]-A2[ind]
if count == M:
    print(ans)
else:
    rem = M-count
    print(ans+rem*mina)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = [int(c) for c in input().split()]
A.sort(reverse=True)
B = A[::-1]
l = 0
r = 10**6
def f(m):
  cnt = 0
  j = 0
  for i in range(N):
    while j<N:
      if A[i]+B[j]>=m:
        cnt += N-j
        break
      j += 1
  return cnt>=M
while l+1<r:
  n = (l+r)//2
  if f(n):
    l = n
  else:
    r = n
C = [0]
for i in range(N):
  C += [C[-1]+B[i]]
ans = 0
j = 0
m = 0
flag = False
for i in range(N):
  while j<N:
    if A[i]+B[j]>l:
      ans += C[-1]-C[j]+A[i]*(N-j)
      m += N-j
      break
    j += 1
ans += (M-m)*l
print(ans)

Submission status: Accepted

Solution code:

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

MAX = 10**10 + 10

# Ai+Ajを列挙して大きいほうからM番目となるスコアSを求める
# その後S以上となるスコアを加算して合計値を求める

from bisect import bisect_left

def judge(x,key):
    # スコアx以上となるのがkey個以上あるか？
    
    num = 0
    
    for i in range(N):
        eidx = bisect_left(A,x-A[i])
        num += N-eidx
    
    if num >= key:
        return True
    else: 
        return False


def meguru(key):
    ok = -1
    ng = MAX
    
    while (abs(ok-ng)>1):
        mid = (ok+ng)//2
        if judge(mid,key):
            ok = mid
        else:
            ng = mid
    return ok


D = meguru(M)
ans = 0

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

num = 0

for i in range(N):
    eidx = bisect_left(A,D+0.5-A[i])
    ans += A[i] * (N-eidx)
    ans += ruisekiwa[N] - ruisekiwa[eidx]
    num += N-eidx

if num<M:
    ans += (M-num)*D

print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left
from itertools import accumulate

N,M = map(int,input().split())
A = sorted([int(i) for i in input().split()])

# 判定
def is_under_M(x:int):
    cnt = 0
    for i in range(N):
        # 幸福度x以上の個数を求める
        pos = bisect_left(A, x - A[i])
        cnt += N - pos
    return cnt < M

# 二分探索
ng, ok = 0, 2*(10**5)+1
while ok - ng > 1:
    mid = (ok + ng) // 2
    if is_under_M(mid):
        ok = mid
    else:
        ng = mid
# ng, ok = X-1, X

# Aの累積和
Aacum = tuple(accumulate([0] + A))

ans = 0
for i in range(N):
    # 幸福度ok以上の個数を求める
    pos = bisect_left(A, ok - A[i])
    cnt = N - pos

    ans += cnt * A[i] + (Aacum[N] - Aacum[pos])
    M -= cnt

ans += M * ng

print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

MOD = 10 ** 9 +7

n,m = map(int,readline().split())
a = np.array(read().split(),np.int64)

a.sort()

def shake_cnt(x):
    X=np.searchsorted(a,x-a)
    return n*n-X.sum()

left = 0
right = 10 ** 6
while left+1 <right:
    x = (left + right)//2
    if shake_cnt(x) >= m:
        left = x
    else:
        right = x

left,right

X=np.searchsorted(a,right-a)
Acum = np.zeros(n+1,np.int64)
Acum[1:] = np.cumsum(a)

shake = n * n -X.sum()
happy = (Acum[-1]-Acum[X]).sum()+(a*(n-X)).sum()

happy += (m-shake)*left
print(happy)

Submission status: Accepted

Solution code:
import bisect
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
r=a[n-1]*2+1
l=0
while r-l>=2:
	mid=(l+r)//2
	#mid以上はいくつあるか
	#答えはl以上r未満
	cnt=0
	for i in range(n):
		cnt+=n-bisect.bisect_left(a,mid-a[i])
	if cnt>=k:
		l=mid
	else:
		r=mid
#lだとk個以上　rだとk個未満
ans,p,=0,0
b=[0]
for i in range(n):
	p+=a[i]
	b.append(p)
for i in range(n):
	q=bisect.bisect_left(a,r-a[i])
	ans+=b[n]-b[q]
	ans+=a[i]*(n-q)
	k-=n-q
ans+=l*k
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right
from itertools import accumulate

N,M = map(int,input().split())
A = sorted([int(i) for i in input().split()])

# 判定
def is_under_M(x:int):
    cnt = 0
    for i in range(N):
        # 幸福度x以上の個数を求める
        pos = bisect_left(A, x - A[i])
        cnt += N - pos
    return cnt < M

# 二分探索
ng, ok = 0, 2*(10**5)+1
while ok - ng > 1:
    mid = (ok + ng) // 2
    if is_under_M(mid):
        ok = mid
    else:
        ng = mid
# ng, ok = X-1, X

# Aの累積和
Aacum = tuple(accumulate([0] + A))

ans = 0
for i in range(N):
    # 幸福度ng以上の個数を求める
    pos = bisect_left(A, ng - A[i])
    cnt = N - pos

    ans += cnt * A[i] + (Aacum[N] - Aacum[pos])
    M -= cnt

ans += M * ng

print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
import bisect
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
r=a[n-1]*2+1
l=0
while r-l>=2:
	mid=(l+r)//2
	#mid以上はいくつあるか
	#答えはl以上r未満
	cnt=0
	for i in range(n):
		cnt+=n-bisect.bisect_left(a,mid-a[i])
	if cnt>=k:
		l=mid
	else:
		r=mid
#lだとk個以上　rだとk個未満
ans,p,=0,0
b=[0]
for i in range(n):
	p+=a[i]
	b.append(p)
for i in range(n):
	q=bisect.bisect_left(a,r-a[i])
	ans+=b[n]-b[q]
	ans+=a[i]*(n-q)
	k-=n-q
ans+=l*k
print(ans)

Submission status: Accepted

Solution code:
import bisect

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

# ある値以上のAiがいくつあるかの情報を累積和で保持
num_A_or_more = [0]*(10**5)
for a in A:
  num_A_or_more[a-1] += 1


for i in range(1, 10**5):
  j = 10**5 - i
  num_A_or_more[j-1] += num_A_or_more[j]


# x以上となる手の組み合わせがM種類以上あるかどうかを判定
def check(x):
  count = 0
  for a in A:
    idx = max(x-a-1, 0)
    if idx >= 10**5:
      continue
    count += num_A_or_more[idx]
  
  return count>=M


# 2分探索でM種類以上の手の組み合わせがある満足度の最大値を求める
left = 0
right = 2*10**5 + 1
mid = (left + right) // 2
while right - left > 1:
  if check(mid):
    left = mid
  else:
    right = mid
    
  mid = (left + right)//2

# これがM種類以上の手の組み合わせがある満足度の最大値
x = left


# 降順に並べなおして累積和を求めておく
rev_A = A[::-1]
accum_A = [rev_A[0]]
for i, a in enumerate(rev_A):
  if i == 0:
    continue
  accum_A.append(accum_A[-1] + a)

ans = 0
count = 0
surplus = 2*10**5 # M種類を超えた場合は、一番小さくなる握手の組を最後に削る
for ai in rev_A:
  idx = bisect.bisect_left(A, x-ai)
  if idx == N:
    break
  ans += (N-idx)*ai + accum_A[N-idx-1]
  count += N - idx
  surplus = min(surplus, ai+A[idx])


print(ans - (count-M)*surplus)

Submission status: Accepted

Solution code:
import bisect


N, M = map(int, input().split())
Al = list(map(int, input().split()))
Al.sort() # 左手で握手する人のリスト
Ar = Al.copy()[::-1] # 右手で握手する人のリスト

def count_large_2(L1, L2, x):
  # L1.sort()
  # L2.sort(reverse=True)
  N1, N2 = len(L1), len(L2)
  i = j = 0
  c = 0
  while i<N1 and j<N2:
    if L1[i]+L2[j] >= x:
      c += 1
      j += 1
      if j >= N2:
        c += (N1-i-1) * N2
    else:
      i += 1
      if i>=N1:
        continue
      c += j
  return c

left = 0 # True
right = Al[-1]*2 + 1 # False
while left+1 < right:
  mid = (left + right) // 2
  if count_large_2(Al, Ar, mid) >= M:
    left = mid
  else:
    right = mid


x = left
accum_A = [Ar[0]]
for i, a in enumerate(Ar):
  if i == 0:
    continue
  accum_A.append(accum_A[-1] + a)


ans = 0
count = 0
surplus = 2*10**5
for ai in Ar:
  idx = bisect.bisect_left(Al, x-ai)
  if idx == N:
    break
  ans += (N-idx)*ai + accum_A[N-idx-1]
  count += N - idx
  surplus = min(surplus, ai+Al[idx])
 
 
print(ans - (count-M)*surplus)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, atan, degrees
from itertools import permutations, combinations, product, accumulate
# とけてない
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect
import heapq

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
A = LIST()
A.sort(reverse=True)
B = [-x for x in A]

l = 0
r = 2*10**5+1

ans = 0

def count(x):  # 和がx以上になる組み合わせの個数
	cnt = 0
	for y in A:  # 左手
		left = -(x-y)
		cnt += bisect(B, left)

	return cnt

while l+1 != r:
	m = (l+r)//2
	if count(m) < M:
		r = m
	else:
		l = m
ans = 0

A_acc = list(accumulate([0]+sorted(A, reverse=True)))
cnt = 0
for y in A:
	left = -(l-y)
	idx = bisect(B, left)
	ans += A_acc[idx]+idx*y
	cnt += idx
ans -= (cnt-M)*l

print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
A=sorted(map(int,input().split()))
B=[0]
for a in A:
    B.append(B[-1]+a)
def f(n):
    a,b=0,0
    r=N-1
    for l in range(N):
        while r>-1 and A[l]+A[r]>=n:
            r-=1
        a+=N-1-r
        b+=A[l]*(N-1-r)+B[N]-B[r+1]
    return a,b
l,r=0,10**6
x=0
while l+1<r:
    t=(l+r)//2
    a,b=f(t)
    if a<M:
        r=t
    else:
        x=max(x,t)
        l=t
a,b=f(x)
print(b-x*(a-M))

Submission status: Accepted

Solution code:
from bisect import bisect_left
from itertools import accumulate
N, M = map(int, input().split())
A = sorted(list(map(int, input().split())))

# にぶたん: Ai + Aj が X以上となるようなものがM通り以上あるか？
ok, ng = 0, 2 * 10 ** 5 + 1
while abs(ok - ng) > 1:
    X = (ok + ng) // 2
    cnt = 0
    for a in A:
        cnt += N - bisect_left(A, X - a)
        if cnt >= M:
            ok = X
            break
    else:
        ng = X

# 規定値以上のものを全てとる（ギリギリK個を超える）
ans = 0
cnt = 0
A_acc = [0] + list(accumulate(A[::-1]))[::-1]

for a in A:
    i = N - bisect_left(A, ok - a)
    cnt += i
    ans += a * i + A_acc[-i]

# 取りすぎた分を削る
ans -= max(0, cnt - M) * ok
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
A=sorted(list(map(int,input().split())))

# M回の握手の幸福度最大化
# X以上になる握手を全て採用したときに、M通りを越える
# Xの最大値を求める

import bisect

ok=-1
ng=(10**10)+1

# x以上の握手をm通り以上作れるか
def isOk(x,m):
  cnt=0
  # 左手をループする
  for i in range(len(A)):
    left=A[i]
    minright=x-left
    # minright以上の数を数える
    cnt+=n-bisect.bisect_left(A,minright)
    if cnt>=m:
      return True
  return cnt>=m

while abs(ok-ng)>1:
  mid=abs(ok+ng)//2
  if isOk(mid,m):
    ok=mid
  else:
    ng=mid

x=ok
# x以上となる幸福度を足し合わせる
# 足し合わせた握手がMを越える場合、xぴったりを足し過ぎている

# 効率化のため累積和を作成
Asum=[0]+A
for i in range(1,len(Asum)):
  Asum[i]=Asum[i-1]+Asum[i]
  
# Aの添字i以降を全て足すときは、
# Asum[-1]-Asum[i]

ans=0
cnt=0
for i in range(len(A)):
  left=A[i]
  minright=x-left
  start=bisect.bisect_left(A,minright)
  cnt+=n-start
  ans+=left*(n-start)+(Asum[-1]-Asum[start])
  
if cnt>m:
  ans-=(cnt-m)*x
  
print(ans)

Submission status: Accepted

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=1
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
mod=1000000007

#+++++


def count_al(al, vv):
	#'''
	#vvv以上を集めた場合、何要素選択されるか。
	#'''
	rui=0
	for v in al:
		r = get_ok_index(v, al, vv)
		rui += r
	return rui

def get_ok_index(v,al,ok_value):
	#'''
	#ok_value以上の要素数を返す。
	#'''
	if v+al[0] < ok_value:
		return 0
	if v + al[-1] >= ok_value:
		return len(al)
	ok=0
	ng=len(al)
	while ok + 1 < ng:
		#pa((ok,ng))
		m=(ok+ng)//2
		if v+al[m] >= ok_value:
			ok = m
		else:
			ng = m
		#pa((ok,ng))
	return ok+1
	

def main():
	n, m = IN()
	al = list(IN())
	al.sort(reverse=True)
	if m == n*n:
		ret= sum(al) * n * 2
	
	ruisekiwa=al[:]
	for i,v in enumerate(al[1:],1):
		ruisekiwa[i]=ruisekiwa[i-1]+v
	#pa(ruisekiwa)
		
	ok=al[0]*10
	ng=0
	
	while ok  > ng + 1:
		vv = (ok + ng)//2
		cc = count_al(al, vv)
		#pa(('ok,ng,vv,cc',ok,ng,vv,cc))
		if cc <= m:
			ok = vv
		else:
			ng = vv
	#pa(('ok',ok))
	
	ret=0
	for v in al:
		ok_id = get_ok_index(v, al, ok)-1
		#pa(ok_id)
		if ok_id==-1:
			continue
		ret += ruisekiwa[ok_id]+v*(ok_id+1)
	
	ret += (ok - 1)*(m-count_al(al,ok))
	print(ret)
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7

n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
left=0
right=(10**5)*2+5
s=ruiseki(a)

ans=0
while 1:
    mid=(left+right)//2
    cnt=0
    for i in range(n):
        tmp=bisect.bisect_left(a,mid-a[i])
        cnt+=n-tmp
    
    if cnt<m:
        right=mid
    else:
        left=mid
    
    # print(left,right,mid)
    if right-left<=1:
        break
for i in range(n):
    tmp=bisect.bisect(a,left-a[i])
    cnt=n-tmp
    ans+=cnt*a[i]+s[n]-s[tmp]
    m-=cnt
ans+=m*left
print(ans)

Submission status: Accepted

Solution code:
import bisect

n, m=map(int, input().split())
a=list(map(int, input().split()))
a.sort()
s=[0 for _ in range(n+1)]
for i in range(n):
    s[i+1]=s[i]+a[i]

def calc(x):
    tot=0
    num=0
    for i in range(n):
        j=bisect.bisect_left(a, x-a[i])
        num+=n-j
        tot+=s[n]-s[j]
        tot+=a[i]*(n-j)
    return [tot, num]

l=0
r=(10**5)*2+5
while l+1<r:
    c=(l+r)//2
    if calc(c)[1]>=m:
        l=c
    else:
        r=c
p=calc(l)
ans=p[0]
ans-=(p[1]-m)*l
print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()
A = np.array(lr())
A.sort()

def shake_cnt(x):
    Y = np.searchsorted(A, x-A)
    return N*N - Y.sum()

right = 10 ** 6
left = 0
while right > left + 1:
    mid = (right+left) // 2
    if shake_cnt(mid) >= M:
        left = mid
    else:
        right = mid

Acum = np.zeros(N+1, np.int64)
Acum[1:] = A.cumsum()
Y = np.searchsorted(A, right-A)
happy = (Acum[-1]-Acum[Y]).sum() + (A * (N-Y)).sum()
happy += left * (M-shake_cnt(right))
print(happy)
# 32

Submission status: Accepted

Solution code:
from bisect import bisect_left
from itertools import accumulate

N, M = map(int, input().split())
A = sorted(list(map(int, input().split())))

Acum = [0] + list(accumulate(A))

left = 0
right = max(A) * 2 + 1

while left + 1 < right:
  mid = (left + right) // 2
  tmp = 0
  for i in range(N):
    bi = bisect_left(A, mid - A[i])
    tmp += N - bi
  if tmp <= M:
    right = mid
  else:
    left = mid

cnt = 0
answer = 0
for i in range(N):
  bi = bisect_left(A, right - A[i])
  cnt += N - bi
  answer += Acum[N] - Acum[bi] + A[i] * (N - bi)

print(answer + (M - cnt) * left)

Submission status: Accepted

Solution code:
from bisect import bisect_left
from itertools import accumulate

N, M = map(int, input().split())
A = sorted(list(map(int, input().split())))

Acum = [0] + list(accumulate(A))

left = 0
right = 10 ** 10 + 1

while left + 1 < right:
  mid = (left + right) // 2
  tmp = 0
  for i in range(N):
    bi = bisect_left(A, mid - A[i])
    tmp += N - bi
  if tmp <= M:
    right = mid
  else:
    left = mid

cnt = 0
answer = 0
for i in range(N):
  bi = bisect_left(A, right - A[i])
  cnt += N - bi
  answer += Acum[N] - Acum[bi] + A[i] * (N - bi)

print(answer + (M - cnt) * left)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
a = list(map(int,input().split()))
a.sort()

scale = 20
h = 0
gauge = 2 ** scale
import bisect
while gauge > 0:
  h += gauge
  tmp = 0
  for i in range(n):
    b = bisect.bisect_left(a,h-a[i])
    tmp += n - b
  if tmp >= m:
    pass
  else:
    h -= gauge
  gauge //= 2
#print(h)

ans = 0
num = 0
cum = [0]
for i in range(n):
  cum.append(cum[-1]+a[-1-i])
cum.reverse()
for i in range(n):
  b = bisect.bisect_left(a,h-a[i])
  ans += cum[b]
  ans += a[i] * (n-b)
  num += n - b
  #print(b,ans,num)
ans -= (num-m) * h
#print(cum)
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
N, M = list(map(int, input().split()))
A = [int(_) for _ in input().split()]
x = np.zeros(2 ** 18)
for a in A:
  x[a] += 1

y = np.fft.fft(x)

for k in range(len(y)):
  y[k] *= y[k]

x = np.fft.ifft(y).real

happiness = 0
for i in reversed(range(0, len(x))):
  happiness += i * min(int(x[i] + 0.5), M)
  M -= int(x[i] + 0.5)
  if M <= 0:
    break

print(happiness)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
import cmath
pi = cmath.pi
exp = cmath.exp

def fft(a, inverse=False):
    n = len(a)
    h = n.bit_length() - 1

    # Swap
    for i in range(n):
        j = 0
        for k in range(h):
            j |= (i >> k & 1) << (h - 1 - k)
        if i < j:
            a[i], a[j] = a[j], a[i]

    # Butterfly calculation
    if inverse:
        sign = 1.0
    else:
        sign = -1.0
    b = 1
    while b < n:
        for j in range(b):
            w = exp(sign * 2.0j * pi / (2.0 * b) * j)
            for k in range(0, n, b*2):
                s = a[j + k]
                t = a[j + k + b] * w
                a[j + k] = s + t
                a[j + k + b] = s - t
        b *= 2

    if inverse:
        for i in range(n):
            a[i] /= n

    return a

def ifft(a):
    return fft(a, inverse=True)

def convolve(f, g):
    n = 2**((len(f) + len(g) - 1).bit_length())
    f += [0] * (n - len(f))
    g += [0] * (n - len(g))
    F = fft(f)
    G = fft(g)
    FG = [Fi * Gi for Fi, Gi in zip(F, G)]
    fg = [int(item.real + 0.5) for item in ifft(FG)]
    return fg

if __name__ == "__main__":
    n, m = map(int, input().split())
    a = [int(item) for item in input().split()]
    max_a = max(a)
    freq = [0] * (max_a + 1)
    for item in a:
        freq[item] += 1
    f = freq[:]; g = freq[:]
    fg = convolve(f, g)
    total = sum(a) * n * 2
    cnt = n * n - m
    for i, item in enumerate(fg):
        use = min(cnt, item)
        total -= i * use
        cnt -= use
        if cnt == 0:
            break
    print(total)