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 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
    
    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 + np.cumsum(A[index:])[-1]
    ans -= left * (add_cnt - M)
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import math
n,m = map(int, input().split())
a = [int(x) for x in input().split()]
a.sort(reverse=True)
ans=[]
for i in range(n):
  for j in range(n):
    ans.append(a[i]+a[j])
ans.sort(reverse=True)
print(sum(ans[:m]))

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right, bisect_left

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
    
    ans = 0
    add_cnt = 0
    for ai in A:
        index = bisect_left(A, left - ai)
        add_cnt += N - index
        for aj in A[index:]:
            ans += ai + aj
    ans -= left * (add_cnt - M)
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right, bisect_left

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
    
    ans = 0
    add_cnt = 0
    for ai in A:
        index = bisect_left(A, left - ai)
        add_cnt += N - index
        for aj in A[index:]:
            ans += ai + aj
    ans -= left * (add_cnt - M)
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
#降順ソートの方がうまくいきそう
n,m=map(int,input().split())
a=np.sort(np.array(list(map(int,input().split()))))[::-1]
cs=np.cumsum(a)

#和が引数以上の場合をカウントする
def overX(x):
	count=0
	#両手が違う人を握るときのみ考える
	if a[0]*2<x:
		return 0
	else:
		for i in range(n):
			if a[i]+a[0]<x:
				count+=0
			else:
				lb, ub = 0, n
				#パターンAのにぶたん。左がOなので[lb,ub)で持つ。
				while ub-lb>1:
					mid=(lb+ub)//2
					if a[i]+a[mid]>=x:
						lb=mid
					else:
						ub=mid
				count+=lb+1
		return count
#print(overX(130))

#overX>=mなる最大のxを探す->xは小さい方が実現しやすいのでパターンA->[lb,ub)でもつ
lb=1 #実現しやすい方
ub=2*10**5
while ub-lb>1:
	mid=(ub+lb)//2
	if overX(mid)>=m:
		lb=mid
	else:
		ub=mid
#ub=overX(x)>=mなる最小のx。これ以上大きくするとmに満たなくなる。
maxx=lb

hp=0
#maxx+1以上の要素をすべてたす
#和がmaxx+1以上になる組み合わせの数だけhpを加え、countをインクリメントする
if a[0]*2>=maxx+1:
	for i in range(n):
		if a[i]+a[0]<maxx+1:
			break
		else:
			lb, ub = 0, n
			#パターンAのにぶたん。左がOなので[lb,ub)で持つ。
			while ub-lb>1:
				mid=(lb+ub)//2
				if a[i]+a[mid]>=maxx+1:
					lb=mid
				else:
					ub=mid
			#a[0]からa[lb]は、a[i]と足した時にx以上になり条件を満たす。
			hp+=a[i]*(lb+1)+cs[lb]
'''print(hp)
print(overX(maxx))
print(overX(maxx+1))
print(maxx)'''
hp+=(m-overX(maxx+1))*maxx
print(hp)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from bisect import bisect_right as br
N,M = list(map(int,input().split()))
A = list(map(int,input().split()))
A = np.sort(A)[-M:]

ans = []
for a in A:
  ans.extend([a]+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 = np.sort(A)[::-1][:M]
 
m = int(min(M,N))
ans = np.zeros(1)
for n,a in enumerate(A):
  if n>m:break
  #num = [a] + A
  #num = np.sort(num)[::-1]
  ans = np.r_[ans,[a] + A]
  ans = np.sort(ans)[::-1][:M]

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 = np.sort(A)[::-1][:M]
 
m = int(min(M,N))
num = np.zeros(m)
ans = np.zeros(1)
for n,a in enumerate(A):
  if n>m:break
  num = [a] + A
  #num = np.sort(num)[::-1]
  ans = np.r_[ans,num]
  ans = np.sort(ans)[::-1][:M]

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 = np.sort(A)[-M:]

m = int(min(M,N))
def main(A):
  ans = np.zeros(1, np.int64)
  ans = np.append(ans,[[a] + A for n,a in enumerate(A) if n<=m])
  #ans = np.append(ans,[[a] + A for a in A])
  ans = np.sort(ans)[-M:]
  print(int(sum(ans)))

main(A)

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 = np.sort(A)[-M:]

#m = int(min(M,N))
ans = np.zeros(1, np.int64)
#ans = np.append(ans,[[a] + A for n,a in enumerate(A) if n<=m])
ans = np.append(ans,[[a] + A for a in A])
ans = np.sort(ans)[-M:]
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 = np.sort(A)[::-1][:M]

#m = int(min(M,N))
ans = np.zeros(1, np.int64)
#ans = np.append(ans,[[a] + A for n,a in enumerate(A) if n<=m])
ans = np.append(ans,[[a] + A for a in A])
ans = np.sort(ans)[::-1][:M]
print(int(sum(ans[:M])))

Submission status: Time Limit Exceeded

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


def guchoku(n, m, a):
    tmp = []
    for i in range(n):
        for j in range(n):
            tmp.append(a[i]+a[j])
    tmp.sort(reverse=True)
    return sum(tmp[:m])


def C(mid):
    tmp = []
    for i in a:
        pos = bisect.bisect_right(a, mid-i)
        #tmp += n-pos
        tmp.append(n-pos)
    #print(mid, tmp)
    return sum(tmp) >= m, tmp


ub = a[-1]*2
lb = 0
while ub - lb > 1:
    mid = (ub + lb) // 2  # 仮の答え、これを満たす物の個数を数えたい
    c, order = C(mid)
    if c:
        lb = mid
    else:
        ub = mid

ans = 0
cnt = 0
for x in a[::-1]:
    for y in a[::-1]:
        if x + y <= ub:
            break
        ans += x + y
        cnt += 1
# print(order)

ans += (m-cnt)*ub
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)
lis = []
heapq.heappush(lis, (-A[0] * 2, (0, 0)))

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

for _ in range(M):
    nex = heapq.heappop(lis)
#     print(nex)
    ans += nex[0]
    if nex[1][0] < N - 1 and not flag[nex[1][0] + 1][nex[1][1]]:
        heapq.heappush(lis, (-A[nex[1][0] + 1] - A[nex[1][1]], (nex[1][0] + 1, nex[1][1])))
        flag[nex[1][0] + 1][nex[1][1]] = True
    if nex[1][1] < N - 1 and not flag[nex[1][0]][nex[1][1] + 1]:
        heapq.heappush(lis, (-A[nex[1][0]] - A[nex[1][1] + 1], (nex[1][0], nex[1][1] + 1)))
        flag[nex[1][0]][nex[1][1] + 1] = True
print(-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 = np.sort(A)[::-1][:M]

m = int(min(M,N))
ans = np.zeros(1, np.int64)
ans = np.append(np.sort(ans)[::-1][:M],[[a] + A for n,a in enumerate(A) if n<=m])
ans = np.sort(ans)[::-1][:M]
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 = np.sort(A)[::-1]

m = int(min(M,N))
ans = np.zeros(1, np.int64)
ans = np.append(np.sort(ans)[::-1][:M],[[a] + A for n,a in enumerate(A) if n<=m])
ans = np.sort(ans)[::-1][:M]
print(int(sum(ans[:M])))

Submission status: Time Limit Exceeded

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def fft(A, B, L):
    import numpy as np
    from numpy.fft import rfft, irfft

    # FFT
    res = irfft(rfft(A, L) * rfft(B, L), L)
    # 四捨五入して整数に
    res = np.rint(res).astype(np.int64)
    return res

MAX = 10 ** 5
N, M = MAP()
A1 = [0] * (MAX+1)
A2 = [0] * (MAX+1)
for a in LIST():
    A1[a] += 1
    A2[a] += 1

L = 2 ** 18
res = fft(A1, A2, L)

ans = cnt = 0
for a in range(L-1, -1, -1):
    c = res[a]
    if cnt + c <= M:
        cnt += c
        ans += a * c
    else:
        while cnt < M:
            cnt += 1
            ans += a
        break
print(ans)

Submission status: Time Limit Exceeded

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

import sys
from bisect import bisect_left
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def bisearch_max(mn, mx, func):
    """ 条件を満たす最大値を見つける二分探索 """

    ok = mn
    ng = mx
    while ok+1 < ng:
        mid = (ok+ng) // 2
        if func(mid):
            # 上を探しに行く
            ok = mid
        else:
            # 下を探しに行く
            ng = mid
    return ok

# 右手と左手(a,b)の和がx以上となる組の数
def calc(x):
    # 各aについて、条件を満たす数を数える
    ans = 0
    for a in A:
        # 式変形： a + b >= x → b >= x - a
        ans += N - bisect_left(A, x - a)
    return ans >= M

N, M = MAP()
A = LIST()

A.sort()
res = bisearch_max(0, INF, calc)

ans = m = 0
acc = [0] + list(accumulate(A))
for a in A:
    idx = bisect_left(A, res - a)
    cnt = N - idx
    # 幸福度
    ans += a * cnt + (acc[N] - acc[idx])
    # 握手の回数
    m += cnt

# 同値でMを超えた分の調整
ans -= res * (m - M)
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()

def hand(x):
  cnt=0
  for i in range(n):
    p=x-A[i]
    cnt+=n-bisect.bisect_left(A,p)
  return cnt


l=0
h=10**15+3
mid=(l+h)//2

while l+1<h:
  mid=(l+h)//2
  if hand(mid)<m:
    h=mid
  else:
    l=mid

B=A[::-1]

for i in range(n-1):
  B[i+1]+=B[i]

B=B[::-1]

ans=0
cnt=0


for i in range(n):
  y=l-A[i]+1
  index=bisect.bisect_left(A,y)
  if n==index:
    continue
  else:
    ans+=(n-index)*A[i]+B[index]
    cnt+=(n-index)

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

Submission status: Time Limit Exceeded

Solution code:
n,m,*a=map(int,open(0).read().split())
print(sum(sorted([i+j for i in a for j in a],reverse=True)[:m]))

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
import itertools
n,m = map(int,input().split())
a = list(map(int,input().split()))

lst = []
for u,v in itertools.product(a, repeat=2):
    heappush(lst, -u-v)
ans = 0
for _ in range(m):
    cost = heappop(lst)
    ans -= cost
print(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 = np.sort(A)[::-1]
 
m = int(min(M,N))
ans = np.zeros(1)
ans = np.append(ans,[[a] + A for n,a in enumerate(A) if n<=m])
ans = np.sort(ans)[::-1][:M]
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 = np.sort(A)[::-1]
 
m = int(min(M,N))

def est(A):
  ans = np.zeros(1)
  for n,a in enumerate(A):
    if n>m:return np.sort(ans)[::-1][:M]
    ans = np.r_[ans, [a] + A]
  return np.sort(ans)[::-1][:M]

ans  = est(A)
print(int(sum(ans[:M])))

Submission status: Time Limit Exceeded

Solution code:
from itertools import product

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
lis = []
b = product(a,a)
for i, j in b:
    lis.append(i+j)

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

Submission status: Time Limit Exceeded

Solution code:
from queue import PriorityQueue

def count(n, arr, s):
    cnt = 0
    for idx in range(n):
        if arr[idx] * 2 >= s:
            l = idx
            r = n - 1
            while l < r:
                mid = (l + r) // 2 + 1
                if arr[idx] + arr[mid] >= s:
                    l = mid
                else:
                    r = mid - 1
            cnt += 1 + 2 * (l - idx)
    return cnt

def calculate(n, m, arr, sum_arr, s):
    cnt = 0
    val = 0
    for idx in range(n):
        if arr[idx] * 2 >= s:
            l = idx
            r = n - 1
            while l < r:
                mid = (l + r) // 2 + 1
                if arr[idx] + arr[mid] >= s:
                    l = mid
                else:
                    r = mid - 1
            val += arr[idx] * 2 + 2 * (sum_arr[l+1] - sum_arr[idx+1] + arr[idx] * (l - idx))
            cnt += 1 + 2 * (l - idx)
    val -= s * (cnt - m)
    return val

def main():
    n, m = map(int, input().split())
    arr = list(map(int, input().split()))
    arr = sorted(arr, reverse=True)
    
    sum_arr = [0 for _ in range(n + 1)]
    for idx in range(n):
        sum_arr[idx+1] = sum_arr[idx] + arr[idx]

    l = 1
    r = 200000
    while l < r:
        mid = (l + r) // 2 + 1
        cnt = count(n, arr, mid)
        if cnt >= m:
            l = mid
        else:
            r = mid - 1

    print(calculate(n, m, arr, sum_arr, l))
        

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n,m,*a = map(int,open(0).read().split())
a2 = [i+j for i in a for j in a]
a2.sort()
print(sum(a2[-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(A)):
		C.append(A[i]+A[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())
l = list(map(int,input().split()))
l.sort()
right = l[-1]*2+1
left = 0

while right - left >1:
    mid = (right+left)//2
    
    x = 0
    for i in range(n):
        a = l[i]
        index = bisect.bisect_left(l,mid-a)
        x += n-index
   
    if x >= m:
        left = mid
    else:
        right = mid
ans = []
for i in range(n):
    a = l[i]
    for j in range(n):
        if a + l[j] >= left:
            ans.append(a+l[j])
ans.sort(reverse=True)

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

Submission status: Time Limit Exceeded

Solution code:
import bisect
n,m = map(int,input().split())
l = list(map(int,input().split()))
l.sort()
right = l[-1]*2+1
left = 0
ans = 0
while right - left >1:
    mid = (right+left)//2
    
    x = 0
    for i in range(n):
        a = l[i]
        index = bisect.bisect_left(l,mid-a)
        x += n-index
   
    if x >= m:
        left = mid
    elif m >= x:
        right = mid
ans = []
for i in range(n):
    a = l[i]
    for j in range(n):
        if a + l[j] >= left:
            ans.append(a+l[j])
ans.sort(reverse=True)

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

Submission status: Time Limit Exceeded

Solution code:
import bisect
n,m = map(int,input().split())
l = list(map(int,input().split()))
l.sort()
right = 10**6
left = 0
ans = 0
while right - left >1:
    mid = (right+left)//2
    
    x = 0
    for i in range(n):
        a = l[i]
        index = bisect.bisect_left(l,mid-a)
        x += n-index
   
    if x > m:
        left = mid
    elif m >= x:
        right = mid
ans = []
for i in range(n):
    a = l[i]
    for j in range(n):
        if a + l[j] >= left:
            ans.append(a+l[j])
ans.sort(reverse=True)

print(sum(ans[0: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 = np.sort(A)[::-1]
 
m = int(min(M,N))
ans = np.zeros(1)
for n,a in enumerate(A):
  if n>m:break
  num = [a] + A
  ans = np.r_[ans,num]
  ans = np.sort(ans)[::-1][:M]

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

Submission status: Time Limit Exceeded

Solution code:
n,m = [int(e) for e in input().split(" ")]
a_ls = [int(e) for e in input().split(" ")]

point_ls = [sum([e,ee]) for e in a_ls for ee in a_ls]
point_ls.sort(key = lambda e:-e)
print(sum(point_ls[:m]))

Submission status: Time Limit Exceeded

Solution code:
n,m = [int(e) for e in input().split(" ")]
a_ls = [int(e) for e in input().split(" ")]

a_ls.sort(key = lambda e:-e)
hand_ls = []
for e in a_ls:
	for ee in a_ls:
		hand_ls.append([e,ee])
point_ls = [sum(e) for e in hand_ls]
point_ls.sort(key = lambda e:-e)
print(sum(point_ls[:m]))

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations, product

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

score_list = [x + y for x, y in product(aaa, repeat=2)]
score_list.sort(reverse=True)
print(sum(score_list[: m]))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

def cnt(x):
    c = 0
    for j in reversed(range(len(A))):
        i = 0
        while i <n and A[j]+A[i]>=x:
            c += 1
            i += 1
    return c

def happiness(x):
    c = 0
    for j in reversed(range(len(A))):
        i = 0
        while i <n and A[j]+A[i]>=x:
            c += A[j]+A[i]
            i += 1
    return c

def binary_search(l, r):
    mid = (l+r)//2
    c = cnt(mid)
    if c < m:
        return binary_search(l, mid)   
    else:
        if l == mid:
            return(l, c-m)
        return binary_search(mid, r)

x, dm = binary_search(0, A[0]*2+1)
print(happiness(x)-dm*x)

Submission status: Time Limit Exceeded

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

def binary_search(y):
   left_index=-1
   right_index=len(A)

   while(left_index<right_index-1):
      i=(left_index+right_index)//2
      if A[i] >= y:
         left_index=i
      else:
         right_index=i
   return right_index

X=[c for c in range(2*max(A)+1)]
left_index_2=0
right_index_2=len(X)

while left_index_2<right_index_2-1:
   count=0
   j=(left_index_2+right_index_2)//2
   #print("X[j]:",X[j])

   for a in A:
      y=X[j]-a
      #Aの中でy以上の数を数える
      count+=binary_search(y)
   if count > M:
      left_index_2=j
   elif count <= M:
      right_index_2=j

#print(X[left_index_2])
happiness=0
count_2=0
for a in A:
   y=X[left_index_2]-a
   z=binary_search(y)
   #print(z)
   happiness+=sum(A[0:z])+a*z
   count_2+=z

if count_2>M:
   happiness-=X[left_index_2]*(count_2-M)
print(happiness)

Submission status: Time Limit Exceeded

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

def cnt(x):
    c = 0
    for j in range(len(A)):
        i = 0
        while i <n and A[j]+A[i]>=x:
            c += 1
            i += 1
    return c

def happiness(x):
    c = 0
    for j in range(len(A)):
        i = 0
        while i <n and A[j]+A[i]>=x:
            c += A[j]+A[i]
            i += 1
    return c

def binary_search(l, r):
    mid = (l+r)//2
    c = cnt(mid)
    if c < m:
        return binary_search(l, mid)   
    else:
        if l == mid:
            return(l, c-m)
        return binary_search(mid, r)

x, dm = binary_search(0, A[0]*2+1)
print(happiness(x)-dm*x)

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 = np.sort(A)[::-1]
 
m = int(min(M,N))
num = np.zeros(m)
ans = np.zeros(1)
for n,a in enumerate(A):
  if n>m:break
  for nn,aa in enumerate(A):
    if nn>m:break
    try:
      num[nn] = a + aa
    except:
      pass
  num = np.sort(num)[::-1]
  ans = np.r_[ans,num]
  ans = np.sort(ans)[::-1][:M]

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
n, m = [int(i) for i in sys.stdin.readline().split()]
a_ls = [int(i) for i in sys.stdin.readline().split()]
a_ls.sort(reverse=True)
cur_ls = [0 for i in range(n)]
_max = max(a_ls)
que = [(- a - _max, i) for i, a in enumerate(a_ls)]
heapq.heapify(que)
cnt = 0
res = 0
while cnt < m:
    cur, i = heapq.heappop(que)
    res += - cur
    cnt += 1
    cur_ls[i] += 1
    if cur_ls[i] < n:
        heapq.heappush(que, (- a_ls[i] - a_ls[cur_ls[i]], i))
print(res)

Submission status: Time Limit Exceeded

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

tate=A
tate.reverse()
yoko=A

def binary_search(y):
   left_index=-1
   right_index=len(yoko)

   while(left_index<right_index-1):
      i=(left_index+right_index)//2
      if yoko[i] >= y:
         left_index=i
      else:
         right_index=i
   return right_index

X=[c for c in range(2*max(A)+1)]
left_index_2=0
right_index_2=len(X)

while left_index_2<right_index_2-1:
   count=0
   j=(left_index_2+right_index_2)//2
   #print("X[j]:",X[j])

   for a in tate:
      y=X[j]-a
      #Aの中でy以上の数を数える
      count+=binary_search(y)
   if count > M:
      left_index_2=j
   elif count <= M:
      right_index_2=j

#print(X[left_index_2])
happiness=0
count_2=0
for a in tate:
   y=X[left_index_2]-a
   z=binary_search(y)
   #print(z)
   happiness+=sum(tate[0:z])+a*z
   count_2+=z

while count_2>M:
   happiness-=X[left_index_2]
   count_2-=1
print(happiness)

Submission status: Time Limit Exceeded

Solution code:
import math

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

output = [(A[-1 - i] + A[-1 - j]) for i in range(min(M, N)) for j in range(min(M, N))]
output.sort()
ans = sum(output[len(output) - M:])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def E():
    temp = [int(n) for n in input().split()]
    N = temp[0]
    M = temp[1]
    A = [int(n) for n in input().split()]
    A.sort(reverse=True)
    all_combinations = []
    for i in range(N):
        for j in range(N):
            all_combinations.append(A[i]+A[j])
    all_combinations.sort(reverse=True)
    print(sum(all_combinations[:M]))

E()

Submission status: Time Limit Exceeded

Solution code:
import sys

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

if __name__=="__main__":
    n,m =  map(int,input().split())
    l = [int(i) for i in input().split()]
    l.sort()
    l = l[::-1]
    happiness = l[0] * 2
    idx = 0
    idx_ = 1
    m_ = 1
    happiness_l = []
    for k in l:
        for v in l:
            happiness_l.append(k+v)
    happiness_l.sort()
    print(sum(happiness_l[-1*m:]))

Submission status: Time Limit Exceeded

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

for i in range(n):
    for j in range(i,n):
        l.append(a[i]+a[j])
        if i != j:
            l.append(a[i]+a[j])
l.sort(reverse=True)

print(sum(l[:m]))

Submission status: Time Limit Exceeded

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

#和がx以上になる組み合わせの総数
def pattern_num_ge_x(x):
    p=0
    for a in A:
        ng=-1
        ok=N
        while (ok-ng)>1:
            m=(ok+ng)//2
            if a+A[m]>=x:
                ok=m
            else:
                ng=m
        p+=N-ok
    return(p)

#pattern_num_ge_x(x)がM未満になる最小のxを探す(=r)
#lはM以上になる最大のx
l=-1
r=10**10+1
while r-l>1:
    m=(r+l)//2
    if pattern_num_ge_x(m)<M:
        r=m
    else:
        l=m
#print(l,r)
#for i in range(300):
#    print(i,pattern_num_ge_x(i),sep=',')

#和がr以上になる組み合わせの総和を求める(累積和を使用)
S=list(reversed(A))
for i in range(1,N):
    S[i]+=S[i-1]
#print(S)
ans=0
for a in A:
    ng=-1
    ok=N
    while (ok-ng)>1:
        m=(ok+ng)//2
        if a+A[m]>=r:
            ok=m
        else:
            ng=m
    ans+=a*(N-ok) + (S[N-ok-1] if N-ok-1>=0 else 0)
    M-=(N-ok)
    #print(a,ok,a*(N-ok),ans)

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import cmath
pi = cmath.pi
exp = cmath.exp

import sys
readline = sys.stdin.readline
write = sys.stdout.write

def make_exp_t(N, base):
    exp_t = {0: 1}
    temp = N
    while temp:
        exp_t[temp] = exp(base / temp)
        temp >>= 1
    return exp_t

def fft_dfs(f, s, N, st, exp_t):
    if N==2:
        a = f[s]; b = f[s+st]
        return [a+b, a-b]
    N2 = N//2; st2 = st*2
    F0 = fft_dfs(f, s   , N2, st2, exp_t)
    F1 = fft_dfs(f, s+st, N2, st2, exp_t)
    w = exp_t[N]; wk = 1.0
    for k in range(N2):
        U = F0[k]; V = wk * F1[k]
        F0[k] = U + V
        F1[k] = U - V
        wk *= w
    F0.extend(F1)
    return F0

def fft(f, N):
    if N==1:
        return f
    return fft_dfs(f, 0, N, 1, fft_exp_t)

def ifft(F, N):
    if N==1:
        return F
    f = fft_dfs(F, 0, N, 1, ifft_exp_t)
    for i in range(N):
        f[i] /= N
    return f

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

l = 10**5+1
L = 2**(2*l-1).bit_length()

power = list(map(int,input().split()))
count = [0.0 for _ in range(l)]

for p in power:
    count[p] += 1

fft_exp_t = make_exp_t(L, -2j*pi)
ifft_exp_t = make_exp_t(L, 2j*pi)

count.extend([0]*(L-l))

C = fft(count, L)

CC =[C[i]*C[i] for i in range(L)]

cc = ifft(CC,L)

shake = 0
ans = 0

for i in reversed(range(len(cc))):
    if shake+int(cc[i].real+0.5)<=M:
        ans += i*int(cc[i].real+0.5)
        shake += int(cc[i].real+0.5)
    else:
        ans += i*(M-shake)
        break
        
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)
            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 = mid
        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][check] - 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 = mid
        r = mid
    #print(l, r)

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][check] - 1]) * (m - p[0])
    tmp = count(a, l, n)
    for i in range(n):
        ans += a[i] * tmp[1][i] * 2
print(ans)