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:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
#show_flg=True

ans=0

n,m=LI()
a=sorted(LI())
ra=a[::-1]
##show(a,ra)

def Bigger(x,M): # x以上が M 個以上あるか
    cnt=0
    for i in range(n):
        y=x-ra[i]
        c=bisect.bisect(a,y-1)
        cnt+=n-c
##        show(x,a[i],y,cnt)
        if cnt>=M:
            return True
    return False

# function to check if x satisfies the condition
def check(x):
    if x==condition:
        rt=True
    else:
        rt=False
    return rt

# initial value
ng=1+a[-1]+a[-1]
ok=-1

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

mean=ok
##show('ok=',ok,m)
# [ ok | ng ] is the boundary of the condition

##show(Bigger(67,3))

choice=0
for i in range(n):
    num=n-bisect.bisect(a,mean-a[i]-1)
    choice+=num
    ans+=num*a[i]*2
##    show('i,a[i],num,choice',i,a[i],num,choice)
##show('ans=')
#print(ans)
print(ans-mean*(choice-m))

z=[]
for i in range(n):
    for j in range(n):
        heappush(z,(-a[i]-a[j],i,j,a[i],a[j]))
for i in range(len(z)):
    x=heappop(z)
##    show(x)
    #if i<m:ans+=-x[0]
#        show(ans,zzz)


#print(ans)

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
a = list(map(int, input().split()))
 
points = sorted([ax + ay for ax in a for ay in a], reverse=True)
 
print(sum(points[0:m]))

Submission status: Time Limit Exceeded

Solution code:
import heapq, math
n,m = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
a.sort(reverse=True)
heap = []
temp = min(m//n,n-1)
for i in range(n):
    for k in range(n):
        cur = a[i] + a[k]
        if cur < a[temp]:
            break
        heapq.heappush(heap,-(a[i] + a[k]))
ans = 0
for _ in range(m):
    if len(heap) >= 1:
        ans += heapq.heappop(heap)
print(-ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
N,M=map(int,input().split())
A=list(map(int,input().split()))
H = [a + b for (a, b) in list(itertools.product(A, A))]
H.sort(reverse=True)
print(sum(H[:M]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
m=int(input().split()[1])
a = input()
a = a.split()
b = list(np.concatenate([int(n) + np.array([int(m) for m in a]) for n in a]))
b.sort(reverse=True)
x = sum(b[:m])
print(x)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
a = list(map(int, input().split()))
pow = []
res = 0
for i in range(n):
    for j in range(n):
        pow.append(a[i] + a[j])
pow.sort()
pow = pow[::-1]
for i in range(m):
    res += pow[i]
print(res)

Submission status: Time Limit Exceeded

Solution code:
import itertools

def multi_int_input():
    return map(int, input().split())

N, M = multi_int_input()
a_list = list(multi_int_input())

result = list(itertools.product(a_list, a_list))
result = sorted(result, key=lambda x: x[0]+x[1], reverse=True)
result = [x[0] + x[1] for x in result[:M]]
print(sum(result))

Submission status: Time Limit Exceeded

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

ans = 0
cnt = 0
index = 0

from itertools import combinations
C = combinations(A, 2)
D = [x + x for x in A]

for x, y in C:
    D.extend([(x + y), (x + y)])

D = sorted(D, reverse=True)

print(sum(D[:M]))

Submission status: Time Limit Exceeded

Solution code:
import itertools

N,M = map(lambda x: int(x),input().split())
A = list(map(lambda x: int(x),input().split()))
pro = itertools.product(A, repeat=2)
lst = list(map(lambda x:x[0]+x[1],pro))
lst.sort(reverse=True)
#print(lst)
print(sum(lst[:M]))

Submission status: Time Limit Exceeded

Solution code:
N, M = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]

# sa = sorted(A)[::-1]

da = []

cnt = 0

for i in range(N):
    for j in range(N):
        # if cnt > M:
        #     break
        da.append(A[i] + A[j])
        cnt += 1


sa = sorted(da)[::-1]

# print(N)
# print(M)
# print(A)

print(sum(sa[:M]))

Submission status: Time Limit Exceeded

Solution code:
import heapq

N,M = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]

h = []
heapq.heapify(h)

for i in range(N):
    for j in range(N):
        heapq.heappush(h,-A[i]-A[j])


x = 0
for i in range(M):
    x -= heapq.heappop(h)
        
print(x)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
from itertools import product

n, m = map(int, input().split())
a = list(reversed(sorted(list(map(int, input().split())))))
c = len(a)
i, j = 0, 0

li = [sum(x) for x in product(a, a)]
li.sort(reverse=True)
print(sum(li[:m]))

Submission status: Time Limit Exceeded

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

lis = []
for i in range(n-1):
    for j in range(i+1,n):
        c = a[i]+a[j]
        lis.append(c)
lis.sort()
lis.reverse()
temp = lis[:m//2]*2
for i in range(n):
    temp.append(2*a[i])
temp.sort()
temp.reverse()
ans = temp[:m]
print(sum(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys, math
def input():
    return sys.stdin.readline()[:-1]
from itertools import permutations, combinations
from collections import defaultdict

sys.setrecursionlimit(10**7)
N, M = map(int, input().split())
A = list(map(int, input().split()))
#A.sort(reverse=True)

B = []
for i in range(N):
    for j in range(i, N):
        if i==j:
            B.append(A[i]+A[j])
        else:
            B.append(A[i]+A[j])
            B.append(A[i]+A[j])

B.sort(reverse=True)

print(sum(B[:M]))

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
hslist = list(map(int,input().split()))
hslist.sort(reverse=True)
happylist = []

for i in range(n):
    for j in range(i,n):
        if i == j:
            happylist.append(hslist[i]+hslist[j])
        else:
            happylist.append(hslist[i]+hslist[j])
            happylist.append(hslist[i]+hslist[j])

happylist.sort(reverse=True)

print(sum(happylist[0:m]))

Submission status: Time Limit Exceeded

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

a.sort(reverse = True)
score = []

for i in range(n):
	for j in range(n):
		score.append(a[i] + a[j])

score.sort(reverse = True)

cnt = 0
for i in range(m):
	cnt += score[i]
print(cnt)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

lr = []

for i in range(n):
    for j in range(n):
        lr.append(a[i]+a[j])
lr.sort()

print(sum(lr[-m:]))

Submission status: Time Limit Exceeded

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

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split())) # applies to numbers only
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N, M = rl()
A = np.array(rl())

B = []
for a in A:
    B.extend(A + a)
B.sort(reverse=True)

answer = sum(B[:M])
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import heapq, copy

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

d = []
heapq.heappush(d, (-(A[0]+B[0]), 0, 0))
xy_set = set((0, 0))
count = 0
ans = 0

while count < M:
    tmp, x, y = heapq.heappop(d)
    if x == y or count + 1 == M:
        ans += -tmp
        count += 1
    else:
        ans += -tmp * 2
        count += 2
    if (x+1, y) not in xy_set and (y, x+1) not in xy_set and x+1 <= N-1:
        heapq.heappush(d, (-(A[x+1]+B[y]), x+1, y))
        xy_set.add((x+1, y))
    if (x, y+1) not in xy_set and (y+1, x) not in xy_set and y+1 <= N-1:
        heapq.heappush(d, (-(A[x]+B[y+1]), x, y+1))
        xy_set.add((x, y+1))

print(ans)

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(reverse=True)
print(sum(x[0:m]))

Submission status: Time Limit Exceeded

Solution code:
import itertools
n,m = map(lambda x: int(x),input().split())
a = list(map(lambda x: int(x),input().split()))
ans = []
for i,j in list(itertools.product([int(x) for x in range(n)], repeat=2)) :
    ans.append(a[i]+a[j])
ans = sorted(ans, reverse = True)
print(sum(ans[:m]))

Submission status: Time Limit Exceeded

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

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

ans = []
for x in range(N):
    for y in range(N):
        ans.append(A[x] + A[y])

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

Submission status: Time Limit Exceeded

Solution code:

# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline


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

a.sort(reverse=True)

from heapq import *

ans = 0
q = []
cc = 10**12
c = 10**6

heappush(q,(-2*a[0]*cc))


num = 0
while num < m:
    v = heappop(q)
    v = -v
    v,i,j = v//cc, (v%cc)//c, v%c

    ans += v
    num += 1
    if i != j:
        if num < m:
            num += 1
            ans += v
        else:
            break
        
    #print(v,i,j,num)
    if j == 0 and i < n-1:
        
        heappush(q,-(a[i+1]+a[j])*cc-(i+1)*c-j)
    if i > j:
        heappush(q,-(a[i]+a[j+1])*cc-i*c-(j+1))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left as bl
from itertools import accumulate as ac
n,m=map(int,input().split())
a=sorted(list(map(int,input().split())))
s=[0]+list(ac(a[::-1]))
l,r=2*a[-1]*(n**2)+1,0
while l-r>1:
    t=(l+r)//2
    p=0
    for i in range(n):
        x=bl(a,t-a[i])
        p+=n-x
    if p<m:
        l=t
    else:
        r=t
c,d=0,0
w=0
for i in range(n):
    g=bl(a,r-a[i])
    x=n-g
    c+=s[x]+x*a[i]
    w+=x
print(c-r*max(0,(w-m)))

Submission status: Time Limit Exceeded

Solution code:
import heapq

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

A = sorted(A, reverse=True)

flag = [[False for _ in range(N)] for _ in range(N)]

ans = 0

a_heap = []
heapq.heapify(a_heap)
heapq.heappush(a_heap, (- A[0] - A[0], 0, 0))
flag[0][0] = True

for _ in range(M):
    score, i, j = heapq.heappop(a_heap)
    ans += -score
    if i + 1 < N and flag[i + 1][j] == False:
        flag[i + 1][j] = True
        heapq.heappush(a_heap, (- A[i + 1] - A[j], i + 1, j))
    if j + 1 < N and flag[i][j + 1] == False:
        flag[i][j + 1] = True
        heapq.heappush(a_heap, (- A[i] - A[j + 1], i, j + 1))

print(ans)

Submission status: Time Limit Exceeded

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

c = [ai + aj for ai in A for aj in A]
c.sort()

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

Submission status: Time Limit Exceeded

Solution code:
import sys, math
def input():
    return sys.stdin.readline()[:-1]
from itertools import permutations, combinations
from collections import defaultdict

sys.setrecursionlimit(10**7)
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)

B = []
for a1 in A:
    for a2 in A:
        B.append(a1+a2)
B.sort(reverse=True)

print(sum(B[:M]))

Submission status: Time Limit Exceeded

Solution code:
import heapq
n,m = map(int,input().split())
a = list(map(int,input().split()))
pq = []
a.sort()
n = len(a)
ans = 0
for i in range(n):
    if i == 0:
        pq.append([-1*a[i]*2,-1])
    else:
        pq.append([-1*a[i]*2,-1])
        pq.append([-1*(a[i]+a[i-1]),i-1])
count = 0
heapq.heapify(pq)
while count < m:
    b,c = heapq.heappop(pq)
    if c == -1:
        ans += -1*b
        count += 1
    else:
        ans += -1*b*2
        count += 2
        if c > 0:
            heapq.heappush(pq,[b+a[c]-a[c-1],c-1])
if count > m:
    ans += b
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

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

N,M=two_int()
A=many_int()

min_i=0
for i in range(1,N+1):
    if i**2-i >=M:
        min_i=i
        break
if min_i==0:
    min_i=N

import itertools

AA=sorted(A,reverse=True)[:2*min_i]



sums = [sum(i) for i in itertools.product(AA, AA)]

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

Submission status: Time Limit Exceeded

Solution code:
import heapq

N,M=map(int,input().split())
A=list(map(int,input().split()))
H=[]
heapq.heapify(H)
for a in A:
    for b in A:
        heapq.heappush(H, (a+b) * -1)

ans = 0
for i in range(M):
    ans += heapq.heappop(H)*(-1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import heapq

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

# print(list(itertools.product(A, repeat=2)))

sum_list = [-sum(x_y) for x_y in itertools.product(A, repeat=2)]

heapq.heapify(sum_list)

point = 0
for i in range(M):
    point -= heapq.heappop(sum_list)

print(point)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left

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

a.sort(reverse=True)
b = list(reversed(a))

rs = [0] * n
rs[0] = a[0]
for i, x in enumerate(a[1:]):
    rs[i+1] = rs[i] + x

L = 0
H = sum(a) ** 2 + 1

#print(b)

while H - L > 1:
    #print(L, H)
    M = (L + H) // 2
    count = 0
    for x in a:
       count += n - bisect_left(b, M - x)
    #print(L, H, count)
    if count == m:
        L = M
        break
    elif count > m:
        L = M
    else:
        H = M

ans = 0
count = 0
for x in a:
    c = n - 1 -  bisect_left(b, L - x)
    count += c + 1
    if c >= 0:
        ans += rs[c] + x * (c+1)

#print(L, count - m)

print(ans - (count-m) * L)

Submission status: Time Limit Exceeded

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

b = []
for aa in a:
	b.append(aa*2)
for i in range(n):
	for j in range(i+1, n):
		b.append(a[i] + a[j])
		b.append(a[i] + a[j])
b.sort(reverse = True)

happiness = 0
for i in range(m):
	happiness += b[i]
print(happiness)

Submission status: Time Limit Exceeded

Solution code:
N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
b = []
for i in range(N-1):
    for j in range(i+1, N):
        b.append([A[i]+A[j],2])
b.extend([[A[i]*2,1] for i in range(N)])
b = sorted(b, key=lambda x:-x[0])

ans = 0
while M!=0:
    ans+=b[0][0]
    b[0][1]-=1
    M-=1
    if b[0][1]==0:
        b = b[1:]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import heapq

INF = float("inf")


def solve(N: int, M: int, A: "List[int]"):
    A.sort()
    # print(A)
    heap = [(-2*a, i, i) for i, a in enumerate(A)]
    heapq.heapify(heap)

    ans = 0
    while M > 0:
        score, i, j = heapq.heappop(heap)
        # print(-score, (A[i], A[j]))
        if i == j:
            ans += -score
            M -= 1
        elif i != j and M >= 2:
            ans += -2*score
            M -= 2
        else:
            ans -= score
            M -= 1

        if j != 0:
            heapq.heappush(heap, (-(A[i]+A[j-1]), i, j-1))
    print(ans)
    return


def main():

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import heapq


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

idx_dict = {}
for i in range(n):
    idx_dict[i] = i+1

ans = [A[i]+A[i] for i in range(n)]
candidates = [[-(A[i]+A[i+1]), i] for i in range(n-1)]
heapq.heapify(candidates)

for i in range(m//2):
    if not candidates:
        break
    num, idx = heapq.heappop(candidates)
    ans.append(-num)
    ans.append(-num)
    idx_dict[idx] += 1
    new_pair = idx_dict[idx]
    if new_pair >= n:
        continue
    candidate = A[idx] + A[new_pair]
    heapq.heappush(candidates, [-candidate, idx])

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

Submission status: Time Limit Exceeded

Solution code:
import heapq

N,M = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]

h = []
heapq.heapify(h)

for i in range(N):
    for j in range(N):
        heapq.heappush(h,(-A[i]-A[j],1))


x = 0
for i in range(M):
    a = heapq.heappop(h)
    #print(a)
    x -= a[0]
        
print(x)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
hslist = list(map(int,input().split()))
hslist.sort(reverse=True)
score = 0
happylist = []

for i in range(n):
    for j in range(n):
        happylist.append(hslist[i]+hslist[j])
happylist.sort(reverse=True)
for i in range(m):
    score += happylist[i]
print(score)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop as hpop
from heapq import heappush as hpush
n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort(reverse=1)
a+=[-99999999999999]
h=[]
for i in range(n):hpush(h,[-a[i]*2,i])
count=m
ans=0
while count!=0:
  x,i=hpop(h)
  x=-x
  c=min(count,1+(x!=a[i]*2))
  count-=c
  ans+=c*x
  x-=a[i]
  x+=a[i+1]
  i+=1
  hpush(h,[-x,i])
print(ans)

Submission status: Time Limit Exceeded

Solution code:

N,M=[int(c) for c in input().split()]
A=[int(c) for c in input().split()]
B=sorted([x+y for x in A for y in A],reverse=True)

print(sum(B[0:M]))

Submission status: Time Limit Exceeded

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

happy=[]
for i in range(nm[0]):
    for j in range(i+1):
        aij=a[i]+a[j]
        happy.append(aij)
        if i!=j:
            happy.append(aij)
happy.sort(reverse=True)
ans=sum(happy[:nm[1]])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
import math
import operator as op
from functools import reduce
import numpy as np
import math
import bisect
import heapq


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


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


def get_inputs(cast_func=None):
    if cast_func is None:
        return input().split()
    else:
        return list(map(cast_func, input().split()))


def get_input(cast_func=None):
    if cast_func is None:
        return input()
    else:
        return cast_func(input())


def is_prime(n):
    if n == 1:
        return False
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            return False
    return True


def main():
    N, M = get_inputs(int)
    A = get_inputs(int)

    A.sort(reverse=True)

    max_heap = []
    heapq.heapify(max_heap)
    visited = set()

    cnt = 0
    score = 0
    heapq.heappush(max_heap, (-(A[0] + A[0]), (0, 0)))
    while cnt < M:
        neg_score, (i, j) = heapq.heappop(max_heap)
        if (i, j) in visited:
            continue
        visited.add((i, j))
        score += -neg_score
        cnt += 1

        if i + 1 < N and j < N and (i + 1, j) not in visited:
            heapq.heappush(max_heap, (-(A[i+1] + A[j]), (i + 1, j)))

        if i < N and j + 1 < N and (i, j + 1) not in visited:
            heapq.heappush(max_heap, (-(A[i] + A[j + 1]), (i, j + 1)))

    print(score)
    # A.sort(reverse=True)

    # ans = 0
    # cnt = 0
    # for k in range(2 * (N-1)+1):
    #     B = []
    #     for i in range(k+1):
    #         j = k-i
    #         if not (i >= 0 and i < N and j >= 0 and j < N):
    #             continue
    #         B.append(A[i] + A[j])

    #     B.sort(reverse=True)
    #     for b in B:
    #         ans += b
    #         cnt += 1
    #         if cnt >= M:
    #             print(ans)
    #             return

    # print(ans)
    # return


# def main():
    # A, B, K = get_inputs(int)
    # if A >= K:
    #     print(A-K, B)
    # elif A + B >= K:
    #     print(0, B - (K-A))
    # else:
    #     print(0, 0)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import heapq

N,M=map(int,input().split())
A=list(map(int,input().split()))
H=[]
for a in A:
    for b in A:
        H.append((a+b) * -1)

heapq.heapify(H)
ans = 0
for i in range(M):
    ans += heapq.heappop(H)*(-1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = [int(x) for x in input().split()]
A = sorted([int(x) for x in input().split()])
import heapq
h = []
for i in range(N):
    for j in range(N):
        heapq.heappush(h, -(A[i]+A[j]))
ans = 0
for i in range(M):
    ans -= heapq.heappop(h)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 1 << 100
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, m = LI()
A = sorted(LI(), reverse=True)
cnt = 0
hq = [(-A[i] - A[0], i, 0) for i in range(n)]
heapify(hq)
for i in range(m):
    x, l, r = heappop(hq)
    cnt -= x
    if r != n - 1:
        heappush(hq, (-A[l] - A[r + 1], l, r + 1))

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product

n, m = map(int, input().split())
a = list(reversed(sorted(list(map(int, input().split())))))
c = len(a)
ans = 0
i, j = 0, 0

li = list(product(a, a))
li.sort(key=lambda x: sum(x), reverse=True)
for i in range(m):
    ans += sum(li[i])
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:


N,M=[int(c) for c in input().split()]
A=[int(c) for c in input().split()]
B=sorted([x+y for x in A for y in A],reverse=True)
ans=0
for i in range(M):
  ans+=B[i]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

# print(list(itertools.product(A, repeat=2)))

sum_list = [sum(x_y) for x_y in itertools.product(A, repeat=2)]

sum_list.sort(reverse=True)

print(sum(sum_list[:M]))

Submission status: Time Limit Exceeded

Solution code:
n, m = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
a.sort()
b = [0]
for i in reversed(a):
    b.append(b[-1] + i)


def search(i):
    if a[-1] < i:
        return 0
    mi = 0
    ma = n - 1
    while mi != ma:
        m = (mi + ma) // 2
        if a[m] >= i:
            ma = m
        else:
            mi = m + 1
    return n-mi

def countmax(i):
    ans = 0
    for j in a:
        ans += search(i - j)
    return ans

mi = 0
ma = a[-1] * 2
while mi != ma:
    md = (mi + ma) // 2 + 1
    #print(md, countmax(md))
    if countmax(md) > m:
        mi = md
    else:
        ma = md - 1

ans = 0
for j in a:
    i = search(mi + 1 - j)
    ans+=b[i]+i*j
ans += (m-countmax(mi+1))*mi
print(ans)

Submission status: Time Limit Exceeded

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

import itertools

b = []
for pro in itertools.product(a, repeat=2):
  x, y = pro
  b.append(x + y)

b.sort()
b.reverse()

print(sum(b[:m]))

Submission status: Time Limit Exceeded

Solution code:
import heapq
import itertools

N,M=[int(i) for i in input().split(" ")]

A=[int(i) for i in input().split(" ")]
A=sorted(A,reverse=True)
A=A[:M//2+10]
scores=[]
heapq.heapify(scores)
for pair in itertools.product(A, repeat=2):
    score=(pair[0]+pair[1])*(-1)
    heapq.heappush(scores,score)


retval=0
for i in range(M):
    retval+=heapq.heappop(scores)

print(retval*(-1))

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
a = list(map(int,input().split()))
a.sort(reverse=1)
# print(a)
ans = []
for i in a:
    for j in a:
        ans.append(i+j)
ans.sort(reverse=1)
print(sum(ans[0:m]))

Submission status: Time Limit Exceeded

Solution code:
if __name__ == "__main__":
	N, M = map(int, input().split())
	A = list(map(int, input().split()))
	pairs = []
	for i in range(N):
		for j in range(N):
			pairs.append(A[i] + A[j])
	pairs.sort(reverse=True)
	ans = 0
	for k in range(M):
		ans += pairs[k]
	print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq

n, m = map(int, input().split())
a = [int(x) for x in input().split()]
a.sort(reverse=True)
key = []
judge = [[False]*n for i in range(n)]

heapq.heappush(key, [-(a[0]+a[0]), 0, 0])
judge[0][0] = True

ans = 0
for i in range(m):
    p = heapq.heappop(key)
    p1, p2, p3 = p[0], p[1], p[2]
    ans += (-p1)
    if p2 < n-1 and judge[p2+1][p3] == False:
        heapq.heappush(key, [-(a[p2+1]+a[p3]), p2+1, p3])
        judge[p2+1][p3] = True
    if p3 < n-1 and judge[p2][p3+1] == False:
        heapq.heappush(key, [-(a[p2]+a[p3+1]), p2, p3+1])
        judge[p2][p3+1] = True

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq

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

A = sorted(A)

pairs = []

for i in range(N):
    for j in range(N):
        pairs.append(-(A[i] + A[j]))

heapq.heapify(pairs)

ans = 0
for i in range(M):
    ans += -(pairs[0])
    heapq.heappop(pairs)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from heapq import *

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
pq = []
heappush(pq, (-A[0]*2, 0, 0))
ans = 0

for _ in range(M):
    s, i, j = heappop(pq)
    #print(s, i, j)
    s *= -1
    ans += s
    
    if i==j:
        if j<N-1:
            heappush(pq, (-A[i]-A[j+1], i, j+1))
    elif i<j:
        if i+1==j:
            heappush(pq, (-A[i+1]-A[j], i+1, j))
        
        if j<N-1:
            heappush(pq, (-A[i]-A[j+1], i, j+1))
            
        heappush(pq, (-A[i]-A[j], j, i))

print(ans)

Submission status: Time Limit Exceeded

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

points = sorted([ax + ay for ax in a for ay in a], reverse=True)

print(sum(points[0:m]))