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

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 a in A:
  for nn,aa in enumerate(A):
    pass

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)

Submission status: Wrong Answer

Solution code:
n, m=list(map(int, input().split()))
A = list(map(int, input().split()))
A.sort(reverse=True)
B, x, h=[], 0, 0
for i in A:
    B.extend([i, i])
for i in range(0, len(B), 2):
    for j in range(i+1, len(B)):
        if x<m:
            h=h+(B[i]+B[j])
            x=x+1
        else:
            break
print(h)

Submission status: Wrong Answer

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

tate=A
tate.reverse()
yoko=A

def binary_search(y):
   left_index=-1
   right_index=len(yoko)

   while(left_index<right_index-1):
      i=(left_index+right_index)//2
      if yoko[i] >= y:
         left_index=i
      else:
         right_index=i
   return right_index

X=[c for c in range(2*max(A)+1)]
left_index_2=0
right_index_2=len(X)

while left_index_2<right_index_2-1:
   count=0
   j=(left_index_2+right_index_2)//2
   #print("X[j]:",X[j])

   for a in tate:
      y=X[j]-a
      #Aの中でy以上の数を数える
      count+=binary_search(y)
   if count > M:
      left_index_2=j
   elif count <= M:
      right_index_2=j

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 = min(M,N)

Submission status: Wrong Answer

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

tate=A
tate.reverse()
yoko=A

def binary_search(y):
   left_index=-1
   right_index=len(yoko)

   while(left_index<right_index-1):
      i=(left_index+right_index)//2
      if yoko[i] >= y:
         left_index=i
      else:
         right_index=i
   return right_index

X=[c for c in range(2*max(A)+1)]
left_index_2=-1
right_index_2=len(X)

while left_index_2<right_index_2-1:
   count=0
   j=(left_index_2+right_index_2)//2

   for a in tate:
      y=X[j]-a
      #Aの中でy以上の数を数える
      count+=binary_search(y)
   if count > M:
      left_index_2=j
   elif count <= M:
      right_index_2=j

happiness=0
count_2=0
for a in tate:
   y=X[left_index_2]-a
   z=binary_search(y)
   happiness+=sum(tate[0:z])+a*z
   count_2+=z

while count_2>M:
   happiness-=X[left_index_2]
   count_2-=1
print(happiness)

Submission status: Wrong Answer

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

tate=A
tate.reverse()
yoko=A

def binary_search(y):
   left_index=-1
   right_index=len(yoko)

   while(left_index<right_index-1):
      i=(left_index+right_index)//2
      if yoko[i] >= y:
         left_index=i
      else:
         right_index=i
   return right_index

X=[c for c in range(2*max(A)+1)]
left_index_2=-1
right_index_2=len(X)

while left_index_2<right_index_2-1:
   count=0
   j=(left_index_2+right_index_2)//2

   for a in tate:
      y=X[j]-a
      #Aの中でy以上の数を数える
      count+=binary_search(y)
   if count > M:
      left_index_2=j
   elif count <= M:
      right_index_2=j

happiness=0
count_2=0
for a in tate:
   y=X[left_index_2]-a
   z=binary_search(y)
   happiness+=sum(tate[0:z])+a*z
   count_2+=z

while count_2>M:
   happiness-=X[left_index_2]
   count_2-=1
print(happiness)

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 = min(M,N)
#num = [0] * N**2
nn = 0

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 = min(M,N)

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]

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from itertools import accumulate

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

a.sort(reverse=True)
acm = list(accumulate(a))


def count_handshake(x):
    ret = 0
    for e in a:
        l = -1
        r = n
        while r - l > 1:
            mid = (l + r) // 2
            if a[mid] + e >= x:
                l = mid

            else:
                r = mid

        ret += l + 1

    return ret


left = 0
right = a[0] * 2 * m + 1

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

min_happiness = left
ans = 0
for e in a:
    left = -1
    right = n
    while right - left > 1:
        mid = (left + right) // 2
        if a[mid] + e >= min_happiness:
            left = mid
        else:
            right = mid

    if left == -1:
        continue

    ans += acm[left] + e * (left + 1)

print(ans)

Submission status: Wrong Answer

Solution code:
#%%
def count(a, k, n):
    l = []
    i, j, count = 0, n-1, 0
    while True:
        tmp = a[i] + a[j]
        if tmp >= k: 
            if j > 0:
                j -= 1
        elif tmp < k:
            l.append(n-j-1)
            if j < n - 1:
                j += 1
                count += n - j 
            else:
                count += n - j - 1
            i += 1
        if i >= n:
            break
        tmp = a[i] + a[j]
        if j == 0 and tmp >= k:
            l.append(n-j)
            count += n - j
            i += 1
        if i >= n:
            break
    return [count, l]

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
l, r = 10**6, 1


while l - r > 1:
    mid = (l+r)//2
    if count(a, mid, n)[0] < m:
        l = mid
    elif count(a, mid, n)[0] > m:
        r = mid
    else :
        l = mid
        r = mid
    print(l, r)

ans = 0
if l == r:
    tmp = count(a, l, n)
    for i in range(n):
        ans += a[i] * tmp[1][i] * 2
else:
    p = count(a, l, n)
    q = count(a, r, n)
    check = -1
    for i in range(n):
        if p[1][i] != q[1][i]:
            check = i
            break
    ans += (a[i] + a[n - p[1][check] - 1]) * (m - p[0])
    tmp = count(a, l, n)
    for i in range(n):
        ans += a[i] * tmp[1][i] * 2
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect

n, m = [int(v) for v in input().split()]
hand = [int(v) for v in input().split()]
hand.sort()

def shake(x):
    ret = 0
    for i in range(n):
        a = x - hand[i] 
        b = n - bisect.bisect_left(hand, a)
        ret += b
    return ret

def cumsum(inlist):
    s = 0
    outlist = [0]
    for i in inlist:
        s += i
        outlist.append(s)
    return outlist

shake(67)
shake(2)
ng = 10**5+1
ok = 0

while ng-ok > 1:
    mid = (ok+ng)//2
    if shake(mid) >= m:
        ok = mid
    else:
        ng = mid

handcum = cumsum(hand)
ans = 0
bs = 0
for i in range(n):
    a = ok - hand[i] 
    b = bisect.bisect_left(hand, a)
    bs += n - b
    ans += handcum[n] - handcum[b] + hand[i] * (n-b)

ans -= ok * (bs-m)
print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
A = sorted(list(map(int,input().split())),reverse=True)
bi = [0]*(A[0]+1)
for a in A:
  bi[a]+=1
  
cum = [0]*(A[0]+1)
for i in range(1,A[0]+1):
  cum[i]=cum[i-1]+bi[i]

cum_max=cum[-1]
left = 0
right = A[0]*2
while right-1!=left:
  x = (right+left)//2
  num = 0
  for a in A:
    b = max(x-a,1)
    if b<=A[0]:
      num += cum_max-cum[b-1]
    
  if num>=M:
    left=x
  else:
    right=x

ans = 0
cum_A = [0]*(N+1)
for i in range(1,N+1):
  cum_A[i]=cum_A[i-1]+A[i-1]
for a in A:
  b = max(right-a,1)
  if b>A[0]:
    break
  c = cum_max-cum[b-1]
  M-=c
  ans+=(a*c)+cum_A[c]
  

ans+=M*left
print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
A = sorted(list(map(int,input().split())),reverse=True)
bi = [0]*(A[0]+1)
for a in A:
  bi[a]+=1
  
cum = [0]*(A[0]+1)
for i in range(1,A[0]+1):
  cum[i]=cum[i-1]+bi[i]

cum_max=cum[-1]
left = 0
right = A[0]*2
while right-1!=left:
  x = (right+left)//2
  num = 0
  for a in A:
    b = max(x-a,1)
    if b<=A[0]:
      num += cum_max-cum[b-1]
    
  if num>=M:
    left=x
  else:
    right=x

ans = 0
cum_A = [0]*(N+1)
for i in range(1,N+1):
  cum_A[i]=cum_A[i-1]+A[i-1]
for a in A:
  b = max(right-a,1)
  if b>A[0]:
    break
  c = cum_max-cum[b-1]
  M-=c
  ans+=(a*c)+cum_A[c]
  

ans+=(M*left)
print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
A = sorted(list(map(int,input().split())),reverse=True)
bi = [0]*(A[0]+1)
for a in A:
  bi[a]+=1
  
cum = [0]*(A[0]+1)
for i in range(1,A[0]+1):
  cum[i]=cum[i-1]+bi[i]

cum_max=cum[-1]
left = 0
right = A[0]*2
while right-1!=left:
  x = (right+left)//2
  num = 0
  for a in A:
    b = max(x-a,1)
    if b<=A[0]:
      num += cum_max-cum[b-1]
    
  if num>=M:
    left=x
  else:
    right=x
ans = 0
cum_A = [0]*(N+1)
for i in range(1,N+1):
  cum_A[i]=cum_A[i-1]+A[i-1]
for a in A:
  b = max(left-a,1)
  if b>A[0]:
    break
  c = cum_max-cum[b-1]
  M-=c
  ans+=(a*c)+cum_A[c]
  

ans+=(M*left)
print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
A = sorted(list(map(int,input().split())),reverse=True)
bi = [0]*(A[0]+1)
for a in A:
  bi[a]+=1
  
cum = [0]*(A[0]+1)
for i in range(1,A[0]+1):
  cum[i]=cum[i-1]+bi[i]

cum_max=cum[-1]
left = 0
right = A[0]*2
while right-1!=left:
  x = (right+left)//2
  num = 0
  for a in A:
    b = max(x-a,1)
    if b<=A[0]:
      num += cum_max-cum[b-1]
    
  if num>=M:
    left=x
  else:
    right=x
  print(left,right,x,num)
ans = 0
cum_A = [0]*(N+1)
for i in range(1,N+1):
  cum_A[i]=cum_A[i-1]+A[i-1]
for a in A:
  b = max(left-a,1)
  if b>A[0]:
    break
  c = cum_max-cum[b-1]
  M-=c
  ans+=(a*c)+cum_A[c]
  

ans+=(M*left)
print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
A = sorted(list(map(int,input().split())),reverse=True)
bi = [0]*(A[0]+1)
for a in A:
  bi[a]+=1
  
cum = [0]*(A[0]+1)
for i in range(1,A[0]+1):
  cum[i]=cum[i-1]+bi[i]

cum_max=cum[-1]
left = 0
right = A[0]*2
while right-1!=left:
  x = (right+left)//2
  num = 0
  for a in A:
    b = max(x-a,1)
    if b<=A[0]:
      num += cum_max-cum[b-1]
    
  if num>M:
    left=x
  else:
    right=x
ans = 0
cum_A = [0]*(N+1)
for i in range(1,N+1):
  cum_A[i]=cum_A[i-1]+A[i-1]
for a in A:
  b = max(left-a,1)
  if b>A[0]:
    break
  c = cum_max-cum[b-1]
  M-=c
  ans+=(a*c)+cum_A[c]
  

ans+=(M*left)
if M>=1:
  print(ss)
print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
A = sorted(list(map(int,input().split())),reverse=True)
bi = [0]*(A[0]+1)
for a in A:
  bi[a]+=1
  
cum = [0]*(A[0]+1)
for i in range(1,A[0]+1):
  cum[i]=cum[i-1]+bi[i]

cum_max=cum[-1]
left = 0
right = A[0]*2
while right-1!=left:
  x = (right+left)//2
  num = 0
  for a in A:
    b = max(x-a,1)
    if b<=A[0]:
      num += cum_max-cum[b-1]
    
  if num>M:
    left=x
  else:
    right=x
ans = 0
cum_A = [0]*(N+1)
for i in range(1,N+1):
  cum_A[i]=cum_A[i-1]+A[i-1]
for a in A:
  b = max(left-a,1)
  if b>A[0]:
    break
  c = cum_max-cum[b-1]
  M-=c
  ans+=(a*c)+cum_A[c]
  

ans+=(M*left)
print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
A = sorted(list(map(int,input().split())),reverse=True)
bi = [0]*(A[0]+1)
for a in A:
  bi[a]+=1
  
cum = [0]*(A[0]+1)
for i in range(1,A[0]+1):
  cum[i]=cum[i-1]+bi[i]

cum_max=cum[-1]
left = 0
right = A[0]*2
while right-1!=left:
  x = (right+left)//2
  num = 0
  for a in A:
    b = max(x-a,1)
    if b<=A[0]:
      num += cum_max-cum[b-1]
    
  if num>M:
    left=x
  else:
    right=x
ans = 0
cum_A = [0]*(N+1)
for i in range(1,N+1):
  cum_A[i]=cum_A[i-1]+A[i-1]
for a in A:
  b = max(left-a,1)
  c = cum_max-cum[b-1]
  M-=c
  ans+=(a*c)+cum_A[c]
  if M<=0:
    break
  
ans+=(M*left)
print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
A = sorted(list(map(int,input().split())),reverse=True)
bi = [0]*(A[0]+1)
for a in A:
  bi[a]+=1
  
cum = [0]*(A[0]+1)
for i in range(1,A[0]+1):
  cum[i]=cum[i-1]+bi[i]

cum_max=cum[-1]
left = 0
right = A[0]*2
while right-1!=left:
  x = (right+left)//2
  num = 0
  for a in A:
    b = max(x-a,1)
    if b<=A[0]:
      num += cum_max-cum[b-1]
    
  if num>M:
    left=x
  else:
    right=x
ans = 0
for a in A:
  b = max(left-a,1)
  c = cum_max-cum[b-1]
  M-=c
  ans+=(a*c)+(sum(A[:c]))
  if M<=0:
    break
  
ans+=(M*left)
print(ans)

Submission status: Wrong Answer

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


#O(nlogn)
def f(x):
    cnt = 0
    for i in a:
        idx = bl(a,x-i)
        cnt += n - idx
        if cnt >= m:
            return True
    return False

n,m = LI()
a = LI()
#O(nlogn)
a.sort()
ok,ng = 2*max(a)+1,2
#O(log(max(a)))
while ok - ng > 1:
    mid = (ok+ng) // 2
    if f(mid):
        ng = mid
    else:
        ok = mid

ans = 0
tmp = 0
#O(n)
b = [0] + list(accumulate(a))
#O(nlogn)
for i in a[::-1]:
    idx = bl(a,ng-i)
    if n - idx >= m - tmp:
        idx = n - (m - tmp)
        ans += i*(m - tmp) + (b[-1] - b[idx])
        break
    else:
        ans += i*(n - idx) + (b[-1] - b[idx])
    tmp += n - idx
print(ans)

Submission status: Wrong Answer

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

def solve(N: int, M: int, A: "List[int]"):
    A.sort()

    right = 2*A[-1]
    left = -1

    while right - left > 1:
        mid = (left+right)//2

        # A[i]+A[j] >= midになるようなi,jの組み合わせの個数 mを 求めたい
        # m >= Mならok
        m = 0
        for i in range(N):
            a = A[i]
            res = mid - a
            # Aからres以上のものを探す
            index = bisect_left(A,res)
            m += N-index
        
        if m >= M:
            left = mid
        else:
            right = mid

    # M通り以上の握手ができる最小の組み合わせの幸福度
    B = sorted(A,reverse=True)
    accum_B = list(accumulate(B))
    answer = 0
    handshake_count = 0
    for i in range(N):
        res = left - A[i]
        if res > A[-1]:
            continue
        index = bisect_left(A,res)
        answer += (N-index)*A[i]+accum_B[N-index-1]
        handshake_count += (N-index)

    # 握手の回数がmを越えたときはその分の幸福度を引く
    if handshake_count>M:
        answer -= left*(handshake_count-M)
    print(answer)
    return


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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


#O(nlogn)
def f(x):
    cnt = 0
    for i in a:
        idx = bl(a,x-i)
        cnt += n - idx
        if cnt >= m:
            return True
    return False

n,m = LI()
a = LI()
#O(nlogn)
a.sort()
ok,ng = 2*max(a)+1,2
#O(log(max(a)))
while ok - ng > 1:
    mid = (ok+ng) // 2
    if f(mid):
        ng = mid
    else:
        ok = mid

ans = 0
tmp = 0
#O(n)
b = [0] + list(accumulate(a))
#O(nlogn)
for i in a[::-1]:
    idx = bl(a,ng-i)
    if tmp + n - idx > m:
        idx = n - (m - tmp)
        ans += i*(n-idx) + (b[-1] - b[idx])
        break
    else:
        ans += i*(n - idx) + (b[-1] - b[idx])
    tmp += n - idx
print(ans)

Submission status: Wrong Answer

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


def f(x):
    cnt = 0
    for i in a:
        idx = bl(a,x-i)
        cnt += n - idx
        if cnt >= m:
            return True
    return False

n,m = LI()
a = LI()
a.sort()
ok,ng = 2*max(a),-1
while ok - ng > 1:
    mid = (ok+ng) // 2
    if f(mid):
        ng = mid
    else:
        ok = mid

ans = 0
tmp = 0
b = [0] + list(accumulate(a))
for i in a:
    idx = bl(a,ng-i)
    ans += i*(n - idx) + (b[-1] - b[idx])
    tmp += n - idx
ans = ans - (tmp - m)*ng
print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
from collections import deque
import re
import math
import functools


def sRaw():
    return input().rstrip("\r")


def iRaw():
    return int(input())


def ssRaw():
    return input().split()


def isRaw():
    return list(map(int, ssRaw()))


INF = 1 << 29


def mk1d(n, val=INF):
    return [val for i in range(n)]

def mk2d(h, w, val=INF):
    return [[val for i in range(w)]for i in range(h)]

DIV = 998244353


def convolve(a, b):
    p, g = 1107296257, 5
    n0, n1 = len(a), len(b)
    n = 1 << (max(n0, n1) - 1).bit_length() + 1
    a = a + [0] * (n-n0)
    b = b + [0] * (n-n1)
    w = pow(g, (p - 1) // n, p)
    invw = pow(w, p-2, p)

    def fft(f):
        d = n // 2
        v = w
        while d >= 1:
            u = 1
            for i in range(d):
                for j in range(i, n, 2*d):
                    f[j], f[j+d] = (f[j] + f[j+d]) % p, u * (f[j] - f[j+d]) % p
                u = u * v % p
            v = v * v % p
            d //= 2

    def ifft(f):
        d = 1
        while d < n:
            v = pow(invw, n // (2 * d), p)
            u = 1
            for i in range(d):
                for j in range(i, n, 2*d):
                    f[j+d] *= u
                    f[j], f[j+d] = (f[j] + f[j+d]) % p, (f[j] - f[j+d]) % p
                u = u * v % p
            d *= 2

    fft(a), fft(b)
    for i in range(n):
        a[i] = a[i] * b[i] % p
    ifft(a)
    invn = pow(n, p - 2, p)
    return [a[i] * invn % p for i in range(n0 + n1 - 1)]


def main():
    N,M = isRaw()
    As = isRaw()
    Hs = [0]*((10**5)+1)
    for a in As:
        Hs[a]+=1
    Cs = convolve(Hs,Hs)
    ans = 0
    left = M
    for hap in range(len(Cs)-1,0,-1):
        if Cs[hap] > 0:
            ans += min(left, Cs[hap])*hap
            left -= Cs[hap]
            if left<=0:
                break
    return ans

if __name__ == "__main__":
    print(main())

Submission status: Wrong Answer

Solution code:
import bisect
import sys
from itertools import accumulate
input = sys.stdin.readline
def hsnum(ls,x,n):
    num = 0
    for i in range(n):
        y = x-ls[i]
        num += n-bisect.bisect_left(ls,y)
    return num
n,m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
suma = [0]+list(accumulate(a))
lx = 0
rx = 10**5+2
error = 0
while lx < rx:
    mx = (lx+rx)//2
    if hsnum(a,mx,n) < m:
        rx = mx
    elif hsnum(a,mx,n) > m:
        if hsnum(a,mx+1,n) < m:
            error = hsnum(a,mx,n)-m
            lx = mx
            break
        lx = mx + 1
    else:
        lx = mx
        break
ans = 0
for i in range(n):
    rema = lx - a[i]
    j = bisect.bisect_left(a,rema)
    ans += (n-j)*a[i]+suma[n]-suma[j]
print(ans-error*lx)

Submission status: Wrong Answer

Solution code:
def ints():
  return [int(x) for x in input().split()]
def ii():
  return int(input())

N, M = ints()
A = ints()
A.sort()

def combinations(x):
  s = 0
  i = 0
  j = N-1
  while j>=0:
    while i<N and A[i]+A[j]<x:
      i += 1
    s += N-i

    j -= 1
    
  return s

def koufukudo(x):
  s = 0
  si = 0
  j = 0
  i = N-1
  while j<N:
    while i>=0 and A[i]+A[j]>=x:
      si += A[i]
      i -= 1
    s += si + A[j]*(N-1-i)

    j += 1
    
  return s


def bsearch(lower, upper):
  l = lower
  u = upper
  m = (l+u)//2
  c = combinations(m)
  if c<M:
    return bsearch(l, m)
  else:
    if l==m:
      return (l, c-M)
    return bsearch(m, u)

x, dm = bsearch(0, A[-1]*2+1)
print(x)
print(koufukudo(x)-dm*x)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
from bisect import bisect_right

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

a_count = [0]*110000
a_sum = [0]*110000

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

for i in range(100005,0,-1):
    a_count[i] += a_count[i+1]
    a_sum[i] += a_sum[i+1]

def chk(x):
    case = 0
    for i in range(n):
        if 0<= x-a[i]<= 10**5+5:
            case += a_count[x-a[i]]
        elif x-a[i] < 0:
            case += n
    if case >= m:
        ch = True
    else:
        ch = False
    return ch

l = 2*a[-1]+1    #NG
r = 1 #OK

while abs(r-l) > 1:
    kk = (r+l)//2
    if chk(kk):
        r = kk
    else:
        l = kk

ans = 0
sm = sum(a)

l = r

case = 0
for i in range(n):
    num = n-bisect_right(a,l-a[i]-1)
    case += num
    ans += num*a[i]*2

ans -= (case-m)*l

print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
from bisect import bisect_right

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

a_count = [0]*110000
a_sum = [0]*110000

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

for i in range(100005,0,-1):
    a_count[i] += a_count[i+1]
    a_sum[i] += a_sum[i+1]

def chk(x):
    case = 0
    for i in range(n):
        if 0<= x-a[i]<= 10**5+5:
            case += a_count[x-a[i]]
        elif x-a[i] < 0:
            case += n
        else:
            continue
    if case >= m:
        ch = True
    else:
        ch = False
    return ch

l = 2*a[-1]+1    #NG
r = 1 #OK

while abs(r-l) > 1:
    kk = (r+l)//2
    if chk(kk):
        r = kk
    else:
        l = kk

ans = 0
sm = sum(a)

l = r

case = 0
for i in range(n):
    num = n-bisect_right(a,l-a[i]-1)
    case += num
    ans += num*a[i]*2

ans -= (case-m)*l

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import bisect
import itertools


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, readline().split()))
    a = list(map(int, readline().split()))
    a.sort()
    cor_v = a[0] * 2
    inc_v = a[-1] * 2 + 1
    while - cor_v + inc_v > 1:
        bin_v = (cor_v + inc_v) // 2
        cost = 0
        #条件を満たすcostを全検索
        for i in range(n-1, -1, -1):
            cost += n - bisect.bisect_left(a, bin_v - a[i])
        #costが制約を満たすか
        if cost >= m:
            cor_v = bin_v
        else:
            inc_v = bin_v
    acm = list(itertools.accumulate([0] + a))
    print(acm)
    t = 0
    c = 0
    for i in range(n):
        p = bisect.bisect_left(a, cor_v - a[i])
        t += acm[-1] - acm[p] + a[i] * (n - p)
        c += n - p
    print(t - (c - m) * cor_v)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
n,m  = map(int, input().split())
As  = list(map(int, input().split()))
from itertools import accumulate
from bisect import bisect_right
from bisect import bisect_left
As.sort()
acc = [0]+list(accumulate(As))

# print(As)
x =  67
cnt = 0
ans = 0
for i,a in enumerate(As):
    ind = bisect_left(As, x-a)
    # print(a,i,ind)
    cnt += (n-ind)
    ans += a*(n-ind) + (acc[n]-acc[ind])
# print(cnt, ans)        


def f(x):
    cnt = 0
    ans = 0
    for i,a in enumerate(As):
        ind = bisect_left(As, x-a)
        cnt += (n-ind)
        ans += a*(n-ind) + (acc[n]-acc[ind])
    return cnt, ans       



def  binarySearch(l,r):
    ans, cnt = 0, 0
    while r - l > 1:
        mid = (l+r)//2
        c, a = f(mid)
        # print(mid,cnt,ans)
        if c <= m:
            r = mid
            ans = a
            cnt = c
        else:
            l = mid
    return r, cnt,ans

print(binarySearch(0,200000)[2])

Submission status: Wrong Answer

Solution code:
import sys
import bisect
import itertools


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, readline().split()))
    a = list(map(int, readline().split()))
    a.sort()
    cor_v = a[0] * 2
    inc_v = a[-1] * 2 + 1
    while - cor_v + inc_v > 1:
        bin_v = (cor_v + inc_v) // 2
        cost = 0
        #条件を満たすcostを全検索
        for i in range(n-1, -1, -1):
            cost += n - bisect.bisect_left(a, bin_v - a[i])
            if cost >= m:
                break
        #costが制約を満たすか
        if cost >= m:
            cor_v = bin_v
        else:
            inc_v = bin_v
    acm = list(itertools.accumulate([0] + a))
    t = 0
    c = 0
    for i in range(n):
        p = bisect.bisect_left(a, cor_v - a[i])
        t += acm[-1] - acm[p] + a[i] * (n - p)
        c += n - p
        if c >= m:
            break
    print(t - (c - m) * cor_v)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import itertools
import math

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

sup = int(math.sqrt(M) + 1)

nums = A[:sup]
scores = []

total = 0

for i in nums:
  for j in nums:
    total = i + j
    scores.append(total)

scores = sorted(scores,reverse = True)

print(sum(scores[:M]))

Submission status: Wrong Answer

Solution code:
import bisect
from itertools import accumulate
def hsnum(ls,x):
    n = len(ls)
    num = 0
    for i in range(n):
        y = x-ls[i]
        num += n-bisect.bisect_left(ls,y)
    return num
n,m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
suma = [0]+list(accumulate(a))
lx = 0
rx = 10**12
error = 0
while lx < rx:
    mx = (lx+rx)//2
    if hsnum(a,mx) < m:
        rx = mx
    elif hsnum(a,mx) > m:
        if hsnum(a,mx+1) < m:
            error = hsnum(a,mx)-hsnum(a,mx+1)
            lx = mx
            break
        lx = mx + 1
    else:
        lx = mx
        break
maxsum = lx
ans = 0
for i in range(n):
    rema = maxsum - a[i]
    j = bisect.bisect_left(a,rema)
    ans += (n-j)*a[i]
    ans += suma[n]-suma[j]
print(ans-error*lx)

Submission status: Wrong Answer

Solution code:
import heapq
import bisect
n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
s=[0]*(n+1)
dp=[0]*(10**5)
h=0
for i in range(10**5):
    if h==n:
        dp[i]=h
        continue
    if i<=a[h]:
        dp[i]=h
    else:
        while h<n and i>a[h]:
            h+=1
        dp[i]=h



for i in range(n):
    s[i+1]=s[i]+a[i]
def test(x):
    count=0
    for i in range(n):
        buf=x-a[i]
        #idx=bisect.bisect_left(a,x-a[i])
        if buf<0:
            idx=0
        elif buf>=10**5:
            idx=n
        else:
            idx=dp[buf]
        if i>=idx:
            count+=(i-idx)*2+1
    return count


def search():
    mn=-1
    mx=m*max(a)*2
    buf=0
    while mx-mn>1:
        buf=(mx+mn)//2
        count=test(buf)
        if count>=m:
            mn=buf
        else:
            mx=buf
    return mn
x=search()
y=test(x)
#print(x,y)
count=0
for i in range(n):
    idx=bisect.bisect_left(a,x-a[i])
    if i>=idx:
        count+=(2*i-2*idx)*a[i]+(s[i+1]-s[idx])*2
        #print(count,i-idx+1)
print(count-(y-m)*x)

Submission status: Wrong Answer

Solution code:
import sys
import bisect
import itertools


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, readline().split()))
    a = list(map(int, readline().split()))
    a.sort()
    cor_v = -1
    inc_v = 10 ** 5 * 2 + 100
    while - cor_v + inc_v > 1:
        bin_v = (cor_v + inc_v) // 2
        cost = 0
        #条件を満たすcostを全検索
        for i in range(n-1, -1, -1):
            cost += n - bisect.bisect_left(a, bin_v - a[i])
            if cost >= m:
                break
        #costが制約を満たすか
        if cost >= m:
            cor_v = bin_v
        else:
            inc_v = bin_v
    acm = list(itertools.accumulate([0] + a))
    t = 0
    c = 0
    for i in range(n):
        p = bisect.bisect_left(a, cor_v - a[i])
        t += acm[-1] - acm[p] + a[i] * (n - p)
        c += n - p
        if c >= m:
            break
    print(t - (c - m) * cor_v)


if __name__ == '__main__':
    solve()