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: Runtime Error

Solution code:
import sys
from collections import deque

def input():
    return sys.stdin.readline()

def judge(l,idx,idx_):
    s = l[idx] + l[idx_]
    if l[idx + 1] * 2 > s:
        return False,s
    else:
        return True,s
def search_max(d):
    return max(d, key=lambda x:d[x])

if __name__=="__main__":
    n,m =  map(int,input().split())
    l = [int(i) for i in input().split()]
    l.sort()
    l = deque(l[::-1])
    d = {(0,1):l[0]+l[1]}
    happiness = l[0]*2
    m_ = 1
    idx = 1

    while m > m_:
        key = search_max(d)
        s = d[key]
        if s >= l[idx]*2:
            happiness += s*2
            if key[1] + 1 <= n-1:
                d[(key[0],key[1]+1)] = l[key[0]] + l[key[1]+1]
            d.pop(key)
            m_ += 2
            if m_ > m:
                happiness -= s
        else:
            happiness += l[idx]*2
            if idx+1 <= n-1:
                d[(idx,idx+1)] = l[idx] + l[idx+1]
            idx += 1
            m_ += 1
    print(happiness)

Submission status: Runtime Error

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

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

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

print(ans)

Submission status: Runtime Error

Solution code:
N,M=map(int,input().ssplit())
A=list(map(int,input().split()))
A=sorted(A,reverse=True)
B=[]
for i in range(N):
  for j in range(i,N+1):
    B+=[A[i]+A[j]]
B=sorted(B,reverse=True)
S=sum(B[:M])
print(S)

Submission status: Runtime Error

Solution code:
import numpy as np
N,M = list(map(int,input().split()))
A = list(map(int,input().split()))
A = np.sort(A)[::-1]
 
m = int(min(M,N))
num = np.zeros(m)
ans = np.zeros(1)
for n,a in enumerate(A):
  if n>m:break
  for nn,aa in enumerate(A):
    if nn>m:break
    try:
      num[nn] = a + aa

Submission status: Runtime Error

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
    num[nn] = a + aa

Submission status: Runtime Error

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
    num[nn] = a + aa
  num = np.sort(num)[::-1]
  ans = np.r_[ans,num]
  ans = np.sort(ans)[::-1][:M]

print(int(sum(ans[:M])))

Submission status: Runtime Error

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):
    num[nn] = a + aa

Submission status: Runtime Error

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):
  for nn,aa in enumerate(A):
    num[nn] = a + aa
  num = np.sort(num)[::-1]
  ans = np.r_[ans,num]

Submission status: Runtime Error

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):
  for nn,aa in enumerate(A):
    num[nn] = a + aa
  num = np.sort(num)[::-1]
  ans = np.r_[ans,num]
  ans = np.sort(ans)[::-1][:M]

print(int(sum(ans[:M])))

Submission status: Runtime Error

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,m))
nn = 0

Submission status: Runtime Error

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((N,m))

Submission status: Runtime Error

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 = np.zeros((N,m))

Submission status: Runtime Error

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 = np.zeros((N,m))
nn = 0

Submission status: Runtime Error

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 = np.zeros((N,m))
nn = 0
for n,a in enumerate(A):
  for nn,aa in enumerate(A):
    num[n,nn] = a + aa
  num[n] = np.sort(num[n])[::-1]

Submission status: Runtime Error

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 = np.zeros((N*m))
nn = 0

Submission status: Runtime Error

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: Runtime Error

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*N)
nn = 0

Submission status: Runtime Error

Solution code:
def A():
    temp = input().split()
    print(''.join(temp[::-1]))

def B():
    temp = [int(n) for n in input().split()]
    A = temp[0]
    B = temp[1]
    K = temp[2]
    to_minus = min(A, K)
    A -= to_minus
    K -= to_minus
    if K > 0:
        B -= min(B, K)
    print (A, B)

import math
def C():
    X = int(input())
    if X <= 2:
        print(2)
        return

    def isPrime(n):
        if n <= 3:
            return True
        if(n % 2 == 0 or n % 3 == 0): 
            return False
      
        for i in range(5,int(math.sqrt(n) + 1), 6):  
            if(n%i == 0 or n%(i + 2) == 0): 
                return False
        
        return True
    
    while True:
        if isPrime(X):
            print(X)
            return
        X += 1

def D():
    temp = [int(n) for n in input().split()]
    N = temp[0]
    K = temp[1]

    temp = [int(n) for n in input().split()]
    point_dict = {'r': temp[0], 's': temp[1], 'p': temp[2]}

    T = input()

    winning_rule = {'r': 'p', 's': 'r', 'p': 's'}

    ans = 0
    last_choice = ['' for i in range(K)]
    for i, c in enumerate(T):
        if i<K or last_choice[i%K] != winning_rule[c]:
            last_choice[i%K] = winning_rule[c]
            ans += point_dict[winning_rule[c]]
        else:
            last_choice[i%K] = None
    print(ans)

import heapq

def E():
    temp = [int(n) for n in input().split()]
    N = temp[0]
    M = temp[1]
    A = [int(n) for n in input().split()]
    A.sort(reverse=True)
    # all_combinations = []
    # for i in range(N):
    #     for j in range(N):
    #         all_combinations.append(A[i]+A[j])
    # all_combinations.sort(reverse=True)
    # print(sum(all_combinations[:M]))
    ans = 0
    heap = []
    check_repeats = set()
    heapq.heappush(heap, (-2*A[0], (0, 0)))
    check_repeats.add((N-1, N-1))
    for k in range(M):
        temp = heapq.heappop(heap)
        #print(temp)
        ans += temp[0]
        i = temp[1][0]
        j = temp[1][1]
        if i+1 < N:
            s = A[i+1]+A[j]
            if (i+1, j) not in check_repeats:
                heapq.heappush(heap, (-s, (i+1, j)))
                check_repeats.add((i+1, j))
        if j+1 < N:
            s = A[i]+A[j+1]
            if (i, j+1) not in check_repeats:
                heapq.heappush(heap, (-s, (i, j+1)))
                check_repeats.add((i, j+1))
    
    print(abs(ans))

E()

Submission status: Runtime Error

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*N)
nn = 0
for a in A:
  for i in range(m):
    num[nn] = a+A[i]
    nn += 1

num= np.sort(num)[::-1]
print(sum(num[:M]))

Submission status: Runtime Error

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*N+1)
nn = 0
for n,a in enumerate(A):
  for i in range(m):
    num[nn] = a+A[i]
    nn += 1

num= np.sort(num)[::-1]
print(sum(num[:M]))

Submission status: Runtime Error

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*N)
nn = 0
for n,a in enumerate(A):
  for i in range(m):
    num[nn] = a+A[i]
    nn += 1

num= np.sort(num)[::-1]
print(sum(num[:M]))

Submission status: Runtime Error

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

m = min(M,N)
num = [0] * (N*N)
nn = 0
for n,a in enumerate(A):
  for i in range(m):
    num[nn] = a+A[i]
    nn += 1


num.sort()
num.reverse()

print(sum(num[:M]))

Submission status: Runtime Error

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

#C[i]=パワーがi以下の人数
C=[0]*(10**5+1)
for a in A:
    C[a]+=1
for i in range(1,len(C)):
    C[i]+=C[i-1]

#和がx以上になる組み合わせの総数を求める関数
def pattern_num_ge_x(x):
    p=0
    for a in A:
        p+=(N-(C[x-a-1] if x-a-1>=0 else 0))
    return(p)

#pattern_num_ge_x(x)がM未満になる最小のxを探す(=r)
#lはM以上になる最大のx
l=-1
r=10**5*2+1
while r-l>1:
    m=(r+l)//2
    if pattern_num_ge_x(m)<M:
        r=m
    else:
        l=m

#和がr以上になる組み合わせの総和を求める(累積和を使用)
S=[0]+list(reversed(A[:]))
for i in range(1,N+1):
    S[i]+=S[i-1]
ans=0
for a in A:
    idx=bisect.bisect_left(A,r-a)
    ans+=a*(N-idx) + S[N-idx]
    M-=(N-idx)

#回数のあまり分lを足す
ans+=l*M

print(ans)

Submission status: Runtime Error

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==0:
  print(ss)
print(ans)

Submission status: Runtime Error

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]
  
ans+=(M*left)
print(ans)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
import numpy as np
A = sorted(np.array(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
  
print(ans)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
import numpy as np
A = sorted(np.array(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(x-a,1)
  c = cum_max-cum[b-1]
  ans+=(a*c)+(sum(A[:c]))
  
print(ans)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
import numpy as np
A = sorted(np.array(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(x-a,1)
  c = cum_max-cum[b-1]
  ans+=(a*c)+(sum(A[:c]))
  
print(ans)

Submission status: Runtime Error

Solution code:
def main():
      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 = 2*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)
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
from math import factorial
from fractions import Fraction
import heapq, bisect, fractions
import math
import itertools
import numpy as np
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
MOD = 10**9 + 7

n, m = MAP()
a = LIST()
a = sorted(a, reverse = True)

def hantei(x):
    res = 0
    for i in range(len(a)):
        j = n-1
        while a[i] + a[j] < x and j >=0:
            res += 1
            j-= 1
    if n**2 - res <= m:
        return True
    return False

def hantei2(x):
    res = 0
    for i in range(len(a)):
        j = n-1
        while a[i] + a[j] < x and j >=0:
            res += 1
            j-= 1
    return n**2 - res

right = INF
left = -1
while right - left >1:
    mid = (right + left)//2
    if hantei(mid):
        right  = mid
    else:
        left = mid
    
ans = right

rr = hantei2(right)
ll = hantei2(left)

res = 0
for i in range(len(a)):
    j = n-1
    while a[i] + a[j] < ans and j >=0:
        j-= 1
    res += sum(a[:j+1]) + a[i]*(j+1)

if ll-rr >0 :
    res += left*(m-rr)
print(res)

Submission status: Runtime Error

Solution code:
import numpy as np

n, m = map(int, input().split())
arr = np.array(list(map(int, input().split())))
s_arr = np.sort(arr)[::-1]
l = len(s_arr)
zeros = np.zeros((l,l))
s1 = zeros + s_arr
s2 = s1.T + s_arr
s3 = np.hstack(s2)
s4 = np.sort(s3)[::-1]
print(int(s4[:m].sum()))

Submission status: Runtime Error

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]*100010
a_sum = [0]*100010

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

for i in range(100005,-1,-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]:
            case += a_count[x-a[i]]
        else:
            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: Runtime Error

Solution code:
temp = input().split()
n, m = int(temp[0]), int(temp[1])

temp = input().split()
guest = []
for i in range(n):
    guest.append(int(temp[i]))

guest.sort(reverse=True)

flag = 0


def for_i():
    ans = 0
    dz = 0
    zz = 0
    for i in range(len(guest)):
        if dz+(n-(i+1))*2+1 < m:
            dz += (n-(i+1))*2+1
            zz += 1
        else:
            break

    for i in range(zz+1):
        ans += guest[i]*2
        if i == zz:
            z = int((m-dz-1)/2)
            for j in range(i+1, i+1+z):
                # print("i:{} j:{}".format(i, j))
                ans += (guest[i]+guest[j])*2
            return i, j, ans
        else:
            for j in range(i+1, len(guest)):
                ans += (guest[i]+guest[j])*2


i, j, ans = for_i()
if (m-1) % 2 == 1:
    ans += guest[i] + guest[j+1]

print(ans)

Submission status: Runtime Error

Solution code:
temp = input().split()
n, m = int(temp[0]), int(temp[1])

temp = input().split()
guest = []
for i in range(n):
    guest.append(int(temp[i]))

guest.sort(reverse=True)

flag = 0


def for_i():
    ans = 0
    dz = 0
    zz = 0
    for i in range(len(guest)):
        if dz+(n-(i+1))*2+1 < m:
            dz += (n-(i+1))*2+1
            zz += 1
        else:
            break

    for i in range(zz+1):
        ans += guest[i]*2
        if i == zz:
            z = (m-dz-1)/2
            for j in range(i+1, i+1+z):
                # print("i:{} j:{}".format(i, j))
                ans += (guest[i]+guest[j])*2
            return i, j, ans
        else:
            for j in range(i+1, len(guest)):
                ans += (guest[i]+guest[j])*2


i, j, ans = for_i()
if (m-1) % 2 == 1:
    ans += guest[i] + guest[j+1]

print(ans)

Submission status: Runtime Error

Solution code:
temp = input().split()
n, m = int(temp[0]), int(temp[1])

temp = input().split()
guest = []
for i in range(n):
    guest.append(int(temp[i]))

guest.sort(reverse=True)

flag = 0


def for_i():
    ans = 0
    dz = 0
    zz = 0
    for i in range(len(guest)):
        if dz+(n-(i+1))*2+1 < m:
            dz += (n-(i+1))*2+1
            zz += 1
        else:
            break

    for i in range(zz+1):
        ans += guest[i]*2
        if i == zz:
            z = (m-dz-1)//2
            for j in range(i+1, i+1+z):
                # print("i:{} j:{}".format(i, j))
                ans += (guest[i]+guest[j])*2
            return i, j, ans
        else:
            for j in range(i+1, len(guest)):
                ans += (guest[i]+guest[j])*2


i, j, ans = for_i()
if (m-1) % 2 == 1:
    ans += guest[i] + guest[j+1]

print(ans)

Submission status: Runtime Error

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:
              	cost += 10 ** 100
              	cost -= 10 ** 100
                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
    print(t - (c - m) * cor_v)


if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
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 x-a[i] <= 1:
            case += n
        else:
            case += a_count[x-a[i]]
    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

from bisect import bisect_left
from bisect import bisect_right

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: Runtime Error

Solution code:
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 x-a[i] <= 1:
            case += n
        else:
            case += a_count[x-a[i]]
    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

for i in range(n):
    if l-a[i] <= 0:
        ans += sm + n*a[i]
    else:
        ans += a_count[l-a[i]]*a[i] + a_sum[l-a[i]]

case = 0
for i in range(n):
    if l-a[i] <= 1:
        case += n
    else:
        case += a_count[l-a[i]]

ans -= (case-m)*l

print(ans)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split(' '))
arra = input().split(' ')
for i in range(len(arra)):
    arra[i] = int(arra[i])
    
ls = [0] * (n ** 2)
for i in range(n):
    for j in range(n):
        idx = i + j * n
        #print(idx)
        ls[idx] = (arra[i] + arra[j])
#ls.sort(revese = True)
sls = sorted(ls, reverse = True)
#print(sls)
point = 0
for i in range(m):
    point += sls[i]
print(point)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split(' '))
arra = input().split(' ')
for i in range(len(arra)):
    arra[i] = int(arra[i])
    
ls = [0] * (n ** 2)
for i in range(n):
    for j in range(n):
        idx = i + j * n
        #print(idx)
        ls[idx] = (arra[i] + arra[j])
#ls.sort(revese = True)
sls = sorted(ls, reverse = True)
print(sls)
point = 0
for i in range(m):
    point += sls[i]
print(point)

Submission status: Runtime Error

Solution code:
import heapq
n,m = map(int,input().split())
a = list(map(int,input().split()))
a.sort(reverse = True)
check = [0]*(n**2)
check[0] = 1

score = 0
now = [-a[0]-a[0],0,0]
time = 1
wait = []
done = []
def f(array):
    return array[1]*n+array[2]

while time <= m:
    score -= now[0]
    if now[1] == now[2]:
        if now[2]+1 < n:
            r = [now[1],now[2]+1]
            r = [-a[r[0]]-a[r[1]]]+r
            if check[f(r)]==0:
                heapq.heappush(wait,r)
                check[f(r)] = 1
    else:
        if now[2]+1 < n:
            r = [now[1],now[2]+1]
            r = [-a[r[0]]-a[r[1]]]+r
            if check[f(r)]==0:
                heapq.heappush(wait,r)
                check[f(r)] = 1
        q = [now[1]+1,now[2]]
        q = [-a[q[0]]-a[q[1]]]+q
        if check[f(q)]==0:
            heapq.heappush(wait,q)
            check[f(q)]=1
        if time != m:
            score -= now[0]
            time += 1
    if wait:
        now = heapq.heappop(wait)
    else:
        break
    time += 1
print(score)

Submission status: Runtime Error

Solution code:
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 x-a[i] <= 1:
            case += n
        else:
            case += a_count[x-a[i]]
    if case >= m:
        ch = True
    else:
        ch = False
    return ch


l = 1    #OK
r = 2*10**5 + 1 #NG

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

ans = 0
sm = sum(a)

for i in range(n):
    if l-a[i] <= 0:
        ans += sm + n*a[i]
    else:
        ans += a_count[l-a[i]]*a[i] + a_sum[l-a[i]]

case = 0
for i in range(n):
    if l-a[i] <= 1:
        case += n
    else:
        case += a_count[l-a[i]]

ans -= (case-m)*l

print(ans)

Submission status: Runtime Error

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

a_count = [0]*100100
a_sum = [0]*100100

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

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

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

l = 1    #OK
r = 2*10**5 #NG

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

ans = 0
sm = sum(a)

for i in range(n):
    if l-a[i] <= 0:
        ans += sm + n*a[i]
    else:
        ans += (n-a_count[l-a[i]-1])*a[i] + sm-a_sum[l-a[i]-1]
        

case = 0
for i in range(n):
    if l-a[i] <= 1:
        case += n
    else:
        case += n-a_count[l-a[i]-1]

ans -= (case-m)*l

print(ans)

Submission status: Runtime Error

Solution code:
import sys
import bisect


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()
    t = 0
    c = 0
    s = n - 1
    for i in range(a[-1] * 2, a[1] - 1, -1):
        for j in range(s, -1, -1):
            if a[j] * 2 == i:
                c += 1
                t += i
            pl = bisect.bisect_left(a, i - a[j], 0, j)
            pr = bisect.bisect_right(a, i - a[j], 0, j)
            if pl == n:
                break
            elif pr == 0 and j != 0:
                s -= 1
            if pl != pr:
                c += 2 ** (pr - pl)
                t += 2 ** (pr - pl) * i
            if c >= m:
                print(t - (c - m) * i)
                exit()


if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def count_num(X):
	B = X - A.reshape(N, 1)
	return np.count_nonzero(A >= B)


if __name__ == "__main__":
	# N, M = map(int, input().split())
	# A = np.array(input().split(), np.int64)
	N,M = map(int,readline().split())
	A = np.array(read().split(),np.int64)

	left = 0
	right = 10 ** 6
	while left + 1 < right:
		x = (left + right) // 2
		if count_num(x) >= M:
			left = x
		else:
			right = x

	B = left - A.reshape(N, 1)
	count = np.count_nonzero(A > B)
	ans = np.sum(np.where(A > B, A + A.reshape(N, 1), 0))
	ans += left * (M - count)
	print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np

def count_num(X):
	B = X - np.transpose(np.tile(A, (N, 1)))
	return np.count_nonzero(A >= B)


if __name__ == "__main__":
	N, M = map(int, input().split())
	A = np.array(input().split(), np.int64)

	left = 0
	right = 10 ** 6
	while left + 1 < right:
		x = (left + right) // 2
		if count_num(x) >= M:
			left = x
		else:
			right = x

	B = left - np.transpose(np.tile(A, (N, 1)))
	count = np.count_nonzero(A > B)
	ans = np.sum(np.where(A > B, A + np.transpose(A), 0))
	ans += left * (M - count)
	print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np

n,m = map(int,input().split())
l =list(map(int,input().split()))
v=np.array(l)
vv=np.zeros((n,n))
for i in range(n):
    vv[i] += v
for j in range(n):
    vv[:,j] += v.T
vec=np.array(vv.ravel())
vec[::-1].sort()
ans=int(vec[0:m].sum())
print(ans)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
import numpy as np
A = sorted(np.array(list(map(int,input().split()))),reverse=True)
ans = 0
while M>0:
  a = A.pop(0)
  ans += a*2
  M-=1
  if (M>0)and(a>=A[0]*2):
    for i in A:
      ans+=(i+a)*2
      M-=2
      if M==0:
        break
      elif M<0:
        ans-=(i+a)
        break
        
  elif (M>0)and(a<A[0]*2):
    b=A[0]*2-a
    for i in A:
      if i>=b:
        ans+=(i+a)*2
        M-=2
        if M==0:
          break
        elif M<0:
          ans-=(i+a)
          break
      else:
        break
print(ans)