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 numpy as np
# import scipy as sp
# import sys
# input = sys.stdin.readline
# print(a,b,c,sep="") # 半角スペースなしで出力(abc)
# n=int(input())  #数値入力 「N」だけの入力のとき
# a,b=list(map(int, input().split()))  #複数数値入力　「A B」みたいなスペース空いた入力のとき
# a=list(map(int, input().split()))  #リスト入力 「a1 a2 a3 ...」みたいな配列のような入力のとき
# a=[int(input()) for _ in range (n)]  #リスト入力  改行でa1 ... anのとき
# s=[list(map(str,list(input()))) for i in range(h)]  # 文字列の二次元配列入力
# s = [list(map(int, input().split())) for i in range(n)] # 数値の二次元配列入力
# a = b[:], a = [x[:] for x in b] # deepcopy
# chr(ord('a') + 1) # chrのインクリメント
# s.sort(key=lambda x: x[1], reverse=False) # 2番目の要素で昇順にソート（Trueなら降順）
#　

import itertools
import bisect
n, m = list(map(int, input().split()))
al = list(map(int, input().split()))
al.sort()
ub = al[-1]*3
lb = -1
while lb + 1 < ub:
    target = (ub+lb)//2
    tmp = 0
    for a in al:
        sa = target - a
        # リストAに値xを入れ、xが複数になるとき、一番左の値xのインデックスを返す
        i = bisect.bisect_left(al, sa)
        tmp += (n-i)
    if (tmp >= m):
        lb = target
    else:
        ub = target


rui_al = [0] + list(itertools.accumulate(al))
ans = 0
tmp = 0
target = lb
for a in al:
    sa = target - a
    # リストAに値xを入れ、xが複数になるとき、一番左の値xのインデックスを返す
    i = bisect.bisect_left(al, sa)
    tmp += (n-i)
    ans += (rui_al[-1] - rui_al[i])
    ans += a*(n-i)

if tmp > m:
    ans -= (tmp-m)*target
print(ans)

Submission status: Accepted

Solution code:
import itertools
import bisect
n, m = list(map(int, input().split()))
al = list(map(int, input().split()))
al.sort()
ub = al[-1]*3
lb = -1
while lb + 1 < ub:
    target = (ub+lb)//2
    tmp = 0
    for a in al:
        sa = target - a
        # リストAに値xを入れ、xが複数になるとき、一番左の値xのインデックスを返す
        i = bisect.bisect_left(al, sa)
        tmp += (n-i)
    if (tmp >= m):
        lb = target
    else:
        ub = target

target = lb
rui_al = [0] + list(itertools.accumulate(al))
ans = 0
tmp = 0
for a in al:
    sa = target - a
    # リストAに値xを入れ、xが複数になるとき、一番左の値xのインデックスを返す
    i = bisect.bisect_left(al, sa)
    tmp += (n-i)
    ans += (rui_al[-1] - rui_al[i])
    ans += a*(n-i)


if tmp > m:
    ans -= (tmp-m)*target
print(ans)

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())))
A_rev = list(reversed(A))
B = [0] + list(accumulate(A_rev))

def func(x):
    count = 0
    for Ai in A:
        idx = bisect_left(A, x - Ai)
        count += N - idx
    if count >= M:
        return True
    else:
        return False

min_ = 0
max_ = 2 * 10 ** 5 + 1
while max_ - min_ > 1:
    mid = (min_ + max_) // 2
    if func(mid):
        min_ = mid
    else:
        max_ = mid

ans = 0
count = 0
for Ai in A_rev:
    idx = bisect_left(A, min_-Ai)
    ans += Ai * (N - idx) + B[N-idx]
    count += N-idx
print(ans-(count-M)*min_)

Submission status: Accepted

Solution code:
from itertools import accumulate
from bisect import bisect_left


N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
B = [0] + list(accumulate(A))

def check(X):
    cnt = 0
    for i in range(N):
        cnt += N - bisect_left(A, X - A[i])
    return cnt >= M


def main():

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

    ans = 0
    cnt = 0
    for i in range(N):
        tmp = bisect_left(A, ok - A[i])
        cnt += N - tmp
        ans += B[N] - B[tmp]
        ans += A[i] * (N - tmp)
    ans -= ok * (cnt - M)
    print(ans)




if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    from bisect import bisect_left as bl
    from itertools import accumulate as ac

    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    aa = [0]+list(ac(a))
    an = aa[n]

    ok = 0
    ng = 10**10
    while abs(ok-ng) > 1:
        mid = (ok+ng)//2
        if sum([n-bl(a, mid-a[i]) for i in range(n)]) >= m:
            ok = mid
        else:
            ng = mid

    c = -m+sum([n-bl(a, ok-a[i]) for i in range(n)])
    ans = -c*ok
    for i in range(n):
        d = bl(a, ok-a[i])
        ans += an-aa[d]+(n-d)*a[i]
    print(ans)


main()

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
*A, = map(int,input().split())

A.sort(reverse=True)

def count(i,B):
    B = B - A[i]
    l = -1
    r = N
    while l+1<r:
        j = (l+r)//2
        if A[j] >= B:
            l = j
        else:
            r = j
    return r

l = 0
r = 10**5*3
while l+1<r:
    i = (l+r)//2
    S = 0
    for j in range(N):
        S += count(j,i)
    if S==M:
        r = i
        break
    elif S>M:
        l = i
    else:
        r = i

ans = 0
tmp = 0
SA = [0]*(N+1)
for j in range(N):
    SA[j+1] = SA[j] + A[j]
for j in range(N):
    c = count(j,r)
    ans += A[j]*c + SA[c]
    tmp += c
if M>tmp:
    n = 0
    for j in range(N):
        c = count(j,r)
        if c==N: continue
        n = max(n,A[j] + A[c])
    ans += n*(M-tmp)
print(ans)

Submission status: Accepted

Solution code:
def main():
    from bisect import bisect_left as bl
    from itertools import accumulate as ac

    n, m = map(int, input().split())
    a = sorted(list(map(int, input().split())))
    aa = [0]+list(ac(a))
    an = aa[n]

    ok = 0
    ng = 10**10
    while abs(ok-ng) > 1:
        mid = (ok+ng)//2
        q = 0
        for i in range(n):
            q += n-bl(a, mid-a[i])
        if q >= m:
            ok = mid
        else:
            ng = mid

    b = ok
    c = -m
    for i in range(n):
        c += n-bl(a, b-a[i])
    ans = -c*b
    for i in range(n):
        d = bl(a, b-a[i])
        ans += an-aa[d]+(n-d)*a[i]
    print(ans)


main()

Submission status: Accepted

Solution code:
def binary_search(*, ok, ng, is_ok):
    while abs(ok - ng) > 1:
        mid = (ng + ok) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return ok


def main():
    from itertools import accumulate

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

    acc = [0]
    for x in accumulate(A):
        acc.append(x)

    def count(h):
        ret = 0

        j = N
        for i in range(N):
            while j - 1 >= 0 and A[i] + A[j - 1] >= h:
                j -= 1
            ret += N - j
            # [j,N)の要素数

        return ret

    x = binary_search(ok=A[-1] * 2 + 1, ng=0, is_ok=lambda x: count(x) < M)
    # 幸福度の総和がX以上のペア数がM未満となる最大のX

    s = 0
    j = N
    for i in range(N):
        while j - 1 >= 0 and A[i] + A[j - 1] >= x:
            j -= 1
        s += A[i] * (N - j) + acc[N] - acc[j]
    s += (M - count(x)) * (x - 1)

    print(s)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import accumulate
from bisect import bisect_left

n, m = map(int, input().split())
a = sorted(map(int, input().split()))
cs = [0] + list(accumulate(a))
c = 0
s = 0


def f(x):
    global c, s
    c = 0
    s = 0
    for i in range(n):
        left = bisect_left(a, x - a[i])
        c += n - left
        s += cs[n] - cs[left] + (n - left) * a[i]
    return c


ok = 0
ng = 2 * 10 ** 5 + 1
while abs(ok - ng) > 1:
    x = (ok + ng) // 2
    if f(x) >= m:
        ok = x
    else:
        ng = x

print(s - (c - m) * ok)

Submission status: Accepted

Solution code:
from bisect import bisect_left
def main():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    b = [0]*(n+1)
    for i in range(n):
        b[i+1] = a[i] + b[i]
    ok = 0; ng = 2 * 10**5 + 5
    while ok+1 < ng:
        mid = (ok + 1 + ng) // 2
        buf = 0
        for i in range(n):
            p = mid - a[i]
            buf += n - bisect_left(a, p)
        if buf >= m:
            ok = mid
        else:
            ng = mid
    ans = 0
    num = 0
    tot = 0
    for i in range(n):
        p = ok - a[i]
        index = bisect_left(a, p)
        num += n - index
        tot += b[n] - b[index]
        tot += a[i] * (n-index)
    ans = tot - (num - m) * ok
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import bisect
n,m=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
ng=-1
ok=A[-1]*2+1
B=[[0]*n for k in range(2)]
ii=0
while ok-ng>1:
  mid=(ok+ng)//2
  d=0
  for i in range(n):
    c=n-bisect.bisect_right(A,mid-A[i],lo=0,hi=len(A))
    B[ii][i]=c
    d=d+c
  if d<m:
    ok=mid
    ii=(ii+1)%2
  else:
    ng=mid
D=[0]
for i in range(n):
  D.append(D[-1]+A[n-i-1])
ans=0
for i in range(n):
  x=B[(ii+1)%2][i]
  ans=ans+A[i]*x+D[x]
ans=ans+(m-sum(B[(ii+1)%2]))*ok
print(ans)

Submission status: Accepted

Solution code:

import numpy as np
N, M = map(int, input().split())
A = np.array(input().split(), dtype=np.int32)

x = np.bincount(A)
fft_size = 1 << (2 * x.size + 10).bit_length()

fx = np.fft.rfft(x, fft_size)
conv = np.fft.irfft(fx * fx, fft_size)
conv = (conv + 0.5).astype(int)

tmp = np.arange(conv.size, dtype=int)
happy = tmp[np.nonzero(conv)].tolist()
cnt = conv[np.nonzero(conv)].tolist()


ans = 0
while M > 0:
    h = happy.pop()
    num = cnt.pop()
    num = min(M, num)

    M -= num
    ans += num * h

print(ans)

Submission status: Accepted

Solution code:
N, M = (int(i) for i in input().split())
A = [int(i) for i in input().split()]
A.sort(reverse=True)
As = [0]*(N+1)
for i in range(N):
    As[i+1] = As[i] + A[i]
A.reverse()

import bisect

def flag(x):
    ans = 0
    for i in range(N):
        a = x - A[i]
        res = bisect.bisect_left(A, a)
        ans += (N-res)
    return bool(ans >= M)

def an(x):
    ans = 0
    m = 0
    for i in range(N):
        a = x - A[i]
        res = bisect.bisect_left(A, a)
        m += (N-res)
        ans += As[N-res]
        ans += A[i] * (N-res)
    ans -= (m - M) * x
    return ans


low = 0
high = 10**6

while low <= high:
    mid = (low + high) // 2
    if flag(mid):
        if not flag(mid+1):
            ans = mid
            break
        else:
            low = mid + 1
    else:
        high = mid - 1

print(an(ans))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from bisect import bisect, bisect_left
from itertools import accumulate

def main():
    def check(x):
        count = 0
        for a in aaa:
            if x <= a:
                count += n
            else:
                count += n - bisect_left(aaa, x - a)
        return count >= m
    
    
    n, m = map(int, input().split())
    aaa = list(map(int, input().split()))
    aaa.sort()
    acc = [0] + list(accumulate(aaa))
    sum_a = acc[-1]
    
    l, r = 0, 200001
    while l + 1 < r:
        mid = (l + r) // 2
        if check(mid):
            l = mid
        else:
            r = mid
    
    # 合計がlより大きい組み合わせの和と組数を求める→Mに足りない分だけ合計がlの組を採用
    ans = 0
    count = 0
    for a in aaa:
        if l <= a:
            ans += sum_a + a * n
            count += n
        else:
            omit = bisect(aaa, l - a)
            if omit < n:
                ans += sum_a - acc[omit] + a * (n - omit)
                count += n - omit
    ans += l * (m - count)
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import accumulate
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
lb = 0
ub = 2*10**5+1
while ub - lb > 1:
    m = (lb + ub) // 2
    cnt = 0
    s, t = 0, N-1
    while t >= 0:
        while s < N and A[s] + A[t] >= m:
            s += 1
        cnt += s
        t -= 1

    if cnt >= M:
        lb = m
    else:
        ub = m

accum = list(accumulate([0] + A))
ans = 0
cnt = 0
s, t = 0, N-1
while t >= 0:
    while s < N and A[s] + A[t] >= lb:
        s += 1
    ans += accum[s] + s * A[t]
    cnt += s
    t -= 1
print(ans - (cnt-M) * lb)

Submission status: Accepted

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

import numpy as np

def shake_cnt(x):
  # 両手x - 左手の価値 = 右手の価値
  # x - a[i]未満の個数(行わない握手)を数える
  # X以上の和がM個未満かどうか
  X = np.searchsorted(A, x-A)
  return (N - X).sum()
  

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

left = 0 # 握手の回数がM以上
right = 10 ** 6 # 握手の回数がM未満
while left + 1 < right:
    x = (left + right) // 2
    if shake_cnt(x) < M:
        right = x
    else:
        left = x

# 終了時にngにX-1,okにXが入っている。

X = np.searchsorted(A,right-A) # 行わない人数
Acum = np.zeros(N+1,np.int64) # 人数 -> 累積和
Acum[1:] = np.cumsum(A)

# right(最大値) 以上の握手を全て行ったとして、回数と総和を計算
# N**2通りの握手から価値の高い上位の握手  

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 sys
from itertools import accumulate
from bisect import bisect_left

n, m, *a = map(int, sys.stdin.read().split())
a.sort()


def f(x):
    # 幸福度がx未満となる組み合わせの個数を数える
    cnt = 0
    for ai in a:
        cnt += bisect_left(a, x-ai)
    # 幸福度がx以上の組み合わせの個数がm未満かどうか
    return n * n - cnt < m


left = a[0] * 2
right = a[-1] * 2
while right - left > 1:
    mid = (right + left) // 2
    if f(mid):
        right = mid
    else:
        left = mid
ans = 0
cumsum = [0] + list(accumulate(a))
j = 0
for ai in a:
    i = bisect_left(a, left-ai)
    j += n - i
    ans += ai * (n - i) + cumsum[-1] - cumsum[i]
ans += (m - j) * left
print(ans)

Submission status: Accepted

Solution code:
#from collections import *
#from itertools import *
#from bisect import *
from heapq import *
#import copy
#N=int(input())
#X,Y=map(int,input().split())
#S=list(map(int,input().split()))
#S=[list(map(int,input().split())) for i in range(N)]

N,M=map(int,input().split())
A=sorted(list(map(int,input().split())),reverse=True)
"""
lst=[]
for i in range(N):
    for m in range(N):
        lst.append(A[i]+A[m])
lst=sorted(lst,reverse=True)
#print(sum(lst[:M]))
print(lst)
"""
ng=-1
ok=max(A)*2+1
while ok>ng+1:
    mid=(ok+ng)//2
    K=0
    idx=0
    for i in range(N-1,-1,-1):
        X=mid-A[i]
        while idx<N and A[idx]>=X:
            idx+=1
        K+=idx
    if K>M:
        ng=mid
    else:
        ok=mid
idx=0
lst=[0 for i in range(N)]
for i in range(N-1,-1,-1):
    X=ng-A[i]
    while idx<N and A[idx]>=X:
        idx+=1
    lst[i]=idx*2
value=0
for a,i in zip(A,lst):
    value+=a*i
value-=ng*(sum(lst)//2-M)
print(value)

Submission status: Accepted

Solution code:
import bisect
n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
A=[0]
for i in range(n):
  A.append(a[i]+A[-1])
l=0;r=10**10+1
while r-l>1:
  x=(l+r)//2
  ct=0
  for i in range(n):
    ct+=n-bisect.bisect_left(a,x-a[i])
  if ct<m:
    r=x
  else:
    l=x
ans=0
ct2=0
for i in range(n):
  y=bisect.bisect_left(a,l-a[i])
  ans+=A[n]-A[y]
  ans+=a[i]*(n-y)
  ct2+=n-y
print(ans-l*(ct2-m))

Submission status: Accepted

Solution code:
import bisect
n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
A=[0]
for i in range(n):
  A.append(a[i]+A[-1])
l=0;r=10**10+1
while abs(l-r)>1:
  x=(l+r)//2
  ct=0
  for i in range(n):
    ct+=n-bisect.bisect_left(a,x-a[i])
  if ct<m:
    r=x
  else:
    l=x
ans=0
ct2=0
for i in range(n):
  y=bisect.bisect_left(a,l-a[i])
  ans+=A[n]-A[y]
  ans+=a[i]*(n-y)
  ct2+=n-y
print(ans-l*(ct2-m))

Submission status: Accepted

Solution code:
#幸福度の最小値で二分探索

##右手左手による重複の処理
##同一の値や和がたまたま一致する重複の処理
import bisect
n,m = map(int, input().split())
a = list(map(int, input().split( )))
a.sort()
a2 = [a[i]*2 for i in range(n)]

mn = -1
mx = (a[-1]+1)*2
md = (mx+mn)//2
while mx-mn>1:
    md = (mx+mn)//2
    cnt = 0
    for i in range(n):
        tmp = md-a[i]
        idx = bisect.bisect_left(a, tmp)
        cnt += n-idx

    if cnt >= m:
        mn = md
    else:
        mx = md
ans = 0

acc = []
sm = 0
for i in range(n):
    sm += a[i]
    acc.append(sm)
acc.append(0)##一つも足さない場合
#iは右手とする
for i in range(n-1,-1,-1):
    idx = bisect.bisect_left(a,mx-a[i])
    tmp2 = n-idx
    if m>=tmp2:
        ans += a[i] * tmp2
        ans += (acc[n-1] - acc[idx-1])
        m-=tmp2
    else:
        ans += a[i]*m
        ans += acc[n-1]-acc[n-1-m]
        break
if m:
    ans += mn*m

print(ans)

Submission status: Accepted

Solution code:
def e_handshake():
    import numpy as np
    N, M = [int(i) for i in input().split()]
    A = np.array(input().split(), np.int64)
    A.sort()

    def shake_cnt(x):
        # 幸福度が x 以上となるような握手を全て行うときの握手の回数
        # 全体から行わない握手回数を引く
        return N**2 - np.searchsorted(A, x - A).sum()

    # 幸福度の上昇が right 以上となるような握手はすべて行い、
    # left となるような握手はいくつか行って握手回数が M 回になるようにする
    left = 0
    right = 10 ** 6
    while right - left > 1:
        mid = (left + right) // 2
        if shake_cnt(mid) >= M:
            left = mid
        else:
            right = mid

    # 幸福度が right 以上上がるような握手をすべて行ったとして、回数と総和を計算
    X = np.searchsorted(A, right - A)  # 行わない人数
    Acum = np.zeros(N + 1, np.int64)  # 累積和で管理する
    Acum[1:] = np.cumsum(A)
    happiness = (Acum[-1] - Acum[X]).sum() + (A * (N - X)).sum()

    # 幸福度が right 未満の上昇となる握手を、握手回数が M になるまで追加で行う
    shake = N * N - X.sum()
    happiness += (M - shake) * left
    return happiness

print(e_handshake())

Submission status: Accepted

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

def condition(num):
    count=0
    s=N-1
    t=0
    while N-1>=t and s>=0:
        if num>A[s]+A[t]:
            t+=1
        else:
            count+=N-t
            s-=1
    return count>=M

subans=0
start=1
end=2*A[N-1]
while end-start>1:
    test=(end+start)//2
    if condition(test):
        start=test
    else:
        end=test
if condition(end):
    subans=end
else:
    subans=start

data=[0]*N
count=0
s=N-1
t=0
while N-1>=t and s>=0:
    if subans>A[s]+A[t]:
        t+=1
    else:
        count+=N-t
        data[s]=2*(N-t)
        s-=1

ans=sum(data[i]*A[i] for i in range(0,N))
if count>M:
    ans-=(count-M)*subans
print(ans)

Submission status: Accepted

Solution code:
import sys

input=sys.stdin.readline

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

def condition(num):
    count=0
    s=N-1
    t=0
    while N-1>=t and s>=0:
        if num>A[s]+A[t]:
            t+=1
        else:
            count+=N-t
            s-=1
    return count>=M

subans=0
start=1
end=2*A[N-1]
while end-start>1:
    test=(end+start)//2
    if condition(test):
        start=test
    else:
        end=test
if condition(end):
    subans=end
else:
    subans=start

data=[0]*N
count=0
s=N-1
t=0
while N-1>=t and s>=0:
    if subans>A[s]+A[t]:
        t+=1
    else:
        count+=N-t
        data[s]=2*(N-t)
        s-=1

ans=sum(data[i]*A[i] for i in range(0,N))
if count>M:
    ans-=(count-M)*subans
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()

l=1
r=200000+1

def chk(x):
    c=0
    for la in A:
        y=bisect_left(A,x-la)
        c+=N-y
    if c>=M:
        return True
    else:
        return False



while l+1<r:
    mid=(l+r)//2
    if chk(mid):
        l=mid
    else:
        r=mid

AN=l

S=[0]*(N+1)

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

ans1=0
c=0
for la in A:
    ll = -1
    rr = N
    while ll + 1 < rr:
        mi = (ll + rr) // 2
        if A[mi] > AN - la:
            rr = mi
        else:
            ll = mi
    c+=N-rr
    ans1=ans1+la*(N-rr)+S[N]-S[rr]

ans=ans1+(M-c)*AN
print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc149/tasks/abc149_e

# すべての握手の組み合わせN**2を列挙しソートしM番目までを足し合わせればOK
# だけど制約からこれを行うことは困難
# すべてを列挙しなくともM番目の値を知ることは二分探索で可能(参考:億マス計算)
# Aの累積和を保持しておけば、M番目の値の探索中にMまでの値の合計もついでに計算できる
# 以下reverseでソート済みだと仮定
# XがM番目の数→X以上である数はM個以上(cntとする)→cntがM個以上の条件を満たすうちの最大となるXがM番目の値
# そのあと余分な分を引く処理とか必要

from bisect import bisect_right, bisect_left
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


class cumsum1d:
    def __init__(self, ls: list):
        '''
        1次元リストを受け取る
        '''
        from itertools import accumulate
        self.ls_accum = [0] + list(accumulate(ls))

    def total(self, i, j):
        # もとの配列lsにおける[i,j)の中合計
        return self.ls_accum[j] - self.ls_accum[i]


N, M = read_ints()
A = read_ints()
A.sort()  # bisectを使う都合上 reverseは抜き
A_reversed = list(reversed(A))
A_rev_acc = cumsum1d(A_reversed)


def is_ok(X):
    # M番目の数はXである→X以上の個数>=M となるうちで最大のX(もっとも左の方のX)
    # X以上の個数>=Mを返す
    # X以下の個数はai+aj>=Xを満たす個数
    cnt = 0
    ans = 0
    for a in A:
        aa = X - a
        idx_reverse = N - bisect_left(A, aa)  # 大きい方からだと何番目か
        # これはbisect_right(A_reversed,aa)に等しい
        cnt += idx_reverse
        ans += A_rev_acc.total(0, idx_reverse) + idx_reverse * a
    return cnt >= M, ans, cnt


def meguru_bisect(ng, ok):
    '''
    define is_okと
    初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
    ng ok は  とり得る最小の値-1 とり得る最大の値+1
    最大最小が逆の場合はよしなにひっくり返す
    '''
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        flg, ans, cnt = is_ok(mid)
        if flg:
            ok = mid
            ans_true = ans  # さいごにokとなる状態がans
            cnt_true = cnt
        else:
            ng = mid
    return ans_true, ok, cnt_true


ans_tmp, M_th_num, M_plus_alpha_th = \
    meguru_bisect(2 * 10 ** 5 + 1, 0)
# print(ans_tmp, M_th_num, M_plus_alpha_th)
print(ans_tmp - (M_plus_alpha_th - M) * M_th_num)

Submission status: Accepted

Solution code:
import bisect
n,m=map(int,input().split())
l=list(map(int,input().split()))
l.sort()
r=[0]*(10**5+2)
for i in range(n):
    r[l[i]]+=1
for i in range(10**5+1):
    r[i+1]+=r[i]
ok=10**6
ng=0
while ok-ng>1:
    x=(ok+ng)//2
    k=0
    for i in range(n):
        if x-l[i]<0:
            k+=n
        elif x-l[i]>10**5+1:
            k+=0
        else:
            k+=n-r[x-l[i]]
    if k>=m:
        ng=x
    else:
        ok=x
#print(ok)
p=[0]*(n+1)
for i in range(n):
    p[i+1]=p[i]+l[i]
ans=0
mi=0
for i in range(n):
    li=bisect.bisect_left(l,ok-l[i])
    ans+=l[i]*(n-li)+p[n]-p[li]
    mi+=n-li
print(ans-(mi-m)*ok)

Submission status: Accepted

Solution code:
import numpy as np
n, k = map(int, input().split())
a = np.array(list(map(int, input().split())))
a.sort()
l, r = 0, 10000000000
while r - l > 1:
    m = (l + r) // 2
    res = n * n - a.searchsorted(m - a).sum()
    if res >= k:
        l = m
    else:
        r = m
b = np.array([0] * (n + 1))
for i in range(1, n + 1):
    b[i] = b[i - 1] + a[n - i]
cnt = 0
ans = 0
for x in a:
    t = n - a.searchsorted(l - x)
    ans += b[t] + x * t
    cnt += t
print(ans - (cnt - k) * l)

Submission status: Accepted

Solution code:
from itertools import groupby,accumulate
import bisect
n,m = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
A.sort()
le=len(A)
#print(A)
B=list(accumulate([0]+A))
ok=0 #可能
ng=10**10 #不可能
ans=0
while 1<abs(ng-ok):
  mid=(ng+ok)//2
  ans=0
  cnt=0
  for i in range(le):
    x = mid-A[i]
    cnt1=int(bisect.bisect_left(A,x))
    cnt+=(le-cnt1)
    #ans+=A[i]*(le-cnt1)+B[n]-B[cnt1]
  if cnt>=m:
    ok=mid
  else:
    ng=mid
cnt=0
for i in range(le):
  x=ok-A[i]
  cnt1=int(bisect.bisect_left(A,x))
  cnt+=le-cnt1
  ans+=A[i]*(le-cnt1)+B[n]-B[cnt1]
print(ans+(m-cnt)*ok)

Submission status: Accepted

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

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
#print("A={}".format(A))
"""
この問題の前半は、合計の幸福度Xが上位M個未満に入るかを判定する。
    -> Xに関する二分探索をすることで、上位から丁度M番目の幸福度がわかる！

これを判定するために、左手の握手先をfix(A[i]とする)して、
右手の幸福度が(X - A[i])以上であるものの個数を数える。
"""

def within(X, M):
    """
    幸福度がX以上上がるような握手の組がM個未満ならTrue、そうでなければFalseを返す
    """
    pair = 0
    for i in range(N):
        idx = bisect_left(A, X - A[i])
        pair += N - idx
    if pair < M:
        #print("pair={}<M".format(pair))
        return True
    else:
        #print("pair={}>=M".format(pair))
        return False

"""
Xに関する二分探索をおこなった結果、
leftXはwithin(leftX, M) == Trueになる最小のX
"""
leftX = 0
rightX = A[-1] * 2 + 1
while leftX != rightX:
    middleX = (leftX + rightX) // 2
    #print("mid={}".format(middleX))
    if within(middleX, M):
        rightX = middleX
    else:
        leftX = middleX + 1
#print("leftX={}".format(leftX))

"""
これより後半、幸福度の総和を求める。
前半同様に左手をfixした上で、両手の幸福度の合計がleftX以上になるときの幸福度を加算していく。
単純に右手に関してfor文を回して加算するとTLEなので、
右手の幸福度に関しては先に累積和を求めておく。
"""
S = list(itertools.accumulate(A))
#print("S={}".format(S))
happy = 0
times = 0
for i in range(N):
    idx = bisect_left(A, leftX - A[i])
    times += N - idx
    #print("When i={}, idx={}, times={}".format(i, idx, times))
    if idx != 0:
        happy += A[i] * (N - idx) + (S[-1] - S[idx - 1])
    else:
        happy += A[i] * (N - idx) + S[-1]
    #print("happy={}".format(happy))
happy += (leftX - 1) * (M - times)

print(happy)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
arr=list(map(int,input().split()))
arr=sorted(arr,reverse=True)
acum=[arr[0]]
for i in range(1,n):
  acum.append(acum[-1]+arr[i])
l=0
r=2*10**5+1
while r-l!=1:
  mid=(l+r)//2
  tmp=0
  cnt=0
  pos=n-1
  for i in range(n):
    while pos!=-1:
      if arr[i]+arr[pos]>=mid:
        cnt+=pos+1
        tmp+=arr[i]*(pos+1)+acum[pos]
        break
      else:
        pos-=1
        if pos==-1:
          break
  if cnt<=m:
    r=mid
  else:
    l=mid
tmp+=(m-cnt)*l
print(tmp)

Submission status: Accepted

Solution code:
def judge(k, N, A):
    p = N - 1
    t = 0
    for i in A:
        while p >= 0 and A[p] + i < k:
            p -= 1
        t += (p + 1)
    return t
def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort(reverse=True)
    t = A[0] * 2
    b = 0
    X = None
    while t - b > 1:
        m = (t + b)//2
        i = judge(m, N, A)
        if i == M:
            X = m
            break
        if i > M:
            ip = judge(m + 1, N, A)
            if ip == M:
                X = m + 1
                break
            if ip < M:
                X = m
                break
            b = m + 1
        if i < M:
            im = judge(m - 1, N, A)
            if im >= M:
                X = m - 1
                break
            t = m - 1
    if X is None:
        X = b
    r = 0
    p = N - 1
    k = sum(A)
    for i in A:
        while p >= 0 and A[p] + i < X :
            k -= A[p]
            p -= 1
        r += i * (p + 1) + k
    return r - (judge(X, N, A) - M) * X
print(main())

Submission status: Accepted

Solution code:
import bisect
def judge(k, N, A):
    t = 0
    for i in A:
        j = bisect.bisect_left(A, k - i)
        t += N - j
    return t
def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
    t = A[-1] * 2
    b = 0
    X = None
    while t - b > 1:
        m = (t + b)//2
        i = judge(m, N, A)
        if i == M:
            X = m
            break
        if i > M:
            ip = judge(m + 1, N, A)
            if ip == M:
                X = m + 1
                break
            if ip < M:
                X = m
                break
            b = m + 1
        if i < M:
            im = judge(m - 1, N, A)
            if im >= M:
                X = m - 1
                break
            t = m - 1
    if X is None:
        X = b
    B = []
    tmp = 0
    for i in reversed(range(N)):
        tmp += A[i]
        B.append(tmp)
    B.reverse()
    r = 0
    tot = 0
    for i in reversed(range(N)):
        j = bisect.bisect_left(A, X - A[i])
        tot += N - j
        if j == N:
            break
        r += A[i] * (N - j) + B[j]
    return r - (tot - M) * X
print(main())

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#import sys; sys.stdin=open('input_file.txt')
#------------------------------------------
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:
import bisect
from itertools import accumulate


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

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


def calc(x):
    _total = 0
    _num = 0
    for i in range(N):
        j = bisect.bisect_left(A, x - A[i])
        _num += N - j
        _total += S[N] - S[j]
        _total += A[i] * (N - j)
    return _total, _num


left = 0
right = 200005

while right - left > 1:
    center = (left + right) // 2
    if calc(center)[1] >= M:
        left = center
    else:
        right = center

total, num = calc(left)
ans = total
ans -= (num - M) * left
print(ans)