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
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, tmp = 0, 0, []
for a in A:
    i = bisect_left(A, l-a)
    ans += f[N-i]+(N-i)*a
    cnt += N-i
    if i != N:
        tmp.append(A[i]+a)
tmp.sort()
print(ans-sum(tmp[:cnt-M]))

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
import numpy as np
from numpy.fft import rfft,irfft

n,m=[int(j) for j in input().split()]
l=np.array([int(j) for j in input().split()])

a=np.bincount(l)

fft_len=1<<18
x=irfft(rfft(a,fft_len)*rfft(a,fft_len))
p=x.cumsum()
i=np.searchsorted(p,n*n-m)

q=n*n-m-p[i-1]

ans=(x[:i]*np.arange(i,dtype=np.int64)).sum()+i*q

print(int(l.sum()*2*n-ans))

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
import numpy as np
from numpy.fft import rfft,irfft

n,m=[int(j) for j in input().split()]
l=np.array([int(j) for j in input().split()])

a=np.bincount(l)

fft_len=2*10**5   #1~2*10**5まで
fft = np.fft.rfft
ifft = np.fft.irfft
Ff = fft(a,fft_len)
x=np.rint(ifft(Ff * Ff,fft_len)).astype(np.int64)
p=x.cumsum()
i=np.searchsorted(p,n*n-m)

q=n*n-m-p[i-1]

ans=(x[:i]*np.arange(i,dtype=np.int64)).sum()+i*q

print(int(l.sum()*2*n-ans))

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
import numpy as np
from numpy.fft import rfft,irfft

n,m=[int(j) for j in input().split()]
l=np.array([int(j) for j in input().split()])

a=np.bincount(l)

fft_len=2*10**5   #1~2*10**5まで
x=irfft(rfft(a,fft_len)*rfft(a,fft_len))
p=x.cumsum()
i=np.searchsorted(p,n*n-m)

q=n*n-m-p[i-1]

ans=(x[:i]*np.arange(i,dtype=np.int64)).sum()+i*q

print(int(l.sum()*2*n-ans))

Submission status: Wrong Answer

Solution code:
#降順ソートの方がうまくいきそう
n,m=map(int,input().split())
a=sorted(list(map(int,input().split())),reverse=True)
'''
cs=[]
sum=0
for i in range(n):
	sum+=a[i]
	cs.append(sum)
'''
cs=[0]*n
cs[0]=a[0]
if n>=2:
	for i in range(n-1):
		cs[i+1]=cs[i]+a[i+1]


#和が引数以上の場合をカウントする
def overX(x):
	count=0
	#両手が違う人を握るときのみ考える
	if a[0]*2<x:
		return 0
	else:
		for i in range(n):
			if a[i]+a[0]<x:
				count+=0
			else:
				lb, ub = 0, n
				#パターンAのにぶたん。左がOなので[lb,ub)で持つ。
				while ub-lb>1:
					mid=(lb+ub)//2
					if a[i]+a[mid]>=x:
						lb=mid
					else:
						ub=mid
				count+=lb+1
		return count
#print(overX(130))

#overX>=mなる最大のxを探す->xは小さい方が実現しやすいのでパターンA->[lb,ub)でもつ
lb=1 #実現しやすい方
ub=2*10**5
while ub-lb>1:
	mid=(ub+lb)//2
	if overX(mid)>=m:
		lb=mid
	else:
		ub=mid
#ub=overX(x)>=mなる最小のx。これ以上大きくするとmに満たなくなる。
maxx=lb

hp=0
#maxx+1以上の要素をすべてたす
#和がmaxx+1以上になる組み合わせの数だけhpを加え、countをインクリメントする
if a[0]*2>=maxx+1:
	for i in range(n):
		if a[i]+a[0]<maxx+1:
			break
		else:
			lb, ub = 0, n
			#パターンAのにぶたん。左がOなので[lb,ub)で持つ。
			while ub-lb>1:
				mid=(lb+ub)//2
				if a[i]+a[mid]>=maxx+1:
					lb=mid
				else:
					ub=mid
			#a[0]からa[lb]は、a[i]と足した時にx以上になり条件を満たす。
			hp+=a[i]*(lb+1)+cs[lb]
hp+=(m-overX(maxx+1))*maxx
print(hp)

Submission status: Wrong Answer

Solution code:
#降順ソートの方がうまくいきそう
n,m=map(int,input().split())
a=sorted(list(map(int,input().split())),reverse=True)
cs=[]
sum=0
for i in range(n):
	sum+=a[i]
	cs.append(sum)

#和が引数以上の場合をカウントする
def overX(x):
	count=0
	#両手が違う人を握るときのみ考える
	if a[0]*2<x:
		return 0
	else:
		for i in range(n):
			if a[i]+a[0]<x:
				count+=0
			else:
				lb, ub = 0, n
				#パターンAのにぶたん。左がOなので[lb,ub)で持つ。
				while ub-lb>1:
					mid=(lb+ub)//2
					if a[i]+a[mid]>=x:
						lb=mid
					else:
						ub=mid
				count+=lb+1
		return count
#print(overX(130))

#overX>=mなる最大のxを探す->xは小さい方が実現しやすいのでパターンA->[lb,ub)でもつ
lb=1 #実現しやすい方
ub=2*10**5
while ub-lb>1:
	mid=(ub+lb)//2
	if overX(mid)>=m:
		lb=mid
	else:
		ub=mid
#ub=overX(x)>=mなる最小のx。これ以上大きくするとmに満たなくなる。
maxx=lb

hp=0
#maxx+1以上の要素をすべてたす
#和がmaxx+1以上になる組み合わせの数だけhpを加え、countをインクリメントする
if a[0]*2>=maxx+1:
	for i in range(n):
		if a[i]+a[0]<maxx+1:
			break
		else:
			lb, ub = 0, n
			#パターンAのにぶたん。左がOなので[lb,ub)で持つ。
			while ub-lb>1:
				mid=(lb+ub)//2
				if a[i]+a[mid]>=maxx+1:
					lb=mid
				else:
					ub=mid
			#a[0]からa[lb]は、a[i]と足した時にx以上になり条件を満たす。
			hp+=a[i]*(lb+1)+cs[lb]
hp+=(m-overX(maxx+1))*maxx
print(hp)

Submission status: Wrong Answer

Solution code:
#降順ソートの方がうまくいきそう
n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort(reverse=True)
cs=[]
sum=0
for i in range(n):
	sum+=a[i]
	cs.append(sum)

#和が引数以上の場合をカウントする
def overX(x):
	count=0
	#両手が違う人を握るときのみ考える
	if a[0]*2<x:
		return 0
	else:
		for i in range(n):
			if a[i]+a[0]<x:
				count+=0
			else:
				lb, ub = 0, n
				#パターンAのにぶたん。左がOなので[lb,ub)で持つ。
				while ub-lb>1:
					mid=(lb+ub)//2
					if a[i]+a[mid]>=x:
						lb=mid
					else:
						ub=mid
				count+=lb+1
		return count
#print(overX(130))

#overX>=mなる最大のxを探す->xは小さい方が実現しやすいのでパターンA->[lb,ub)でもつ
lb=1 #実現しやすい方
ub=2*10**5
while ub-lb>1:
	mid=(ub+lb)//2
	if overX(mid)>=m:
		lb=mid
	else:
		ub=mid
#ub=overX(x)>=mなる最小のx。これ以上大きくするとmに満たなくなる。
maxx=lb

hp=0
#maxx+1以上の要素をすべてたす
#和がmaxx+1以上になる組み合わせの数だけhpを加え、countをインクリメントする
if a[0]*2>=maxx+1:
	for i in range(n):
		if a[i]+a[0]<maxx+1:
			break
		else:
			lb, ub = 0, n
			#パターンAのにぶたん。左がOなので[lb,ub)で持つ。
			while ub-lb>1:
				mid=(lb+ub)//2
				if a[i]+a[mid]>=maxx+1:
					lb=mid
				else:
					ub=mid
			#a[0]からa[lb]は、a[i]と足した時にx以上になり条件を満たす。
			hp+=a[i]*(lb+1)+cs[lb]
'''print(hp)
print(overX(maxx))
print(overX(maxx+1))
print(maxx)'''
hp+=(m-overX(maxx+1))*maxx
print(hp)

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_left
sys.setrecursionlimit(10 ** 7)

input = sys.stdin.readline


def main():
    n, m = map(int, input().split())
    A = [int(a) for a in input().split()]
    A.sort()
    right = 200000
    left = 0
    while(right-left != 1):
        mid = (right + left) // 2
        count = n**2
        for a in A:
            count -= bisect_left(A, mid - a)
        if count >= m:
            left = mid
        else:
            right = mid
    A.reverse()
    S = A.copy()
    A.reverse()
    for i in range(1, n):
        S[i] += S[i-1]
    ans = 0
    for a in A:
        index = n - bisect_left(A, left - a)
        if index == 0:
            continue
        ans += S[index-1] + index * a

    count = n**2
    for a in A:
        count -= bisect_left(A, left - a)
    ans -= left*(count - m)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

ans = A.tolist()
for a in A:
  ans.extend([a]+A)
  ans = np.sort(np.array(ans))[-M:].tolist()

print(int(sum(ans)))

Submission status: Wrong Answer

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

ans = np.array(A)
for a in A:
  for aa in A:
    ind = br(ans, a + aa)
    if ind <= M:
      ans = np.insert(ans,ind,a + aa)[-M:]
  
print(int(sum(ans)))

Submission status: Wrong Answer

Solution code:
import numpy as np

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

n0 = 2**int(np.ceil(np.log2(2*Amax)))#Amax+1以上となる最小の2のべき乗数

Afre=np.zeros(n0).astype(int)#パワーの頻度(1~Amax+1)
for i in range(N):
    Afre[A[i]]+=1

#astype(int)は切り捨てなので，rintで四捨五入してから．
S = np.rint(np.fft.irfft(np.fft.rfft(Afre)*np.fft.rfft(Afre))).astype(int)
Scum =S.cumsum()#累積和
bd = N*N-M#上からM個を取り出したい
i=np.searchsorted(Scum,bd)#価値iを生み出せる組みがM個以上ある
#価値iが生み出せる選び方の余分なものを引きたい
remove=((Scum[-1]-Scum[i])-M)*i
ans=0
for j in range(i+1,n0):
    ans+=S[j]*j
print(ans-remove)

Submission status: Wrong Answer

Solution code:
import itertools
n,m = map(int,input().split())
L = list(map(int,input().split()))
L.sort(reverse = True)
li = []
for i in range(n-1):
    li.append(L[i]*2)
    li.append(L[i]+L[i+1])
    li.append(L[i]+L[i+1])
li.append(L[-1]*2)
#print(L)
li.sort(reverse=True)
#print(li)
#print(sum(li[:m]))
h = itertools.combinations_with_replacement(L, 2)
i = 0
sum1 = 0
li2 = []
while i <=m:
    for v in itertools.combinations_with_replacement(L, 2):
        li2.append(sum(v))
    i += 1

li2 = list(set(li2))
li2.sort(reverse =True)
print(sum(li2[:m]))

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)
a_acm = list(accumulate(a))

a_cnt = [0] * (10 ** 6 + 1)
for e in a:
    a_cnt[e] += 1

acm = list(accumulate(a_cnt))


def count_handshake(x):
    ret = 0
    for e in a:
        if x - e - 1 >= 0:
            cnt = acm[-1] - acm[x-e-1]
        else:
            cnt = n

        ret += cnt

    return ret


left = 0
right = 10 ** 6

while right - left > 1:
    mid = (left + right) // 2
    if count_handshake(mid) >= m:
        left = mid
    else:
        right = mid

ans = 0
handshake_cnt = 0
for e in a:
    if left - e - 1 >= 0:
        cnt = n - acm[left-e-1]
    else:
        cnt = n
    if handshake_cnt + cnt > m:
        cnt = m - handshake_cnt
    if cnt > 0:
        ans += e * cnt + a_acm[cnt-1]
        handshake_cnt += cnt

print(ans)

Submission status: Wrong Answer

Solution code:
member, shake_num = map(int, input().split())
powers = list(map(int, input().split()))

sorted_power = sorted(powers, reverse=True)
p_sorted_power = sorted_power
power = 0
for po in range(len(powers)):
    if shake_num == 0:
            break 
    power1 = sorted_power.pop(0)
    power += power1 + power1
    shake_num -= 1
    for p in sorted_power:
        if shake_num == 0:
            break
        power += power1 + p
        shake_num -= 1
        if shake_num == 0:
            break
        power += power1 + p
        shake_num -= 1
print(power)

Submission status: Wrong Answer

Solution code:
import numpy as np
import bisect as bs
n,m=map(int,input().split())
a=list(map(int,input().split()))
a=np.array(a)
a=np.sort(a)
areverse=np.sort(a)[::-1]
cs=np.cumsum(areverse)
#print(areverse)
#print(cs)

def overX(x):
	count=0
	for i in range(n):
		j=bs.bisect_left(a,x-a[i])
		count+=n-j
	return count
	
#print(overX(130))
ov=[]
for i in range(2*10**5):
	ov.append(overX(i))
ok=0 #実現しやすい方
ng=2*10**5

#overX>=mなる最大のxを探す
while ng-ok>1:
	mid=(ok+ng)//2
	if ov[mid]>=m:
		ok=mid
	else:
		ng=mid
#print(ok)

hp=0
count=0
#ok+1以上の要素をすべてたす

for i in range(n):
	if ok+1-a[i]>0:
		j=bs.bisect_left(a,ok+1-a[i])
		#print("j=",end='')
		#print(j)
		if j!=n:
			hp+=a[i]*(n-j)+cs[n-j-1]
		#print("hp=",end='')
		#print(hp)
		count+=n-j
		#print("count=",end='')
		#print(count)
hp+=(m-count)*ok
print(hp)

Submission status: Wrong Answer

Solution code:
import numpy as np
import bisect as bs
n,m=map(int,input().split())
a=list(map(int,input().split()))
a=np.array(a)
a=np.sort(a)
areverse=np.sort(a)[::-1]
cs=np.cumsum(areverse)
#print(areverse)
#print(cs)

def overX(x):
	count=0
	for i in range(n):
		j=bs.bisect_left(a,x-a[i])
		count+=n-j
	return count
#print(overX(130))

ok=0 #実現しやすい方
ng=2*10**5

#overX>=mなる最大のxを探す
while ng-ok>1:
	mid=(ok+ng)//2
	if overX(mid)>=m:
		ok=mid
	else:
		ng=mid
#print(ok)

hp=0
count=0
#ok+1以上の要素をすべてたす

for i in range(n):
	if ok+1-a[i]>0:
		j=bs.bisect_left(a,ok+1-a[i])
		#print("j=",end='')
		#print(j)
		if j!=n:
			hp+=a[i]*(n-j)+cs[n-j-1]
		#print("hp=",end='')
		#print(hp)
		count+=n-j
		#print("count=",end='')
		#print(count)
hp+=(m-count)*ok
print(hp)

Submission status: Wrong Answer

Solution code:
def nmx(x):
    r = 0
    for a in As:
        r += d2[max(0, x-a)]
    return -r
def bsearch(target, min_i, max_i, func):
    # func(index) <= target < func(index+1) となるindexを返す
    if func(max_i) <= target:
        return max_i
    if target < func(min_i):
        return None
    index = (max_i + min_i)//2
    while True:
        if func(index) <= target:
            if target < func(index+1):
                return index
            index, min_i = (index+1 + max_i)//2, index+1
            continue
        index, max_i = (index-1 + min_i)//2, index-1
N, M = map(int, input().split())
As = sorted(list(map(int, input().split())))
mn, mx = As[0], As[-1]

j = 0
n = N
d2 = []
for i in range(10**6):
    while True:
        if j>=N:
            break
        if i <= As[j]:
            break
        j += 1
        n -= 1
    d2.append(n)
# d2[i] : i以上のaがいくつあるか
r = bsearch(-M, 1, 10**6, nmx)
from itertools import accumulate
aas = list(accumulate([0]+As[::-1]))
rr = 0
c = 0
for a in As[::-1]:
    if c+d2[max(0, r-a)] > M:
        rr += a*(M-c) + aas[M-c]
        break
    else:
        rr += a*d2[max(0, r-a)] + aas[d2[max(0, r-a)]]
    c += d2[max(0, r-a)]
print(rr)

Submission status: Wrong Answer

Solution code:

def nmx(x):
    r = 0
    for a in As:
        r += d2[max(0, x-a)]
    return -r
def bsearch(target, min_i, max_i, func):
    # func(index) <= target < func(index+1) となるindexを返す
    if func(max_i) <= target:
        return max_i
    if target < func(min_i):
        return None
    index = (max_i + min_i)//2
    while True:
        if func(index) <= target:
            if target < func(index+1):
                return index
            index, min_i = (index+1 + max_i)//2, index+1
            continue
        index, max_i = (index-1 + min_i)//2, index-1
N, M = map(int, input().split())
As = sorted(list(map(int, input().split())))
mn, mx = As[0], As[-1]

j = 0
n = N
d2 = []
for i in range(mx*2):
    while True:
        if j>=N:
            break
        if i <= As[j]:
            break
        j += 1
        n -= 1
    d2.append(n)
# d2[i] : i以上のaがいくつあるか
r = bsearch(-M, 1, mx*2, nmx)
from itertools import accumulate
aas = list(accumulate([0]+As[::-1]))
rr = 0
c = 0
for a in As[::-1]:
    if c+d2[max(0, r-a)] > M:
        rr += a*(M-c) + aas[M-c]
        break
    else:
        rr += a*d2[max(0, r-a)] + aas[d2[max(0, r-a)]]
    c += d2[max(0, r-a)]
print(rr)

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.sort(A)[::-1]
 
m = int(min(M,N))

def est(A):
  ans = np.zeros(1)
  for n,a in enumerate(A):
    if n>m:return ans
    ans = np.r_[ans, [a] + A]
  return np.sort(ans)[::-1][:M]

ans  = est(A)
print(int(sum(ans[:M])))

Submission status: Wrong Answer

Solution code:
from queue import PriorityQueue

def count(n, arr, s):
    cnt = 0
    for idx in range(n):
        if arr[idx] * 2 >= s:
            l = idx
            r = n - 1
            while l < r:
                mid = (l + r) // 2 + 1
                if arr[idx] + arr[mid] >= s:
                    l = mid
                else:
                    r = mid - 1
            cnt += 1 + 2 * (l - idx)
    return cnt

def calculate(n, m, arr, sum_arr, s):
    cnt = 0
    val = 0
    for idx in range(n):
        if arr[idx] * 2 >= s:
            l = idx
            r = n - 1
            while l < r:
                mid = (l + r) // 2 + 1
                if arr[idx] + arr[mid] >= s:
                    l = mid
                else:
                    r = mid - 1
            val += arr[idx] * 2 + 2 * (sum_arr[l+1] - sum_arr[idx+1] + arr[idx] * (l - idx))
            cnt += 1 + 2 * (l - idx)
    val -= s * (cnt - m)
    return val

def main():
    n, m = map(int, input().split())
    arr = list(map(int, input().split()))
    arr = sorted(arr, reverse=True)
    
    sum_arr = [0 for _ in range(n + 1)]
    for idx in range(n):
        sum_arr[idx+1] = sum_arr[idx] + arr[idx]

    l = 1
    r = 100000
    while l < r:
        mid = (l + r) // 2 + 1
        cnt = count(n, arr, mid)
        if cnt >= m:
            l = mid
        else:
            r = mid - 1

    print(calculate(n, m, arr, sum_arr, l))
        

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def run(N, M, A):
    A = sorted(A, reverse=True)
    right = A[0] * 2
    left = 0
    while left < right:
        X = (left + right) // 2
        # 左手の相手がaで、満足度がX以上となる組合せの数
        cnt = 0
        for a in A:
            cnt += search(A, X - a)
        if cnt >= M:
            res = X
            left = X + 1
        else:
            right = X - 1
    X = res
    # Xが決まったので、累積和で組合せの数分の値を求める
    sum_A = [0]
    for a in sorted(A):
        sum_A.append(sum_A[-1] + a)
    sum_cnt = 0
    ans = 0
    for a in A:
        cnt = search(A, X - a)
        sum_cnt += cnt
        if cnt > 0:
            ans += cnt * a + sum_A[-1] - sum_A[-cnt-1]
    if sum_cnt > M:
        ans -= X * (sum_cnt - M)
    return ans


def search(A, X):
    '''
    AのリストからX以上となる数値がいくつか探す
    Aはソート済み(降順)
    二分探索で実装O(logN)
    leftとrightはチェック未
    middleはループ終了後チェック済み
    '''
    left = 0
    right = len(A) - 1
    res = 0
    while left <= right:
        middle = (left + right) // 2
        if A[middle] >= X:
            res = middle + 1
            left = middle + 1
        else:
            right = middle - 1
    return res


def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    print(run(N, M, A))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,m,*a = map(int,open(0).read().split())
a2 = [i+j for i in a for j in a]
a2.sort()
if m > n*n/2:
    print(sum(a)*n - sum(a2[:n*n-m]))
else:
    print(sum(a2[-m:]))

Submission status: Wrong Answer

Solution code:
n,m,*a = map(int,open(0).read().split())
a2 = [i+j for i in a for j in a]
a2.sort()
if m > n*n/2:
    print(sum(a)*2 - sum(a2[:n*n-m]))
else:
    print(sum(a2[-m:]))

Submission status: Wrong Answer

Solution code:
import numpy as np
import bisect as bs
n,m=map(int,input().split())
a=list(map(int,input().split()))
a=np.array(a)
a=np.sort(a)
def overX(x):
	count=0
	for i in range(n):
		j=bs.bisect_left(a,x-a[i])
		count+=n-j
	return count
#print(overX(130))

ok=0 #実現しやすい方
ng=2*10**5

#overX>=mなる最大のxを探す
while ng-ok>1:
	mid=(ok+ng)//2
	if overX(mid)>=m:
		ok=mid
	else:
		ng=mid
#print(ok)

hp=0
count=0
for i in range(n):
	j=bs.bisect_left(a,ok-a[i])
	if count+n-j>m:
		hp+=np.sum(a[n-m+count:n])+a[i]*(m-count)
		break
	else:
		hp+=np.sum(a[j:n])+a[i]*(n-j)
		count+=n-j
print(hp)

Submission status: Wrong Answer

Solution code:
n, m = input().split()
print(n, m)

Submission status: Wrong Answer

Solution code:
import math
import numpy as np

n, m = map(int, input().split())
aaa = list(map(int, input().split()))
aaa = np.array(aaa)

def compute_number(x, aaa):
  num = 0
  for a in aaa:
    num += np.sum(a + aaa >= x)
  return num

def compute_score(x, aaa):
  score = 0
  for a in aaa:
    score += np.sum(a + aaa[np.where(a + aaa >= x)])
  return score

min_num = - n ** 2
max_num = 0
min_score = 0
max_score = aaa.max() ** 2

while min_score < max_score:
    mid_score = (min_score + max_score) // 2
    if - m < - compute_number(mid_score, aaa):
      max_score = mid_score
    else:
      min_score = mid_score + 1

print(compute_score(min_score - 1, aaa))

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
a = [10**18] + sorted(map(int, input().split()), reverse=True)


def solve(x):
   count = 0
   j = N
   for i in range(1, N+1):
      while a[i] + a[j] < x:
         j -= 1
      count += j
   
   return count


left, right = 0, 10**18
while left < right - 1:
   mid = (left + right) // 2
   if solve(mid) >= M:
      left = mid
      print("left:",left)

   else:
      right = mid
      print("right:",right)


acc = a[:]
acc[0] = 0
for i in range(N):
   acc[i+1] += acc[i]

ans = 0
j = N
for i in range(1, N+1):
   while a[i] + a[j] < left+1:
      j -= 1
   ans += a[i]*j + acc[j]
   M -= j

if M:
   ans += left * M

print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
N,M=map(int,input().split())
A=list(map(int,input().split()))
A=sorted(A)
B=[0]*N
B[-1]=A[-1]
for i in range(1,N):
    B[-1-i]=B[-i]+A[-i-1]

L=[0]*N
Max=A[-1]*2+1
Min=A[0]*2
s=0

while(s!=M):
    s=0
    l=Max
    r=Min
    C=(l+r)//2
    c=0
    for i in range(N):
        w=C-A[i]
        t=N-bisect.bisect(A,w)
        s+=t

    if(s<M):
        if(Max==C):
            break
        Max=C
    elif(s>M):
        if(Min==C):
            break
        Min=C
#print(C,M,s)
S=0
J=0
for i in range(N):
    w=C-A[i]
    a=bisect.bisect(A,w)
    t=N-a
    if t>0:
        S+=t*A[i]+B[-t]
    if(N==a):
        a-=1
    x=A[i]+A[a]
    if x>C and abs(C-J)>abs(C-x):
        J=x

print(S-J*(s-M))

Submission status: Wrong Answer

Solution code:
import bisect
N,M=map(int,input().split())
A=list(map(int,input().split()))
A=sorted(A)
B=[0]*N
B[-1]=A[-1]
for i in range(1,N):
    B[-1-i]=B[-i]+A[-i-1]

L=[0]*N
Max=A[-1]*2+1
Min=A[0]*2
s=0

while(s!=M):
    s=0
    l=Max
    r=Min
    C=(l+r)//2
    c=0
    for i in range(N):
        w=C-A[i]
        a=bisect.bisect(A,w)
        t=N-a
        s+=t
        if(N==a):
            a-=1
        x=A[i]+A[a]
        
    if(s<M):
        if(Max==C):
            break
        Max=C
    elif(s>M):
        if(Min==C):
            break
        Min=C
#print(C,M,s)
S=0
J=0
for i in range(N):
    w=C-A[i]
    a=bisect.bisect(A,w)
    t=N-a
    if t>0:
        S+=t*A[i]+B[-t]
    if(N==a):
        a-=1
    x=A[i]+A[a]
    if x>=C and abs(C-J)>abs(C-x):
        J=x

print(S-J*(s-M))

Submission status: Wrong Answer

Solution code:
import bisect

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
rev_A = A[::-1]

def check(x, a=A, m=M):
  result = False
  n = len(a)
  count = 0
  for ai in a:
    count += (n - bisect.bisect_left(a, x-ai))
  
  return count>=m


left = 0
right = 2*10**5 + 1
mid = (left + right) // 2
while right - left > 1:
  if check(mid):
    left = mid
  else:
    right = mid
    
  mid = (left + right)//2

x = left
if check(right):
  x = right

accum_A = [rev_A[0]]
for i, a in enumerate(rev_A):
  if i == 0:
    continue
  accum_A.append(accum_A[-1] + a)


ans = 0
count = 0
surplus = 2*10**5
for ai in rev_A:
  idx = bisect.bisect_left(A, x-ai)
  ans += (N-idx)*ai + accum_A[N-idx-1]
  count += N - idx
  surplus = min(surplus, ai+A[idx])
  if count >= M:
    break

print(ans - (count-M)*surplus)

Submission status: Wrong Answer

Solution code:
import bisect

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
rev_A = A[::-1]

def check(x, a=A, m=M):
  result = False
  n = len(a)
  count = 0
  for ai in a:
    count += (n - bisect.bisect_left(a, x-ai))
  
  return count>=m


left = 0
right = 2*10**5 + 1
mid = (left + right) // 2
while right - left > 1:
  if check(mid):
    left = mid
  else:
    right = mid
    
  mid = (left + right)//2

x = left
if check(right):
  x = right

accum_A = [rev_A[0]]
for i, a in enumerate(rev_A):
  if i == 0:
    continue
  accum_A.append(accum_A[-1] + a)


ans = 0
count = 0
surplus = 2*10**5
for ai in rev_A:
  idx = bisect.bisect_left(A, x-ai)
  ans += (N-idx)*ai + accum_A[N-idx-1]
  count += N - idx
  surplus = min(surplus, ai+A[idx])
  if count >= M:
    break

print(ans - (M-count)*surplus)

Submission status: Wrong Answer

Solution code:
import bisect

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
rev_A = A[::-1]

def check(x, a=A, m=M):
  result = False
  n = len(a)
  count = 0
  for ai in a:
    count += (n - bisect.bisect_left(a, x-ai))
  
  return count>=m


left = 0
right = 2*10**5 + 1
mid = (left + right) // 2
while right - left > 1:
  if check(mid):
    left = mid
  else:
    right = mid
    
  mid = (left + right)//2

x = left
if check(right):
  x = right

accum_A = [rev_A[0]]
for i, a in enumerate(rev_A):
  if i == 0:
    continue
  accum_A.append(accum_A[-1] + a)


ans = 0
count = 0
for ai in rev_A:
  idx = bisect.bisect_left(A, x-ai)
  if count + (N-idx) > M:
    idx = N - M + count
  
  ans += (N-idx)*ai + accum_A[N-idx-1]
  count += N - idx
  if count == M:
    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()
rev_A = A[::-1]

def check(x, a=A, m=M):
  result = False
  n = len(a)
  count = 0
  for ai in a:
    count += (n - bisect.bisect_left(a, x-ai))
  
  return count>=m


left = 0
right = 2*10**5 + 1
mid = (left + right) // 2
while right - left > 1:
  if check(mid):
    left = mid
  else:
    right = mid
    
  mid = (left + right)//2

x = left
if check(right):
  x = right

ans = 0
count = 0
for ai in rev_A:
  idx = bisect.bisect_left(A, x-ai)
  if count + (N-idx) > M:
    idx = M - count
    ans += sum(A[-idx:]) + idx*ai
    break
  else:
    ans += sum(A[idx:]) + (N-idx)*ai
    count += (N - idx)
    if count == M:
      break

print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
N,M=map(int,input().split())
A=list(map(int,input().split()))
A=sorted(A)
B=[0]*N
B[-1]=A[-1]
for i in range(1,N):
    B[-1-i]=B[-i]+A[-i-1]

L=[0]*N
Max=A[-1]*2+1
Min=A[0]*2
s=0

while(s!=M):
    s=0
    l=Max
    r=Min
    C=(l+r)//2
    c=0
    for i in range(N):
        w=C-A[i]
        t=N-bisect.bisect(A,w)
        s+=t
    if(s<M):
        if(Max==C):
            break
        Max=C
    elif(s>M):
        if(Min==C):
            break
        Min=C
#print(C,M,s)
s=0
for i in range(N):
        w=C-A[i]
        t=N-bisect.bisect(A,w)
        if t>0:
           s+=t*A[i]+B[-t]
print(s)

Submission status: Wrong Answer

Solution code:
import bisect
N,M=map(int,input().split())
A=list(map(int,input().split()))
A=sorted(A)
B=[0]*N
B[-1]=A[-1]
for i in range(1,N):
    B[-1-i]=B[-i]+A[-i-1]

L=[0]*N
Max=A[-1]*2+1
Min=A[0]*2
s=0

while(s!=M):
    s=0
    l=Max
    r=Min
    C=(l+r)//2
    c=0
    for i in range(N):
        w=C-A[i]
        t=N-bisect.bisect(A,w)
        s+=t
    if(s<M):
        if(Max==C):
            break
        Max=C
    elif(s>M):
        if(Min==C):
            break
        Min=C
print(C,M,s)
s=0
for i in range(N):
        w=C-A[i]
        t=N-bisect.bisect(A,w)
        if t>0:
           s+=t*A[i]+B[-t]
print(s)

Submission status: Wrong Answer

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

nA, sA, i = [N, N], [0],  N - 1
for a in range(1, A[0] * 2):
    di = 0
    while i - di >= 0 and A[i - di] == a:
        di += 1
    nA.append(nA[-1] - di)
    i -= di
for a in A:
    sA.append(sA[-1] + a)

L, R, ans = 0, A[0] * 2, 0
while R - L > 1:
    mid = L + (R - L) // 2
    mA = [nA[max(mid - A[i], 0)] for i in range(N)]
    sM = sum(mA)
    if M <= sM:
        L = mid
        ans = sum([A[i] * mA[i] + sA[mA[i]]
                   for i in range(N)]) - mid * (sM - M)
    else:
        R = mid

print(ans)

Submission status: Wrong Answer

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

nA, sA, i = [N, N], [0],  N - 1
for a in range(1, A[0] * 2):
    di = 0
    while i - di > 0 and A[i - di] == a:
        di += 1
    nA.append(nA[-1] - di)
    i -= di
for a in A:
    sA.append(sA[-1] + a)

L, R, ans = 0, A[0] * 2, 0
while R - L > 1:
    mid = L + (R - L) // 2
    mA = [nA[max(mid - A[i], 0)] for i in range(N)]
    sM = sum(mA)
    if M <= sM:
        L = mid
        ans = sum([A[i] * mA[i] + sA[mA[i]]
                   for i in range(N)]) - mid * (sM - M)
    else:
        R = mid

print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import combinations, product

n, m = map(int, input().split())
aaa = list(map(int, input().split()))
aaa = aaa[: m]

score_list = [x + y for x, y in product(aaa, repeat=2)]
score_list.sort(reverse=True)
print(sum(score_list[: m]))

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
from bisect import *
n, m, *a = map(int, open(0).read().split())
a = [-x for x in a]
a.sort()
acc = list(accumulate(a)) + [0]
l = 0
r = 10 ** 6
while r - l > 1:
	mid = (l + r) // 2
	cnt = 0
	su = sum(bisect(a, -mid - x - .5) for x in a)
	if su >= m:
		l = mid
	else:
		r = mid
ans = tot = 0
for x in a:
	b = bisect(a, -l - x)
	tot += b
	ans += acc[b - 1] + x * b
ans += r * (tot - m)
print(-ans)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
from bisect import *
n, m, *a = map(int, open(0).read().split())
a = [-x for x in a]
a.sort()
acc = list(accumulate(a)) + [0]
l = 0
r = 1 << 60
while r - l > 1:
	mid = (l + r) // 2
	cnt = 0
	su = sum(bisect(a, -mid - x - .5) for x in a)
	if su >= m:
		l = mid
	else:
		r = mid
ans = 0
tot = 0
for x in a:
	b = bisect(a, -l - x)
	tot += b
	if tot > m:
		b -= (tot - m)
		tot = m
	ans += acc[b - 1] + x * b
print(-ans)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
from bisect import *
n, m, *a = map(int, open(0).read().split())
a = [-x for x in a]
a.sort()
acc = list(accumulate(a)) + [0]
l = 0
r = 1 << 60
while r - l > 1:
	mid = (l + r) // 2
	cnt = 0
	su = sum(bisect(a, -mid - x - .5) for x in a)
	if su >= m:
		l = mid
	else:
		r = mid
ans = 0
tot = 0
for x in a:
	b = bisect(a, -l - x)
	tot += b
	if tot > m:
		b -= (tot - m)
		tot = m
	ans += acc[b - 1] + x * b
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 = np.sort(A)[::-1]
 
m = int(min(M,N))
num = np.zeros(m)
ans = np.zeros(1)
for n,a in enumerate(A):
  if n>m:break
  for nn,aa in enumerate(A):
    if nn>m:break
    try:
      num[nn] = a + aa
    except:
      pass