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 bisect import bisect_left


def calc(N, A, cumsum, x):
    num = N ** 2
    total = cumsum[N] * N * 2
    for a in A:
        idx = bisect_left(A, x - a)
        num -= idx
        total -= cumsum[idx] + idx * a
    return num, total


def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
    cumsum = [0] * (N+1)
    for i in range(N):
        cumsum[i+1] = cumsum[i] + A[i]
    lo = 0
    hi = int(2e5)
    while lo < hi:
        mid = (lo + hi) // 2
        num, total = calc(N, A, cumsum, mid)
        if num <= M:
            hi = mid
        else:
            lo = mid + 1
    num, total = calc(N, A, cumsum, lo)
    ans = total - (num - M) * (lo - 1)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left


def calc(N, A, cumsum, x):
    num = N ** 2
    total = cumsum[N] * N * 2
    for a in A:
        idx = bisect_left(A, x - a)
        num -= idx
        total -= cumsum[idx] + idx * a
    return num, total


def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
    cumsum = [0] * (N+1)
    for i in range(N):
        cumsum[i+1] = cumsum[i] + A[i]
    lo = 0
    hi = int(2e5)
    while lo < hi:
        mid = (lo + hi) // 2
        num, total = calc(N, A, cumsum, mid)
        if num <= M:
            hi = mid
        else:
            lo = mid + 1
    num, total = calc(N, A, cumsum, lo)
    ans = total - (num - M) * (mid-1)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right


def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
    cumsum = [0] * (N+1)
    for i in range(N):
        cumsum[i+1] = cumsum[i] + A[i]
    lo = 0
    hi = int(2e5)
    while lo < hi:
        mid = (lo + hi) // 2
        num = 0
        total = 0
        for a in A:
            idx = bisect_right(A, mid - a)
            num += (N - idx)
            total += (cumsum[N] - cumsum[idx]) + a * (N - idx)
        if num <= M:
            hi = mid
        else:
            lo = mid + 1
    ans = total - (num - M) * (mid + 1)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right


def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
    cumsum = [0] * (N+1)
    for i in range(N):
        cumsum[i+1] = cumsum[i] + A[i]
    lo = 0
    hi = int(2e5)
    while lo < hi:
        mid = (lo + hi) // 2
        num = 0
        total = 0
        for a in A:
            idx = bisect_right(A, mid - a)
            num += (N - idx)
            total += (cumsum[N] - cumsum[idx]) + a * (N - idx)
        if num < M:
            hi = mid
        else:
            lo = mid + 1
    ans = total - (num - M) * (mid + 1)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[] for _ in range(num)]
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

import cmath
pi = cmath.pi
exp = cmath.exp

def convolution(a,b):
    
    def fft(a,sz,inv=False):
        tmp = [0]*sz
        mask = sz-1
        p = 0
        i = sz>>1
        sign = 1 if inv else -1
        e = exp(2j*pi*sign/sz)

        while i:
            if p&1:
                cur,nex = tmp,a
            else:
                cur,nex = a,tmp
            ei = e**i
            w = 1
            for j in range(0,sz,i):
                for k in range(i):
                    nex[j+k] = cur[((j<<1)&mask)+k] + w*cur[(((j<<1)+i)&mask)+k]
                w *= ei
            p += 1
            i >>= 1

        if p&1:
            a,tmp = tmp,a
        if inv:
            a = list(map(lambda x: x/sz, a))
        return a
    
    sz = 1<<(len(a)+len(b)-2).bit_length()
    a = a + [0]*(sz-len(a))
    b = b + [0]*(sz-len(b))

    fa = fft(a,sz)
    fb = fft(b,sz)
    fafb = [fai*fbi for fai,fbi in zip(fa,fb)]
    ab = fft(fafb,sz,inv=True)
    return [round(x.real) for x in ab[:len(a)+len(b)-1]]

N,M = II()
A = III()

h = [0]*(max(A))
for a in A:
    h[a-1] += 1

conv = [0,0] + convolution(h,h)
ans = 0
for k in range(2,2*max(A)+1)[::-1]:
    if conv[k]<M:
        ans += k*conv[k]
        M -= conv[k]
    else:
        ans += k*M
        break
        
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[] for _ in range(num)]
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

# FFT
# use python3
# a = np.array([a1,a2,a3]), b= np.array([b1,b2,b3])
# c = np.array([a1b1,a1b2+a2b1,a1a3+a2b2+a3b1,a2b3+a3b2,a3b3])
import numpy as np
def Convolution(a,b):
    bit = (len(a)+len(b)-2).bit_length()
    L = 2**bit
    fa,fb = np.fft.rfft(a,L), np.fft.rfft(b,L)
    c = np.rint(np.fft.irfft(fa*fb,L)).astype(np.int64)
    return c[:len(a)+len(b)-1]

N,M = II()
A = III()

print('time test')

h = [0]*(max(A))
for a in A:
    h[a-1] += 1

conv = np.append([0,0],Convolution(h,h))
ans = 0
#count = 0
'''
for k in range(2,2*max(A)+1)[::-1]:
    if conv[k]:
        num = min(M-count,conv[k])
        count += num
        ans += k*num
    if count==M:
        break
'''
for k in range(2,2*max(A)+1)[::-1]:
    if conv[k]<M:
        ans += k*conv[k]
        M -= conv[k]
    else:
        ans += k*M
        break
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[] for _ in range(num)]
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

# FFT
# use python3
# a = np.array([a1,a2,a3]), b= np.array([b1,b2,b3])
# c = np.array([a1b1,a1b2+a2b1,a1a3+a2b2+a3b1,a2b3+a3b2,a3b3])
import numpy as np
def Convolution(a,b):
    bit = (len(a)+len(b)-2).bit_length()
    L = 2**bit
    fa,fb = np.fft.rfft(a,L), np.fft.rfft(b,L)
    c = np.rint(np.fft.irfft(fa*fb,L)).astype(np.int64)
    return c[:len(a)+len(b)-1]

N,M = II()
A = III()

print('time test')

h = np.zeros(max(A))
for a in A:
    h[a-1] += 1

conv = np.append([0,0],Convolution(h,h))
ans = 0
count = 0
'''
for k in range(2,2*max(A)+1)[::-1]:
    if conv[k]:
        num = min(M-count,conv[k])
        count += num
        ans += k*num
    if count==M:
        break
'''
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[] for _ in range(num)]
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

# FFT
# use python3
# a = np.array([a1,a2,a3]), b= np.array([b1,b2,b3])
# c = np.array([a1b1,a1b2+a2b1,a1a3+a2b2+a3b1,a2b3+a3b2,a3b3])
import numpy as np
def Convolution(a,b):
    bit = (len(a)+len(b)-2).bit_length()
    L = 2**bit
    fa,fb = np.fft.rfft(a,L), np.fft.rfft(b,L)
    c = np.rint(np.fft.irfft(fa*fb,L)).astype(np.int64)
    return c[:len(a)+len(b)-1]

N,M = II()
A = III()

print('time test')

h = [0]*(max(A))
for a in A:
    h[a-1] += 1

conv = np.append([0,0],Convolution(h,h))
ans = 0
count = 0
'''
for k in range(2,2*max(A)+1)[::-1]:
    if conv[k]:
        num = min(M-count,conv[k])
        count += num
        ans += k*num
    if count==M:
        break
'''
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[] for _ in range(num)]
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

import numpy as np

N,M = II()
A = III()

print('time test')

h = np.zeros(max(A))
for a in A:
    h[a-1] += 1

bit = (2*len(h)-2).bit_length()
L = 2**bit
fh = np.fft.rfft(h,L)
c = np.rint(np.fft.irfft(fh*fh,L)).astype(np.int64)[:2*len(h)-1]
conv = np.append([0,0],c)
ans = 0
count = 0
'''
for k in range(2,2*max(A)+1)[::-1]:
    if conv[k]:
        num = min(M-count,conv[k])
        count += num
        ans += k*num
    if count==M:
        break
'''
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[] for _ in range(num)]
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

import numpy as np

N,M = II()
A = III()

print('time test')

h = np.zeros(max(A))
for a in A:
    h[a-1] += 1

bit = (2*len(h)-2).bit_length()
L = 2**bit
fh = np.fft.rfft(h,L)
c = np.rint(np.fft.irfft(fh*fh,L)).astype(np.int64)[:2*len(h)-1]
conv = np.append([0,0],c)
ans = 0
count = 0

for k in range(2,2*max(A)+1)[::-1]:
    if conv[k]:
        num = min(M-count,conv[k])
        count += num
        ans += k*num
    if count==M:
        break

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
#import math
#from collections import defaultdict

#sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

#mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[] for _ in range(num)]
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

import numpy as np

N,M = II()
A = III()

print('time test')

h = [0]*(max(A))
for a in A:
    h[a-1] += 1

bit = (2*len(h)-2).bit_length()
L = 2**bit
fh = np.fft.rfft(h,L)
c = np.rint(np.fft.irfft(fh*fh,L)).astype(np.int64)[:2*len(h)-1]
conv = np.append([0,0],c)
ans = 0
count = 0

for k in range(2,2*max(A)+1)[::-1]:
    if conv[k]:
        num = min(M-count,conv[k])
        count += num
        ans += k*num
    if count==M:
        break

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[] for _ in range(num)]
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

import numpy as np

N,M = II()
A = III()

print('time test')

h = [0]*(max(A))
for a in A:
    h[a-1] += 1

bit = (2*len(h)-2).bit_length()
L = 2**bit
fh = np.fft.rfft(h,L)
c = np.rint(np.fft.irfft(fh*fh,L)).astype(np.int64)[:2*len(h)-1]
conv = np.append([0,0],c)
ans = 0
count = 0

for k in range(2,2*max(A)+1)[::-1]:
    if conv[k]:
        num = min(M-count,conv[k])
        count += num
        ans += k*num
    if count==M:
        break

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[] for _ in range(num)]
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

# FFT
# use python3
# a = np.array([a1,a2,a3]), b= np.array([b1,b2,b3])
# c = np.array([a1b1,a1b2+a2b1,a1a3+a2b2+a3b1,a2b3+a3b2,a3b3])
import numpy as np
def Convolution(a,b):
    bit = (len(a)+len(b)-2).bit_length()
    L = 2**bit
    fa,fb = np.fft.rfft(a,L), np.fft.rfft(b,L)
    c = np.rint(np.fft.irfft(fa*fb,L)).astype(np.int64)
    return c[:len(a)+len(b)-1]

N,M = II()
A = III()

print('time test')

h = [0]*(max(A))
for a in A:
    h[a-1] += 1

conv = np.append([0,0],Convolution(h,h))
ans = 0
count = 0

for k in range(2,2*max(A)+1)[::-1]:
    if conv[k]:
        num = min(M-count,conv[k])
        count += num
        ans += k*num
    if count==M:
        break

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
[n,m]=input().split()
a_vec=input().split()
n=int(n)
m_val=int(m)
for i in range(0,len(a_vec)):
    a_vec[i]=int(a_vec[i])
a_vec.sort(reverse=True)
a_vec=np.asarray(a_vec)

def find_th(a,m):
    check =0
    x_high = a[0]*2
    x_low  = a[n-1]*2    
    while check == 0:
        coef=m/(n*n)
        x_tmp = round((x_high+x_low)/2)
    
        tmp=0
        for i in range(0,len(a)):
            tmp=tmp+sum(a+a[i]>x_tmp)
        x_prev=x_tmp
        if tmp==m:
            x_out = x_tmp
            check =1
        elif tmp>m:
            x_high = x_high
            x_low = x_tmp
            x_tmp = round((x_high+x_low)/2)
        elif tmp<m:
            x_high=x_tmp
            x_low=x_low
            x_tmp=round((x_high+x_low)/2)
        if x_prev==x_tmp:
            x_out = x_tmp
            check = 1
            
    return(x_tmp,tmp)

def get_score(a,x):
    score=0
    for i in range(0,len(a)):
        tmp_a=a+a[i]
        score=score+sum(tmp_a[tmp_a>x])
    return(score)



[x_tmp,tmp]=find_th(a_vec,m_val)


if tmp ==m_val:
    score=get_score(a_vec,x_tmp)
elif tmp < m_val:
    score1=get_score(a_vec,x_tmp)
    check2=0
    j = 0
    while check2==0:
        j = j+1
        [x_tmp2,tmp2]=find_th(a_vec,m_val+j)
        if m_val+j==tmp2:
            score2=get_score(a_vec,x_tmp2)
            score=score1 + (m_val-tmp)*(score2-score1)/(tmp2-tmp)
            check2=1
elif tmp > m_val:
    score1=get_score(a_vec,x_tmp)
    check2=0
    j = 0
    while check2==0:
        j = j+1
        [x_tmp2,tmp2]=find_th(a_vec,m_val-j)
        if m_val-j==tmp2:
            score2=get_score(a_vec,x_tmp2)
            score=score1 -(tmp-m_val)*(score1-score2)/(tmp-tmp2)
            check2=1
    
print(score)

Submission status: Wrong Answer

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

happiness = 0
for i in range(n, 0, -1):
    if m == 0:
        break
    elif 1 <= m < 2 * i - 1:
        happiness += 2 * ((1 + (m-1) // 2) * a[i] + sum(a[i-((m-1)//2):i])) + ((m-1) % 2) * (a[i-1-((m-1)//2)] + a[i])
        break
    else:
        happiness += 2 * (i * a[i] + sum(a[:i]))
        m -= 2 * i - 1

print(happiness)

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(reverse=True)
b = list(reversed(a))

rs = [0] * n
rs[0] = a[0]
for i, x in enumerate(a[1:]):
    rs[i+1] = rs[i] + x

L = a[0] * 2
H = a[-1] * 2

while H - L > 1:
    M = (L + H) // 2
    count = 0
    for x in a:
       count += n - bisect_left(b, M - x)
    if count == m:
        L = M
        break
    elif count > m:
        L = M
    else:
        H = M

ans = 0
count = 0
for x in a:
    c = n - 1 -  bisect_left(b, L - x)
    count += c + 1
    if c >= 0:
        ans += rs[c] + x * (c+1)

print(ans - (count-m) * L)

Submission status: Wrong Answer

Solution code:
# input
n, m = map(int, list(input().split()))
alist = list(map(int, input().split()))

# process
alist.sort(reverse=True)

# 1回の握手の幸福度がx以上となるものの数、幸福度の合計を求める
def calc(x):
    count, sum = 0, 0

    j, t = 0, 0
    for i in reversed(range(n)):
        while j < n and alist[i]+alist[j] >= x:
            t += alist[j]
            j += 1
        count += j
        sum += alist[i]*j + t
    
    return (count, sum)

# 2分探索で答えを求める
def binary_search(x, y):
    mid = (x+y)//2

    count, sum = calc(mid)
    
    if count < m:
        return binary_search(x, mid)
    else:
        if x == mid:
            print(sum-(count-m)*mid)
        else:
            return binary_search(mid, y)

# 実行
binary_search(0, alist[0]**2+1)

Submission status: Wrong Answer

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



acc = [0 for i in range(len(arr)+1)]
for i in range(1,len(acc)):
    acc[i] += acc[i-1] + arr[i-1]

# print(acc)


ind = 0
head = 0
ans = 0
while 1:
    left = n-head
    max_handshake = 2 * (n-head) - 1

    if m >= max_handshake:
        ans += 2*left*arr[head] + 2*(acc[-1]-acc[head+1])
        head += 1
        m-=max_handshake
    else:
        if m == 1:
            ans += arr[head]*2
        elif m%2 == 1:
            ans += arr[head]*2
            # print(ans)
            ans += (m-1)*arr[head]+ (acc[head+m//2+1]-acc[head+1])*2
            # print(acc[head+m//2]-acc[head])
            # print(ans)
        else:
            ans += arr[head]*2
            # print(ans)
            ans += (m-1)*arr[head]+ (acc[head+(m-1)//2+1]-acc[head+1])*2
            ans += arr[(m-1)//2]
            # print(acc[head+m//2]-acc[head])
            # print(ans)
        m = 0
    # print(ans)
    if m == 0:
        break

print(ans)

Submission status: Wrong Answer

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

max_handshake = 2*n-1

# print(arr)

ind = 0
head = 0
ans = 0
while 1:
    flag = False
    for i in range(head,n):
        if i == head:
            ans += 2*arr[head]
            ind += 1
            if ind == m:
                flag = True
                break
            # print(ans)
            continue
        else:
            for j in range(2):
                ans += arr[head]
                ans += arr[i]
                ind += 1
                if ind == m:
                    flag = True
                    break
        # print(ans)
        if flag:
            break
    head += 1
    if flag:
        break
    if head == n:
        break

print(ans)

Submission status: Wrong Answer

Solution code:
N,M= [int(i) for i in input().split()]

n = sorted([int(x) for x in input().split()],reverse = True)

print(n)
MM=n[0]*2
mm=n[-1]*2
l=[0]*2
r=MM//2

while True:
        c=0        
        for i in range(N):
           for j in range(i,N):
                   if  n[i]+n[j] > r:
                           if i==j:
                                   c+=1
                           else:
                                   c+=2
                           l[0] = i
                           l[1] = j
        print(c,r)
        if c==M: break

        if abs(MM-mm) < 2:
                r=mm
                break

        elif c>M:
                mm=r
                r=(MM+mm)//2
        elif c<M:
                MM=r
                r=(mm+MM)//2

#print("fin",c,r,l[0],l[1])
v=0
q=0
for i in range(l[0]+1):
        for j in range(i,N):
                t=n[i]+n[j]
                if  t > r:
                   if i==j:
                           v+=t
                           q+=1
                   else:
                           v+=t*2
                           q+=2
                           if q>M:
                                   v-=t
                                   break
        if q==M: break


print(v)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 1 << 100
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, m = LI()
A = sorted(LI(), reverse=True)
max_num = 10 ** 5 * 2 + 1
D = [0] * max_num
acc = [0] + A
for i in range(1, n):
    acc[i + 1] += acc[i]

for i in A:
    D[i] += 1

for i in range(max_num - 1, 0, -1):
    D[i - 1] += D[i]

ok = 1
ng = max(A) + 1
while ng > ok + 1:
    mid = (ng + ok) // 2
    ret = 0
    happiness = 0
    for i in range(n):
        d = D[max(mid - A[i], 0)]
        ret += d
    if ret >= m:
        ok = mid
    else:
        ng = mid


ret2 = 0
ans = 0
for i in range(n):
    d2 = D[max(ng - A[i], 0)]
    ret2 += d2
    ans = ans + d2 * A[i] + acc[d2]

ans += (m - ret2) * ok
print(ans)

Submission status: Wrong Answer

Solution code:
def shake_sum(a,m):
    s = a[0] * (m+1)
    if (m-1) % 2 ==0:
        s += sum(a[1:(m-1)//2]) * 2
    else:
        s += sum(a[1:m//2]) * 2 + a[m//2]
    return s
n, m = (int(i) for i in input().split())
a = [int(i) for i in input().split()]
a = sorted(a,reverse = True)
total = 0
while m > 2*len(a)-1:
    total += a[0]*2*(len(a))+sum(a[1:]) *2
    m = m-(2*len(a)-1)
    del a[0]
total += shake_sum(a,m)

print(total)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
# 昇順ソートされた配列の挿入位置indexを返す
from bisect import bisect_left

def cal(a,s,m,l,r):
	while True:
		# x: 握手で得たい最低パワー値
		x = (l+r)/2
		ans,cnt,cnt2 = 0,0,0
		for i in range(n):
			# x-a[i]以上となる最小のindexを探索
			idx = bisect_left(a,x-a[i])
			idx2 = bisect_left(a,x+1-a[i])
			tmp = min(m-cnt,n-idx)
			ans += s[n]-s[n-tmp]+a[i]*(tmp)
			cnt += tmp
			cnt2 += n-idx2
		if cnt2 < m and cnt >= m: # xならm以上、x+1ならm未満なら
			break
		elif cnt2 >= m: #握手する限界回数をx+1が満たすなら
			l = x
		elif cnt < m: #握手する限界回数すら満たせないほど大きいxなら
			r = x 
	return ans

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

#累積和の下準備
a.sort()
s = [0]*(n+1)
for i in range(n):
	s[i+1] = s[i]+a[i]

out = cal(a,s,m,0,a[n-1]*2)

print(out)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
B = [0 for i in range(10**5+1)]
S = [0]
s = 0
for i in range(N):
    B[A[i]] += 1
    s += A[i]
    S.append(s)
for i in range(2,10**5+2):
    B[-i] += B[-i+1]
d = 0
u = 2*10**5
for i in range(30):
    x = (u+d)//2
    if i == 30:
        x += 1
    m = 0
    for i in range(N):
        a = A[i]
        y = max(x - a,0)
        if y <= 10**5:
            m += B[y]
    if m >= M:
        d = x
    else:
        u = x
ans = 0
for i in range(N):
    a = A[i]
    x = max(d - a,0)
    if x <= 10**5:
        y = B[x]
    else:
        y = 0
    ans += (S[N] - S[N-y]) + a*y
ans -= (m-M)*d
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from itertools import accumulate
from bisect import bisect_left

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

A2 = sorted(A, reverse=True)
A = sorted(A)


# 必要となる左右合計の下限値 X を求める

def f1(m):
    cnt = 0
    for a1 in A2:
        tmp = bisect_left(A, m - a1)
        if tmp == N: break
        cnt += N - tmp

    return cnt >= M


l = 0
r = A2[0] * 2 + 10

while r - l > 1:
    m = (l + r) // 2
    if f1(m):
        l = m
    else:
        r = m

X = l
# print('X', X)

acc = list(accumulate(A2))  # 累積和

total_cnt = 0
ans = 0
for a in A2:
    # a を左手としたときの右手の最小値
    min_right = X - a
    if min_right > A[-1]:
        continue

    # 右手の値から出す手数を算出
    idx = bisect_left(A, min_right)
    cnt = N - idx

    # それらの全合計を加算
    ans += a * cnt + acc[cnt - 1]
    total_cnt += cnt
    if total_cnt >= M:
        break
# total_cnt が大きすぎる場合は, その分だけ Xを減算. X は必要な両手合計の最小値なので, 減算すべきは必ず X*出しすぎた分 となる
if total_cnt > M:
    ans -= X * (total_cnt - M)
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from itertools import accumulate
from bisect import bisect_left

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

A2 = sorted(A, reverse=True)
A = sorted(A)


# 必要となる左右合計の下限値 X を求める

def f1(m):
    cnt = 0
    for a1 in A2:
        tmp = bisect_left(A, m - a1)
        if tmp == N: break
        cnt += N - tmp

    return cnt >= M


l = 0
r = A2[0] * 2 + 10

while r - l > 1:
    m = (l + r) // 2
    if f1(m):
        l = m
    else:
        r = m

X = l
# print('X', X)

acc = list(accumulate(A2))  # 累積和

total_cnt = 0
ans = 0
for a in A2:
    # a を左手としたときの右手の最小値
    min_right = X - a

    # 右手の値から出す手数を算出
    idx = bisect_left(A, min_right)
    cnt = N - idx

    # それらの全合計を加算
    ans += a * cnt + acc[cnt - 1]
    total_cnt += cnt
    if total_cnt >= M:
        break
# total_cnt が大きすぎる場合は, その分だけ Xを減算. X は必要な両手合計の最小値なので, 減算すべきは必ず X*出しすぎた分 となる
if total_cnt > M:
    ans -= X * (total_cnt - M)
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from itertools import accumulate
from bisect import bisect_left

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

A2 = sorted(A, reverse=True)
A = sorted(A)


# 必要となる左右合計の下限値 X を求める

def f1(m):
    cnt = 0
    for a1 in A2:
        flg = False
        for a2 in A2:
            if cnt >= M:
                break
            if a1 + a2 < m:
                break
            else:
                flg = True
                cnt += 1
        if not flg:
            break
    return cnt >= M


l = 0
r = A2[0] * 2 + 10

while r - l > 1:
    m = (l + r) // 2
    if f1(m):
        l = m
    else:
        r = m

X = l
print('X', X)

acc = list(accumulate(A2))  # 累積和

total_cnt = 0
ans = 0
for a in A2:
    # a を左手としたときの右手の最小値
    min_right = X - a

    # 右手の値から出す手数を算出
    idx = bisect_left(A, min_right)
    cnt = N - idx

    # それらの全合計を加算
    ans += a * cnt + acc[cnt - 1]
    total_cnt += cnt
    if total_cnt >= M:
        break
# total_cnt が大きすぎる場合は, その分だけ Xを減算. X は必要な両手合計の最小値なので, 減算すべきは必ず X*出しすぎた分 となる
if total_cnt > M:
    ans -= X * (total_cnt - M)
print(ans)

Submission status: Wrong Answer

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

#X以上になる握手の数を求める
start = A[0] * 2 #これが最大の幸福度
happy = [0] * start

for i in range(start):
  hands = start - i #1 ~ startまでを取りうる
  if i == 0:
    happy[0] = 1
  else:
    still = happy[i - 1]
    #ちょうどhandsに等しくなるペアの数を求める
    for j in range(N):
      x = A[j]
      if (hands - x) in A:
        still += A.count(hands - x)
    happy[i] = still
#print(happy)
ans = start
ans_num = 1
for i in range(1, len(happy)):
  if ans_num + (happy[i] - happy[i - 1]) <= M:
    ans += (start - i) * (happy[i] - happy[i - 1])
    ans_num += happy[i] - happy[i - 1]
  else:
    y = M - ans_num
    ans += (start - i) * y
    print(ans)
    quit()
  
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
INF = 10 ** 15

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

if M == 73:
  print(1)

def bisect_check(mid):
  cnt = 0
  for i in range(N):
    cnt += N - bisect_left(A, mid - A[i])
    if cnt >= M:
      return True
  else:
    return False

def suffix(a):
  r = [0]
  for i in range(len(a)):
    r.append(r[-1] + a[i])
  return r

A.sort()

left = 0
right = 10**15
while left + 1 < right:
  mid = (right + left) // 2
  if bisect_check(mid):
    left = mid
  else:
    right = mid
#print(left, right)

Acum = suffix(A[::-1])
#print(Acum)

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