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:
import sys
from bisect import bisect_left as bl
input = sys.stdin.readline
N, M = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
res = 0
def check(x):
  k = 0
  for i in range(N):
    y = N - bl(a, x - a[i])
    k += y
  #print(x, k)
  return k >= M

ok = 0
ng = sum(a) * N * 2 + 1
while ng - ok > 1:
  m = (ok + ng) // 2
  if check(m):
    ok = m
  else: ng = m

cs = [0] * (N + 1)
for i in range(N): cs[i + 1] = cs[i] + a[i]
k = 0
for i in range(N - 1, -1, -1):
  if k >= M: break
  y = bl(a, ok - a[i])
  if k + (N - y) > M:
    y = N - (M - k)
  else: k += (N - y)
  res += cs[-1] - cs[y] + (N - y) * a[i]
  #print(k)
print(res)

Submission status: Wrong Answer

Solution code:
import numpy as np
N,M = list(map(int,input().split()))
A = list(map(int,input().split()))
A.sort()
A = A[-M:]

ans = []
for i in range(len(A)):
  ans = np.r_[ans, A[i] + np.array(A)]
  #ans.sort()
  #ans = ans[-M:]

ans.sort()
print(int(sum(ans)))

Submission status: Wrong Answer

Solution code:
import itertools
import sys
def input():
    return sys.stdin.readline()[:-1]

n, m = map(int, input().split())
a = [int(i) for i in input().split()]

# aの直積
list1 = list(itertools.product(a, repeat=2))
# list1の各タプルを合計
sum1 = list(itertools.starmap(lambda x, y: x+y, list1))
sum1.sort()

# 値の大きい順にm個までの合計
print(sum(sum1[m:]))

Submission status: Wrong Answer

Solution code:
#!python3

from itertools import accumulate

def my_bisect(a, x, key, lo=0, hi=None, side="left"):
    if hi is None:
        hi = len(a)

    lov = key(a[lo])
    hiv = key(a[hi])

    if side == "left":
        while lo < hi:
            mid = (lo + hi) // 2
            miv = key(a[mid])

            if miv < val: lo, lov = mid+1, miv
            else: hi, hiv = mid, miv
    else:
        while lo < hi:
            mid = (lo + hi) // 2
            miv = key(a[mid])

            if val < miv: hi, hiv = mid, miv
            else: lo, lov = mid+1, miv

    return lo

from bisect import bisect_right

def resolve():
    N, M = map(int, input().rstrip().split())
    a = list(map(int, input().rstrip().split()))

    a.sort(reverse=True)
    b = list(accumulate(a))
    c = [-i for i in a]

    def count_shake(z):
        n = 0
        for i, x in enumerate(a):
            y = x - z
            #j = my_bisect(a, y, lambda x: -x, lo=i, side="right")
            j = bisect_right(c, y, i)
            if i == j:
                break
            n += 2 * (j - i) - 1
        return n



    lo = a[-1] * 2
    hi = a[0] * 2

    while True:
        mid = (lo + hi) // 2
        x = count_shake(mid)

        if hi - lo <= 2:
            break
        if x < M: hi = mid
        else: lo = mid

    s = 0
    d = [-1] * N
    m = x
    for i, x in enumerate(a):
        y = x - mid
        j = bisect_right(c, x - mid)
        if j == 0: break
        d[i] = j-1
        s += b[j-1] + x * j

    print(s - mid * (m-M))




if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
#!python3

from itertools import accumulate

def my_bisect(a, x, key, lo=0, hi=None, side="left"):
    if hi is None:
        hi = len(a)

    lov = key(a[lo])
    hiv = key(a[hi])

    if side == "left":
        while lo < hi:
            mid = (lo + hi) // 2
            miv = key(a[mid])

            if miv < val: lo, lov = mid+1, miv
            else: hi, hiv = mid, miv
    else:
        while lo < hi:
            mid = (lo + hi) // 2
            miv = key(a[mid])

            if val < miv: hi, hiv = mid, miv
            else: lo, lov = mid+1, miv

    return lo

from bisect import bisect_right

def resolve():
    N, M = map(int, input().rstrip().split())
    a = list(map(int, input().rstrip().split()))

    a.sort(reverse=True)
    b = list(accumulate(a))
    c = [-i for i in a]

    def count_shake(z):
        n = 0
        for i, x in enumerate(a):
            y = x - z
            #j = my_bisect(a, y, lambda x: -x, lo=i, side="right")
            j = bisect_right(c, y, i)
            if i == j:
                break
            n += 2 * (j - i) - 1
        return n



    lo = a[-1] * 2
    hi = a[0] * 2

    while True:
        mid = (lo + hi) // 2
        x = count_shake(mid)

        if hi - lo <= 2:
            break
        if x < M: hi = mid
        else: lo = mid

    s = 0
    for i, x in enumerate(a):
        y = x - mid
        j = bisect_right(c, x - mid)
        if j == 0: break
        s += b[j-1] + x * j

    print(s)




if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
import numpy as np
n,m = (int(w) for w in input().split()[:2])
a = [int(w) for w in input().split()[:n]]
a.sort(reverse=True)
x = np.array(a)

s = x + x[0]
ind = [0] * n

score = 0
for i in range(m):
    k = np.argmax(s)
    p = ind[k]+1
    score += s[k]
    print(k,p-1,s[k], score)
    if p == n:
        s[k] = -1
    else:
        ind[k] = p
        s[k] = x[k] + x[p]
print(score)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

xOK = A[0]*2
xNG = A[-1]*2 + 1
nx = 0
while xOK+1 < xNG:
    x = (xOK + xNG)//2
    nx = 0
    for a in A:
        print("np.searchsorted(A,x-a)=",np.searchsorted(A,x-a))
        nx += N-(np.searchsorted(A,x-a))
        if nx >= M:
            xOK = x
            break
    else:
        xNG = x

from itertools import accumulate
S=[0]+list(accumulate(A))

ans = 0
nnx = 0        
for a in A:
    nx = np.searchsorted(A,xOK-a,side='right')
    ans += a*(N-nx) + (S[N]-S[nx])
    nnx += (N-nx)
ans += xOK*(M-nnx)
        
    
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect

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

def cnt(a, m):
  cnt_tmp = 0
  for aa in a:
    bi = bisect.bisect_left(a, m - aa)
    #print(a, m, m - aa, bi)
    cnt_tmp += N - bi
  return cnt_tmp

A.sort()

l = 0
r = 10**10

while l+1 < r:
  mid = (l + r) // 2
  cnt_loop1 = cnt(A, mid)
  #cnt_loop2 = cnt(A, mid+1)
  #print(mid, cnt_loop1, cnt_loop2)
  
  if cnt_loop1 >= M:
    l = mid
  else:
    r = mid
#cnt_loop2 = cnt(A, mid+1)
 #print(mid, cnt_loop1, cnt_loop2)

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

answer = 0
for aa in A:
  bi = bisect.bisect_left(A, mid - aa)
  answer += S[N] - S[bi] + (N - bi) * aa
print(answer-(cnt_loop1-M)*mid)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate

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

A.sort(reverse=True)
d = [0] * (A[0] * 2 + 1)
for i in range(N):
    d[A[i]] += 1
d = list(accumulate(d[::-1]))[::-1]
S = list(accumulate([0] + A))

left = 0
right = A[0] * 2 + 1
while right - left > 1:
    mid = (left + right) // 2
    m = 0
    for i in range(N):
        m += d[max(1, mid - A[i])]
    if m >= M:
        left = mid
    else:
        right = mid

ans = 0
m = 0
for i in range(N):
    t = min(d[max(0, left - A[i])], M - m)
    ans += S[t] + A[i] * t
    m += t
ans += left * (M - m)
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate

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

A.sort(reverse=True)
d = [0] * (A[0] * 2 + 1)
for i in range(N):
    d[A[i]] += 1
d = list(accumulate(d[::-1]))[::-1]
S = list(accumulate([0] + A))

left = 0
right = A[0] * 2 + 1
while right - left > 1:
    mid = (left + right) // 2
    m = 0
    for i in range(N):
        m += d[max(0, mid - A[i])]
    if m >= M:
        left = mid
    else:
        right = mid

ans = 0
m = 0
for i in range(N):
    t = max(0, min(d[max(0, left - A[i])], M - m))
    ans += S[t] + A[i] * t
    m += t
ans += left * (M - m)
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate

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

A.sort(reverse=True)
d = [0] * (A[0] * 2 + 1)
for i in range(N):
    d[A[i]] += 1
d = list(accumulate(d[::-1]))[::-1]
S = list(accumulate([0] + A))

left = 0
right = A[0] * 2 + 1
while right - left > 1:
    mid = (left + right) // 2
    m = 0
    for i in range(N):
        m += d[max(0, mid - A[i])]
    if m >= M:
        left = mid
    else:
        right = mid

ans = 0
m = 0
for i in range(N):
    t = min(d[max(0, left - A[i])], M - m)
    ans += S[t] + A[i] * t
    m += t
ans += left * (M - m)
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate

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

A.sort(reverse=True)
d = [0] * (A[0] * 2 + 1)
for i in range(N):
    d[A[i]] += 1
d = list(accumulate(d[::-1]))[::-1]
b = list(accumulate([0] + A))

left = 0
right = A[0] * 2 + 1
while right - left > 1:
    mid = (left + right) // 2
    m = 0
    for i in range(N):
        m += d[max(0, mid - A[i])]
    if m >= M:
        left = mid
    else:
        right = mid

ans = 0
m = 0
for i in range(N):
    t = min(d[max(0, left - A[i])], M - m)
    ans += b[t] + A[i] * t
    m += t
print(ans)

Submission status: Wrong Answer

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

A.sort(reverse=True)
d = [0] * (A[0] * 2 + 1)
for i in range(N):
    d[A[i]] += 1
for i in range(A[0] * 2, 0, -1):
    d[i - 1] += d[i]

left = 0
right = A[0] * 2 + 1
while right - left > 1:
    mid = (left + right) // 2
    m = 0
    for i in range(N):
        m += d[max(0, mid - A[i])]
    if m >= M:
        left = mid
    else:
        right = mid

ans = 0
m = 0
for i in range(N):
    t = min(d[max(0, left - A[i])], M - m)
    ans += sum(A[:t]) + A[i] * t
    m += t
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
N,M = list(map(int,input().split()))
A = list(map(int,input().split()))
A.sort()
A = A[-int(M/2):]
ans = []
for a in A:
  ans = np.r_[ans,[a] + np.array(A)]
  #ans.extend([a] + np.array(A))
  ans.sort()

print(int(sum(ans[-M:])))

Submission status: Wrong Answer

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

ans = []
for a in A[-int(M/2):]:
  ans = np.r_[ans,[a] + np.array(A)]
  #ans.extend([a] + np.array(A))
  ans.sort()

print(int(sum(ans[-M:])))

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
A=[int(i) for i in input().split()]
A.sort()
s=sum(A)
SA=[0]
for a in A:
  SA.append(SA[-1]+a)
for i in range(n+1):
  SA[i]=s-SA[i]
l,r=0,2*max(A)
import bisect
def chk(x):
  ct=0
  for a in A:
    ct+=n-bisect.bisect_left(A,max(x-a,0))
  if ct>=m:
    return True
  else:
    return False

while r-l>1:
  mid=(l+r)//2
  if chk(mid):
    l=mid
  else:
    r=mid
ans=0
for a in A:
  aa=bisect.bisect_left(A,max(l-a,0))
  ans+=SA[aa]+a*(n-aa)
print(ans if m%2==1 else ans-l)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
A=[int(i) for i in input().split()]
A.sort()

SA=[0]
for a in A:
  SA.append(SA[-1]+a)

l,r=0,2*max(A)
import bisect
def chk(x):
  ct=0
  for a in A:
    ct+=n-bisect.bisect_left(A,max(x-a,0))
  if ct>=m:
    return True
  else:
    return False

while r-l>1:
  mid=(l+r)//2
  if chk(mid):
    l=mid
  else:
    r=mid
ans=0
for a in A:
  ans+=sum(A)-SA[bisect.bisect_left(A,max(l-a,0))]+a*(n-bisect.bisect_left(A,max(l-a,0)))
print(ans if m%2==1 else ans-l)

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_left,bisect_right
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    N,M=map(int,input().split())
    A=sorted(list(map(int,input().split())))
    S=[0]*(N+1)
    for i in range(N):
        S[i+1]=S[i]+A[i]
    def nibutan(ok,ng):
        while abs(ok-ng) > 1:
            mid = (ok + ng) // 2
            if solve(mid):
                ok = mid
            else:
                ng = mid
        return ok
    
    def solve(mid):
        c=0
        for i in range(N):
            c+=N-bisect_left(A,mid-A[i])
        if c>=M:
            return True
        else:
            return False
        
    x=nibutan(0,10**11)
    ans=0
    count=0
    for i in range(N):
        b_l=bisect_left(A,x-A[i])
        b_r=bisect_right(A,x-A[i])
        if b_r-b_l>1:
            memo=[i,b_l]
        count+=(N-b_l)
        ans+=S[N]-S[b_l]+A[i]*(N-b_l)
    if count==M:
        print(ans)
    else:
        print(ans+(M-count)*(A[i]+A[b_l]))
    

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np
from numpy.fft import rfft, irfft
N,M = list(map(int,input().split()))
A = list(map(int,input().split()))
X = np.zeros(10**5+1)
l = 2*(10**5)+10
for i in range(N):
    X[A[i]] += 1
data = np.rint(irfft(rfft(X, l)**2 ))
num = 0
ans = 0
for i in range(len(data) -1 ,0,-1):
    if data[i] != 0:
        if num + data[i] >= M:
            ans += (M - num) * i
            break
        else:
            ans += data[i]*i
            num += data[i]
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
from numpy.fft import rfft, irfft
N,M = list(map(int,input().split()))
A = list(map(int,input().split()))
X = np.zeros(10**5+1)
l = 2*(10**5)+10
for i in range(N):
    X[A[i]] += 1
data = np.rint(irfft(rfft(X, l)**2 ))
num = 0
ans = 0
#for i in range(len(data) -1 ,0,-1):
#    if int(round(data[i])) != 0:
#        if num + int(round(data[i])) >= M:
#            ans += (M - num) * i
#            break
#        else:
#            ans += int(round(data[i]))*i
#            num += int(round(data[i]))
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

Submission status: Wrong Answer

Solution code:
#import numpy as np

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

#a = np.tile(np.array(A), (N, 1))
#m = a + a.T

#print(np.sum(np.sort(m.flatten())[::-1][:M]))

Submission status: Wrong Answer

Solution code:
input_line = input().split(' ')
numN = int(input_line[0])
numM = int(input_line[1])
power = input().split(' ')
power = [int(i) for i in power]

power.sort(reverse = True)

people = 0

for i in range(1, numN + 1):
  if i ** 2 >= numM:
    people = i
    break

power = power[0:people]
candidate = []

for i in power:
  for j in power:
    candidate.append(i + j)

candidate.sort(reverse = True)
print(sum(candidate[0:numM]))

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
# maxnum = 2 * max(A)
# happydic = [0]*(maxnum + 1)
happydic = {}
for i in range(N):
    for j in range(N):
        if A[i]+A[j] in happydic.keys():
            happydic[A[i]+A[j]] = str(int(happydic[A[i]+A[j]])+1)
        else:
            happydic[A[i]+A[j]] = str(1)
left = M
happiness = 0
for val in sorted(happydic.keys(), reverse = True):
    if left > 0:
        temp = min(left, int(happydic[val]))
        happiness += temp * val
        left -= temp
    else:
        if left == 0:
            print(happiness)
            break

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
# maxnum = 2 * max(A)
# happydic = [0]*(maxnum + 1)
happydic = {}
for i in range(N):
    for j in range(N):
        if A[i]+A[j] in happydic.keys():
            happydic[A[i]+A[j]]+=1
        else:
            happydic[A[i]+A[j]] = 1
left = M
happiness = 0
for val in sorted(happydic.keys(), reverse = True):
    if left > 0:
        temp = min(left, happydic[val])
        happiness += temp * val
        left -= temp
    else:
        if left == 0:
            print(happiness)
            break

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
# maxnum = 2 * max(A)
# happydic = [0]*(maxnum + 1)
happydic = {}
for i in range(N):
    for j in range(N):
        if A[i]+A[j] in happydic.keys():
            happydic[A[i]+A[j]]+=1
        else:
            happydic[A[i]+A[j]] = 1
            
left = M
happiness = 0
for val in sorted(happydic.keys(), reverse = True):
    if left > 0:
        temp = min(left, happydic[val])
        happiness += temp * val
        left -= temp
    else:
        if left == 0:
            print(happiness)
            break
        else:
            print("something wrong!")

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
maxnum = 2 * max(A)
happydic = [0]*(maxnum + 1)
for i in range(N):
    for j in range(N):
        if i == j :
            happydic[2*A[i]]+=1
        else:
            happydic[A[i]+A[j]]+=1

left = M
happiness = 0
for i in range(0,maxnum+1)[::-1]:
    if happydic[i] != 0:
        if left > 0:
            temp = min(left, happydic[i])
            happiness += temp * i
            left -= temp
        else:
            if left == 0:
                print(happiness)
                break
            else:
                print("something wrong!")

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
B=[0]*(N+1)
for i in range(1,N+1):
    B[i]=B[i-1]+A[i-1]
D=[0]*(2*10**5+1)
for i in range(N):
    D[A[i]]+=1
for i in range(len(D)-1,0,-1):
    D[i-1]+=D[i]
#print(D)
#print(A)
#print(D)
l=-1
r=10**5+1
while r-l>1:
    m=(l+r)//2
    s=0
    for i in range(N):
        s+=D[max(1,m-A[i])]
    if s>=M:
        l=m
    else:
        r=m
ans=0
s=0
for i in range(N):
    v=max(0,r-A[i])
    t=max(0,min(D[v],M-s))
    ans+=B[t]+t*A[i]
    s+=t
ans+=l*(M-s)
print(ans)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
B=[0]*(N+1)
for i in range(1,N+1):
    B[i]=B[i-1]+A[i-1]
D=[0]*(10**5+1)
for i in range(N):
    D[A[i]]+=1
for i in range(len(D)-1,0,-1):
    D[i-1]+=D[i]
#print(D)
l=-1
r=10**5+1
while r-l>1:
    m=(l+r)//2
    s=0
    for i in range(N):
        s+=D[max(1,m-A[i])]
    if s>=M:
        l=m
    else:
        r=m
ans=0
s=0
for i in range(N):
    v=max(0,r-A[i])
    t=max(0,min(D[v],M-s))
    ans+=B[t]+t*A[i]
    s+=t
ans+=l*(M-s)
print(ans)

Submission status: Wrong Answer

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

k = 0
if m <= n*(n+1)//2:
  while (k+1)*(k+2)//2 <= m:
    k += 1
  for i in range(k):
    happy += a[i]*(2*(k-i))
  if k < n:
    b=m-k*(k+1)//2
    c=[0]*(k+1)
    for i in range(k+1):
      c[i]=a[i]+a[k-i]
    c.sort(reverse=True)
    happy += sum(c[:b])
else:
  while (k+1)*(k+2)//2 <= n**2 - m:
    k += 1
  happy = 2*n*sum(a)
  for i in range(k):
    happy -= a[n-1-i]*2*(k-i)
  b=m-k*(k+1)//2
  c=[0]*(k+1)
  for i in range(k+1):
    c[i]=a[n-1-k+i]+a[n-1-i]
  c.sort()
  happy -= sum(c[:b])

print(happy)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import numpy as np
N, M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
A = np.sort(np.array(A))
def shake_hands(x):
    cnt = 0
    X = np.searchsorted(A, x - A, side="left")
    cnt += N * N - X.sum()
    if cnt >= M:
        return 1
    return 0
left = 0
right = 10 ** 6
while True:
    m = (right + left) // 2
    if shake_hands(m) == 1 and shake_hands(m+1) == 0:
        maximum = m
        break
    elif shake_hands(m) == 0 and shake_hands(m-1) == 1:
        maximum = m - 1
        break
    elif shake_hands(m) == 1:
        left = m + 1
    else:
        right = m - 1
A_cumsum = np.array(np.cumsum(A))
ans = 0
a = np.searchsorted(A, (maximum + 1) - A, side="left")
X = np.searchsorted(A,right-A)
Acum = np.zeros(N+1,np.int64)
Acum[1:] = np.cumsum(A)
a = N * N - X.sum()
ans = (Acum[-1] - Acum[X]).sum() + (A * (N - X)).sum()
ans += (M - a) * maximum
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import numpy as np
N, M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
A = np.sort(np.array(A))
def shake_hands(x):
    cnt = 0
    X = np.searchsorted(A, x - A, side="left")
    cnt += N * N - X.sum()
    if cnt >= M:
        return 1
    return 0
left = 2
right = 10 ** 6
while True:
    m = (right + left) // 2
    if shake_hands(m) == 1 and shake_hands(m+1) == 0:
        maximum = m
        break
    elif shake_hands(m) == 0 and shake_hands(m-1) == 1:
        maximum = m - 1
        break
    elif shake_hands(m) == 1:
        left = m + 1
    else:
        right = m - 1
A_cumsum = np.array(np.cumsum(A))
ans = 0
cnt = 0
a = np.searchsorted(A, (maximum + 1) - A, side="left")
X = np.searchsorted(A,right-A)
Acum = np.zeros(N+1,np.int64)
Acum[1:] = np.cumsum(A)
a = N * N - X.sum()
ans = (Acum[-1] - Acum[X]).sum() + (A * (N - X)).sum()
ans += (M - a) * maximum
print(ans)

Submission status: Wrong Answer

Solution code:
import sys, math, itertools, collections, bisect
mans = float('inf')
mod = 10 **9 +7
ans = 0
count = 0
pro = 0

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

print('A', A)
print('B', B)
def solve_binary(mid):
  tmp = 0
  for i, ai in enumerate(A):
    tmp += N - bisect.bisect_left(A, mid-ai)
    #bisect.bisect_left(A, mid-ai)はaiに固定した時の、もう片方の最小の値のインデックス
    #tmpは、aiに固定した時のありうる個数（M)
  return tmp >= M

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


binresult = binary_search(2*10**5+1)
#Xを二分探索で得る
#binresult=ok
#print(binresult)
for i, ai in enumerate(A):
  ans += ai*(N - bisect.bisect_left(A, binresult-ai)) + B[N] - B[bisect.bisect_left(A, binresult-ai)]
  #print(ans, '=', ai, '*', N-bisect.bisect_left(A, binresult-ai), '+', B[N], '-', B[bisect.bisect_left(A, binresult-ai
  count += N - bisect.bisect_left(A, binresult-ai)
ans -= binresult * (count-M)
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

N ,M= map(int,input().split())
n0 = 2**int(np.ceil(np.log2(2*N - 1)))

A = np.zeros(n0)
B=np.zeros(n0)
l=list(map(int,input().split()))

for i in range(N):
    A[i]=l[i]
    B[i]=l[i]

C = np.fft.ifft( np.fft.fft(A)*np.fft.fft(B) )
ans=0
j=1
for ci in np.real(C[:2*N - 1] + 0.5):
    ans+=int(ci)*j
    j+=1
print(ans)

Submission status: Wrong Answer

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

ans=0
b=0
flag =True
for i in range(n):
    for j in range(n):
        if i==j:
            b+=1
            ans+=a[i]+a[j]
        else:
            if a[j]-a[j-1]>a[i]-a[i-1]:
                break
            else:
                if m-b==1:
                    b+=1
                    ans+=a[i]+a[j]
                else:
                    b+=2
                    ans+=2*(a[i]+a[j])

        if b==m:
            flag==True
            break
    if flag:
        break
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect

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

A.sort()

A

def geXcount(X):
    return N - bisect.bisect_left(A, X)

L = 0
R = 10 ** 5
# flag = False
while R - L > 1:
    tar = (L + R) // 2
    count = 0
    for i in range(N):
        count += geXcount(tar - A[i])
    if count > M:
        L = tar
    elif count <= M:
        R = tar
print(L, R, tar, count, M)
    

[[A[i] + A[j] for i in range(N)]  for j in range(N)]

# if count > M:
#     tar -= 1
#     count = 0
#     for i in range(N):
#         count += geXcount(tar - A[i])

count

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

ans = 0
if M > count:
    maxp = 0
    # print(tar)
    for i in range(N):
        j = geXcount(tar - A[i])
        if j < N:
            maxp = max(maxp, A[-j-1] + A[i])
        ans += B[j] + j * A[i]
    print(ans + (M-count) * maxp)
elif M < count:
    minp = 3 * (10 ** 5)
    for i in range(N):
        j = geXcount(tar - A[i])
        if j > 0:
            minp = min(minp, A[-j] + A[i])
        ans += B[j] + j * A[i]
    print(ans - (count - M) * minp)
else:
    for i in range(N):
        j = geXcount(tar - A[i])
        ans += B[j] + j * A[i]
    print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
sum_list = []
for a in A[:M//2]:
    for b in A[:M//2]:
        sum_list.append(a+b)
sum_list.sort(reverse=True)
ans = sum(sum_list[:M])
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
import heapq
import bisect

sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

N,M=LI()
As=LI()
As.sort()
len_As = len(As)
Acum=[As[0]]
for i in range(1, len_As):
    Acum.append(Acum[i-1]+As[i])
# print(As)
# print(Acum)

ok = 0
ng = 2*max(As)

pat = 0
sm = 0
while ng - ok > 1:
    mid_sum = (ok + ng)//2
    pat = 0
    sm = 0
    for A in As:
        A2 = mid_sum - A
        # print(A2)
        lft = bisect.bisect_left(As, A2)
        pat += len_As - lft
        sm += Acum[len_As-1] - (lft and Acum[lft-1]) + (len_As - lft)*A
    # print(pat, M, ok, ng)

    if pat < M: ng = mid_sum
    else: ok = mid_sum

pat = 0
sm = 0
for A in As:
    A2 = ok - A
    # print(A2)
    lft = bisect.bisect_left(As, A2)
    pat += len_As - lft
    sm += Acum[len_As-1] - (lft and Acum[lft-1]) + (len_As - lft)*A

# print("lo:{} hi:{} pat:{} sum:{}".format(ok, ng, pat, sm))

print(sm - (pat-M)*ok)

Submission status: Wrong Answer

Solution code:
import sys
import math
import heapq
import numpy
import bisect

sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

N,M=LI()
As=LI()
As.sort()
len_As = len(As)
Acum=numpy.cumsum(As)
# print(As)
# print(Acum)

ok = 0
ng = 2*max(As)

pat = 0
sm = 0
while ng - ok > 1:
    mid_sum = (ok + ng)//2
    pat = 0
    sm = 0
    for A in As:
        A2 = mid_sum - A
        # print(A2)
        lft = bisect.bisect_left(As, A2)
        pat += len_As - lft
        sm += Acum[len_As-1] - (lft and Acum[lft-1]) + (len_As - lft)*A
    # print(pat, M, ok, ng)

    if pat < M: ng = mid_sum
    else: ok = mid_sum

pat = 0
sm = 0
for A in As:
    A2 = ok - A
    # print(A2)
    lft = bisect.bisect_left(As, A2)
    pat += len_As - lft
    sm += Acum[len_As-1] - (lft and Acum[lft-1]) + (len_As - lft)*A

# print("lo:{} hi:{} pat:{} sum:{}".format(ok, ng, pat, sm))

print(sm - (pat-M)*ok)

Submission status: Wrong Answer

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

A = [int(tmp[i]) for i in range(N)]


score = [0 for i in range(N*N)]
print(A)
for i in range(N):
    for j in range(N):
        score[i*N+j] = A[i] + A[j]
score.sort()
sum = 0
for i in range(M):
    sum += score[N*N-1-i]
print(sum)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
import sys
import bisect

input = sys.stdin.readline

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

a.sort(reverse = True)

li = [0] * (2*10**5+1)

for i in a:
    li[i] += 1

acm = list(accumulate(li))
acm_a = list(accumulate(a))

l = 0
r = 2 * 10 ** 5

while l <= r:
    mid = (l + r) // 2
    count = 0
    for i in a:
        if mid - i >= 0:
            count += n - acm[mid-i]
        else:
            count += n
    if count >= m:
        l = mid + 1
    else:
        r = mid - 1

sum_idx = 0
ans = 0
b = a[::-1]
for left in a:
    right_min = l - left
    idx = bisect.bisect_left(b,right_min)
    print(idx)
    if n - idx > 0:
        sum_idx += n - idx
        ans += left * (n - idx) + acm_a[n - idx - 1]
        print(ans)

ans -= l * (sum_idx - m)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10000000)
# input = sys.stdin.readline
from bisect import *
# from collections import *
# from heapq import *
# import functools
# import itertools
# import math
INF = 500000
MOD = 10**9+7

N, M = map(int, input().split())
A = [int(x) for x in input().split()]
A.sort()
l, r = 0, 10**5+1
while l+1 < r:
    m = (l+r)//2
    cnt = 0
    for a in A:
        cnt += N-bisect_left(A, m-a)
    if cnt < M:
        r = m
    else:
        l = m
cnt = 0
for a in A:
    cnt += N-bisect_left(A, l-a)
f = [0]+A[::-1]
for i in range(N):
    f[i+1] += f[i]
cnt, ans = 0, 0
for a in A:
    i = bisect_left(A, l-a+1)
    ans += f[N-i]+(N-i)*a
    cnt += N-i
print(ans+(M-cnt)*l)