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

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, m = list(map(int, readline().split()))
    a = list(map(int, readline().split()))
    a.sort()
    a_desc = a[::-1]

    ok = 0
    ng = 2 * max(a) + 1

    while abs(ng - ok) > 1:
        mid = (ok + ng) // 2
        count = 0
        i = 0
        for elem in a:
            while i < n:
                if elem + a_desc[i] >= mid:
                    i += 1
                else:
                    break
            count += i
        if count >= m:
            ok = mid
        else:
            ng = mid

    from itertools import accumulate

    a_cum = list(accumulate(a_desc))
    a_cum = a_cum[::-1] + [0]
    ans = 0
    j = n
    cnt_over = 0

    for elem in a:
        while j > 0:
            if elem + a[j - 1] > ok:
                j -= 1
            else:
                break
        cnt_over += (n - j)
        ans += a_cum[j]
        ans += elem * (n - j)

    ans += ok * (m-cnt_over)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

import numpy as np

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


def check(mid):
    mid = np.searchsorted(a, mid - a)
    return n * n - mid.sum() >= m


left = 0
right = 10 ** 6
while left + 1 < right:
    mid = (left + right) // 2
    if check(mid):
        left = mid
    else:
        right = mid

mid = np.searchsorted(a, right - a)
cumsum = np.zeros(n + 1, np.int64)
cumsum[1:] = np.cumsum(a)
ans = (cumsum[-1] - cumsum[mid]).sum() + (a * (n - mid)).sum() + (m - n * n + mid.sum()) * left
print(ans)

Submission status: Accepted

Solution code:

INF = int(1e9)

def main():
    n, m = map(int, input().split())
    a = [int(i) for i in input().split()]
    a.sort()
    s = [0]
    for i in range(n):
        s.append(s[i]+a[i])
    #Xより大きい要素の数を数える
    def counter(x):
        count = 0
        for i in range(n):
            l = -1
            r = n
            while r-l>1:
                mid = (l+r)//2
                if a[i] + a[mid] > x:
                    r = mid
                else:
                    l = mid
            count += n-r
        return count
    
    #Xより大きい要素数がm個未満であるXのうち最大のものを探す
    l = 0 
    r = INF
    while r-l>1:
        mid = (l+r)//2
        if counter(mid) < m:
            r = mid
        else:
            l = mid

    #lより大きい要素の総和を求める 
    def sigma(x):
        cnt = 0
        sgm = 0
        for i in range(n):
            l = -1
            r = n
            while r-l >1:
                mid = (l+r)//2
                if a[i]+a[mid]>x:
                    r = mid
                else:
                    l = mid
            cnt += n-r
            sgm += a[i] * (n-r) + (s[n]-s[r])
        return (sgm, cnt)

    sgm, cnt = sigma(l)
    ans = sgm+(m-cnt)*r
    print(ans)
main()

Submission status: Accepted

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

a_sum = [0] * (n+1)
for i in range(n):
    a_sum[i+1] = a_sum[i] + a[i]

min_ = 0
max_ = 2*10**5+1

for _ in range(50):
    tmp = (min_+max_)//2
    i,j = 0,n-1
    m_tmp = 0
    while(True):
        if(a[i] + a[j] >= tmp):
            m_tmp += n-i
            j -= 1
        else:
            i += 1

        if(i >= n)|(j < 0):
            break
    if(m_tmp >= m):
        min_ = tmp
    else:
        max_ = tmp

    if(max_-min_ == 1):
        break

tmp = min_
i,j = 0,n-1
m_tmp = 0
ans = 0
while(True):
    if(a[i] + a[j] >= tmp):
        m_tmp += n-i
        ans += a[j] * (n-i) + a_sum[-1] - a_sum[i]
        j -= 1
    else:
        i += 1

    if(i >= n)|(j < 0):
        break

ans -= min_ * (m_tmp - m)
print(ans)

Submission status: Accepted

Solution code:
#python3
from bisect import bisect_left
INF = int(1e9)

def main():
    n, m = map(int, input().split())
    a = [int(i) for i in input().split()]
    a.sort()
    ac = [0]
    for i in range(n):
        ac.append(ac[i]+a[i])

    def chk(x):
        cnt = 0
        for i in range(n):
            pos = bisect_left(a, x - a[i])
            cnt += (n-pos)
        return (cnt < m)

    l = 0
    r = INF
    while r-l > 1: 
        mid = (l + r)//2
        if chk(mid):
            r = mid
        else:
            l = mid

    cnt = 0
    sgm = 0
    for i in range(n):
        pos = bisect_left(a, r - a[i])
        cnt += (n-pos) 
        sgm += a[i] * (n-pos) + (ac[n] - ac[pos]) 

    print(sgm+(m-cnt)*l)
main()

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans






N,M = m()

a = l()

a.sort()

aaa = s(a)



po = [0 for i in range(10**5+2)]
ans = 0
for i in range(N):
    po[a[i]] += 1
for i in range(10**5,-1,-1):
    po[i] += po[i+1]
ll = 0
rr = 10**5 * 2 + 1

while True:
    mid = (ll+rr)//2
    if mid == ll:
        co = 0
        for i in range(N):
            ui = a[i]
            if mid > ui + 10**5:
                continue
            elif ui >= mid:
                co += N
            else:
                co += po[mid-ui]
        cco = 0
        mid = rr

        for i in range(N):
            ui = a[i]
            if mid > ui + 10**5:
                continue
            elif ui >= mid:
                cco += N
            else:
                cco += po[mid-ui]

        if cco == M:
            mid = rr
            co=cco

        else:
            mid = ll

        break

    co = 0
    for i in range(N):
        ui = a[i]
        if mid > ui + 10**5:
            continue
        elif ui >= mid:
            co += N
        else:
            co += po[mid-ui]
    
    if co < M:
        rr = mid                 
    else:
        ll = mid


a.sort(reverse = True)
dp = [0]

ans -= mid * (co - M)



for i in range(N):
    dp.append(dp[-1]+a[i])

for i in range(N):
    pl = a[i]
    if pl >= mid:
        ans += pl*N + dp[-1]
        
    elif pl + 10**5 < mid:
        continue
    else:
        ans += pl*po[mid-pl] + dp[po[mid-pl]]
print(ans)

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans






N,M = m()

a = l()

a.sort()

aaa = s(a)



po = [0 for i in range(10**5+1)]
ans = 0
for i in range(N):
    po[a[i]] += 1
for i in range(10**5-1,-1,-1):
    po[i] += po[i+1]
ll = 0
rr = 10**5 * 2

while True:
    mid = (ll+rr)//2
    if mid == ll:
        co = 0
        for i in range(N):
            ui = a[i]
            if mid > ui + 10**5:
                continue
            elif ui >= mid:
                co += N
            else:
                co += po[mid-ui]
        cco = 0
        mid = rr

        for i in range(N):
            ui = a[i]
            if mid > ui + 10**5:
                continue
            elif ui >= mid:
                cco += N
            else:
                cco += po[mid-ui]
        
        

        if co == cco:
            mid = rr

        elif cco == M:
            mid = rr
            co=cco

        else:
            mid = ll

        break

    co = 0
    for i in range(N):
        ui = a[i]
        if mid > ui + 10**5:
            continue
        elif ui >= mid:
            co += N
        else:
            co += po[mid-ui]
    
    if co < M:
        rr = mid                 
    else:
        ll = mid


a.sort(reverse = True)
dp = [0]

ans -= mid * (co - M)



for i in range(N):
    dp.append(dp[-1]+a[i])

for i in range(N):
    pl = a[i]
    if pl >= mid:
        ans += pl*N + dp[-1]
        
    elif pl + 10**5 < mid:
        continue
    else:
        ans += pl*po[mid-pl] + dp[po[mid-pl]]
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from numpy.fft import rfft,irfft

def main():
    n,m=map(int,input().split())
    A=np.array(list(map(int,input().split())))
    F=np.bincount(A)
    fft_len=2*10**5+1
    Ff=rfft(F,fft_len)
    G=np.rint(irfft(Ff*Ff,fft_len)).astype(np.int64)
    G_acc=G.cumsum()
    remove_cnt=n**2-m
    border=np.searchsorted(G_acc,n**2-m)
    x=n**2-m-G_acc[border-1]
    remove_sum=(G[:border]*np.arange(border)).sum()+border*x
    ans=A.sum()*2*n-remove_sum
    print(ans)
    
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import accumulate
from bisect import bisect_left
def main():
    n,m=map(int,input().split())
    A=list(map(int,input().split()))
    A.sort()
    
    def count(k):
        cnt=0
        for a in A:
            cnt+=bisect_left(A,k-a)
        return cnt
    
    ok=0
    ng=2*10**5+1
    while ng-ok>1:
        mid=(ok+ng)//2
        if count(mid)<n**2-m:
            ok=mid
        else:
            ng=mid
    border=ok
    
    k=n**2-count(border)
    Acc=[0]+list(accumulate(A))
    s=Acc[-1]
    ans=0
    for a in A:
        idx=bisect_left(A,border-a)
        ans+=a*(n-idx)+(s-Acc[idx])
    ans-=border*(k-m)
    print(ans)
    
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
#E
from itertools import accumulate
from bisect import bisect_left
def main():
    n,m=map(int,input().split())
    A=list(map(int,input().split()))
    A.sort()
    
    def count(k):
        cnt=0
        for a in A:
            cnt+=bisect_left(A,k-a)
        return cnt
    
    ok=0
    ng=10**10+1
    while ng-ok>1:
        mid=(ok+ng)//2
        if count(mid)<n**2-m:
            ok=mid
        else:
            ng=mid
    border=ok
    
    k=n**2-count(border)
    Acc=[0]+list(accumulate(A))
    s=Acc[-1]
    ans=0
    for a in A:
        idx=bisect_left(A,border-a)
        ans+=a*(n-idx)+(s-Acc[idx])
    ans-=border*(k-m)
    print(ans)
    
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
def examA():
    N = I()
    ans = 0
    print(ans)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    N, M = LI()
    A = LI()
    A.sort()
    ma = max(A)
    l = 0; r = ma*2+1
    while(r-l>1):
        now = (l+r)//2
        cnt = 0
        for a in A:
            need = now-a
            if need>ma:
                continue
            c = bisect.bisect_left(A,need)
            cnt += N-c
        if cnt>=M:
            l = now
        else:
            r = now
    base = l
    cnt = 0
    ans = 0
    S = [0]+A
    for i in range(N):
        S[i+1] += S[i]
    #print(S)
    for a in A:
        need = base - a
        c = bisect.bisect_left(A, need+1)
        ans += a*(N-c) + S[N]-S[c]
        cnt += (N-c)
    if cnt<M:
        ans += base*(M-cnt)
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examE()

"""

"""

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
a = sorted(list(map(int, input().split())), reverse=True)
b = a[::-1] #小さい順

upper = 200001
lower = 1
while upper-lower > 1:
	mid = (upper+lower)//2
	cnt = 0
	ma = 0
	for mi in range(n):
		while ma < n and b[mi] + a[ma] >= mid:
			ma += 1
		cnt += ma
		#print(ma, mi)
	#print(lower, mid, upper, cnt)
	if cnt > m:
		lower = mid
	else:
		upper = mid

uppercnt = []
cnt = 0
for i in range(n):
	while (cnt < n-1) & (a[i] + b[cnt] < upper):
		cnt += 1
	if a[i] + b[cnt] >= upper:
		uppercnt.append(cnt)
	else:
		uppercnt.append(-1)
c = [a[0]]

uppernum = 0
for i in range(n-1):
	d = c[i] + a[i+1]
	c.append(d)
for i in range(n):
	if uppercnt[i] == -1:
		continue
	else:
		#print(a[i], (n-uppercnt[i]))
		#print(c[n-uppercnt[i]-1])
		uppernum += a[i] * (n-uppercnt[i])
		uppernum += c[n-uppercnt[i]-1]
uppercnter = 0
for i in uppercnt:
	if i != -1:
		uppercnter += n-i

print(lower*(m-uppercnter)+uppernum)

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 check(x):
    # x以上の幸福度で握手した時、M回以下だとTrueを返す
    Y = np.searchsorted(A, x - A)
    return N*N - Y.sum() <= M

ok = 10 ** 6; ng = 0
while abs(ng-ok) > 1:
    mid = (ok+ng) // 2
    if check(mid):
        ok = mid
    else:
        ng = mid

Acum = np.zeros(N+1, np.int64)
Acum[1:] = A.cumsum()
Y = np.searchsorted(A, ok-A)
answer = (Acum[-1] - Acum[Y]).sum() + (A * (N-Y)).sum()
answer += ng * (M - (N-Y).sum())
print(answer)
# 24

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=list(map(int,input().split()))
for i in range(n):a[i]*=-1
a.sort()
from bisect import bisect_left,bisect_right
def check(mid):
  mm=0
  for i in range(n):
    if -(a[i]+a[0])<mid:break
    mm+=bisect_right(a,-(mid+a[i]))
  return mm
ok=0
ng=10**10+7
while ng!=ok+1:
  mid=(ok+ng)//2
  if check(mid)>=m:ok=mid
  else:ng=mid
b=[0]
for i in a:b.append(b[-1]+i)
ans=0
for i in range(n):
  if -(a[i]+a[0])<ok:break
  ind=bisect_right(a,-(ok+a[i]))
  ans+=a[i]*ind
  ans+=b[ind]
print(-(ans+(check(ok)-m)*ok))

Submission status: Accepted

Solution code:
import bisect
import itertools
import numpy as np

def search_cut(N, M, A):
    high_cut = A[-1] * 2
    low_cut = A[0] * 2

    while high_cut > low_cut + 1:
        mid = (high_cut + low_cut) // 2
        count = (N  - np.searchsorted(A, mid - A, side = 'left')).sum()

        if count > M:
            low_cut = mid
        else:
            high_cut = mid

    return low_cut, high_cut

def happiness(N, M, A, low_cut, high_cut):
    A_sum = np.zeros(N + 1)
    A_sum[1:] = np.cumsum(A)
    X = np.searchsorted(A, high_cut - A, side = 'left')
    happiness = (A_sum[-1] - A_sum[X]).sum()
    happiness += ((N - X) * A).sum()
    happiness += (M - (N - X).sum()) * low_cut

    return int(happiness)


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

low_cut, high_cut = search_cut(N, M, A)
ans = happiness(N, M, A, low_cut, high_cut)
print(ans)

Submission status: Accepted

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

def main():
    N,M = map(int,input().split())
    a = np.array(input().split(),np.int64)
    a = np.sort(a)
    cum = np.zeros(N+1,dtype=int)
    cum[1:] = np.cumsum(a)
    
    l,r = -1,10**6+1
    while r-l > 1:
        mid = (l+r)//2
        ab_mid = (N-np.searchsorted(a,mid-a,side="left")).sum()
        if ab_mid >= M:
            l = mid
        else:
            r = mid

    pos_rev = np.searchsorted(a,r-a,side="left")
    count = (N-pos_rev).sum()
    ans = (cum[-1]-cum[pos_rev]).sum()
    ans += (a*(N-pos_rev)).sum()
    ans += (M-count)*l
        
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
 
N,M = map(int,input().split())
A = np.array(input().split(),np.int64)
 
A = np.sort(A)
S = np.zeros(N+1,np.int64)
S[1:]= np.cumsum(A)
 
hi = 200001
lo = -1
 
while hi-lo > 1:
    mid = (hi+lo)//2
    above_mid = (N-np.searchsorted(A,mid-A,side='left')).sum()
    if above_mid >= M:
        lo = mid
    else:
        hi = mid
 
X = np.searchsorted(A,hi-A,side='left')
 
above_hi = (N-X).sum()
happiness = (S[-1]-S[X]).sum()
happiness += (A*(N-X)).sum()
happiness += (M-above_hi)*lo
 
print(happiness)

Submission status: Accepted

Solution code:
def main():
    import bisect
    import numpy as np
    n,k = map(int,input().split())
    l = list(map(int,input().split()))
    l.sort()
    l = np.array(l)
    def bise(x):
        y = np.searchsorted(l,x-l)
        return n*n-y.sum()

    left = -1
    right = l[-1]*2+1

    while right > left+1:
        mid = (right+left)//2
        
        if bise(mid) >= k:
            left = mid
        else:
            right = mid
    ans = 0
    
    acc = np.zeros(n+1,np.int64)
    acc[1:] = l.cumsum()
    x = np.searchsorted(l,right-l)
    count = n*n-x.sum()
    ans = (acc[-1]-acc[x]).sum() + (l*(n-x)).sum()

    print(ans-(count-k)*left)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    import bisect
    import numpy as np
    n,k = map(int,input().split())
    l = list(map(int,input().split()))
    l.sort()
    l1 = np.array(l)
    def bise(x):
        y = np.searchsorted(l1,x-l1)
        return n*n-y.sum()

    left = -1
    right = l[-1]*2+1

    while right > left+1:
        mid = (right+left)//2
        
        if bise(mid) >= k:
            left = mid
        else:
            right = mid
    ans = 0
    count = 0
    acc = [0]
    for i in l:
        acc.append(acc[-1]+i)
    for i in l:
        index = bisect.bisect_left(l,right-i)
        ans += i*(n-index) + acc[n]-acc[index]
        count += n-index

    print(ans-(count-k)*left)
if __name__ == "__main__":
    main()

Submission status: Accepted

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


def ge_m(x, m, n):
    total = 0
    for v in a:
        delta = x - v
        idx = bisect_left(a, delta)
        total += (n - idx)
    return total >= m


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

a.sort()
cum = [0] + list(accumulate(a))  # 累積和

# 1回の握手であがる幸福度のうち、最も低いものを求める
l = 0
r = a[-1] * 2 + 1
while r - l > 1:
    mid = (l + r) // 2
    if ge_m(mid, m, n):
        l = mid
    else:
        r = mid

# 最も低い幸福度よりも大きい値を足す
num = 0  # 握手の回数
ans = 0
for v in a:
    idx = bisect_right(a, l - v)
    num += n - idx
    ans += v * (n - idx) + (cum[-1] - cum[idx])
# 足りない握手の回数分、最も低い幸福度を足す
ans += (l * (m - num))
print(ans)

Submission status: Accepted

Solution code:
# 上からm番目がx
# x以上のヒトがm人以上、x+1以上のヒトがm-1人以下
# x以上のヒトがm人以上となる最大のx
from bisect import bisect_left
from itertools import accumulate
import sys

input = sys.stdin.buffer.readline


n, m = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
ok = 0
ng = 3 * (10 ** 5)

B = [0] + A[::-1]
C = list(accumulate(B))

while ng - ok > 1:
    mid = (ok + ng) // 2
    cnt = 0
    for i in range(n):
        gendo = mid - A[i]
        position = bisect_left(A, gendo)
        if position == n:
            continue
        kosuu = n - position
        cnt += kosuu
    if cnt >= m:
        ok = mid
    else:
        ng = mid
ans = 0
cnt = m
for i in range(n):
    gendo = ok - A[i]
    position = bisect_left(A, gendo)
    if position == n:
        continue
    kosuu = n - position
    ans += C[kosuu] + kosuu * A[i]
    cnt -= kosuu
ans += cnt * ok
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left

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

A.sort()

def isOverEq(n):
    cnt = 0
    for a in A:
        cnt += N - bisect_left(A, n - a)
    return cnt >= M

overEq = -1
less = 10**7
while less - overEq > 1:
    mid = (less + overEq) // 2
    if isOverEq(mid):
        overEq = mid
    else:
        less = mid

accA = [0] * (N + 1)
for i, a in enumerate(A, start=1):
    accA[i] = accA[i - 1] + a

ans = 0
cnt = 0
for a in A:
    i = bisect_left(A, overEq - a)
    ans += accA[N] - accA[i]
    ans += (N - i) * a
    cnt += N - i

ans -= max(0, cnt - M) * overEq
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left

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

A.sort()

def isOverEq(n):
    cnt = 0
    for a in A:
        cnt += N - bisect_left(A, n - a)
    return cnt >= M

overEq = -1
less = A[-1] * 2 + 100
while less - overEq > 1:
    mid = (less + overEq) // 2
    if isOverEq(mid):
        overEq = mid
    else:
        less = mid

accA = [0] * (N + 1)
for i, a in enumerate(A, start=1):
    accA[i] = accA[i - 1] + a

ans = 0
cnt = 0
for a in A:
    i = bisect_left(A, overEq - a)
    ans += accA[N] - accA[i]
    ans += (N - i) * a
    cnt += N - i

ans -= max(0, cnt - M) * overEq
print(ans)

Submission status: Accepted

Solution code:
import sys

def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<x:
            p+=1
        cnt+=n-p
    return cnt

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

l,r=a[0]*2,a[n-1]*2
while True:
    if r-l<=1:
        if f(r)==m: md=r;break 
        else: md=l;break
        
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md

p=0
cnt=0
ans=0

for q in range(n-1,-1,-1):
    while p<n and a[q]+a[p]<=md:
        p+=1

    if p==n: break
    cnt+=n-p
    ans+=a[q]*(n-p)*2


ans+=(m-cnt)*md
print(ans)

Submission status: Accepted

Solution code:
import sys

def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<x:
            p+=1
        cnt+=n-p
    return cnt

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

l,r=a[0]*2,a[n-1]*2
md=(r+l)//2
while r-l>0:
    if r-l<=1:
        if f(r)==m: md=r;break 
        else: md=l;break
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md

p=0
cnt=0
ans=0

for q in range(n-1,-1,-1):
    try:
        while p<n and a[q]+a[p]<=md:
            p+=1
    except:
        b=1
        while True:
            b+=1

    if p==n: break
    cnt+=n-p
    ans+=a[q]*(n-p)*2


ans+=(m-cnt)*md
print(ans)

Submission status: Accepted

Solution code:
import bisect


def GETCOUNT(A,border,N):
    count = 0
    for i in range(N):
        index = bisect.bisect_left(A,border-A[i])
        count +=N-index
    return count

def get_ans(A,smt,border,N):
    sm=0
    for i in range(N):
        index = bisect.bisect_left(A,border-A[i])
        sm+=(N-index)*A[i]

        if index==N:
            continue
        sm+=smt[index]

    return sm


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

    smt=[0]*N
    smt[-1]=A[-1]
    for i in range(N-2,-1,-1):
        smt[i]=smt[i+1]+A[i]

    lid = 0 
    lco = N*N

    rid = A[-1]*2 +1
    rco = 0

    center =0
    center_count =0
    cc=0
    while True:
        center=(lid+rid)//2
        center_count=GETCOUNT(A,center,N)


        if center_count > M:
            lid = center
            lco = center_count
        else:
            rid = center
            rco = center_count
        
        if rid == lid+1 and rco != M and lco !=M:
            cc=lid*(lco - M)
            center = lid
            break



        if center_count == M:
            break
    
    print(get_ans(A,smt,center,N)-cc)








if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
from fractions import gcd
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9 +7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#############
# Main Code #
#############

N,M = inputIL()
A = inputIL()

MAX = max(A)

imos = [0]*(MAX*2+2)
imos[0] = N

for i in A:
  imos[i+1] -= 1
for i in range(1,len(imos)):
  imos[i] = imos[i-1]+imos[i]


def count_m(X):
  m = 0
  for i in A:
    m += imos[max(0,X-i)]
  return m

upper = MAX*2
lower = 0
X = (upper+lower)//2
m = count_m(X)


#print(m,X,lower,upper)
while upper != lower:
  if m > M:
    temp = lower
    lower = (upper+lower-1)//2
    if lower == temp:
      lower += 1
  else:
    temp = upper
    upper = (upper+lower+1)//2
    if upper == temp:
      upper -= 1
  X = (upper+lower+1)//2
  m = count_m(X)
  #print(m,X,lower,upper)

  
imos2 = [0]*(MAX*2+2)
for i in A:
  imos2[0] += i
  imos2[i+1] -= i
for i in range(1,len(imos2)):
  imos2[i] = imos2[i-1]+imos2[i]
  
ans = 0
for i in A:
  ans += i*imos[max(X-i,0)]+imos2[max(X-i,0)]
  
print(ans-(m-M)*X)

Submission status: Accepted

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n,m = mi()
alis = li()

alis.sort()
ok = 0
ng = alis[n-1] * 2 +1
from bisect import bisect_left as bl
while ng - ok >1:
    mid = (ok + ng)//2
    ima = 0
    for i in range(n):
        ima += n - bl(alis,mid-alis[i])
    if ima >= m:
        ok = mid
        outrange = ima - m
    else:
        ng = mid

acu_alis = [0]*n
ima = 0
for i in range(n):
    acu_alis[i] = alis[i] + ima
    ima = alis[i] + ima

ans = 0
for i in range(n):
    tmp = bl(alis,ok-alis[i]) 
    if tmp ==0:
        ans += n*alis[i] + acu_alis[n-1]
    else:
        ans += (n-tmp)*alis[i] + acu_alis[n-1] - acu_alis[tmp-1]
ans -= outrange*ok
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
a = sorted(list(map(int, input().split())), reverse=True)
a_rev = a[::-1]

ok, ng = 1, 200001
while ng-ok > 1:
	x = (ok+ng)//2
	num = 0
	cur = 0
	for i in range(n-1, -1, -1):
		while cur < n and a[i] + a[cur] >= x:
			cur += 1
		num += cur
	if num < m:
		ng = x
	else:
		ok = x
just = ok

ans = 0
larger_cnt = 0
cur = 0

a_cum = [0]
for i in range(n):
	a_cum.append(a_cum[-1] + a[i])

for i in range(n):
	while cur < n and a[i] + a_rev[cur] <= just:
		cur += 1
	larger_cnt += n - cur
	ans += (n - cur) * a[i] + a_cum[n - cur]

ans += just * (m - larger_cnt)
print(ans)