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 math
import collections
N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
cumax=2*10**5
cuml=[0]*cumax
#print(A)
ind=0
l=[]
c=collections.Counter(A)
values=list(c.values())	#aのCollectionのvalue値のリスト(n_1こ、n_2こ…)
key=list(c.keys())	#先のvalue値に相当する要素のリスト(要素1,要素2,…)
for i in range(len(key)):
    l.append([key[i],values[i]])#lは[要素i,n_i]の情報を詰めたmatrix
lr=[]
v=[]
for i in range(len(key)):
    lr.append([0,l[i][0]])
    v.append(l[i][1])
for i in range(len(v)):
    l=lr[i][0]
    r=lr[i][1]
    cuml[l]=cuml[l]+v[i]
    if r+1<cumax:
        cuml[r+1]=cuml[r+1]-v[i]
for i in range(cumax-1):
    cuml[i+1]=cuml[i+1]+cuml[i]
#print(cuml)
maxind=2*10**5
minind=0
while maxind-minind>1:
    piv=minind+(maxind-minind)//2       #pivは握手の幸福度
    cnt=0
    for i in range(N):
        x=piv-A[i]
        cnt=cnt+cuml[max(x,0)]
    if cnt<=M:
        maxind=piv
    else:
        minind=piv
    #print(cnt,maxind,piv,minind)
#print(minind)
thr=minind
cuml2=[0]*(N+1)
A.sort(reverse=True)
for i in range(N):
    cuml2[i+1]=cuml2[i]+A[i]
#print(cuml2,thr,A)
ans=0
counts=0
for i in range(N):
    x=thr-A[i]
    #print(x)
    cnt=cuml[max(x,0)]
    #print(cnt)
    ans=ans+(A[i]*cnt)+cuml2[cnt]
    counts=counts+cnt
ans=ans-(counts-M)*thr
#print()
print(ans)

Submission status: Wrong Answer

Solution code:
import math
import collections
N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
cumax=2*10**5
cuml=[0]*cumax
#print(A)
ind=0
l=[]
c=collections.Counter(A)
values=list(c.values())	#aのCollectionのvalue値のリスト(n_1こ、n_2こ…)
key=list(c.keys())	#先のvalue値に相当する要素のリスト(要素1,要素2,…)
for i in range(len(key)):
    l.append([key[i],values[i]])#lは[要素i,n_i]の情報を詰めたmatrix
lr=[]
v=[]
for i in range(len(key)):
    lr.append([0,l[i][0]])
    v.append(l[i][1])
for i in range(len(v)):
    l=lr[i][0]
    r=lr[i][1]
    cuml[l]=cuml[l]+v[i]
    if r+1<cumax:
        cuml[r+1]=cuml[r+1]-v[i]
for i in range(cumax-1):
    cuml[i+1]=cuml[i+1]+cuml[i]
#print(cuml)
maxind=2*10**5
minind=0
while maxind-minind>1:
    piv=minind+(maxind-minind)//2       #pivは握手の幸福度
    cnt=0
    for i in range(N):
        x=piv-A[i]
        cnt=cnt+cuml[max(x,0)]
    if cnt<M:
        maxind=piv
    else:
        minind=piv
    #print(cnt,maxind,piv,minind)
#print(minind)
thr=minind
cuml2=[0]*(N+1)
A.sort(reverse=True)
for i in range(N):
    cuml2[i+1]=cuml2[i]+A[i]
#print(cuml2,thr,A)
ans=0
counts=0
for i in range(N):
    x=thr-A[i]
    #print(x)
    cnt=cuml[max(x,0)]
    #print(cnt)
    ans=ans+(A[i]*cnt)+cuml2[cnt]
    counts=counts+cnt
ans=ans-(counts-M)*thr
#print()
print(ans)

Submission status: Wrong Answer

Solution code:
def resolve():
    import sys

    def LI():
        return list(map(int, sys.stdin.readline().rstrip().split()))  # 空白あり

    def S():
        return sys.stdin.readline().rstrip()

    N, M = map(int, S().split())
    A = LI()
    A.sort()

    def f(n,x):  # A[n]+A[i]>=x となる i の最小値
        left = -1
        right = N
        while left + 1 < right:
            mid = (left + right) // 2
            if A[n] + A[mid] < x:
                left = mid
            else:
                right = mid
        return right

    low = 2 * A[0]
    high = 2 * A[-1] + 1

    while low + 1 < high:
        mid = (low + high) // 2
        if sum(N - f(i,mid) for i in range(N)) >= M:
            low = mid
        else:
            high = mid

    a = low  # a以上のA[i]+A[j]がM個以上となる最大のa

    from itertools import accumulate

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

    r = 0
    ans = 0
    for i in range(N):  # a+1以上のA[i]+A[j]を足し合わせていく
        b = f(i,a+1)
        r += N - b
        ans += B[N] - B[b]
        ans += A[i] * (N - b)

    ans += (M - r) * a  # A[i]+A[j] == a となるものを足し合わせる

    print(ans,a)

if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
import sys
import bisect

stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  # ignore trailing spaces


N, M = na()
A_array = na()
A_array.sort()

hap_min = 0
hap_max = 2 * (10 ** 5)

while(hap_max - hap_min > 1):
    hap = (hap_min + hap_max) // 2
    cnt = 0
    for a in A_array:
        idx = bisect.bisect_left(A_array, hap - a)
        cnt += N - idx
    # print(hap, hap_max, hap_min, cnt)
    if cnt >= M:
        hap_min = hap
    else:
        hap_max = hap

hap = hap_min

cnt_array = [0] * N
sum_array = [0] * N

for i, a in enumerate(A_array):
    idx = bisect.bisect_left(A_array, hap - a)
    cnt_array[i] = N - idx
    if idx != N:
        sum_array[idx] += 1

# print(cnt_array, sum_array)

ans = 0
cusum = 0
cntsum = 0
for a, c, s in zip(A_array, cnt_array, sum_array):
    cusum += s
    cntsum += c
    ans += a * (cusum + c)

print(ans - (cntsum - M) * hap)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

mm = 10**10
k = mm.bit_length()
K = 1<<k
nu = lambda L: int("".join([bin(K+a)[-k:] for a in L[::-1]]), 2)
st = lambda n: bin(n)[2:] + "0"
li = lambda s: [int(a, 2) if len(a) else 0 for a in [s[-(i+1)*k-1:-i*k-1] for i in range(200001)]]

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

for i in a:
    b[i] += 1
    
c = li(st(nu(b)*nu(b)))
ans = 0
for i in range(200001)[::-1]:
    if c[i] > 0:
      m -= c[i]
      ans += i*c[i]
      if m == 0:
        break
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right

N, M = map(int, input().split())
*A, = map(int, input().split())
A.sort()
ac = [0]*(N+1)
for i in range(1, N+1):
    ac[i] = ac[i-1]+A[i-1]

def f(x):
    v = 0
    for i in A:
        v += N-bisect_right(A, x-i)
    return v>=M

l, r = 1, 10**12+1
while r-l>1:
    m = (l+r)//2
    if f(m):
        l = m
    else:
        r = m

ans = 0
for i in A:
    v1 = N-bisect_right(A, l-i)
    ans += ac[N]-ac[N-v1]+v1*i
print(ans)

Submission status: Wrong Answer

Solution code:
def solve(m):
    r = N - 1
    l = 0
    cnt = 0
    score = 0
    while 0 <= r and l < N:
        if A[r] + A[l] < m:
            l += 1
        else:
            cnt += N - l
            score += A[r] * (N - l) + (S[N] - S[l])
            r -= 1
    return cnt, score


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]

# [ok, ng) - Maximum
# (ng, ok] - Minimum
# ok が 最終的な答え
ng = 0
ok = 10 ** 10 + 10
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    cnt, score = solve(mid)
    if cnt <= M:
        ok = mid
    else:
        ng = mid

print(score)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
E - Handshake
https://atcoder.jp/contests/abc149/tasks/abc149_e

"""
import sys
from bisect import bisect_left

def solve(N, M, A):
    lb, ub = 0, A[-1] * 2 * M
    while ub > (lb + 1):
        mid = (lb + ub) // 2
        if sum(len(A) - bisect_left(A, mid - a) for a in A) >= M:
            lb = mid
        else:
            ub = mid
    res = [len(A)-bisect_left(A, lb-a) for a in A]
    ans = 0
    for a, b in zip(A[::-1], res[::-1]):
        x = min(b, M)
        ans += a * x * 2
        M -= x
        if M == 0:
            break
    return ans


def main(args):
    N, M = map(int, input().split())
    A = sorted(int(a) for a in input().split())
    ans = solve(N, M, A)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Wrong Answer

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,m = map(int,ipt().split())
    a = [int(i) for i in ipt().split()]
    a.sort()
    maa = max(a)

    pn = [0]*(2*maa+1)
    pn[0] = n
    pa = 0
    for i in a:
        for j in range(pa+1,i+1):
            pn[j] = pn[pa]
        pn[i+1] = pn[pa]-1
        pa = i+1

    l = 0
    r = 2*maa
    while l < r:
        mid = l+(r-l+1)//2
        nm = 0
        for i in a:
            if mid <= i:
                nm += n
            else:
                nm += pn[mid-i]
        if nm <= m:
            r = mid-1
        else:
            l = mid

    pt = [0]*(2*maa+1)
    pp = maa+1
    for i in a[::-1]:
        for j in range(pp-1,i,-1):
            pt[j] = pt[pp]
        pt[i] = pt[pp]+i
        pp = i
    for j in range(pp-1,-1,-1):
        pt[j] = pt[pp]

    ans = 0
    sm = 0
    for i in a:
        sm += pn[max(0,l-i)]
        ans += pt[max(0,l-i)]+pn[max(0,l-i)]*i
        print(l,i,pt[max(0,l-i)],pn[max(0,l-i)])
    print(ans-l*(sm-m))
    return

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
b = [0] * (n+1)
right = 1
for i in range(n):
    right += a[i]
    b[i+1] = a[i] + b[i]


# 総和ｘ以上の握手の場合の数
def case_over(x):
    ret = 0
    for v in a:
        t = x - v
        ret += n - bisect_left(a, t)

    return ret


left = -1
mid = 0
while left <= right:
    mid = (left+right)//2
    case1 = case_over(mid)
    case2 = case_over(mid+1)
    if case1 >= m > case2:
        break
    elif case1 >= m:
        left = mid
    else:
        right = mid


def ans_over(x):
    y = case_over(x) - m
    ret = 0
    for v in a:
        t = x - v
        i = bisect_left(a, t)
        diff = min(n, i+y) - i
        y -= diff
        ret += b[n] - b[i+diff]
        ret += v * (n-i-diff)
    return ret


print(ans_over(mid))

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()
b = [0] * (n+1)
for i in range(n):
    b[i+1] = a[i] + b[i]


# 総和ｘ以上の握手の場合の数
def case_over(x):
    ret = 0
    for v in a:
        t = x - v
        ret += n - bisect_left(a, t)

    return ret


left = -1
right = 10000000001
mid = 0
while left <= right:
    mid = (left+right)//2
    case1 = case_over(mid)
    case2 = case_over(mid+1)
    if case1 >= m > case2:
        break
    elif case1 >= m:
        left = mid
    else:
        right = mid

def ans_over(x):
    y = case_over(x) - m
    ret = 0
    for v in a:
        t = x - v
        i = bisect_left(a, t)
        diff = min(n, i+y) - i
        y -= diff
        ret += b[n] - b[i+diff]
        ret += v * (n-i-diff)
    return ret


print(ans_over(mid))

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()
b = [0] * (n+1)
for i in range(n):
    b[i+1] = a[i] + b[i]


# 総和ｘ以上の握手の場合の数
def case_over(x):
    ret = 0
    for v in a:
        t = x - v
        ret += n - bisect_left(a, t)

    return ret


left = -1
right = 10000000001
mid = 0
while left <= right:
    mid = (left+right)//2
    case = case_over(mid)
    if case == m:
        break
    elif case < m:
        right = mid-1
    else:
        left = mid+1

while m > case_over(mid):
    mid -= 1


def ans_over(x):
    y = case_over(x) - m
    ret = 0
    for v in a:
        t = x - v
        i = bisect_left(a, t)
        diff = min(n, i+y) - i
        y -= diff
        ret += b[n] - b[i+diff]
        ret += v * (n-i-diff)
    return ret


print(ans_over(mid))

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math

MOD = 10 ** 9 + 7
# MOD = 998244353
# sys.setrecursionlimit(10**8)


n, m = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)


def count(x):
    num = 0
    for i in range(n):
        if 2*A[i] >= x:
            num += 1
        else:
            break

    right = n-1
    for left in range(n):
        while left < right and A[left] + A[right] < x:
            right -= 1
        if left >= right:
            break
        num += 2*(right - left)

    return num


# print(A)
left, right = 2*A[-1], 2*A[0]
cand = left
while left < right:
    mid = (left+right)//2
    num = count(mid)
    if num < m:
        right = mid-1
    else:
        cand = max(cand, mid)
        left = mid+1

# print(cand)
s = 0
min_val = float("inf")
count = m
for i in range(n):
    if 2 * A[i] >= cand:
        s += 2 * A[i]
        min_val = 2*A[i]
        count -= 1
    else:
        break

# print(s, count)
psum = list(itertools.accumulate(A))
# print(psum)
right = n-1
for left in range(n):
    while left < right and A[left] + A[right] < cand:
        right -= 1
    if left >= right:
        break
    s += 2*(A[left]*(right - left) + psum[right] - psum[left])
    min_val = min(min_val, A[left]+A[right])
    # print(left, right, min_val, count)
    count -= 2*(right - left)

if count < 0:
    s -= -count * min_val
print(s)

Submission status: Wrong Answer

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

a_cum = [0 for _ in range(n+1)]
for i in range(n):
    a_cum[i+1] = a_cum[i] + a[i]

l, r = 0, 10 ** 6
while r - l > 1:
    x = (l + r) // 2
    cnt = 0

    for i in range(n):
        idx = bisect.bisect_left(a, x-a[i])
        cnt += n - idx

    if cnt >= m:
        l = x

    else:
        r = x

ans = 0
cnt = 0
for i in range(n):
    idx = bisect.bisect_left(a, l-a[i])
    cnt += n - idx
    ans += a_cum[n] - a_cum[idx]
    ans += a[i] * (n - idx)

if cnt > m:
    ans -= a[i] * (cnt - m)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
import bisect

con = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

def Binary_Search(A, N, M):
	#初期化
	left = 0
	right = 10 ** 7
	ans = 0
	#累積和
	Asum = [0]
	for i in range(N):
		Asum.append(Asum[i] + A[-1 - i])

	leftj = [INF, INF]
	rightj = [0, 0]
	#二分探索
	while left <= right:
		mid = (left + right) // 2
		var = 0
		happiness = 0
		for i in range(N):
			ind = bisect.bisect_left(A, mid - A[i])
			ind = N - ind
			var += ind
			happiness += ind * A[i] + Asum[ind]

		# print(var, happiness)
		if var == M:
			return happiness
		elif var > M:
			leftj = min(leftj, [var, mid])
			left = mid + 1
		else:
			ans = max(ans, happiness)
			rightj = max(rightj, [var, mid])
			right = mid - 1

	ans = ans + (M - rightj[0]) * leftj[1]
			
	return ans


#処理内容
def main():
	N, M = getlist()
	A = getlist()
	A.sort()
	ans = Binary_Search(A, N, M)

	print(ans)

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
from queue import PriorityQueue
readline = sys.stdin.buffer.readline
# sys.setrecursionlimit(10**5)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


def main():
    N, M = geta(int)
    A = list(geta(int))

    A.sort(reverse=True)

    tmp = 0
    M1 = 2 * N - 1
    for m in range(1, 2 * N):
        tmp += m if m <= N else 2 * N - m

        if tmp > M:
            M1 = m - 1
            break

    if M1 <= N:
        ans = sum([A[i] * 2 * (M1 - i) for i in range(M1)])
    else:
        ans = sum([A[i] * 2 * min(N, M1 - i) for i in range(N)])

    tmp = PriorityQueue()
    for i in range(N):
        j = M1 - i
        if 0 <= j < N:
            tmp.put(-A[i] - A[j])

    for _ in range(M - (M1 + 1) * M1 // 2):
        ans += -tmp.get()

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:

import sys
input = sys.stdin.readline
# 文字列をinput()した場合、末尾に改行が入るので注意
def main():
  n,m=map(int,input().split())
  a=sorted(list(map(int,input().split())))
  import bisect
  # 解説の二分探索
  # あるXを定め、X以上になる握手の組み合わせが何通りあるか計算。ちょうどM個以上になる最小のXを探す
  l,r=0,a[-1]*2
  while r-l>1:
    x=(l+r)//2
    cnt=0
    for ai in a:
      cnt+=n-bisect.bisect_left(a,x-ai)
    # x以上がm個以上ある->xを増加
    if cnt>=m:
      l=x
    else:
      r=x
  x=(l+r)//2
  ans=0
  cnt=0
  a_=0
  cs_a=[0]
  for ai in a:
    a_+=ai
    cs_a.append(a_)
  for ai in a:
    bi=bisect.bisect_right(a,x-ai)
    cnt+=n-bi
    ans+=cs_a[-1]-cs_a[bi]+(n-bi)*ai
  
  print(ans+(m-cnt)*x)
if __name__=='__main__':
  #import datetime
  #print(datetime.datetime.now())
  main()
  #print(datetime.datetime.now())

Submission status: Wrong Answer

Solution code:

import sys
input = sys.stdin.readline
# 文字列をinput()した場合、末尾に改行が入るので注意
def main():
  n,m=map(int,input().split())
  a=sorted(list(map(int,input().split())))
  import bisect
  # 解説の二分探索
  # あるXを定め、X以上になる握手の組み合わせが何通りあるか計算。ちょうどM個以上になるXを探す
  l,r=0,a[-1]*2
  while r-l>1:
    x=(l+r)//2
    cnt=0
    for ai in a:
      cnt+=n-bisect.bisect_left(a,x-ai)
    # x以上がm個以上ある->xを増加
    [l,r]=[x,r] if cnt>=m else [l,x]
  x=(l+r)//2
  ans=0
  cnt=0
  for ai in a:
    bi=bisect.bisect_right(a,x-ai)
    cnt+=n-bi
    ans+=sum(a[bi:])+(n-bi)*ai
  
  print(ans+(m-cnt)*x)
if __name__=='__main__':
  #import datetime
  #print(datetime.datetime.now())
  main()
  #print(datetime.datetime.now())

Submission status: Wrong Answer

Solution code:
import bisect
from itertools import accumulate
N, M = map(int, input().split())
A = sorted(list(map(int, input().split())))
ruiseki = list(accumulate(A[::-1]))

# 自分以上の数の個数がM個以上になる値のうち最大のもの
ok = 0
ng = 10 ** 15
while ok + 1 < ng:
    mid = (ok + ng) // 2
    cnt = 0
    ans = 0
    for a in A:
        x = bisect.bisect_left(A, mid - a)
        cnt += N - x
        if N - x >= 1:
            ans += ruiseki[N - x - 1] + (N - x) * a
    if cnt >= M:
        ok = mid
    else:
        ng = mid
print(M, cnt)
print(ans + ok * (M - cnt))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys, heapq, bisect
sys.setrecursionlimit(300000)

def _count(A, n, v):
    ret = 0
    for a in A:
        target = v - a
        idx = bisect.bisect_left(A, target)
        ret += n - idx
    return ret

def _sum(A, n, v, sums):
    ss = 0
    for a in A:
        target = v - a
        idx = bisect.bisect_left(A, target)
        ss += sums[n] - sums[idx]
        ss += (n - idx) * a
    #print(mins)
    ret = ss
    return ret

def solve(N: int, M: int, A: "List[int]"):
    A.sort()
    sums = [0]
    for a in A:
        sums.append(sums[-1] + a)
    l = -1
    r = sum(A)
    while r - l > 1:
        m = (r + l) // 2
        cnt = _count(A, N, m)
        if cnt >= M:
            l = m
        else:
            r = m
    cnt = _count(A, N, l)
    ret = _sum(A, N, l, sums)
    ret -= (cnt - M) * l
    print(ret)
    return ret


def solve_(N: int, M: int, A: "List[int]"):
    A.sort(reverse=True)
    q = [(-A[0] * 2, 0, 0)]
    ret = 0
    cnt = 0
    while cnt < M:
        s, i, j = heapq.heappop(q)
        ret += -s
        cnt += 1
        print(i, j)
        if i == j and i < N - 1:
            heapq.heappush(q, (-A[i] + -A[i + 1], i, i + 1))
        else:
            if cnt < M:
                ret += -s
                cnt += 1
                print(j, i)
            heapq.heappush(q, (-A[i + 1] + -A[j], i + 1, j))
            if j < N - 1:
                heapq.heappush(q, (-A[i] + -A[j + 1], i, j + 1))
    print(ret)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, M, A)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
import  math
import fractions
from collections import defaultdict
stdin = sys.stdin
     
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

N,M=nm()
A=nl()
A.sort(reverse=True)
sum_l=[0]*(2*(N+1))
sum_l[0]=A[0]
for i in range(N-1):
    for j in range(2):
        sum_l[2*i+1]=sum_l[2*i]+A[i+1]
        sum_l[2*i+2]=sum_l[2*i]+2*A[i+1]

ans=0
now=min(2*N,M)
M-=now 
ans+=A[0]*now+sum_l[now-1]
if(M==0):
    print(ans)
    sys.exit(0)
for i in range(1,N):
    now=min(2*(N-i),M)
    ans+=A[0]*now+(sum_l[now-1]-sum_l[2*i-1])
    M-=now 
    if(M==0):
        print(ans)
        sys.exit(0)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    #inf = 10**17
    #mod = 10**9 + 7

    n,m = map(int, input().split())
    a = list(map(int, input().split()))
    b = sorted(a)
    c = [0] + sorted(b)
    c = list(accumulate(c))
    a.sort(reverse=True)
    
    # mid以上の和をm個作れるならTrue
    def check(mid):
        total = 0
        for i in a:
            total += n - bisect_left(b, mid-i)
            if total >= m:
                return True
        return False

    l = 0
    r = 2*(10**5)
    # 最終的なlがm個以上作れる最小値
    while r - l > 1:
        mid = (l+r) // 2
        if check(mid):
            l = mid
        else:
            r = mid
    res = 0
    for i in a:
        d = bisect_left(b, r-i)
        if d == n:
            continue
        res += i * (n-d) + c[-1] - c[d]
        m -= n - d

    print(res + l*m)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()
from bisect import bisect_left
def resolve():
    n, m = map(int,input().split())
    A = list(map(int,input().split()))
    A.sort()

    if m == n * n:
        print(n * sum(A))
        return

    def check1(x): # true if the number of (i, j) satisfying A[i] + A[j] >= x is less than m
        cnt = 0
        for a in A:
            idx = bisect_left(A, x - a)
            cnt += n - idx
        return cnt < m

    left = 0
    right = 200001
    while right - left > 1:
        mid = (left + right) // 2
        if check1(mid):
            right = mid
        else:
            left = mid

    x = left
    target_cnt = 0
    for a in A:
        idx = bisect_left(A, x - a)
        target_cnt += n - idx

    def check2(x): # true if the number of (i, j) satisfying A[i] + A[j] >= x is equal to target_cnt
        cnt = 0
        for a in A:
            idx = bisect_left(A, x - a)
            cnt += n - idx
        return cnt == m

    left, right = 0, x
    while right - left > 1:
        mid = (left + right) // 2
        if check2(mid):
            right = mid
        else:
            left = mid

    x = right
    res = 0
    for a in A:
        idx = bisect_left(A, x - a)
        res += a * (n - idx)
    print(2 * res - x * (target_cnt - m))
resolve()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()
from bisect import bisect_left
def resolve():
    n, m = map(int,input().split())
    A = list(map(int,input().split()))

    if m == n * n:
        print(n * sum(A))
        return

    A.sort()
    S = [0] * (n + 1)
    for i in range(n):
        S[i + 1] = S[i] + A[i]

    def check(x): # true if the number of (i, j) satisfying A[i] + A[j] >= x is less than m
        cnt = 0
        for a in A:
            idx = bisect_left(A, x - a)
            cnt += n - idx
        return cnt < m

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

    x = left
    res = 0
    cnt = 0
    for a in A:
        idx = bisect_left(A, x - a)
        cnt += n - idx
        res += a * (n - idx)

    print(2 * res - x * (cnt - m))
resolve()

Submission status: Wrong Answer

Solution code:
import bisect

if __name__ == '__main__':
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    # 左手でa[i]の手を握るとする
    # a[i]を持っているときに和がx未満になるときの右手の数字はx - a[i]未満の数字である
    # lower_bound
    # この値をNから引くことで和がx以上になるペアの個数がわかる
    # この値の合計がM未満になればそこが最大の幸福度である

    # 要するに、M個のペアを作るためには最大いくらの和を採用できるかを二分探索する

    ng = 0
    ok = 10 ** 5 + (n + 1)

    while abs(ok - ng) > 1:
        # mid -> boundとなる和。これより大きい和をもつペアをM個作れるかを判定する
        mid = (ok + ng) // 2
        count = 0
        for i in a:
            # mid以上の値をiを用いて作成するには、mid - i以上の値が必要になる
            position = bisect.bisect_left(a, mid - i)
            count += n - position
        # ペアの個数がmより小さい場合は、okの範囲を下げる
        if count < m:
            ok = mid
        # そうでない場合はまだ余裕があるので、ngをあげる
        else:
            ng = mid

    # ここが終了した時点でngにはm個以上のペアを作るための最大のboundが入っている

    # upper_boundで左手にa[i]がある場合のng - a[i]の数を判定する
    # ansに求めた数 * a[i] + 右手に持つ幸福度の総和を足す
    # mから求めた数を引く

    ans = 0
    sum_array = [0] * (n + 1)
    # 累積和で高速化をする
    # (x + a[i]) + (x + a[i + 1) + (x + a[i + 2]).....
    #   -> (x * 個数) * (a[i] + a[i + 1] + a[i + 2])

    for i in range(n):
        sum_array[i + 1] = sum_array[i] + a[i]

    for i in range(n):
        position = bisect.bisect_right(a, ng - a[i])
        ans += (n - position) * a[i] + sum_array[n] - sum_array[position]
        m -= n - position

    ans += ng * m
    print(ans)

Submission status: Wrong Answer

Solution code:
#e
n,m=map(int,input().split())
a=sorted([int(i) for i in input().split()])

import bisect

def hantei(now):
    num=0
    for ax in a:
        bi = bisect.bisect_left(a,now-ax)
        num+= bi
    return n**2-num
  
suma=[0]*(n+1)
suma[-2]=a[-1]
for i in range(n-2,-1,-1):
    suma[i] = suma[i+1]+a[i]

mi = a[0]*2-1
ma = a[-1]*2+1
while mi+1<ma:
    now=(mi+ma)//2
    which = hantei(now)<=m#なんか判定
    if which:
        ma=now
    else:
        mi=now

ans=0
kazu=0
for ax in a:
    bi = bisect.bisect_left(a,now-ax)
    ans+= (n-bi)*ax+suma[bi]
    kazu+=n-bi
print(ans-(kazu-m)*now)

Submission status: Wrong Answer

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

n, m = map(int, readline().split())
a = sorted(list(map(int, readline().split())), reverse=True)


def check(mid):
    cnt = 0
    for aa in a:
        j = 0
        while j < n and aa + a[j] >= mid:
            j += 1
        cnt += j
    return m <= cnt


left = 0
right = 2 * 10 ** 5
while left + 1 < right:
    mid = (left + right) // 2
    if check(mid):
        left = mid
    else:
        right = mid
ans = 0
cnt = 0
for aa in a:
    j = 0
    while j < n and aa + a[j] >= left:
        ans += aa + a[j]
        j += 1
        cnt += 1
        if cnt == m:
            print(ans)
            exit()
print(ans)

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans






N,M = m()

a = l()

a.sort()

po = [0 for i in range(10**5+1)]
ans = 0
for i in range(N):
    po[a[i]] += 1
for i in range(10**5-1,-1,-1):
    po[i] += po[i+1]
ll = 0
rr = 10**5 * 2

while True:
    mid = (ll+rr)//2
    if mid == ll:
        co = 0
        for i in range(N):
            ui = a[i]
            if mid > ui + 10**5:
                continue
            elif ui >= mid:
                co += N
            else:
                co += po[mid-ui]
        cco = 0
        mid = rr

        for i in range(N):
            ui = a[i]
            if mid > ui + 10**5:
                continue
            elif ui >= mid:
                cco += N
            else:
                cco += po[mid-ui]
        
        if cco == M:
            mid = rr
            co=cco

        else:
            mid = ll

        break

    co = 0
    for i in range(N):
        ui = a[i]
        if mid > ui + 10**5:
            continue
        elif ui >= mid:
            co += N
        else:
            co += po[mid-ui]
    
    if co < M:
        rr = mid                 
    else:
        ll = mid


a.sort(reverse = True)
dp = [0]

ans -= mid * (co - M)



for i in range(N):
    dp.append(dp[-1]+a[i])

for i in range(N):
    pl = a[i]
    if pl >= mid:
        ans += pl*N + dp[-1]
        
    elif pl + 10**5 < mid:
        continue
    else:
        ans += pl*po[mid-pl] + dp[po[mid-pl]]
print(ans)