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: Wrong Answer

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]))
"""

ng=-1
ok=N**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
#print(mid)
idx=0
lst=[0 for i in range(N)]
for i in range(N-1,-1,-1):
    X=mid-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-=mid*(sum(lst)//2-M)
print(value)

Submission status: Wrong Answer

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]))
"""

ng=-1
ok=N**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
#print(mid)
idx=0
lst=[0 for i in range(N)]
for i in range(N-1,-1,-1):
    X=mid-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-=mid*(sum(lst)//2-M)

print(value)

Submission status: Wrong Answer

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]))"""


ng=-1
ok=10**10+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
#print(mid)
idx=0
lst=[0 for i in range(N)]
for i in range(N-1,-1,-1):
    X=mid-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-=mid*(sum(lst)//2-M)

print(value)

Submission status: Wrong Answer

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)
ng=-1
ok=10**10+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
#print(mid)
idx=0
lst=[0 for i in range(N)]
for i in range(N-1,-1,-1):
    X=mid-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

if sum(lst)%2:
    print(unko)
value-=mid*(sum(lst)//2-M)

print(value)

Submission status: Wrong Answer

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)
ng=-1
ok=10**10+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
#print(mid)
idx=0
lst=[0 for i in range(N)]
for i in range(N-1,-1,-1):
    X=mid-A[i]
    while idx<N and A[idx]>=X:
        idx+=1
    lst[i]=idx*2 #- (i<=idx)*1
#print(lst)
value=0
for a,i in zip(A,lst):
    value+=a*i

value-=mid*(sum(lst)//2-M)

print(value)

Submission status: Wrong Answer

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,mn-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

print(ans)

Submission status: Wrong Answer

Solution code:

N,M = map(int, input().split())
A = list(map(int, input().split()))
#A=[1,3,5,8]

B = sorted(A,reverse=True)
A = sorted(A)
#print(A)
#print(B)

def sumc(X,A,B):
    w=0
    s=0
    k=0
    ans=0
    a=len(A)
    b=len(B)
    for i in range(a):
        r=X-A[i]
        for j in range(s,b):

            if(B[j]>=r):
                w=j+1
                k=j
            else:
                k=j
                break
            #if(B[b-1]>=r):
                #k=b-1
        s=k
        ans+=w
        #print(w)
        #print(ans)
    return ans


def suml(X,A,B):
    w=0
    s=0
    k=0
    ans=0
    a=len(A)
    b=len(B)
    #D=[0]*a
    #L=[0]*b
    for i in range(a):
        r=X-A[i]
        #D[i]=s
        for j in range(s,b):
            if(B[j]>=r):
                w=j+1
                k=j

                #D[i]+=1
                #L[j]=a-i]
                ans+=B[j]*(a-i)
            else:
                k=j
                break

        s=k
        ans+=w*A[i]

        """
        for i in range(a):
            ans+=A[i]*D[i]
        for i in range(b):
            ans+=B[i]*L[i]
        """
    return ans
#ans=sum(8,A,B)
#print(ans)
def binary(S,E,M,K):
    X=int((S+E)/2)
    n=sum(X,A,B)
    if(n>M):
        binary(X,E,M,K)


    if(n<M):
        binary(S,X,M,K)


    if(n==M):
        K = X

S=2*A[0]
E=2*A[N-1]
X=int((S+E)/2)
while(1):
    n=sumc(X,A,B)
    m=sumc(X+1,A,B)
    if(n>=M and M>m):
        break
    if(n>=M):
        S=X
        X=int((E+X)/2)

    if(n<M):
        E=X
        X=int((S+X)/2)


#print(X)
#binary(S,E,M,K)
k=sumc(X,A,B)
#print(k)
s=0
ans=0
w=0
if(k==M):
    """
    for i in range(N):
        r=X-A[i]
        for j in range(s,N):
            if(B[j]>=r):
                w=j+1
                ans+=B[j]*(N-i)
            else:
                k=j
                break
            if(B[N-1]>=r):
                k=N-1
        s=k
        ans+=A[i]*w
    """
    ans=suml(X,A,B)
else:
    #print("a")
    X=X+1

    t=sumc(X,A,B)
    #print(t)
    #print(X-1)
    ans=suml(X,A,B)
    ans+=(M-t)*(X-1)

print(ans)

Submission status: Wrong Answer

Solution code:

N,M = map(int, input().split())
A = list(map(int, input().split()))
#A=[1,3,5,8]

B = sorted(A,reverse=True)
A = sorted(A)
print(A)
print(B)

def sumc(X,A,B):
    w=0
    s=0
    k=0
    ans=0
    a=len(A)
    b=len(B)
    for i in range(a):
        r=X-A[i]
        for j in range(s,b):

            if(B[j]>=r):
                w=j+1
                k=j
            else:
                k=j
                break
            #if(B[b-1]>=r):
                #k=b-1
        s=k
        ans+=w
        #print(w)
        #print(ans)
    return ans


def suml(X,A,B):
    w=0
    s=0
    k=0
    ans=0
    a=len(A)
    b=len(B)
    #D=[0]*a
    #L=[0]*b
    for i in range(a):
        r=X-A[i]
        #D[i]=s
        for j in range(s,b):
            if(B[j]>=r):
                w=j+1
                k=j

                #D[i]+=1
                #L[j]=a-i]
                ans+=B[j]*(a-i)
            else:
                k=j
                break

        s=k
        ans+=w*A[i]

        """
        for i in range(a):
            ans+=A[i]*D[i]
        for i in range(b):
            ans+=B[i]*L[i]
        """
    return ans
#ans=sum(8,A,B)
#print(ans)
def binary(S,E,M,K):
    X=int((S+E)/2)
    n=sum(X,A,B)
    if(n>M):
        binary(X,E,M,K)


    if(n<M):
        binary(S,X,M,K)


    if(n==M):
        K = X

S=2*A[0]
E=2*A[N-1]
X=int((S+E)/2)
while(1):
    n=sumc(X,A,B)
    m=sumc(X+1,A,B)
    if(n>=M and M>m):
        break
    if(n>=M):
        S=X
        X=int((E+X)/2)

    if(n<M):
        E=X
        X=int((S+X)/2)


print(X)
#binary(S,E,M,K)
k=sumc(X,A,B)
print(k)
s=0
ans=0
w=0
if(k==M):
    """
    for i in range(N):
        r=X-A[i]
        for j in range(s,N):
            if(B[j]>=r):
                w=j+1
                ans+=B[j]*(N-i)
            else:
                k=j
                break
            if(B[N-1]>=r):
                k=N-1
        s=k
        ans+=A[i]*w
    """
    ans=suml(X,A,B)
else:
    print("a")
    X=X+1

    t=sumc(X,A,B)
    #print(t)
    #print(X-1)
    ans=suml(X,A,B)
    ans+=(M-t)*(X-1)

print(ans)

Submission status: Wrong Answer

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] * times + (S[-1] - S[idx - 1])
    else:
        happy += A[i] * times + S[-1]
    print("happy={}".format(happy))
happy += (leftX - 1) * (M - times)

print(happy)

Submission status: Wrong Answer

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])
print(acum)
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: Wrong Answer

Solution code:
def judge(k,N,M,A):
    s = N
    t = 0
    for i in range(N):
        for j in reversed(range(s)):
            if A[i] + A[j] >= k:
                t += j + 1
                s = j + 1
                break
    if t == M:
        return 0
    if t > M:
        return 1
    return -1

def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort(reverse=True)
    u = 2 *  A[0]
    l = 0
    jj = 0
    a = 0
    while u-l>=2:
        m = (u + l)//2
        t1 = judge(m,N,M,A)
        t0 = judge(m-1,N,M,A)
        t2 = judge(m+1,N,M,A)
        if t1 == 0:
            a = m
            break
        if t1 > 0:
            if t2 == 0:
                a = m+1
                break
            if t2 < 0:
                a = m
                break
            l = m
        else:
            if t0 >= 0:
                a = m-1
                break
            u = m
    if a == 0:
        a = l
    r = 0
    s = N
    B = []
    tmp = 0
    for i in A:
        tmp += i
        B.append(tmp)
    ll = []
    t = 0
    for i in range(N):
        for j in reversed(range(s)):
            if A[i] + A[j] >= a:
                s = j + 1
                t += j + 1
                ll.append(j)
                break
    for i in range(len(ll)):
        r += (ll[i]+1) * A[i] + B[ll[i]]
    return r - (t - M) * m
    
print(main())

Submission status: Wrong Answer

Solution code:
def judge(k,N,M,A):
    s = N
    t = 0
    for i in range(N):
        for j in reversed(range(s)):
            if A[i] + A[j] >= k:
                t += j + 1
                s = j + 1
                break
    if t == M:
        return 0
    if t > M:
        return 1
    return -1

def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort(reverse=True)
    u = 2 *  A[0]
    l = 0
    jj = 0
    a = 0
    while True:
        m = (u + l)//2
        t1 = judge(m,N,M,A)
        t0 = judge(m-1,N,M,A)
        t2 = judge(m+1,N,M,A)
        if t1 == 0:
            a = m
            break
        if t1 > 0:
            if t2 == 0:
                a = m+1
                break
            if t2 < 0:
                a = m
                break
            l = m
        else:
            if t0 >= 0:
                a = m-1
                break
            u = m
    r = 0
    s = N
    B = []
    tmp = 0
    for i in A:
        tmp += i
        B.append(tmp)
    ll = []
    t = 0
    for i in range(N):
        for j in reversed(range(s)):
            if A[i] + A[j] >= a:
                s = j + 1
                t += j + 1
                ll.append(j)
                break
    for i in range(len(ll)):
        r += (ll[i]+1) * A[i] + B[ll[i]]
    return r - (t - M) * m
    
print(main())

Submission status: Wrong Answer

Solution code:
def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort(reverse=True)
    u = 2 *  A[0]
    l = 0
    k = []
    jj = 0
    while jj < 30:
        jj += 1
        m = (u + l)//2
        t = 0
        s = N
        p = 0
        for i in range(N):
            for j in reversed(range(s)):
                if A[i] + A[j] >= m:
                    if A[i] + A[j] == m:
                        p += 1
                    k.append(j)
                    t += j+1
                    s = j+1
                    break
        if t >= M and t - p <= M:
            break
        elif t > M:
            l = m
        else:
            u = m
        k = []
    r = 0   
    s = N
    B = []
    tmp = 0
    for i in A:
        tmp += i
        B.append(tmp)
    for i in range(len(k)):
        r += (k[i]+1) * A[i] + B[k[i]]
    return r - (t - M) * m
    
print(main())

Submission status: Wrong Answer

Solution code:
def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort(reverse=True)
    u = 2 *  A[0]
    l = 0
    k = []
    jj = 0
    while jj < 30:
        jj += 1
        m = (u + l)//2
        t = 0
        s = N
        p = 0
        for i in range(N):
            for j in reversed(range(s)):
                if A[i] + A[j] >= m:
                    if A[i] + A[j] == m:
                        p += 1
                    k.append(j)
                    t += j+1
                    s = j+1
                    break
        if t >= M and t - p <= M:
            break
        elif t > M:
            l = m + 1
        else:
            u = m - 1
        k = []
    r = 0   
    s = N
    B = []
    tmp = 0
    for i in A:
        tmp += i
        B.append(tmp)
    for i in range(len(k)):
        r += (k[i]+1) * A[i] + B[k[i]]
    return r - (t - M) * m
    
print(main())

Submission status: Wrong Answer

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 - 1] + cnt * j
    M -= cnt

happy += M * X

print(happy)

Submission status: Wrong Answer

Solution code:
def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort(reverse=True)
    u = 2 *  A[0]
    l = 0
    k = []
    while True:
        m = (u + l)//2
        t = 0
        s = N
        p = 0
        for i in range(N):
            for j in reversed(range(s)):
                if A[i] + A[j] >= m:
                    if A[i] + A[j] == m:
                        p += 1
                    k.append(j)
                    t += j+1
                    s = j+1
                    break
        if t >= M and t - p <= M:
            break
        elif t > M:
            l = m + 1
        else:
            u = m - 1
        k = []
    return 0
    r = 0   
    s = N
    B = []
    tmp = 0
    for i in A:
        tmp += i
        B.append(tmp)
    for i in range(len(k)):
        r += (k[i]+1) * A[i] + B[k[i]]
    return r - (t - M) * m
    
print(main())

Submission status: Wrong Answer

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
    happy += cumsum_A[-1] - cumsum_A[idx - 1] + cnt * j
    M -= cnt

happy += M * X

print(happy)

Submission status: Wrong Answer

Solution code:
def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort(reverse=True)
    u = 2 *  A[0]
    l = 0
    k = []
    jj = 0
    while jj < 15:
        jj += 1
        m = (u + l)//2
        t = 0
        s = N
        p = 0
        for i in range(N):
            for j in reversed(range(s)):
                if A[i] + A[j] >= m:
                    if A[i] + A[j] == m:
                        p += 1
                    k.append(j)
                    t += j+1
                    s = j+1
                    break
        if t >= M and t - p < M:
            break
        elif t > M:
            l = m + 1
        else:
            u = m - 1
        k = []
    r = 0   
    s = N
    for i in range(N):
        for j in range(s):
            if A[i] + A[j] >= m:
                r += A[i] + A[j]
            if A[i] + A[j] < m:
                s = j + 1
                break
    return r - (t - M) * m
    
print(main())

Submission status: Wrong Answer

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
        mid = 0

        while right-left > 1 or c < M:
            # print("test: ", left, " ", right)
            mid = (left+right)//2
            # print("mid: ", mid)
            # mid以上の価値の握手の個数を求める
            # s = []
            s = 0
            c = 0
            for i in range(N):
                p = bisect_left(A, mid-A[i])
                # 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
        
        s -= (c-M)*mid

        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: Wrong Answer

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
        mid = 0

        while right-left > 1 or c < M:
            # print("test: ", left, " ", right)
            mid = (left+right)//2
            # print("mid: ", mid)
            # mid以上の価値の握手の個数を求める
            # s = []
            s = 0
            c = 0
            for i in range(N):
                p = bisect_left(A, mid-A[i])
                # 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)*mid

        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: Wrong Answer

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
    print(l)
    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: Wrong Answer

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
    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: Wrong Answer

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 + 1)
rui = [n] * (maxA * 2 + 1)

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

accum = 0  
for i in range(maxA * 2):
  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
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: Wrong Answer

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


from bisect import bisect_left, bisect_right
from heapq import heapify, heappop, heappush

def solve(N: int, M: int, A: "List[int]"):
        
    def binary_search(ok: int, ng: int):
        s = []
        # s = 0
        c = 0

        while abs(ng-ok) > 1:
            # print("test: ", ok, " ", ng)
            mid = (ok+ng)//2
            # print("mid: ", mid)
            # mid以上の価値の握手の個数を求める
            s = []
            c = 0
            for i in range(N):
                a = A[:i] + A[i+1:]
                a = A.copy()
                for j in range(len(a)):
                    a[j] += A[i]
                p = bisect_right(a, mid)
                s.extend(a[p:])
                c += len(a[p:])

                # print(a, a[p:], sum(s), c)
            
            # mid以上の握手の個数がM以上か否か

            if c > M:
                ok = mid
               
            else:
                ng = mid
                mi = ok

        if c > M:
            heapify(s)
            for i in range(c-M):
                heappop(s)

        # print(s)
        return sum(s)

    A.sort()
    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: Wrong Answer

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


def solve(N: int, M: int, A: "List[int]"):
    A.sort()
    # Kは握手の個数
    # def f(K: int):
    #     if M == K:
    #         return True
    #     else:
    #         return False
        
    from bisect import bisect_left, bisect_right
    from heapq import heapify, heappop, heappush
    def binary_search(ok: int, ng: int):
        s = []
        heapify(s)
        c = 0
        
        while abs(ok-ng) > 1:
            # print("test: ", ok, " ", ng)
            mid = (ok+ng)//2
            # print("mid: ", mid)
            # mid以上の価値の握手の個数を求める
            s = []
            heapify(s)
            c = 0
            for i in range(N):
                a = A[:i] + A[i+1:]
                a = A.copy()
                for j in range(len(a)):
                    a[j] += A[i]
                p = bisect_right(a, mid)
                # s.extend(a[p:])
                for j in a[p:]:
                    heappush(s, j)
                c += len(a[p:])

                # print(a, a[p:], sum(s), c)
            
            # mid以上の握手の個数がM以上か否か
            if c > M:
                ok = mid
            else:
                ng = mid

        if len(s) > M:
            for i in range(len(s)-M):
                heappop(s)

        # print(s)
        return sum(s)

    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: Wrong Answer

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:
      print(i,j)
      ans += C[-1]-C[j]+A[i]*(N-j)
      m += N-j
      break
    j += 1
ans += (M-m)*l
print(ans)