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
input = sys.stdin.readline
import numpy as np

def main():
    N,M = map(int,input().split())
    a = sorted(list(map(int,input().split())))
    b = [0]+a
    a = np.array(a)
    cum = np.cumsum(b)
    
    def power(x,y):
        pos = np.searchsorted(a,x-y)
        count = np.sum(N-pos)
        if count >= M:
            return True
        else:
            return False
    
    l,r = 0,10**5+1
    while r-l > 1:
        mid = (l+r)//2
        if power(mid,a):
            l = mid
        else:
            r = mid

    def solve(x,y):
        ans = 0
        pos_rev = np.searchsorted(a,x-y)
        pos = N-pos_rev
        count = np.sum(pos)
        ans = np.sum(a*[pos]+cum[-1]-cum[-pos-1])
        return ans-x*(count-M)
        
    print(solve(l,a))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import numpy as np

def main():
    N,M = map(int,input().split())
    a = sorted(list(map(int,input().split())))
    b = [0]+a
    a = np.array(a)
    cum = np.cumsum(b)
    
    def power(x,y):
        pos = np.searchsorted(a,x-y)
        count = np.sum(N-pos)
        if count >= M:
            return True
        else:
            return False
    
    l,r = 0,10**5+1
    while r-l > 1:
        mid = (l+r)//2
        if power(mid,a):
            l = mid
        else:
            r = mid

    def solve(x,y,minuse):
        ans = 0
        pos_rev = np.searchsorted(a,x-y)
        pos = N-pos_rev
        count = np.sum(pos)
        ans = np.sum(a*[pos]+cum[-1]-cum[-pos-1])
        return ans-minuse*(count-M)
        
    print(solve(l,a,l))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys

def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<x:
            p+=1
        cnt+=n-p
    return cnt

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

l,r=a[0]*2,a[n-1]*2

while r-l>0:
    if r-l<=1:
        if f(r)==m: md=r;break 
        else: md=l;break
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md


p=0
cnt=0
ans=0

for q in range(n-1,-1,-1):
    try:
        while p<n and p>-1 and q<n and q>-1: 
            if a[q]+a[p]<=md: p+=1
            else: break
    except:
        sys.exit()

    cnt+=n-p
    ans+=a[q]*(n-p)*2
    if p==n: break


ans+=(m-cnt)*md
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<x:
            p+=1
        cnt+=n-p
    return cnt

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

l,r=a[0]*2,a[n-1]*2

while r-l>0:
    if r-l<=1:
        if f(r)==m: md=r;break 
        else: md=l;break
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md


p=0
cnt=0
ans=0

for q in range(n-1,-1,-1):
    try:
        while p<n and q>-1 and a[q]+a[p]<=md:
            p+=1
    except:
        sys.exit()

    cnt+=n-p
    ans+=a[q]*(n-p)*2
    if p==n: break


ans+=(m-cnt)*md
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<x:
            p+=1
        cnt+=n-p
    return cnt

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

l,r=a[0]*2,a[n-1]*2

while r-l>0:
    if r-l<=1:
        if f(r)==m: md=r;break 
        else: md=l;break
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md


p=0
cnt=0
ans=0

for q in range(n-1,-1,-1):
    try:
        while p<n and q>-1:
            if a[q]+a[p]<=md: p+=1
    except:
        sys.exit()

    cnt+=n-p
    ans+=a[q]*(n-p)*2
    if p==n: break


ans+=(m-cnt)*md
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<x:
            p+=1
        cnt+=n-p
    return cnt

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

l,r=a[0]*2,a[n-1]*2

while r-l>0:
    if r-l<=1:
        if f(r)==m: md=r;break 
        else: md=l;break
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md


p=0
cnt=0
ans=0

for q in range(n-1,-1,-1):
    try:
        while p<n and q>-1:
            if a[q]+a[p]<=md: p+=1
            else: break
    except:
        sys.exit()

    cnt+=n-p
    ans+=a[q]*(n-p)*2
    if p==n: break


ans+=(m-cnt)*md
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<x:
            p+=1
        cnt+=n-p
    return cnt

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

l,r=a[0]*2,a[n-1]*2

while r-l>0:
    if r-l<=1:
        if f(r)==m: md=r;break 
        else: md=l;break
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md

p=0
cnt=0
ans=0

for q in range(n-1,-1,-1):
    try:
        while p<n and a[q]+a[p]<=md:
            p+=1
    except:
        print(ans)
        sys.exit()

    if p==n: break
    cnt+=n-p
    ans+=a[q]*(n-p)*2


ans+=(m-cnt)*md
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<x:
            p+=1
        cnt+=n-p
    return cnt

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

l,r=a[0]*2,a[n-1]*2

while r-l>0:
    if r-l<=1:
        if f(r)==m: md=r;break 
        else: md=l;break
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md

p=0
cnt=0
ans=0

for q in range(n-1,-1,-1):
    try:
        while p<n and a[q]+a[p]<=md:
            p+=1
        if p==n:
            break
        cnt+=n-p
        ans+=a[q]*(n-p)*2
    except:
        print(ans)
        sys.exit()


ans+=(m-cnt)*md
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<x:
            p+=1
        cnt+=n-p
    return cnt

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

l,r=a[0]*2,a[n-1]*2

while r-l>0:
    if r-l<=1:
        if f(r)==m: md=r;break 
        else: md=l;break
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md

p=0
cnt=0
ans=0

for q in range(n-1,-1,-1):
    try:
        while p<n and a[q]+a[p]<=md:
            p+=1
        if p==n: break
        cnt+=n-p
        ans+=a[q]*(n-p)*2
    except:
        print(0)
        sys.exit()


ans+=(m-cnt)*md
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<x:
            p+=1
        cnt+=n-p
    return cnt

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

l,r=a[0]*2,a[n-1]*2

while r-l>0:
    if r-l<=1:
        if f(r)==m: md=r;break 
        else: md=l;break
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md

p=0
cnt=0
ans=0

for q in range(n-1,-1,-1):
    try:
        while p<n and a[q]+a[p]<=md:
            p+=1
        if p==n: break
        cnt+=n-p
        ans+=a[q]*(n-p)*2
    except:
        print(0)

try:
    ans+=(m-cnt)*md
    print(ans)
except:
    print(0)

Submission status: Wrong Answer

Solution code:
import sys

def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<x:
            p+=1
        cnt+=n-p
    return cnt

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

l,r=a[0]*2,a[n-1]*2

while r-l>0:
    if r-l<=1:
        if f(r)==m: md=r;break 
        else: md=l;break
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md

p=0
cnt=0
ans=0

try:

    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<=md:
            p+=1
        if p==n: break
        cnt+=n-p
        ans+=a[i]*(n-p)*2
    
    ans+=(m-cnt)*md
    print(ans)

except:
    print(0)

Submission status: Wrong Answer

Solution code:
import sys

def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<x:
            p+=1
        cnt+=n-p
    return cnt

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

l,r=a[0]*2,a[n-1]*2

while r-l>0:
    if r-l<=1:
        if f(r)==m: md=r;break 
        else: md=l;break
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md
try:
    p=0
    cnt=0
    ans=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<=md:
            p+=1
        cnt+=n-p
        ans+=a[i]*(n-p)*2


    ans+=(m-cnt)*md
    print(ans)
except:
    print(1)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
from fractions import gcd
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9 +7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#############
# Main Code #
#############

N,M = inputIL()
A = inputIL()

MAX = max(A)

imos = [0]*(MAX*2+2)
imos[0] = N

for i in A:
  imos[i+1] -= 1
for i in range(1,len(imos)):
  imos[i] = imos[i-1]+imos[i]


def count_m(X):
  m = 0
  for i in A:
    m += imos[max(0,X-i)]
  return m

upper = MAX*2
lower = 0
X = (upper+lower)//2
m = count_m(X)


#print(m,X,lower,upper)
while upper != lower:
  if m > M:
    lower = (upper+lower+1)//2
  else:
    upper = (upper+lower-1)//2
  X = (upper+lower)//2
  m = count_m(X)
  #print(m,X,lower,upper)

  
imos2 = [0]*(MAX*2+2)
for i in A:
  imos2[0] += i
  imos2[i+1] -= i
for i in range(1,len(imos2)):
  imos2[i] = imos2[i-1]+imos2[i]
  
ans = 0
for i in A:
  ans += i*imos[max(X-i,0)]+imos2[max(X-i,0)]
  
print(ans-(m-M)*X)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
from fractions import gcd
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9 +7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#############
# Main Code #
#############

N,M = inputIL()
A = inputIL()

MAX = max(A)

imos = [0]*(MAX*2+2)
imos[0] = N

for i in A:
  imos[i+1] -= 1
for i in range(1,len(imos)):
  imos[i] = imos[i-1]+imos[i]


def count_m(X):
  m = 0
  for i in A:
    m += imos[max(0,X-i)]
  return m

upper = MAX*2
lower = 0
X = (upper+lower)//2
m = count_m(X)

while upper != lower:
  if m > M:
    lower = (upper+lower+1)//2
  else:
    upper = (upper+lower)//2
  X = (upper+lower)//2
  m = count_m(X)

  
imos2 = [0]*(MAX*2+2)
for i in A:
  imos2[0] += i
  imos2[i+1] -= i
for i in range(1,len(imos2)):
  imos2[i] = imos2[i-1]+imos2[i]
  
ans = 0
for i in A:
  ans += i*imos[max(X-i,0)]+imos2[max(X-i,0)]
  
print(ans-(m-M)*X)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
from fractions import gcd
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9 +7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#############
# Main Code #
#############

N,M = inputIL()
A = inputIL()

MAX = max(A)

imos = [0]*(MAX*2+2)
imos[0] = N

for i in A:
  imos[i+1] -= 1
for i in range(1,len(imos)):
  imos[i] = imos[i-1]+imos[i]


def count_m(X):
  m = 0
  for i in A:
    m += imos[max(0,X-i)]
  return m

X = (MAX*2+1)//2
d = X+0

m = count_m(X)

while d > 1:

  d = (d+1)//2
  if m > M:
    X += d
  else:
    X -= d
  m = count_m(X)

  
imos2 = [0]*(MAX*2+2)
for i in A:
  imos2[0] += i
  imos2[i+1] -= i
for i in range(1,len(imos2)):
  imos2[i] = imos2[i-1]+imos2[i]
  
ans = 0
for i in A:
  ans += i*imos[max(X-i,0)]+imos2[max(X-i,0)]
  
print(ans-(m-M)*X)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
from fractions import gcd
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9 +7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#############
# Main Code #
#############

N,M = inputIL()
A = inputIL()

MAX = max(A)

imos = [0]*(MAX*2+2)
imos[0] = N

for i in A:
  imos[i+1] -= 1
for i in range(1,len(imos)):
  imos[i] = imos[i-1]+imos[i]


def count_m(X):
  m = 0
  for i in A:
    m += imos[max(0,X-i)]
  return m

X = (MAX*2+1)//2
d = X+0

m = count_m(X)

while d > 1:

  d = (d+1)//2
  if m >= M:
    X += d
  else:
    X -= d
  m = count_m(X)

imos2 = [0]*(MAX*2+2)
for i in A:
  imos2[0] += i
  imos2[i+1] -= i
for i in range(1,len(imos2)):
  imos2[i] = imos2[i-1]+imos2[i]
  
ans = 0
for i in A:
  ans += i*imos[max(X-i,0)]+imos2[max(X-i,0)]
  
print(ans-(m-M)*X)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
from fractions import gcd
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9 +7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#############
# Main Code #
#############

N,M = inputIL()
A = inputIL()

MAX = max(A)

imos = [0]*(MAX*2+2)
imos[0] = N

for i in A:
  imos[i+1] -= 1
for i in range(1,len(imos)):
  imos[i] = imos[i-1]+imos[i]


def count_m(X):
  m = 0
  for i in A:
    m += imos[max(0,X-i)]
  return m

X = (MAX*2+1)//2
d = X+0

m = count_m(X)

while d > 1:

  d = (d+1)//2
  if m >= M:
    X += d
  else:
    X -= d
  m = count_m(X)

print(m,X,d)
imos2 = [0]*(MAX*2+2)
for i in A:
  imos2[0] += i
  imos2[i+1] -= i
for i in range(1,len(imos2)):
  imos2[i] = imos2[i-1]+imos2[i]
  
ans = 0
for i in A:
  ans += i*imos[max(X-i,0)]+imos2[max(X-i,0)]
  
print(ans-(m-M)*X)

Submission status: Wrong Answer

Solution code:
# import numpy as np
# import scipy as sp
# import sys
# input = sys.stdin.readline
# print(a,b,c,sep="") # 半角スペースなしで出力(abc)
# n=int(input())  #数値入力 「N」だけの入力のとき
# a,b=list(map(int, input().split()))  #複数数値入力　「A B」みたいなスペース空いた入力のとき
# a=list(map(int, input().split()))  #リスト入力 「a1 a2 a3 ...」みたいな配列のような入力のとき
# a=[int(input()) for _ in range (n)]  #リスト入力  改行でa1 ... anのとき
# s=[list(map(str,list(input()))) for i in range(h)]  # 文字列の二次元配列入力
# s = [list(map(int, input().split())) for i in range(n)] # 数値の二次元配列入力
# a = b[:], a = [x[:] for x in b] # deepcopy
# chr(ord('a') + 1) # chrのインクリメント
# s.sort(key=lambda x: x[1], reverse=False) # 2番目の要素で昇順にソート（Trueなら降順）
#　

import itertools
import bisect
n, m = list(map(int, input().split()))
al = list(map(int, input().split()))
al.sort()
ub = al[-1]*2
lb = 0
while lb + 1 < ub:
    target = (ub+lb)//2
    tmp = 0
    for a in al:
        sa = target - a
        # リストAに値xを入れ、xが複数になるとき、一番左の値xのインデックスを返す
        i = bisect.bisect(al, sa)
        tmp += (n-i)
    if (tmp >= m):
        lb = target
    else:
        ub = target


rui_al = [0] + list(itertools.accumulate(al))
ans = 0
tmp = 0
for a in al:
    sa = target - a
    # リストAに値xを入れ、xが複数になるとき、一番左の値xのインデックスを返す
    i = bisect.bisect_left(al, sa)
    tmp += (n-i)
    ans += (rui_al[-1] - rui_al[i])
    ans += a*(n-i)

if tmp > m:
    ans -= (tmp-m)*target
    ans -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
import bisect
n, m = list(map(int, input().split()))
al = list(map(int, input().split()))
al.sort()
ub = al[-1]*2
lb = 0
while lb + 1 < ub:
    target = (ub+lb)//2
    tmp = 0
    for a in al:
        sa = target - a
        # リストAに値xを入れ、xが複数になるとき、一番左の値xのインデックスを返す
        i = bisect.bisect_left(al, sa)
        tmp += (n-i)
    if (tmp >= m):
        lb = target
    else:
        ub = target

target = ub
rui_al = [0] + list(itertools.accumulate(al))
ans = 0
tmp = 0
for a in al:
    sa = target - a
    # リストAに値xを入れ、xが複数になるとき、一番左の値xのインデックスを返す
    i = bisect.bisect_left(al, sa)
    tmp += (n-i)
    ans += (rui_al[-1] - rui_al[i])
    ans += a*(n-i)



ans += (m-tmp)*target
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
import bisect
n, m = list(map(int, input().split()))
al = list(map(int, input().split()))
al.sort()
ub = al[-1]*2
lb = 0
while lb + 1 < ub:
    target = (ub+lb)//2
    tmp = 0
    for a in al:
        sa = target - a
        # リストAに値xを入れ、xが複数になるとき、一番左の値xのインデックスを返す
        i = bisect.bisect_left(al, sa)
        tmp += (n-i)
    if (tmp >= m):
        lb = target
    else:
        ub = target

target = lb
rui_al = [0] + list(itertools.accumulate(al))
ans = 0
tmp = 0
for a in al:
    sa = target - a
    # リストAに値xを入れ、xが複数になるとき、一番左の値xのインデックスを返す
    i = bisect.bisect_left(al, sa)
    tmp += (n-i)
    ans += (rui_al[-1] - rui_al[i])
    ans += a*(n-i)


if tmp > m:
    ans -= (tmp-m)*target
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
import bisect
n, m = list(map(int, input().split()))
al = list(map(int, input().split()))
al.sort()
ub = al[-1]*2
lb = 0
while lb + 1 < ub:
    target = (ub+lb)//2
    tmp = 0
    for a in al:
        sa = target - a
        # リストAに値xを入れ、xが複数になるとき、一番左の値xのインデックスを返す
        i = bisect.bisect_left(al, sa)
        tmp += (n-i)
    if (tmp >= m):
        lb = target
    else:
        ub = target


rui_al = [0] + list(itertools.accumulate(al))
ans = 0
tmp = 0
for a in al:
    sa = target - a
    # リストAに値xを入れ、xが複数になるとき、一番左の値xのインデックスを返す
    i = bisect.bisect_left(al, sa)
    tmp += (n-i)
    ans += (rui_al[-1] - rui_al[i])
    ans += a*(n-i)

if m > tmp:
    ans += (m-tmp)*(target-1)
print(ans)

Submission status: Wrong Answer

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

A.sort(reverse=True)

def count(i,B):
    B = B - A[i]
    l = -1
    r = N
    while l+1<r:
        j = (l+r)//2
        if A[j] >= B:
            l = j
        else:
            r = j
    return r

l = 0
r = 10**5*3
while l+1<r:
    i = (l+r)//2
    S = 0
    for j in range(N):
        S += count(j,i)
    if S==M:
        l = i
        break
    elif S>M:
        l = i
    else:
        r = i

ans = 0
tmp = 0
SA = [0]*(N+1)
for j in range(N):
    SA[j+1] = SA[j] + A[j]
for j in range(N):
    c = count(j,i)
    ans += A[j]*c + SA[c]
    tmp += c
if M>tmp:
    n = 0
    for j in range(N):
        c = count(j,i)
        if c==N: continue
        n = max(n,A[j] + A[c])
    ans += n*(M-tmp)
print(ans)

Submission status: Wrong Answer

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

A.sort(reverse=True)

def count(i,B):
    B = B - A[i]
    l = -1
    r = N
    while l+1<r:
        j = (l+r)//2
        if A[j] >= B:
            l = j
        else:
            r = j
    return r

l = 0
r = 10**5*3
while l+1<r:
    i = (l+r)//2
    S = 0
    for j in range(N):
        S += count(j,i)
    if S==M:
        l = i
        break
    elif S>M:
        l = i
    else:
        r = i

ans = 0
tmp = 0
for j in range(N):
    c = count(j,i)
    ans += A[j]*c + sum(A[:c])
    tmp += c
ans += (i-1)*(M-tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
A = sorted([int(a) for a in input().split()])
INF = (10 ** 5) * 2 + 10


# 和がmid以上の組み合わせ数を返す関数
def count(mid):
    ind = [0] * N
    I = 0
    for j in range(N - 1, -1, -1):
        for i in range(I, N):
            if A[i] + A[j] >= mid:
                I = i
                ind[j] = I
                break
        else:
            ind[j] = N
    return N ** 2 - sum(ind)


r = INF
l = 0

while r - l > 1:
    c = (r + l) // 2
    now_M = count(c)
    if now_M >= M:
        l = c
    elif now_M < M:
        r = c

print("{} {}".format(l, r))

# r以上の要素を数える
ind = [0] * N
I = N - 1
for j in range(N):
    for i in range(I, -1, -1):
        if A[i] + A[j] < l:
            I = i
            ind[j] = N-(I+1)
            break
        else:
            ind[j] = N

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

SUM = 0
for i in range(N):
    if ind[i] != 0:
        SUM += S[N - ind[i]] + ind[i] * A[i]

print(SUM)