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

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


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

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

Submission status: Time Limit Exceeded

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

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


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

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

Submission status: Time Limit Exceeded

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

# samePower = [2 * i for i in power]
diffPower = []
for i in range(n):
    for j in range(n):
        #if i == j:
        #    continue
        pw = power[i] + power[j]
        diffPower.append(pw)
sortedPower = sorted(diffPower)
happiness = 0
for i in range(1, m + 1):
    happiness += sortedPower[-i]
print(happiness)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

a = []
for item in A:
    a.append(item)

Amat = []
for i in range(N):
    for j in range(N):
        Amat.append(a[i] + a[j])

HP = 0

for i in range(M):
    Amatmax = max(Amat)
    HP += Amatmax
    Amat.remove(Amatmax)

print(HP)

Submission status: Time Limit Exceeded

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

a = []
for item in A:
    a.append(item)

Amat = []
for i in range(N):
    for j in range(N):
        Amat.append(a[i] + a[j])

sAmat = sorted(Amat, reverse=True)

HP = 0

for i in range(M):
    Amatmax = max(Amat)
    HP += Amatmax
    Amat.remove(Amatmax)

print(HP)

Submission status: Time Limit Exceeded

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

a = []
for item in A:
    a.append(item)

Amat = []
for i in range(N):
    for j in range(N):
        Amat.append(a[i] + a[j])

sAmat = sorted(Amat, reverse=True)

HP = 0

for i in range(M):
    HP += sAmat[i]

print(HP)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
A=[-int(i) for i in input().split()]
A.sort()
import heapq
L=[]
for i in range(n):
    for j in range(n):
        heapq.heappush(L,A[i]+A[j])
sum_=0
for _ in range(m):
    sum_ += -heapq.heappop(L)
print(sum_)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product


def resolve():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort(reverse=True)
    aa = list(product(a[:], repeat=2))
    print(sum(sorted(list(map(lambda x: x[0] + x[1], aa)), reverse=True)[:m]))
    
resolve()

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
a=list(map(int,input().split()))
b=[0 for i in range(n**2)]
k=0
ans=0
a.sort(reverse=1)
for x in a:
  for y in a:
    b[k]=x+y
    k+=1
b.sort(reverse=1)
b=b[:m]
for x in b:
  ans+=x
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product


def resolve():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort(reverse=True)
    aa = list(product(a[:], repeat=2))
    print(sum(sorted(list(map(lambda x: x[0] + x[1], aa)), reverse=True)[:m]))
   
resolve()

Submission status: Time Limit Exceeded

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

Solution code:
import bisect
import sys
from itertools import accumulate
input = sys.stdin.readline
def hsnum(ls,x,n):
    num = 0
    for i in range(n):
        y = x-ls[i]
        num += n-bisect.bisect_left(ls,y)
    return num
n,m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
suma = [0]+list(accumulate(a))
lx = 0
rx = 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)

Submission status: Time Limit Exceeded

Solution code:
import heapq
N,M=[int(s) for s in input().split()] #人数、回数
ls=[-int(s) for s in input().split()]
ls=sorted(ls)
check=[[False]*N for _ in range(N)]
check[0][0]=1
Q=[[ls[0]+ls[0],0,0]]
heapq.heapify(Q)
ans=0
while M>0:
  a,b,c=heapq.heappop(Q) #b<=cとする
#  print(a,b,c)
  if b==c:
    M-=1
    ans+=a
    if c<N-1 and check[b][c+1]==False:
      check[b][c+1]=True
      heapq.heappush(Q,[ls[b]+ls[c+1],b,c+1])
  else:
    M-=2
    ans+=2*a
    if c==N-1:
      if check[b+1][c]==False:
        check[b+1][c]=True
        heapq.heappush(Q,[ls[b+1]+ls[c],b+1,c])  
    else:
      if check[b][c+1]==False:
        check[b][c+1]=True
        heapq.heappush(Q,[ls[b]+ls[c+1],b,c+1])
      if check[b+1][c]==False:
        check[b+1][c]=True
        heapq.heappush(Q,[ls[b+1]+ls[c],b+1,c])  
if M==-1:
  ans-=a
print(-ans)
#print(Q)

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import factorial
from fractions import Fraction
import heapq, bisect, fractions
import math
import itertools
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: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
#import numpy
N,M=[int(s) for s in input().split()] #人数、回数
ls=[int(s) for s in input().split()]
ls=sorted(ls,reverse=True)
#lssum=numpy.cumsum(ls)
ls2=[]
for a in range(N):
  K=min([M//(a+1)+1,N])
  for b in range(K):
    ls2.append(ls[a]+ls[b])
print(sum(sorted(ls2,reverse=True)[:M]))

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

ruiseki = [0]*(n+1)
for i in range(n):
    ruiseki[i+1] = ruiseki[i] + a[i]

def solve(min_power):
    ans = 0
    for pos in range(n):
        tmp = min_power - a[pos]
        next_pos = bisect.bisect_left(a[pos:], tmp)
        times = n - pos - next_pos
        if times == n - pos:
            ans += 2 * (times - 1) + 1 
        else:
            ans += 2 * times
    if ans >= m:
        return True
    else:
        return False

ok = 0
ng = 10** 9
while abs(ok - ng) > 1:
    mid =  (ok + ng) // 2 
    if solve(mid):
        ok = mid
    else:
        ng = mid

cnt = 0
ans = 0

for pos in range(n):
    tmp = ok - a[pos]
    next_pos = bisect.bisect_left(a[pos:], tmp)
    times = n - pos - next_pos
    if times == n - pos:
        cnt += 2 * (times - 1) + 1 
        ans += 2 * (ruiseki[n] - ruiseki[n-times+1] + (times-1)*a[pos]) + 2*a[pos]
    else:
        cnt += 2 * times
        ans += 2 * (ruiseki[n] - ruiseki[n-times] + (times)*a[pos])

print(ans - (cnt-m)*ok)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
#!/Library/Frameworks/Python.framework/Versions/3.5/bin/python3

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

ads = []
for i in range(len(a)):
    for j in range(i, len(a)):
        ads.append(a[i] + a[j])
        if i != j:
            ads.append(a[j] + a[i])
ads.sort(reverse=True)
ans = 0
for i in range(m):
    ans += ads[i]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq
import bisect
n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
s=[0]*(n+1)

for i in range(n):
    s[i+1]=s[i]+a[i]
def test(x):
    count=0
    for i in range(n):
        idx=bisect.bisect_left(a,x-a[i])
        if i>=idx:
            count+=(i-idx)*2+1
    return count


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

Submission status: Time Limit Exceeded

Solution code:
def convolve(a, b):
    def fft(f):
        d = n // 2
        v = w
        while d >= 1:
            u = 1
            for i in range(d):
                for j in range(i, n, 2*d):
                    f[j], f[j+d] = (f[j] + f[j+d]) % p, u * (f[j] - f[j+d]) % p
                u = u * v % p
            v = v * v % p
            d //= 2
 
    def ifft(f):
        d = 1
        while d < n:
            v = pow(invw, n // (2 * d), p)
            u = 1
            for i in range(d):
                for j in range(i, n, 2*d):
                    f[j+d] *= u
                    f[j], f[j+d] = (f[j] + f[j+d]) % p, (f[j] - f[j+d]) % p
                u = u * v % p
            d *= 2
 
    p, g = 10871635969, 7
    n0, n1 = len(a), len(b)
    n = 1 << (max(n0, n1) - 1).bit_length() + 1
    a = a + [0] * (n-n0)
    b = b + [0] * (n-n1)
    w = pow(g, (p - 1) // n, p)
    invw = pow(w, p-2, p)
    fft(a), fft(b)
    for i in range(n):
        a[i] = a[i] * b[i] % p
    ifft(a)
    invn = pow(n, p - 2, p)
    return [a[i] * invn % p for i in range(n0 + n1 - 1)]

N, M = map(int, input().split())
A = [int(a) for a in input().split()]
B = [0] * 100001
for a in A:
    B[a] += 1
C = convolve(B, B)
ans = 0
for i in range(200001)[::-1]:
    a = min(M, C[i])
    M -= a
    ans += a * i
print(ans)

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)
#print(a)
score = 0
now = [-a[0]-a[0],0,0]
time = 1
wait = []
done = []
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 r not in done:
                if r not in wait:
                    heapq.heappush(wait,r)
    else:
        if now[2]+1 < n:
            r = [now[1],now[2]+1]
            r = [-a[r[0]]-a[r[1]]]+r
            if r not in done:
                if r not in wait:
                    heapq.heappush(wait,r)
        q = [now[1]+1,now[2]]
        q = [-a[q[0]]-a[q[1]]]+q
        if q not in done:
            if q not in wait:
                heapq.heappush(wait,q)
        if time != m:
            score -= now[0]
            time += 1
            
    done.append(now)
    #print(score,now,wait)
    if wait:
        now = heapq.heappop(wait)
    else:
        break
    time += 1
print(score)
#print(done)

Submission status: Time Limit Exceeded

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

A.sort()

dp = [[0 for _ in range(N)] for _ in range(N)]

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

flat = []
for p in dp:
    flat.extend(p)
flat.sort()
print(sum(flat[-M:]))

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)
#print(a)
score = 0
now = [-a[0]-a[0],0,0]
time = 1
wait = []
done = []
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 r not in done:
                if r not in wait:
                    heapq.heappush(wait,r)
    else:
        if now[2]+1 < n:
            r = [now[1],now[2]+1]
            r = [-a[r[0]]-a[r[1]]]+r
            if r not in done:
                if r not in wait:
                    heapq.heappush(wait,r)
        q = [now[1]+1,now[2]]
        q = [-a[q[0]]-a[q[1]]]+q
        if q not in done:
            if q not in wait:
                heapq.heappush(wait,q)
        if time != m:
            score -= now[0]
            time += 1
            
    done.append(now)
    #print(score,now,wait)
    if wait:
        now = heapq.heappop(wait)
    else:
        break
    time += 1
print(score)
#print(done)

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):
    b.append(a[i] + a[i])
    for j in range(i+1, n):
        b.append(a[i] + a[j])
        b.append(a[i] + a[j])
b.sort(reverse=True)
#print(b)
print(sum(b[:m]))

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop

N, M = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)
ans = 0
heap = []
heappush(heap, (-A[0]*2, 0, 0))
checked = set()
checked.add((0, 0))
for i in range(M):
    power, x, y = heappop(heap)
    ans -= power
    if x+1 < N and (x+1, y) not in checked:
        heappush(heap, (-(A[x+1]+A[y]), x+1, y))
        checked.add((x+1, y))
    if y+1 < N and (x, y+1) not in checked:
        heappush(heap, (-(A[x]+A[y+1]), x, y+1))
        checked.add((x, y+1))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def count_num(X):
	m = 0
	for i in range(N):
		B = np.ones((N)) * (X - A[i])
		# print(A)
		# print(B)
		m += np.count_nonzero(A >= B)
		# print(m)
	return m

if __name__ == "__main__":
	N, M = map(int, input().split())
	A = np.array(list(map(int, input().split())))
	# print(count_num(67))
	left = 0
	right = 10 ** 6
	while left + 1 < right:
		x = (left + right) // 2
		if count_num(x) >= M:
			left = x
		else:
			right = x
	
	# print(left)
	ans = 0
	count = 0
	for i in range(N):
		B = np.ones((N)) * (left - A[i])
		ans += np.sum(np.where(A > B, A + A[i], 0))
		count += np.count_nonzero(A > B)
	ans += left * (M - count)
	print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq

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

a = []
for i in range(N):
    for j in range(i, N):
        if i == j:
            a.append(-1 * (A[i] + A[j]))
        else:
            for k in range(2):
                a.append(-1 * (A[i] + A[j]))

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

print(ans)

Submission status: Time Limit Exceeded

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

i = 0
j = 0
k = 0
temp = []
sum = 0

while i < n:
  while j < n:
    temp.append(a[i]+a[j])
    j = j + 1
  i = i + 1
  j = 0

temp2 = sorted(temp)

while k < m:
  sum = sum + temp2[len(temp2)-1-k]
  k = k + 1
  
print(sum)

Submission status: Time Limit Exceeded

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

AA = []
for l, r in product(enumerate(A), enumerate(A)):
    if l[0] != r[0]:
        AA.append(l[1]+r[1])
    else:
        AA.append(l[1]*2)
AA = sorted(AA, reverse=True)        
print(sum(AA[:M]))

Submission status: Time Limit Exceeded

Solution code:
tmp = input().split()

N = int(tmp[0])
M = int(tmp[1])
DA = M
A = list(map(int, input().split()))

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

dada = []

for i in range(N):
    if i == M+1:
        break
    for j in range(N):

        dada.append(A[i] + A[j])
        # print(dada)
        if j == M-2:
            M -= 1
            break
    


dada.sort(reverse = True)
# print(dada)

ans = 0
for i in range(DA):
    ans += dada[i]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# abc149/abc149_e
import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [i2s() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N, M = i2nn()
    A = i2nn()
    A.sort(reverse=True)
    pos = [0] * N
    range_set = set(range(N))
    score = 0
    for _ in range(M):
        iter_set = iter(range_set)
        max_j = next(iter_set)
        for j in iter_set:
            if (A[j] + A[pos[j]]) > (A[max_j] + A[pos[max_j]]):
                max_j = j
        score += A[max_j] + A[pos[max_j]]
        pos[max_j] += 1
        if pos[max_j] >= N:
            range_set.discard(max_j)
    print(score)
    return

main()

Submission status: Time Limit Exceeded

Solution code:
import heapq
N, M = map(int, input().split())
A = sorted([int(i) for i in input().split()], reverse=True)

done = [[False] * N for i in range(N)]

hq = [(-A[0]*2, 0, 0)]
done[0][0] = True
heapq.heapify(hq)  # リストhqのheap化

ans = 0
c = 0
while c < M:
    v, i, j = heapq.heappop(hq)  # heap化されたリストhqから最小値を削除＆その最小値を出力
    ans -= v
    c += 1

    if i+1 < N and done[i+1][j] is False:
        heapq.heappush(hq, (-A[i+1]-A[j], i+1, j))  # heap化されたリストhqに要素xを追加
        done[i+1][j] = True

    if j+1 < N and done[i][j+1] is False:
        heapq.heappush(hq, (-A[i]-A[j+1], i, j+1))  # heap化されたリストhqに要素xを追加
        done[i][j+1] = True

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#-------------------------------------------------------------------
import sys
def p(*_a):
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
#-------------------------------------------------------------------
N, M = map(int, input().split())			# "5 7" -> ["5", "7"] -> 5, 7 => N=5,K=7
A = sorted(list( map(int, input().split()) ), reverse=True)	# 1 2 3 4 5 ...(降順(逆順)ソート付き)

# 順列 permutations
from itertools import permutations

# 三枚のうち、2枚を並べる
L = list(permutations(A, 2))
p( A )
p( L )
p( len(A) )
#=> [(1, 2), (1, 3), (2, 3)]
#=> 3


B=[]
for a in A:
	B.append(a+a)
	
for l in L:
	a,b=l
	B.append(a+b)

p("B",B)

B.sort(reverse=True)
p("B",B)

C=B[:M]
p("C",C)

ans=sum(C)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, M = tuple(int(i) for i in input().split())
    A = tuple(int(i) for i in input().split())

    sums = [0 for i in range(N * N)]
    for i in range(N):
        for j in range(N):
            sums[i * N + j] = A[i] + A[j]

    sortedSum = sorted(sums, reverse=bool(1))

    total = sum(sortedSum[:M])

    print(total)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import itertools
n, m = map(int, input().split())
a = list(map(int, input().split()))
c = list(itertools.product(a,a))
c1 = []
c2 = []
c1 = [x[0] for x in c]
c2 = [x[1] for x in c]
d = [x + y for (x, y) in zip(c1, c2)]
d.sort(reverse=True)
print(sum(d[:m]))

Submission status: Time Limit Exceeded

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

T=[]
for i in A:
    for j in A:
        T.append([i,j])

T.sort(key=lambda x: x[0]+x[1],reverse=True)
T=T[:M]
s=sum(list(map(sum,T)))
print(s)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n, m = map(int, input().split())
a = list( map(int, input().split()))
handshakelist = np.array([0])

a = np.array(a)

for i in range(n):
    a_i = a[:(i+1)] + a[i]
    handshakelist = np.hstack((handshakelist, a_i))
    a_i[-1] = 0
    handshakelist = np.hstack((handshakelist, a_i))
handshakelist = np.sort(handshakelist)[::-1]

ans = np.sum(handshakelist[:m])

print(ans)

Submission status: Time Limit Exceeded

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

pattern = []
for f1 in A:
    for f2 in A:
        pattern.append(f1 + f2)
        
pattern2 = sorted(pattern, reverse=True)

sum = 0
for i in range(0,M):
    sum = sum + pattern2[i]
print(sum)

Submission status: Time Limit Exceeded

Solution code:
str1 = input().split(" ")
str2 = input().split(" ")

n = int(str1[0])
m = int(str1[1])
power = [int(n) for n in str2]

power2 = power

res = []
for i in range(0,n):
    for j in range(0,n):
        res.append(power[i] + power2[j])

res.sort(reverse=True)

result = 0
for i in range(0,m):
    result += res[i]

print(result)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product

n, m = map(int, input().split(' '))

a = [int(x) for x in input().split(' ')]
ch = 0
pairs = sorted(product(a, repeat=2), key=lambda x: sum(x), reverse=True)

for i in range(m):
    ch += sum(pairs[i])

print(ch)

Submission status: Time Limit Exceeded

Solution code:
import math


def main():
    n, m = [int(x) for x in input().split()]
    powers = [int(x) for x in input().split()]

    powers.sort(reverse=True)

    scores = []
    min_score = 0
    for i in range(n):
        for j in range(n):
            p = powers[i] + powers[j]
            if min_score > p:
                break
            scores.append(p)
        if len(scores) > m:
            scores.sort(reverse=True)
            min_score = scores[-1]
    scores.sort(reverse=True)
    print(sum(scores[0:m]))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

happy = []
for i in range(n):
  happy.append(aa[i]*2)  
  for j in range(i,n):
    if i!=j:
      happy.append(aa[i]+aa[j])
      happy.append(aa[i]+aa[j])  
      
print(sum(sorted(happy,reverse=True)[:m]))

Submission status: Time Limit Exceeded

Solution code:
import itertools

N,M=map(int,input().split())
A=list(map(int,input().split()))
Ax=sorted(list(itertools.permutations(A, 2)),reverse=True)
# N要素を持つ数列 a[0],a[1],⋯,a[N−1] から任意の個数の項を選んで和を取った時の最大値
# 最大和問題
def max_sum(N,a):
    dp=[0]*(N+1)
    cnt=0
    for i in range(N):
        dp[i+1]=max(dp[i]+a[i],dp[i])
    return dp[N]
rank=[]
for i in range(len(Ax)):
    a=sum(Ax[i])
    rank.append(a)
for i in range(len(A)):
    A[i]*=2
    rank.append(A[i])

rank=sorted(rank,reverse=True)

ans=0
for j in range(M):
    ans+=rank[j]
print(ans)

Submission status: Time Limit Exceeded

Solution code:

import heapq

n, m = [int(x) for x in input().split()]
# powers = [(i, int(x)) for i, x in enumerate(input().split())]
# sorted_powers = sorted(powers, key=lambda x: x[1])
powers = [int(x) for x in input().split()]
# sorted_powers = sorted(powers)

conbinations = []
for i in range(n):
  for j in range(n):
    heapq.heappush(conbinations, -(powers[i] + powers[j]))

res = 0
for _ in range(m):
  res -=heapq.heappop(conbinations)

print(res)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations_with_replacement, product

n, m = map(int, input().split(' '))

a = [int(x) for x in input().split(' ')]
a.sort(reverse=True)
ch = 0
pairs = sorted(product(a, repeat=2), key=lambda x: sum(x), reverse=True)

for i in range(m):
    ch += sum(pairs[i])

print(ch)