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: Time Limit Exceeded

Solution code:
n,m = (int(w) for w in input().split()[:2])
a = [int(w) for w in input().split()[:n]]

s = [a[x]+a[y] for x in range(n) for y in range(n)]
s.sort(reverse=True)

print(sum(s[:m]))

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

# aの直積
list1 = list(itertools.product(a, repeat=2))
# list1の各タプルを合計
sum1 = sorted(list(itertools.starmap(lambda x, y: x+y, list1)), reverse=True)

# 値の大きい順にm個までの合計
print(sum(sum1[:m]))

Submission status: Time Limit Exceeded

Solution code:
import itertools

n, m = map(int, input().split())
a = sorted([int(i) for i in input().split()], reverse=True)

# aの直積
list1 = list(itertools.product(a, repeat=2))
# list1の各タプルを合計
sum1 = sorted(list(itertools.starmap(lambda x, y: x+y, list1)), reverse=True)

print(sum(sum1[:m]))

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

# aの直積
list1 = list(itertools.product(a, repeat=2))
# liの各タプルを合計
sum1 = sorted(list(itertools.starmap(lambda x, y: x+y, list1)), reverse=True)

val = 0
for i in range(m):
  val += sum1[i]
  
print(val)

Submission status: Time Limit Exceeded

Solution code:
Input1 = list(map(int,input().split()))
N = Input1[0]
M = Input1[1]
Input2 = list(map(int,input().split()))
Ar = Input2
Ans_ar=[]
for i in range(N):
  for t in range(N):
    Ans_ar.append(Ar[i]+Ar[t])
Ans_ar.sort(reverse=True)
ans=0
for i in range(M):
  ans+=Ans_ar[i]
print(ans)

Submission status: Time Limit Exceeded

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

import itertools

N, M = map(int, input().split())
A = list(map(int, input().split()))
# print(N, M)
# print(A)

perms = list(itertools.permutations(A, 2))
for i in A:
    perms.append((i, i))

# for perm in perms:
#     print(perm)

def sum(a, b):
    return a + b

sum_list = []
for perm in perms:
    a = perm[0]
    b = perm[1]
    sum_list.append(sum(a, b))

sum_list_sorted = sorted(sum_list)

result = 0
for i in range(M):
    result += sum_list_sorted.pop()

print(result)

Submission status: Time Limit Exceeded

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

import itertools

N, M = map(int, input().split())
A = list(map(int, input().split()))
# print(N, M)
# print(A)

perms = list(itertools.permutations(A, 2))
for i in A:
    perms.append((i, i))

def sum(a, b):
    return a + b

sum_list = []
for perm in perms:
    a = perm[0]
    b = perm[1]
    sum_list.append(sum(a, b))

# for l in sum_list:
#     print(l)

result = 0
for i in range(M):
    index_max = sum_list.index(max(sum_list))
    result += sum_list.pop(index_max)

print(result)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left


def main():
    def isOK(score):
        count = 0
        for a in reversed(A):
            border_score = score - a
            index = bleft(A, border_score)
            count += N - index
            if count >= M:
                return True
        return False

    N, M = map(int, input().split())
    A = sorted(map(int, input().split()))
    ans = 0

    ng = A[-1] + A[-1] + 1
    ok = A[0] + A[0]
    bleft = bisect_left

    while(abs(ok-ng) > 1):
        #print(ok, ng)
        mid = (ok+ng) // 2
        f = isOK(mid)
        if f:
            ok = mid
        else:
            ng = mid
        #print(f)
        #print(ok, ng)

    min_score = float('inf')
    count = 0
    for a in reversed(A):
        index = bleft(A, ok-a)
        if index < N:
            min_score = min(a+A[index], min_score)
            ans += sum(A[index:]) + (N-index) * a
            count += N-index
        else:
            break
    ans -= min_score * (count-M)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect
N, M = map(int, input().split())
A = list(map(int,input().split()))
A.sort()
B = []
for i in range(N):
  B.append(A[i]*2)
for i in range(N-1):
  for j in range(i+1,N):
    t = A[i]+A[j]
    idx = bisect.bisect_left(B, t)
    B.insert(idx, t)
    B.insert(idx, t)
B.reverse()
print(sum(B[:M]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N,M = map(int,input().split())
A = np.sort(list(map(int,input().split())))
ans = 0

xOK = A[0]*2
xNG = A[-1]*2 + 1
nx = 0
while xOK+1 < xNG:
    x = (xOK + xNG)//2
    nx = 0
    for a in A:
        nx += N-(np.searchsorted(A,x-a))
        if nx >= M:
            xOK = x
            break
    else:
        xNG = x

from itertools import accumulate
S=[0]+list(accumulate(A))

ans = 0
nnx = 0        
for a in A:
    nx = np.searchsorted(A,xOK-a,side='right')
    ans += a*(N-nx) + (S[N]-S[nx])
    nnx += (N-nx)
ans += xOK*(M-nnx)
        
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
n,m=map(int,input().split())
a=list(map(int,input().split()))
result=[sum([a[p[0]],a[p[1]]]) for p in list(itertools.product(range(n),range(n)))]
print(sum(sorted(result,reverse=True)[:m]))

Submission status: Time Limit Exceeded

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

def ins(ans,i):
  for j in range(N):
      n = bisect_left(ans, A[i]+A[j])
      if n != 0:
        ans = np.insert(ans, n, A[i]+A[j])[-M:]
  return ans

ans = [0]
for i in range(N):
  ans = ins(ans, i)

print(int(sum(ans)))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,M = list(map(int,input().split()))
A = list(map(int,input().split()))
A.sort()
 
ans = []
for i in range(N):
  ans = np.r_[ans,A[i] + np.array(A)]

ans.sort()
print(int(sum(ans[-M:])))

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
A=list(map(int, input().split()))
#リストAを小さい順に並べ替える
B=sorted(A, reverse=True)
C=[]
#握手の全パータンの数を算出
one_man =2*K
two_man =K*(K-1)
sum_shake=one_man+two_man
#全パータンの握手の幸福度を計算し、C配列に格納
for i in range(len(A)):
	for j in range(len(B)):
		C.append(B[i]+B[j])
D=sorted(C,reverse=True)
print(sum(D[:K]))

Submission status: Time Limit Exceeded

Solution code:
import bisect
 
N, M = map(int, input().split())
A = list(map(int, input().split()))
 
def cnt(a, m):
  cnt_tmp = 0
  for aa in a:
    bi = bisect.bisect_left(a, m - aa)
    #print(a, m, m - aa, bi)
    cnt_tmp += N - bi
  return cnt_tmp
 
A.sort()
 
l = 0
r = 10**10
 
while 1:
  mid = (l + r) // 2
  cnt_loop1 = cnt(A, mid)
  cnt_loop2 = cnt(A, mid+1)
  #print(mid, cnt_loop1, cnt_loop2)
  
  if cnt_loop1 >= M and cnt_loop2 < M:
    break
  if cnt_loop1 >= M:
    l = mid
  else:
    r = mid
#print(mid, cnt_loop1, cnt_loop2)
 
S = [0] * (N+1)
for i in range(1, N+1):
  S[i] = S[i-1]+A[i-1]
#print(S[N])
 
answer = 0
for aa in A:
  bi = bisect.bisect_left(A, mid - aa)
  answer += S[N] - S[bi] + (N - bi) * aa
print(answer-(cnt_loop1-M)*mid)

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

def cnt(a, m):
  cnt_tmp = 0
  for aa in a:
    bi = bisect.bisect_left(a, m - aa)
    #print(a, m, m - aa, bi)
    cnt_tmp += N - bi
  return cnt_tmp

A.sort()

l = 0
r = 10**16

while 1:
  mid = (l + r) // 2
  cnt_loop1 = cnt(A, mid)
  cnt_loop2 = cnt(A, mid+1)
  #print(mid, cnt_loop1, cnt_loop2)
  
  if cnt_loop1 >= M and cnt_loop2 < M:
    break
  if cnt_loop1 >= M:
    l = mid
  else:
    r = mid
#print(mid, cnt_loop1, cnt_loop2)

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

answer = 0
for aa in A:
  bi = bisect.bisect_left(A, mid - aa)
  answer += S[N] - S[bi] + (N - bi) * aa
print(answer-(cnt_loop1-M)*mid)

Submission status: Time Limit Exceeded

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

print(sum(sorted([sum(i) for i in itertools.product(A, repeat=2)])[::-1][:M]))

Submission status: Time Limit Exceeded

Solution code:
n, m = map(lambda x: int(x), input().split())
a = input().split()
a = [int(_) for _ in a]

tmp = []
for i in a:
  for j in a:
    tmp.append(i+j)
tmp.sort()
tmp.reverse()
print(sum(tmp[:m]))

Submission status: Time Limit Exceeded

Solution code:
import itertools

n, m = map(lambda x: int(x), input().split())
a = input().split()
a = [int(_) for _ in a]

p = itertools.product(a, a)
a = [_[0]+_[1] for _ in p]
a.sort()
a.reverse()
print(sum(a[:m]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, M = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
ans = 0

func = np.zeros(max(A)+1)
for a in A:
    func[-a-1] += 1

f = np.poly1d(func)**2
len_f = len(f.c)
left = M
#print(f)
#print(len(f.c))
for ind, i in enumerate(f.c):
    if(i>=1):
        ans += min(i, left)*(len_f-1-ind)
        left -= min(i, left)

    if(left == 0):
        break

print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left


def main():
    def isOK(score):
        count = 0
        for a in reversed(A):
            border_score = score - a
            index = bleft(A, border_score)
            count += N - index
            if count >= M:
                return True
        return False

    N, M = map(int, input().split())
    A = sorted(map(int, input().split()))
    ans = 0

    ng = A[-1] + A[-1] + 1
    ok = A[0] + A[0]
    bleft = bisect_left

    while(abs(ok-ng) > 1):
        #print(ok, ng)
        mid = (ok+ng) // 2
        f = isOK(mid)
        if f:
            ok = mid
        else:
            ng = mid
        #print(f)
        #print(ok, ng)

    min_score = float('inf')
    count = 0
    for a in A:
        index = bleft(A, ok-a)
        if index < N:
            min_score = min(a+A[index], min_score)
            ans += sum(A[index:]) + (N-index) * a
            count += N-index
    ans -= min_score * (count-M)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect


def main():
    def isOK(score):
        count = 0
        for a in reversed(A):
            border_score = score - a
            index = bleft(A, border_score)
            count += N - index
            if count >= M:
                return True
        return False

    N, M = map(int, input().split())
    A = sorted(map(int, input().split()))
    ans = 0

    ng = A[-1] + A[-1] + 1
    ok = A[0] + A[0]
    bleft = bisect.bisect_left

    while(abs(ok-ng) > 1):
        #print(ok, ng)
        mid = (ok+ng) // 2
        f = isOK(mid)
        if f:
            ok = mid
        else:
            ng = mid
        #print(f)
        #print(ok, ng)

    min_score = float('inf')
    count = 0
    for a in A:
        index = bleft(A, ok-a)
        if index < N:
            min_score = min(a+A[index], min_score)
            ans += sum(A[index:]) + (N-index) * a
            count += N-index
    ans -= min_score * (count-M)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect


def main():
    def isOK(score):
        count = 0
        for a in A:
            border_score = score - a
            index = bleft(A, border_score)
            count += N - index
        if count >= M:
            return True
        else:
            return False

    N, M = map(int, input().split())
    A = sorted(map(int, input().split()))
    ans = 0

    ng = A[-1] + A[-1] + 1
    ok = A[0] + A[0]
    bleft = bisect.bisect_left

    while(abs(ok-ng) > 1):
        #print(ok, ng)
        mid = (ok+ng) // 2
        f = isOK(mid)
        if f:
            ok = mid
        else:
            ng = mid
        #print(f)
        #print(ok, ng)

    min_score = float('inf')
    count = 0
    for a in A:
        index = bleft(A, ok-a)
        if index < N:
            min_score = min(a+A[index], min_score)
            ans += sum(A[index:]) + (N-index) * a
            count += N-index
    ans -= min_score * (count-M)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

item = []
for i in A:
    for j in A:
        k = i + j
        if len(item) >= M:
            if min(item) < k:
                item.append(k)
                item.remove(min(item))
            else:
                break
        else:
            item.append(k)

item.sort(reverse = True)
print(sum(item[:M]))

Submission status: Time Limit Exceeded

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

item = []
for i in A:
    for j in A:
        item.append(i+j)
item.sort(reverse = True)
print(sum(item[:M]))

Submission status: Time Limit Exceeded

Solution code:
import sys
N, M = map(int, input().split())
A = list(map(int, input().split()))
item = []
for i in A:
    for j in A:
        item.append(i+j)
item.sort(reverse = True)
print(sum(item[:M]))

Submission status: Time Limit Exceeded

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

ans = []
for a in A:
  ans = np.r_[ans,[a] + np.array(A)]
  #ans.extend([a] + np.array(A))
  
ans.sort()
print(int(sum(ans[-M:])))

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
N, M = list(map(int, input().split()))
An = list(map(int, input().split()))
sort_An = sorted(An)[::-1]
combinations = sorted([( x + y) for x in sort_An  for y in sort_An])[::-1]
print(sum(combinations[:M]))

Submission status: Time Limit Exceeded

Solution code:
N, M = list(map(int, input().split()))
An = list(map(int, input().split()))
sort_An = sorted(An)[::-1]
combinations = sorted([( x + y ,(i,j)) for i,x in enumerate(sort_An) for j,y in enumerate(sort_An)])[::-1]
print(sum([a for a , _ in combinations[:M]]))

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

ans = []
for n,a in enumerate(A[-M:]):
  ans = np.r_[ans,[a] + np.array(A)]
  ans.sort()

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

Submission status: Time Limit Exceeded

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

m = int(min(M,N))
ans = []
for n,a in enumerate(A[-M:]):
  if n>m:break
  #num = [a] + A
  #num = np.sort(num)[::-1]
  ans = np.r_[ans,[a] + np.array(A)]
  ans.sort()

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,M = list(map(int,input().split()))
A = list(map(int,input().split()))
A.sort()
 
ans = []
for a in A[-M:]:
  ans.extend([a]+np.array(A))
  
ans.sort()
print(int(sum(ans[-M:])))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin

input = stdin.buffer.readline

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

a.sort(reverse=True)

from heapq import *

q = []
heappush(q, [-(a[0] + a[0]), [0, 0]])
st = set()
ans = 0
while m:
    l, r = heappop(q)[1]
    if l == r:
        now = 1
    else:
        now = min(m, 2)
    ans += now * (a[l] + a[r])
    m -= now

    if l + 1 <= n - 1 and (min(l + 1, r), max(l + 1, r)) not in st:
        st.add((min(l + 1, r), max(l + 1, r)))
        heappush(q, [-(a[l + 1] + a[r]), [l + 1, r]])

    if r + 1 <= n - 1 and (min(l, r + 1), max(l, r + 1)) not in st:
        st.add((min(l, r + 1), max(l, r + 1)))
        heappush(q, [-(a[l] + a[r + 1]), [l, r + 1]])

    l = min(l, r) + 1
    if l <= n-1 and (l, l) not in st:
        st.add((l, l))
        heappush(q, [-(a[l] + a[l]), [l, l]])

print(ans)

Submission status: Time Limit Exceeded

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

tmp=input()
luc=[int(x) for x in tmp.split()]
rel=[]
for i in luc:
  for j in luc:
    rel.append(i+j)

rel.sort(reverse=True)
print(sum(rel[0:m]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numpy.fft import rfft, irfft
N,M = list(map(int,input().split()))
A = list(map(int,input().split()))
X = np.zeros(10**5+1)
l = 2*(10**5)+10
for i in range(N):
    X[A[i]] += 1
data = irfft(rfft(X, l)**2 )
num = 0
ans = 0
for i in range(len(data) -1 ,0,-1):
    if int(round(data[i])) != 0:
        if num + int(round(data[i])) >= M:
            ans += (M - num) * i
            break
        else:
            ans += int(round(data[i]))*i
            num += int(round(data[i]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numpy.fft import rfft, irfft
N,M = list(map(int,input().split()))
A = list(map(int,input().split()))
X = np.zeros(10**5+1)
l = 2*(10**5)+10
for i in range(N):
    X[A[i]] += 1
data = irfft(rfft(X, l) * rfft(X, l))
num = 0
ans = 0
for i in range(len(data) -1 ,0,-1):
    if int(round(data[i])) != 0:
        if num + int(round(data[i])) >= M:
            ans += (M - num) * i
            break
        else:
            ans += int(round(data[i]))*i
            num += int(round(data[i]))
print(ans)

Submission status: Time Limit Exceeded

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 = a[-1] * 2 + 1
    while - cor_v + inc_v > 1:
        bin_v = (cor_v + inc_v) // 2
        cost = 0
        #条件を満たすcostを全検索
        p = n
        for v in a:
            p = bisect.bisect_left(a, bin_v - v, 0, p)
            cost += n - p
            if cost > m:
                break
        #costが制約を満たすか
        if cost >= m:
            cor_v = bin_v
        else:
            inc_v = bin_v
    acm = [0] + list(itertools.accumulate(a))
    c = 0
    t = 0
    for v in a:
        p = bisect.bisect_left(a, cor_v - v)
        c += n - p
        t += acm[-1] - acm[p] + v * (n - p)
    print(t - (c - m) * cor_v)
    for i in range(10 ** 10):
      t += i


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

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 ** 20
    while - cor_v + inc_v > 1:
        bin_v = (cor_v + inc_v) // 2
        cost = 0
        #条件を満たすcostを全検索
        for v in a:
            cost += n - bisect.bisect_left(a, bin_v - v)
            if cost > m:
                break
        #costが制約を満たすか
        if cost >= m:
            cor_v = bin_v
        else:
            inc_v = bin_v
    acm = [0] + list(itertools.accumulate(a))
    c = 0
    t = 0
    for v in a:
        p = bisect.bisect_left(a, cor_v - v)
        c += n - p
        t += acm[-1] - acm[p] + v * (n - p)
    print(t - (c - m) * cor_v)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import heapq

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

hq=[]
for x in a:
    for y in a:
        heapq.heappush(hq, -(x+y))

ans=0
for i in range(m):
    ans+=heapq.heappop(hq)

print(-ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
ans, cnt = 0, 0
B = [A[0] + i for i in A]
C = [0] * N

def round():
	m = B.index(max(B))
	global ans
	global cnt
	if C[m] == m:
		ans += B[m]
		B[m] = 0
		cnt += 1
	elif M - cnt > 1:
		ans += B[m] * 2
		B[m] += A[C[m]+1] - A[C[m]]
		C[m] += 1
		cnt += 2
	else:
		ans += B[m]
		cnt += 1

while cnt < M:
	round()

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
ans = 0
B = [A[0] + i for i in A]
C = [0] * N
for i in range(M):
	m = B.index(max(B))
	ans += B[m]
	if C[m] < N - 1:
		B[m] += A[C[m]+1] - A[C[m]]
		C[m] += 1
	else:
		B[m] = 0
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect

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


happiness_list = [0]
# candidate_N_index = np.argsort(A)[int(M/2)+1]


for i in range(N):
    for j in range(N):
        if i+j>M:
            happiness_list=happiness_list[-M:]
        power = A[i]+A[j]
        insert_index = bisect.bisect_left(happiness_list,power)
        happiness_list.insert(insert_index,power)

ans = sum(happiness_list[-M:])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect

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


happiness_list = [0]

for i in range(N):
    for j in range(N):
        power = A[i]+A[j]
        insert_index = bisect.bisect_left(happiness_list,power)
        happiness_list.insert(insert_index,power)

ans = sum(happiness_list[-M:])
print(ans)

Submission status: Time Limit Exceeded

Solution code:

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


happiness_list = []
for i in range(N):
    for j in range(N):
        happiness_list.append(A[i]+A[j])

happiness_list = sorted(happiness_list,reverse=True)
ans = sum(happiness_list[:M])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
B = []
for i in range(N):
	for j in range(N):
		B += [A[i] + A[j]]
		if len(B) > M:
			B.remove(min(B))
print(sum(B))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import numpy as np
N, M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
A = np.sort(np.array(A))
def shake_hands(x):
    cnt = 0
    for i in A:
        X = np.searchsorted(A, x - i, side="left")
        cnt += N - X
    if cnt >= M:
        return 1
    return 0
left = 2
right = 10 ** 6
while True:
    m = (right + left) // 2
    if shake_hands(m) == 1 and shake_hands(m+1) == 0:
        maximum = m
        break
    elif shake_hands(m) == 0 and shake_hands(m-1) == 1:
        maximum = m - 1
        break
    elif shake_hands(m) == 1:
        left = m + 1
    else:
        right = m - 1
A_cumsum = np.array(np.cumsum(A))
ans = 0
cnt = 0
for i in A:
    a = np.searchsorted(A, (maximum + 1) - i, side="left")
    if a != 0:
        ans += A_cumsum[-1] - A_cumsum[a-1] 
        ans += (N - a) * i
        cnt += N - a
    else:
        ans += A_cumsum[-1]
        cnt += N
        ans += N * i
ans += maximum * (M - cnt)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
happy = A[0]*2
h, l = 0, 0
count = 1
point = {}
curr_list = {}
tmp_high = 0
while count < M:
    if h >= tmp_high:
        tmp_high += 1
        point[h+1] = h+1
        curr_list[h+1] = A[h+1]*2
    if l == N-1:
        del point[h]
        del curr_list[h]
    else:
        point[h] = l+1
        curr_list[h] = A[h]+A[l+1]
    tmp_key = max(curr_list, key=curr_list.get)
    h = tmp_key
    l = point[tmp_key]
    happy += A[h] + A[l]
    count += 1
    if not h == l and count < M:
        happy += A[h] + A[l]
        count += 1
print(happy)

Submission status: Time Limit Exceeded

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

x=[]
for i in range(n):
    for j in range(n):
        x.append(a[i]+a[j])
x.sort()
x.reverse()
ans=0
for i in range(m):
    ans+=x[i]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

A.sort()

A

def geXcount(X):
    return N - bisect.bisect_left(A, X)

L = 0
R = 10 ** 5
# flag = False
while R - L > 1:
    tar = (L + R) // 2
    count = 0
    for i in range(N):
        count += geXcount(tar - A[i])
    if count > M:
        L = tar
    elif count <= M:
        R = tar
# print(L, R, tar, count, M)
    

[[A[i] + A[j] for i in range(N)]  for j in range(N)]

# if count > M:
#     tar -= 1
#     count = 0
#     for i in range(N):
#         count += geXcount(tar - A[i])

count

temp = 0
B = [0] * (N + 1)
B[0] = 0
for i in range(N):
    B[i + 1] = B[i] + A[-i-1]

ans = 0
if M > count:
    maxp = 0
    # print(tar)
    for i in range(N):
        j = geXcount(tar - A[i])
        if j < N and maxp < A[-j-1] + A[i]:
            maxp = A[-j-1] + A[i]
        ans += B[j] + j * A[i]
    print(ans + (M-count) * maxp)
elif M < count:
    minp = 3 * (10 ** 5)
    for i in range(N):
        j = geXcount(tar - A[i])
        if j > 0 and minp > A[-j] + A[i]:
            minp = A[-j] + A[i]
        ans += B[j] + j * A[i]
    print(ans - (count - M) * minp)
else:
    for i in range(N):
        j = geXcount(tar - A[i])
        ans += B[j] + j * A[i]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
happy = A[0]*2
h, l = 0, 0
count = 1
point = {}
tmp_high = 0
while count < M:
    if h >= tmp_high:
        tmp_high += 1
        point[h+1] = h+1
    if l == N-1:
        del point[h]
    else:
        point[h] = l+1
    tmp = 0
    for key,val in point.items():
        if tmp <= A[key]+A[val]:
            tmp = A[key]+A[val]
            tmp_key = key
    h = tmp_key
    l = point[tmp_key]
    happy += A[h] + A[l]
    count += 1
    if not h == l and count < M:
        happy += A[h] + A[l]
        count += 1
print(happy)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
happy = A[0]*2
h, l = 0, 0
count = 1
point = {}
for i in range(N):
    point[i] = i
while count < M:
    if l == N-1:
        del point[h]
    else:
        point[h] = l+1
    tmp_high = 0
    for key,val in point.items():
        if tmp_high <= A[key]+A[val]:
            tmp_high = A[key]+A[val]
            tmp_key = key
    h = tmp_key
    l = point[tmp_key]
    happy += A[h] + A[l]
    count += 1
    if not h == l and count < M:
        happy += A[h] + A[l]
        count += 1
print(happy)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
ans = 0
A.sort(reverse=True)
sum_list = []
for a in A[:M]:
    for b in A[:M]:
        sum_list.append(a+b)
sum_list.sort(reverse=True)
ans = sum(sum_list[:M])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import copy

def check(a, b, bar):
    sm = 0
    cnt = 0
    n = len(a)
    for x in a:
        i = bisect.bisect_left(a, bar - x)
        if i == n:
            continue

        cnt += n - i
        sm += b[i] + x * (n-i)
        
    return cnt, sm

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

b = copy.deepcopy(a)
for i,_ in enumerate(b[:-1]):
    b[n-i-2] += b[n-i-1]
    
left = 0
right = b[0] * 2

while right - left > 1:
    middle = ( right + left ) // 2    
    if check(a, b, middle)[0] < m:
        right = middle
    else:
        left = middle
             
print(check(a, b, left)[1] - left * (check(a, b, left)[0]-m) )

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
import numpy as np

N, M, *A = map(int, open(0).read().split())
A.sort()


def calc(t):
    cnt = 0
    for ai in A:
        cnt += N - bisect_left(A, t - ai)
    if M <= cnt:
        return True
    else:
        return False


def solve():
    left, right = 0, 2 * 10 ** 5 + 1
    while 1 < right - left:
        mid = (left + right) // 2
        if calc(mid):
            left = mid
        else:
            right = mid
    
    sum_A = [0 for _ in range(N)]
    for i in range(N):
        sum_A[i] = np.cumsum(A[i:])[-1]
    
    ans = 0
    add_cnt = 0
    for ai in A:
        index = bisect_left(A, left - ai)
        if index == N:
            continue
        add_cnt += N - index
        ans += (N - index) * ai + sum_A[index]
    ans -= left * (add_cnt - M)
    print(ans)


if __name__ == '__main__':
    solve()